ECCC - Reports beginning with Y

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > Y:

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

Y

TR18-109 | 29th May 2018
Kasper Green Larsen, Jesper Buus Nielsen

Yes, There is an Oblivious RAM Lower Bound!

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky
[JACM'96] is a (possibly randomized) RAM, for which the memory access
pattern reveals no information about the operations
performed. The main performance metric of an ORAM is the bandwidth
overhead, i.e., the multiplicative factor extra memory blocks that must be
accessed ... more >>>

TR26-004 | 16th January 2026
Ilya Volkovich

Yet Another Proof that $BPP \subseteq PH$

We present a new, simplified proof that the complexity class BPP is contained in the Polynomial Hierarchy (PH), using $k$-wise independent hashing as the main tool. We further extend this approach to recover several other previously known inclusions between complexity classes. Our techniques are inspired by the work of Bellare, ... more >>>

ISSN 1433-8092 | Imprint