Isolation, matching, and counting uniform and nonuniform upper bounds
type: Item
instance of: scholarly article
title: Isolation, matching, and counting uniform and nonuniform upper bounds
zbMATH Open document ID: 0944.68068
author: Eric Allender
author: Shiyu Zhou
author: Klaus Reinhardt
published in: Journal of Computer and System Sciences
publication date: 2000-03-02T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1389781
zbMATH Keywords: perfect matching problem
MaRDI profile type: Publication
cites work: Q4228466
cites work: A very hard log-space counting class
cites work: Relationships among $PL$, $\#L$, and the determinant
cites work: P-Printable Sets
cites work: Q4004078
cites work: Q4240333
cites work: Log Depth Circuits for Division and Related Problems
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: Structure and importance of logspace-MOD class
cites work: Circuits over PP and PL
cites work: Q4266543
cites work: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
cites work: On the power of parity polynomial time
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q5798359
cites work: Gap-definable counting classes
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: Nondeterministic Space is Closed under Complementation
cites work: Q4526985
cites work: Turing machines with few accepting computations and low sets for PP
cites work: Constructing a perfect matching is in random NC
cites work: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
cites work: Q4259990
cites work: Matching is as easy as matrix inversion
cites work: Hardness vs randomness
cites work: The PL Hierarchy Collapses
cites work: Making Nondeterminism Unambiguous
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Verifying the determinant in parallel
cites work: Pseudorandom generators without the XOR lemma
cites work: The method of forced enumeration for nondeterministic automata
cites work: Properties that characterize LOGCFL
description: scientific article; zbMATH DE number 1389781