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.

# 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.