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

TR97-013 | 13th February 1997
Bernd Borchert, Dietrich Kuske, Frank Stephan

On Existentially First-Order Definable Languages and their Relation to NP

Pin & Weil [PW95] characterized the automata of existentially
first-order definable languages. We will use this result for the following
characterization of the complexity class NP. Assume that the
Polynomial-Time Hierarchy does not collapse. Then a regular language
L characterizes NP as an unbalanced polynomial-time leaf language
if and ... more >>>


TR97-012 | 19th March 1997
Luca Trevisan

On Local versus Global Satisfiability

We prove an extremal combinatorial result regarding
the fraction of satisfiable clauses in boolean CNF
formulae enjoying a locally checkable property, thus
solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint
satisfaction ... more >>>


TR97-011 | 7th April 1997
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

Weak Random Sources, Hitting Sets, and BPP Simulations

We show how to simulate any BPP algorithm in polynomial time
using a weak random source of min-entropy $r^{\gamma}$
for any $\gamma >0$.
This follows from a more general result about {\em sampling\/}
with weak random sources.
Our result matches an information-theoretic lower bound ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint