Is Valiant-Vazirani's isolation probability improvable?
From MaRDI portal
Publication:354652
DOI10.1007/s00037-013-0059-7zbMath1286.68167OpenAlexW2125063528MaRDI QIDQ354652
Osamu Watanabe, Valentine Kabanets, Holger Dell, Dieter van Melkebeek
Publication date: 19 July 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0059-7
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (5)
AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ The query complexity of witness finding ⋮ Testing the satisfiability of algebraic formulas over the field of two elements ⋮ Derandomizing Isolation in Space-Bounded Settings
Cites Work
- Is Valiant-Vazirani's isolation probability improvable?
- On quasilinear-time complexity theory
- On self-reducibility and weak P-selectivity
- NP is as easy as detecting unique solutions
- Matching is as easy as matrix inversion
- On the theory of average case complexity
- A taxonomy of complexity classes of functions
- Isolating and odd number of elements and applications in complexity theory
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- PP is as Hard as the Polynomial-Time Hierarchy
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
- Making Nondeterminism Unambiguous
- The Query Complexity of Witness Finding
- Computational Complexity
- Probability Inequalities for Sums of Bounded Random Variables
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Unnamed Item
This page was built for publication: Is Valiant-Vazirani's isolation probability improvable?
