
PreviousNext
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 >>>
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 >>>
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 >>>
PreviousNext