Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR98-037 | 29th June 1998
Johannes Köbler, Rainer Schuler

Average-Case Intractability vs. Worst-Case Intractability

We use the assumption that all sets in NP (or other levels
of the polynomial-time hierarchy) have efficient average-case
algorithms to derive collapse consequences for MA, AM, and various
subclasses of P/poly. As a further consequence we show for
C in {P(PP), PSPACE} that ... more >>>


TR98-036 | 11th June 1998
Vince Grolmusz, Gábor Tardos

Lower Bounds for (MOD p -- MOD m) Circuits

Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause ... more >>>


TR98-035 | 8th May 1998
Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

We prove an exponential lower bound for tree-like Cutting Planes
refutations of a set of clauses which has polynomial size resolution
refutations. This implies an exponential separation between tree-like
and dag-like proofs for both Cutting Planes and resolution; in both
cases only superpolynomial separations were known before.
In order to ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint