The complexity of the comparator circuit value problem

DOI10.1145/2635822zbMath1347.68156arXiv1208.2721OpenAlexW2016263640MaRDI QIDQ2828221

Yuval Filmus, Dai Tri Man Lê, Stephen A. Cook

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.2721

zbMATH Keywords

P-completenesscomparator circuits

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Comparator circuits over finite bounded posets ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Adventures in monotone complexity and TFNP

Cites Work

• Unnamed Item
• Relativizing small complexity classes and their theories
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• The complexity of circuit value and network stability
• A new fixed point approach for stable networks and stable marriages
• Internal diffusion-limited aggregation: parallel algorithms and complexity
• On uniformity within \(NC^ 1\)
• A Formal Theory for the Complexity Class Associated with the Stable Marriage Problem
• A taxonomy of problems with fast parallel algorithms
• A fast parallel algorithm for the maximal independent set problem
• A New Approach to Stable Matching Problems
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Stable networks and product graphs
• An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
• Logical Foundations of Proof Complexity
• College Admissions and the Stability of Marriage

This page was built for publication: The complexity of the comparator circuit value problem