Theory Seminar: Pseudorandom graphs - what if distinguishers where first order

Asaf Nussbaum (Weizmann Institute of Science)

Sunday, 03.08.2008, 11:00

Room 337-8 Taub Bld.

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.

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.