Special Computer Science/Discrete Mathematics Seminar

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.