The Taub Faculty of Computer Science Events and Talks

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. We suggest and analyze a new criterion of faithful emulation, inspired by the famous 0/1-law of random graphs. This 0/1-law 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.

We consider preserving even depth-D properties, namely, properties expressible via an entire sequence of formulas {\psi_N} where thequantifier depth of \psi_N is bounded by D=D(N). We first ask what is the maximal depth D_1 for which random graphs' 0/1-laws can be generalized fordepth D_1 properties. We then ask what is the maximal depth D_2 for whichrandom graphs can be efficiently emulated by capturing similar 0/1-laws. Both D_1 and D_2 are shown to be precisely log(N)/log(1/p), where p denotes the graphs' density. These hardness results require no computational assumptions.

Relevant background on random graphs and pseudorandomness will be provided.

Joint work with Moni Naor and Eran Tromer.