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

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>> TR16-158 | 9th October 2016 Alexander Kulikov, Vladimir Podolskii #### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates We study the following computational problem: for which values of$k$, the majority of$n$bits$\text{MAJ}_n$can be computed with a depth two formula whose each gate computes a majority function of at most$k$bits? The corresponding computational model is denoted by$\text{MAJ}_k \circ \text{MAJ}_k\$. We observe that ... more >>>

ISSN 1433-8092 | Imprint