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

אסף נוסבאום (מכון ויצמן למדע)
יום ראשון, 3.8.2008, 11:00
חדר 337, בניין טאוב למדעי המחשב

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.

בחזרה לאינדקס האירועים