Isolation, matching, and counting uniform and nonuniform upper bounds
From MaRDI portal
(Redirected from Publication:1961370)
Recommendations
- scientific article; zbMATH DE number 1335883
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Space complexity of perfect matching in bounded genus bipartite graphs
- Space complexity of perfect matching in bounded genus bipartite graphs
- The Polynomially Bounded Perfect Matching Problem Is in NC 2
Cites work
- A very hard log-space counting class
- Circuits over PP and PL
- Computational Complexity of Probabilistic Turing Machines
- Constructing a perfect matching is in random NC
- Gap-definable counting classes
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Hardness vs randomness
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 1256731 (Why is no real title available?)
- scientific article; zbMATH DE number 1283991 (Why is no real title available?)
- scientific article; zbMATH DE number 1332669 (Why is no real title available?)
- scientific article; zbMATH DE number 1346519 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 3059214 (Why is no real title available?)
- Log Depth Circuits for Division and Related Problems
- Making Nondeterminism Unambiguous
- Matching is as easy as matrix inversion
- Maximum matching and a polyhedron with 0,1-vertices
- Nondeterministic Space is Closed under Complementation
- On the power of parity polynomial time
- P-Printable Sets
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Properties that characterize LOGCFL
- Pseudorandom generators without the XOR lemma
- Relationships among $PL$, $\#L$, and the determinant
- Space-bounded hierarchies and probabilistic computations
- Structure and importance of logspace-MOD class
- The method of forced enumeration for nondeterministic automata
- The PL Hierarchy Collapses
- Turing machines with few accepting computations and low sets for PP
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Verifying the determinant in parallel
Cited in
(28)- Tight bounds and conjectures for the isolation lemma
- Sparse sets and collapse of complexity classes
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- The combinatorial approach yields an NC algorithm for computing Pfaffians
- On the power of unambiguity in log-space
- Deterministically isolating a perfect matching in bipartite planar graphs
- Depth-first search in directed planar graphs, revisited
- NL-printable sets and nondeterministic Kolmogorov complexity
- Dual VP classes
- Space complexity of the directed reachability problem over surface-embedded graphs
- Reachability is in DynFO
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- The Simple Reachability Problem in Switch Graphs
- scientific article; zbMATH DE number 1335883 (Why is no real title available?)
- Space complexity of perfect matching in bounded genus bipartite graphs
- NL-printable sets and nondeterministic Kolmogorov complexity
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- 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
- Robustness for space-bounded statistical zero knowledge
- Green's theorem and isolation in planar graphs
- Unambiguous, randomized, and symmetric catalytic computation
- Planar and grid graph reachability problems
- Reachability in graphs with polynomially many surface non-separating cycles is in UL
- \textsc{ReachFewL} = \textsc{ReachUL}
This page was built for publication: Isolation, matching, and counting uniform and nonuniform upper bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961370)
