The complexity of circuit value and network stability
DOI10.1016/0022-0000(92)90024-DzbMATH Open0762.68024OpenAlexW2173502887MaRDI QIDQ1190989FDOQ1190989
Authors: Ernst W. Mayr, Ashok Subramanian 
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
Recommendations
- The complexity of the comparator circuit value problem
- On the construction of parallel computers from various basis of Boolean functions
- Upper bounds for monotone planar circuit value and variants
- An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
- Parallel algorithms for the circuit value update problem
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- On uniform circuit complexity
- A taxonomy of problems with fast parallel algorithms
- Title not available (Why is that?)
- College Admissions and the Stability of Marriage
- Problems complete for deterministic logarithmic space
- Nondeterministic Space is Closed under Complementation
- Title not available (Why is that?)
- Title not available (Why is that?)
- The method of forced enumeration for nondeterministic automata
- Fast parallel matrix and GCD computations
- On Relating Time and Space to Size and Depth
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classifying the computational complexity of problems
- On the construction of parallel computers from various basis of Boolean functions
- Space-bounded reducibility among combinatorial problems
- Title not available (Why is that?)
- A New Approach to Stable Matching Problems
Cited In (12)
- Algorithms and lower bounds for comparator circuits from shrinkage
- Parallel approximation algorithms for maximum weighted matching in general graphs
- Comparator circuits over finite bounded posets
- Global similarity tests of physical designs of circuits: a complex network approach
- Fanout limitations on constraint systems
- On the construction of parallel computers from various basis of Boolean functions
- The complexity of the comparator circuit value problem
- Title not available (Why is that?)
- Verifying minimum stable circuit values
- Adventures in monotone complexity and TFNP
- A sublinear parallel algorithm for stable matching
- Using maximal independent sets to solve problems in parallel
This page was built for publication: The complexity of circuit value and network stability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190989)
