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
[toci@dimacs.rutgers.edu].
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