Explicit Constructions of Ramsey Graphs and Complexity Theory

Complexity Theory and Explicit Constructions of Ramsey Graphs Rahul Santhanam University of Edinburgh

Plan of the Talk Setting the Stage Constructions and List Constructions An Approach Through Logic Testability, Combinability and Reductions

Plan of the Talk Setting the Stage Constructions and List Constructions An Approach Through Logic Testability, Combinability and Reductions

Framework Motivating Problem: Construct graphs on N vertices without cliques or independent sets of size 2 log(N) in time poly(N) We give elements of a structural theory of explicit constructions emphasizing connections to complexity theory; use the Ramsey problem as an illustrative example

Dramatis Personae Protagonist: Ramsey graphs Secondary Characters: Hard Boolean functions (functions of high circuit complexity), pseudo- random generators Minor Characters: Good error-correcting codes, expanders, extractors, primes etc.

Brief Intro to Complexity Theory P = Boolean functions computable in deterministic time poly(n) E = Boolean functions in time 2O(n) NP = Boolean functions verifiable in time poly(n) SIZE(s) = Boolean functions computable by Boolean circuits of size s(n) SIZEA(s) = Boolean functions computed by A-oracle circuits of size s(n) P is contained in SIZE(poly), NP in SIZENP(poly)

Hard Boolean Functions Some of the fundamental lower bound questions in complexity theory are explicit construction questions E not in SIZE(s) is equivalent to a poly(N)-time construction of a truth table of a Boolean function on log(N) bits which does not have circuits of size s(log(N)) We know that hard functions exist, but we don t know explicit examples

Pseudorandomness and the Probabilistic Method We know that a random graph is Ramsey, a random Boolean function is hard etc. Theory of pseudorandomness studies pseudorandom objects, which are indistinguishable from random ones but are constructed using much less randomness We would like to argue that pseudorandom graphs are Ramsey, pseudorandom functions are hard etc.

Properties and their Complexity We model properties simply as Boolean functions Ramsey is in coNP To verify that a graph is non-Ramsey, simply guess a subset of vertices of size 2 log(N) and check that it is a clique or independent set Hard Boolean Function is in coNP To verify that a Boolean function (given by its truth table) has small circuits, simply guess the circuit and check that it is consistent with the truth table by evaluating circuit on all inputs of size log(N) Primes is in P [AKS]

Pseudorandom Generators A quick PRG against a class C of properties is a poly-time computable sequence of functions GN: {0,1}O(log(N)) {0,1}Nsuch that for any Q in C, Prx(Q(x) = 1) ~ Pry(Q(G(y)) = 1) Note that if Prx(Q(x) = 1) = 1 o(1) (as is typical for properties on which probabilistic method is successful) and if G is a quick PRG against Q, then for each N, Range(GN) is an efficiently computable poly(N)-sized list of objects at least one of which satisfies Q

Hardness = Pseudorandomness PRGs exist non-constructively for any natural class of properties (by the probabilistic method), but when do quick PRGs exist? Theorem [NW, IW, KvM] : There is a quick PRG against SIZEA(poly) iff there are explicit functions which are hard against A-oracle circuits of size 2o(n)

Plan of the Talk Setting the Stage Constructions and List Constructions An Approach Through Logic Testability, Combinability and Reductions

Weak Explicit Constructions We weaken the goal of explicit constructions of Ramsey graphs in the following ways Asking for an explicit list-construction, i.e., an explicit construction of a poly(N) sized list of graphs at least one of which is Ramsey Asking for a quasi-explicit construction, i.e., a construction that works in time 2polylog(N) We observe that an explicit list-construction exists under standard complexity assumptions, and a quasi-explicit construction unconditionally

A Conditional Explicit List Construction Observation: If there is an explicit Boolean function hard against NP-oracle circuits, there is an explicit list-construction for Ramsey property Proof: Ramsey is in coNP, hard Boolean function implies quick PRG, range of quick PRG is an explicit list This construction is generic: same list (i.e., range of a certain quick PRG G) works for any property in NP or coNP Also, note that for a property in P, we get an explicit construction rather than just a list

A Quasi-Explicit Construction Consider the proof that the Ramsey property holds for a random graph This proof requires only O(log2(N))-wise independence between choices of random edges There is an O(log2(N))-wise independent sample space of size 2O(log^3(N))of strings of length N2 at least one member of this sample space represents a Ramsey graph Since Ramsey property is testable in time NO(log(N)), we can go through all possibilities in quasi-poly time and choose one which is Ramsey

Explicit = Efficiently Constructible? The previous construction cheats in some sense we don t really get our hands on a graph which is Ramsey However, the PRG-based approach does give candidate explicit constructions for which there is a natural combinatorial interpretation

Evidence for Explicit Constructions? Is there a plausible complexity-theoretic hypothesis under which we can prove there is an explicit construction of Ramsey graphs? Hypothesis: There is poly-time computable sequence {xN} of strings, |xN| = N, such that for all super-efficient f and almost all N, |y| < N (1) implies f(y) xN When interpreted as a graph, xNwould be Ramsey (since non-Ramsey graphs can be compressed) How reasonable is hypothesis?

Plan of the Talk Setting the Stage Constructions and List Constructions An Approach Through Logic Testability, Combinability and Reductions

Narrowing the Focus Question: Is there an explicit list-construction for Ramsey? Note that to get this, we just need a PRG against the Ramsey property, not against all of coNP or SIZENP(poly) Approach: Consider smaller natural families of properties containing Ramsey and try to show PRGs against them, eg., families based on logical definability

EMSO and the Ramsey property Consider Existential Monadic Second Order logic on graphs with arithmetic (+, *) The negation of the Ramsey property is expressible in this logic There exists a set S of size at least 2 log(N) such that S is either a clique or an independent set Is there a PRG against the class of properties definable in this logic (or even for EMSO without arithmetic)?

PRGs for Logics One could hope to unconditionally construct a quick PRG for any logic for which inexpressibility results are known There has been a lot of work on 0-1 laws and limit laws. One could hope to get PRGs even for logics for which such laws do not hold

Plan of the Talk Setting the Stage Constructions and List Constructions An Approach Through Logic Testability, Combinability and Reductions

Testability Question: Is the Ramsey property in P? We care about this because if so We can make the standard probabilistic construction zero-error We can prove that explicit constructions exist under a standard complexity-theoretic hypothesis [RR] showed that if Factoring is hard, then testing whether a Boolean function has high circuit complexity can t be done in poly time

The Planted Clique Problem Consider the following distributions D: Erdos-Renyi graph with edge prob D : Erdos-Renyi graph with edge prob + random planted clique of size 3 log(n) Planted Clique Problem: Is there a polynomial- time algorithm to distinguish D and D ? Widely studied problem [K] [J] [AKS] [FK] [AAKMRX] with applications to crypto [JP]

Hardness of Ramsey Property Observation: If Planted Clique problem is hard, then Ramsey property is not in P Proof: A graph drawn from D is Ramsey with high probability, a graph drawn from D is not Question: Is Ramsey property hard under more standard crypto assumptions?

Combinability Given a poly-sized list of objects at least one of which satisfies property Q, can we produce in poly time a single object satisfying property Q? Clearly yes if Q is poly-time testable. But how about properties such as Ramsey property? [N] uses graph products to give explicit Ramsey construction with weak parameters

Combinability (contd) Combinability holds for Hard Boolean Function property just concatenate truth tables of Boolean functions in the list Is there a nice characterization of properties for which combinability holds?

Reductions Among Explicit Constructions Say that property Q reduces to property R (Q <= R) if there is a polynomial-time oracle machine which, when given oracle access to explicit constructions of R, produces an explicit construction for Q Hardness=Pseudorandomness theorem shows that PRG <= Hard Boolean Function and Hard Boolean Function <= PRG; also that any property in P reduces to Hard Boolean Function (against NP-oracle circuits) [V] surveys reductions between expanders, error- correcting codes, extractors...

Open Questions Is there an explicit list-construction for Ramsey? Are there PRGs against MSO or other logics where inexpressibility results are known? More evidence that Ramsey is not efficiently testable? Is the Ramsey property combinable?

Thank You