Isolation, matching, and counting uniform and nonuniform upper bounds

zbMath0944.68068MaRDI QIDQ1961370

Shiyu Zhou, Eric W. Allender, Klaus Reinhardt

Publication date: 2 March 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

perfect matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (23)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ The combinatorial approach yields an NC algorithm for computing Pfaffians ⋮ Reachability is in DynFO ⋮ Depth-first search in directed planar graphs, revisited ⋮ Dual VP classes ⋮ On the power of unambiguity in log-space ⋮ Unnamed Item ⋮ Space complexity of perfect matching in bounded genus bipartite graphs ⋮ Deterministically isolating a perfect matching in bipartite planar graphs ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ NL-printable sets and Nondeterministic Kolmogorov Complexity ⋮ Green's theorem and isolation in planar graphs ⋮ The Simple Reachability Problem in Switch Graphs ⋮ Planar and grid graph reachability problems ⋮ \textsc{ReachFewL} = \textsc{ReachUL} ⋮ Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Compressed Decision Problems in Hyperbolic Groups. ⋮ Planar Maximum Matching: Towards a Parallel Algorithm ⋮ Typically-correct derandomization for small time and space ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Sparse sets and collapse of complexity classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• Matching is as easy as matrix inversion
• The method of forced enumeration for nondeterministic automata
• Constructing a perfect matching is in random NC
• Properties that characterize LOGCFL
• Turing machines with few accepting computations and low sets for PP
• A very hard log-space counting class
• Verifying the determinant in parallel
• Gap-definable counting classes
• Hardness vs randomness
• Circuits over PP and PL
• Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Log Depth Circuits for Division and Related Problems
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Nondeterministic Space is Closed under Complementation
• Structure and importance of logspace-MOD class
• Computational Complexity of Probabilistic Turing Machines
• The PL Hierarchy Collapses
• P-Printable Sets
• Relationships among $PL$, $\#L$, and the determinant
• Making Nondeterminism Unambiguous
• Maximum matching and a polyhedron with 0,1-vertices
• On the power of parity polynomial time
• Pseudorandom generators without the XOR lemma

This page was built for publication: Isolation, matching, and counting uniform and nonuniform upper bounds