Is Valiant-Vazirani's isolation probability improvable?

DOI10.1007/S00037-013-0059-7zbMATH Open1286.68167OpenAlexW2125063528MaRDI QIDQ354652FDOQ354652

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

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

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)

Cites Work

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

Cited In (6)

• Testing the satisfiability of algebraic formulas over the field of two elements
• AND-compression of NP-complete problems: streamlined proof and minor observations
• Is Valiant-Vazirani's isolation probability improvable?
• Derandomizing isolation in space-bounded settings
• Derandomizing isolation in space-bounded settings
• The query complexity of witness finding

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)