FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

DOI10.1007/B104325MaRDI QIDQ5465877zbMATH OpenOpenAlexFDO

Authors Ashok Kumar Ponnuswami, H. Venkateswaran

Publication date 12 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b104325

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Monotone circuits for matching require linear depth
• Monotone real circuits are more powerful than monotone Boolean circuits
• An improved Boolean circuit for maximum matching in a convex bipartite graph
• Bipartite perfect matching is in quasi-NC
• A lower bound for monotone arithmetic circuits computing \(0-1\) permanent

Cited in

(3)

• Monotone circuits for matching require linear depth
• Lower bounds for monotone q-multilinear Boolean circuits
• Notes on Boolean read-k and multilinear circuits

This page was built for publication: FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5465877)