Oblivious RAMs without cryptogrpahic assumptions
Miklós Ajtai
STOC 2010
We give an exponential lower bound for the size of any linear-time Boolean branching program computing an explicitly given function. More precisely, we prove that for all positive integers k and for all sufficiently small ε > 0, if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2εn which, for all inputs X ⊆{0,1,…,n−1}, computes in time kn the parity of the number of elements of theset of all pairs 〈x, y〉 with the property x ∈ X, y ∈ X, x < y, x + y ∈ X. For the proof of this fact we show that if A = (ai,j)mi=0,j=0 is a random n by n matrix over the field with 2 elements with the condition that “A is constant on each minor diagonal,” then with high probability the rank of each δ n by δ n submatrix of A is at least cδ | log δ |−2n, where c > 0 is an absolute constant and n is sufficiently large with respect to δ. (A preliminary version of this paper has appeared in the Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.).
Miklós Ajtai
STOC 2010
Miklós Ajtai, T.S. Jayram, et al.
STOC 2002
Miklós Ajtai
STOC 2003
Miklós Ajtai
STOC 2012