Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > VALIANT-VAZIRANI LEMMA:
Reports tagged with Valiant-Vazirani Lemma:
TR08-063 | 21st April 2008
Müller Moritz

Valiant-Vazirani Lemmata for Various Logics

We show analogues of a theorem due to Valiant and Vazirani
for intractable parameterized complexity classes such as W[P], W[SAT]
and the classes of the W-hierarchy as well as those of the A-hierarchy.
We do so by proving a general ``logical'' version of it which may be of
independent interest

... more >>>

TR26-230 | 5th October 2026
Simon Apers, Roman Edenhofer, Benjamin Mathieu-Bloise, Partha Mukhopadhyay

Robust subspace designs and the power of a unique small quantum witness

The concept of subspace designs was introduced by Guruswami and Xing (STOC'13), and explicit constructions were given by Guruswami and Kopparty (FOCS'13). These are families of subspaces that have small intersection with any given subspace of a fixed dimension. We introduce \emph{robust subspace designs}. Informally, these are a quantitative extension ... more >>>


TR26-246 | 11th October 2026
Sebastian Ben Daniel

Constant-Probability Witness Isolation Implies NP in P/poly

A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, ... more >>>




ISSN 1433-8092 | Imprint