Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size

DOI10.1007/978-3-540-85363-3_23zbMath1159.68634OpenAlexW1564399013MaRDI QIDQ3541802

V. Arvind, Partha Mukhopadhyay

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_23

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (max. 100)

Arithmetic Circuits, Monomial Algebras and Finite Automata ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Unnamed Item ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds ⋮ Recent Results on Polynomial Identity Testing ⋮ Deterministic Algorithms for Multi-criteria TSP ⋮ Deterministic algorithms for multi-criteria max-TSP ⋮ Green's theorem and isolation in planar graphs ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Dynamic programming for graphs on surfaces ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New results on noncommutative and commutative polynomial identity testing
• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• Deterministic polynomial identity testing in non-commutative models
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Isolation, matching, and counting uniform and nonuniform upper bounds
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
• Making Nondeterminism Unambiguous
• Randomness efficient identity testing of multivariate polynomials
• Algebras with Polynomial Identities and Computing the Determinant
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size