Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > THRESHOLD:
Reports tagged with threshold:
TR01-079 | 6th September 2001
Michele Zito

An Upper Bound on the Space Complexity of Random Formulae in Resolution

We prove that, with high probability, the space complexity of refuting
a random unsatisfiable boolean formula in $k$-CNF on $n$
variables and $m = \Delta n$ clauses is
$O(n \cdot \Delta^{-\frac{1}{k-2}})$.

more >>>

TR09-120 | 18th November 2009
Charanjit Jutla

Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not
be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of
such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.
Canetti et ... more >>>

TR11-152 | 12th November 2011
Emanuele Viola