Two Applications of Inductive Counting for Complementation Problems
DOI10.1137/0218038zbMATH Open0678.68031OpenAlexW2071260871WikidataQ29542907 ScholiaQ29542907MaRDI QIDQ3835019FDOQ3835019
Authors: Allan Borodin, Walter L. Ruzzo, Martin Tompa, Stephen Cook, P. Dymond 
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218038
Recommendations
random walkhierarchyconnectivitypebblingNCcomplementationprobabilistic algorithmLOGCFLsemi-unboundednessinductive countingsymmetric computation
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Circuits, networks (94C99) Sums of independent random variables; random walks (60G50) 2-person games (91A05) Hierarchies of computability and definability (03D55)
Cited In (37)
- 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
- Title not available (Why is that?)
- Title not available (Why is that?)
- Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}
- Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
- The electrical resistance of a graph captures its commute and cover times
- A very hard log-space counting class
- Computing LOGCFL certificates
- Structure and importance of logspace-MOD class
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- Universal traversal sequences for expander graphs
- Context-free grammars with linked nonterminals
- On read-once vs. multiple access to randomness in logspace
- On adaptive DLOGTIME and POLYLOGTIME reductions
- Equivalence classes and conditional hardness in massively parallel computations
- The complexity of graph connectivity
- \(\text{RL}\subseteq \text{SC}\)
- The parameterized space complexity of model-checking bounded variable first-order logic
- A spectrum of time-space trade-offs for undirected \(s-t\) connectivity
- Characterizing parallel hierarchies by reducibilities
- The complexity of computing maximal word functions
- Inductive counting below LOGSPACE
- Generalized quantifier and a bounded arithmetic theory for LOGCFL
- Tradeoff lower lounds for stack machines
- Properties that characterize LOGCFL
- Bounded tree-width and LOGCFL
- Relationships among $PL$, $\#L$, and the determinant
- Lower bounds on the length of universal traversal sequences
- Unambiguous and co-nondeterministic computations of finite automata and pushdown automata families and the effects of multiple counters
- Adaptive logspace reducibility and parallel time
- Depth lower bounds for monotone semi-unbounded fan-in circuits.
- Empty alternation
- A fast randomized LOGSPACE algorithm for graph connectivity
- Dual VP classes
- Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs
- A variant of inductive counting
- Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
This page was built for publication: Two Applications of Inductive Counting for Complementation Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3835019)
