Derandomizing Isolation in Space-Bounded Settings

DOI10.1137/17M1130538zbMath1430.68109OpenAlexW2944729076WikidataQ127903949 ScholiaQ127903949MaRDI QIDQ5232318

Dieter van Melkebeek, Gautam Prakriya

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/17m1130538

zbMATH Keywords

derandomizationisolation lemmagraph reachabilitycircuit certificationunambiguous nondeterminism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Is Valiant-Vazirani's isolation probability improvable?
• On enumerating monomials and other combinatorial structures by polynomial interpolation
• Space complexity of perfect matching in bounded genus bipartite graphs
• Computing the shortest essential cycle
• New results on noncommutative and commutative polynomial identity testing
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• Shortest \((A+B)\)-path packing via hafnian
• On self-reducibility and weak P-selectivity
• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• The method of forced enumeration for nondeterministic automata
• Constructing a perfect matching is in random NC
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Properties that characterize LOGCFL
• On the theory of average case complexity
• Pseudorandom generators for space-bounded computation
• Universal classes of hash functions
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Parallel algorithms for the assignment and minimum-cost flow problems
• Depth reduction for circuits of unbounded fan-in
• Deterministically isolating a perfect matching in bipartite planar graphs
• Isolation, matching, and counting uniform and nonuniform upper bounds
• A fast parallel algorithm for minimum-cost small integral flows
• A circuit-based proof of Toda's theorem
• Time-space tradeoff in derandomizing probabilistic logspace
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Relationships between nondeterministic and deterministic tape complexities
• Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
• Directed Planar Reachability Is in Unambiguous Log-Space
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• PP is as Hard as the Polynomial-Time Hierarchy
• Reachability is in DynFO
• The Time Complexity of Constraint Satisfaction
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Nondeterministic Space is Closed under Complementation
• Structural analysis of the complexity of inverse functions
• On the Tape Complexity of Deterministic Context-Free Languages
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
• Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
• Boolean complexity classes vs. their arithmetic analogs
• On the Complexity of Equivalence and Minimisation for Q-weighted Automata
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
• Making Nondeterminism Unambiguous
• Shortest Two Disjoint Paths in Polynomial Time
• Dynamic Complexity of Directed Reachability and Other Problems
• Randomness efficient identity testing of multivariate polynomials
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Bipartite perfect matching is in quasi-NC
• On the Lattice Isomorphism Problem
• Determinant Sums for Undirected Hamiltonicity
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: Derandomizing Isolation in Space-Bounded Settings