On the bottleneck counting argument

DOI10.1016/S0304-3975(99)00321-7MaRDI QIDQ1566741zbMATH OpenOpenAlexFDO

Authors Janos Simon, Shi-Chun Tsai

Publication date 4 June 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00321-7

zbMATH Keywords

bottleneck counting argumentcircuit complexitycomputational complexitymonotone circuit complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• An exponential lower bound for the size of monotone real circuits
• scientific article; zbMATH DE number 4049557
• On the incompressibility of monotone DNFs
• The Potential of the Approximation Method
• Symmetric approximation arguments for monotone lower bounds without sunflowers

Cites work

• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4012495 (Why is no real title available?)
• scientific article; zbMATH DE number 1261805 (Why is no real title available?)
• scientific article; zbMATH DE number 1263233 (Why is no real title available?)
• scientific article; zbMATH DE number 3999837 (Why is no real title available?)
• Symmetric approximation arguments for monotone lower bounds without sunflowers
• The intractability of resolution
• The monotone circuit complexity of Boolean functions

Cited in

(3)

• On Negations in Boolean Networks
• The Potential of the Approximation Method
• Monotone circuit lower bounds from resolution

This page was built for publication: On the bottleneck counting argument

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