Complexity Day at DIMACS


Complexity Day at DIMACS


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


10:00 AM - 4:00 PM
Friday, February 17, 1995
Scheduled Speakers:

10:00 Russell Impagliazzo (U.C. San Diego)
        "Recent Directions in the Complexity of Propositional Proofs"

10:45 Klaus Ambos-Spies (University of Heidelberg) "Resource Bounded Genericity Concepts"

2:00 Kenneth Regan (SUNY/Buffalo) "Pseudorandom Generators, Measure Theory, and Natural Proofs."

2:45 Johannes Koebler (University of Ulm) "New Consequences of Self-Reducible Sets Having Small Circuits"

3:30 Break

3:45 Lance Fortnow (University of Chicago) "On Inverting Onto Functions"

The talks are free and open to the public.

If you are interested in attending, please contact Patricia Toci [].

Abstracts of the talks: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1. Russell Impagliazzo (U.C. San Diego) "Recent Directions in the Complexity of Propositional Proofs"

This talk will be an informal survey of some selected topics concerning the relationship of propostional proof systems and complexity theory. Rather than a general survey, I will discuss a few semi-related topics from recent papers by myself and others.

I use the term ``propositional proof system'' to mean any method of producing easily verifiable certificates that a propositional formula is a tautology, i.e., any non-deterministic algorithm for the Co-NP complete language of Boolean tautologies. By proving exponential lower bounds for fixed proof systems, we derive similar bounds for any algorithm for NP-complete problems that uses ``reasoning'' formalizable in the proof system. Thus, by proving lower bounds on stronger and stronger proof systems, we come closer and closer to proving that P is not equal to NP. From a positive view point, finding simple yet powerful proof systems might give us powerful heuristics for NP-complete problems.

The talk will include an informal presentation of standard proof systems, and then discuss the non-standard Nullstellensatz proof system based on algebraic reasoning introduced by Beame, myself, Krajicek, Pitassi, and Pudlak. If time permits, I will also discuss some recent interpolation theorems of Razbarov and Bonet, Pitassi, and Raz, and their consequences to the Razbarov-Rudich ``natural proofs'' paradigm for provability of circuit lower bounds.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2. Klaus Ambos-Spies (University of Heidelberg) "Resource Bounded Genericity Concepts"

We introduce new concepts of resource bounded genericity and compare them with previously introduced genericity notions of Lutz, Fenner, and Ambos-Spies, Fleischhack and Huwig. Our central new concept unifies all the previous approaches without increasing the complexity of the generic sets. This concept seems to be sufficient to cover the most important standard diagonalization arguments. As we also point out, however, this concept has some shortcomings. To overcome these limitations we introduce a hierarchy of still stronger genericicty concepts,thereby showing that there are no optimal genericity concepts for the standard complexity classes.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3. Kenneth Regan (SUNY/Buffalo) "Pseudorandom Generators, Measure Theory, and Natural Proofs."

We establish close connections between the resource-bounded measure theory of Lutz and the "Natural Proofs" of Razborov and Rudich. The main result is that if strong pseudorandom number generators or one-way functions exist, then the class of languages that have polynomial-sized circuits does not have measure zero in EXP. (Here "strong" means that for some e > 0, the PSRG/one-way function is secure against 2^{n^e}-sized circuits.)

The proof shows that for all time complexity classes C containing P that have reasonable closure properties, a C-martingale yields a nonuniform-C natural proof against the success class of the martingale. We also show conversely that a "very large" C-natural proof yields a non-uniform C martingale that succeeds on the class that the natural proof diagonalizes against. Similar results, not quite as strong, are shown for the polylog-time measures of Allender and Strauss and AC^0-natural proofs.

The talk will present refinements and technical improvements in both the measure and the natural-proof theories. It is also motivated by Lutz's hypothesis that NP does not have measure zero in EXP---obtaining our results with NP in place of P/poly would show much more far-reaching consequences from the existence of PSRGs than are currently known.

This is joint work with D. Sivakumar and J.-Y. Cai of SUNY/Buffalo

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 4. Johannes Koebler (Ulm) "New Consequences of Self-Reducible Sets Having Small Circuits"

We show that if a self-reducible set has polynomial-size circuits, then it is low for the probabilistic class ZPP(NP). As a consequence we get an apparently deeper collapse of the polynomial-time hierarchy PH to ZPP(NP) under the assumption that NP has polynomial-size circuits. This improves on the well-known result of Karp, Lipton, and Sipser (1980) stating a collapse of PH to its second level under the same assumption.

As a further consequence, we derive new collapse consequences under the assumption that complexity classes like UP, FewP, and C=P have polynomial-size circuits.

Finally, we investigate the circuit-size complexity of several language classes. In particular, we show that for every fixed polynomial s, there is a set in ZPP(NP) that does not have O(s(n))-size circuits.

This is joint work with Osamu Watanabe (Tokyo).

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 5. Lance Fortnow (Chicago) "On Inverting Onto Functions"

We will examine the proposition that given any polynomial-time computable onto function f, there is a polynomial-time function g such x = f(g(x)) for all x. We show this proposition equivalent to: - Given any NP machine that accepts everything we can find an accepting path in polynomial time. - Given any polytime computable subset of SAT there is a single polytime algorithm for finding assignments in that subset. - Given any NP machine M that accepts SAT there is a polytime function mapping accepting paths of M(phi) to assignments of phi.

We also look a possible weaker assumption where we only want a single bit of an inverse of an onto function. We show an equivalence to a host a similar single bit versions of the above and also to - For all disjoint pairs of co-NP sets are polynomial-time separable.

We show many other equivalences and discuss relationships to other conjectures in complexity theory such as - If any of the above conjectures hold and UP = NP then the polynomial-time hierarchy collapses.

We also discuss some related relativization results and open questions.

This research is joint work with Steve Fenner, Ashish Naik and John Rogers.

Document last modified on February 10, 1995