This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 93

Square root ORAM, more or less

Due: April 26
Points: 2

Why is the stash size \(O(\sqrt(n))\) for the square root ORAM? Specifically, tell me what the effects would be if the stash size were smaller, like \(O(n^{1/3})\), and what would happen if the stash size were larger, like \(O(n^{2/3})\). Use this to explain why \(O(\sqrt{n})\) is the very best choice.