Is Valiant-Vazirani's isolation probability improvable?

DOI10.1007/S00037-013-0059-7MaRDI QIDQ354652zbMATH OpenOpenAlexFDO

Authors Holger Dell, Valentine Kabanets, Dieter Van Melkebeek, Osamu Watanabe

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

zbMATH Keywords

derandomizationisolation lemmaparity satisfiabilityunique satisfiability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Isolating and odd number of elements and applications in complexity theory
• scientific article; zbMATH DE number 8776
• Derandomizing isolation in space-bounded settings
• Derandomizing isolation in space-bounded settings

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A taxonomy of complexity classes of functions
• Computational Complexity
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Is Valiant-Vazirani's isolation probability improvable?
• Isolating and odd number of elements and applications in complexity theory
• Making Nondeterminism Unambiguous
• Matching is as easy as matrix inversion
• NP is as easy as detecting unique solutions
• On quasilinear-time complexity theory
• On self-reducibility and weak P-selectivity
• On the theory of average case complexity
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• PP is as Hard as the Polynomial-Time Hierarchy
• Probability Inequalities for Sums of Bounded Random Variables
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• The query complexity of witness finding

Cited in

(5)

• Derandomizing isolation in space-bounded settings
• Derandomizing isolation in space-bounded settings
• Testing the satisfiability of algebraic formulas over the field of two elements
• The query complexity of witness finding
• Is Valiant-Vazirani's isolation probability improvable?

This page was built for publication: Is Valiant-Vazirani's isolation probability improvable?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354652)