The complexity of circuit value and network stability
From MaRDI portal
Publication:1190989
DOI10.1016/0022-0000(92)90024-DzbMath0762.68024OpenAlexW2173502887MaRDI QIDQ1190989
Ashok Subramanian, Ernst W. Mayr
Publication date: 27 September 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(92)90024-d
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (9)
Parallel approximation algorithms for maximum weighted matching in general graphs ⋮ Comparator circuits over finite bounded posets ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Using maximal independent sets to solve problems in parallel ⋮ Unnamed Item ⋮ Fanout limitations on constraint systems ⋮ Adventures in monotone complexity and TFNP ⋮ The complexity of the comparator circuit value problem ⋮ A sublinear parallel algorithm for stable matching
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the construction of parallel computers from various basis of Boolean functions
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- The method of forced enumeration for nondeterministic automata
- On uniform circuit complexity
- Space-bounded reducibility among combinatorial problems
- A taxonomy of problems with fast parallel algorithms
- Classifying the computational complexity of problems
- Problems complete for deterministic logarithmic space
- Nondeterministic Space is Closed under Complementation
- On Relating Time and Space to Size and Depth
- A New Approach to Stable Matching Problems
- Fast parallel matrix and GCD computations
- College Admissions and the Stability of Marriage
This page was built for publication: The complexity of circuit value and network stability
