Algorithms and Complexity Seminar
Pseudorandom and k-wise independent random graphs
Asaf Nussbaum (Weizmann Institute)
We study the limits of efficient computation in the context of
constructing random-looking graph distributions that can be used to
emulate huge random graphs over N=2^n vertices. In particular we study
k-wise independent graphs where (as in the traditional random graphs
model G(N,p)) each edge appears with probability p, however, it is only
required that the distribution of any subset of k edges is independent.
It is shown that the main combinatorial qualities of random graphs can be
efficiently captured. This is done by proving that k-wise independence
(for relatively small k) suffices for preserving a long list of random
graphs properties (e.g. connectivity, Hamiltonicity, the clique and
chromatic number) and also suffices for preserving the famous 0/1-law
of random graphs, which states that any graph property T holds with
probability converging either to 0 or to 1 whenever T is expressible by
a single formula on graphs.
Generalizing this 0/1-law, we consider preserving even depth-D properties,
namely, properties expressible via an entire sequence of formulas {psi_N}
where the quantifier depth of psi_N is bounded by D=D(N). Relying on
powerful results regarding 0/1 laws, we show that D*= log(N)/ log(1/p)
is precisely the maximal depth up to which capturing the properties of
random graphs is efficiently possible, and that in fact, any efficiently
computable graphs can be strongly separated from random graphs (not only
by low depth formulas but even) by formulas of short poly(n) length.
Relevant background on random graphs and pseudorandomness will be
provided.
Joint work with Noga Alon, Moni Naor and Eran Tromer.