scientific article; zbMATH DE number 806749

MaRDI QIDQ4850550zbMATH OpenFDO

Authors Mauricio Karchmer

Publication date 18 March 1996

zbMATH Keywords

Boolean functionscircuit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Circuit size lower bounds and \#SAT upper bounds through a general framework
• On the limit of some algorithmic approach to circuit lower bounds
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• Models of lower-bounds proofs
• scientific article; zbMATH DE number 4170847

Cited in

(17)

• Lower bounds on the area complexity of Boolean circuits
• Feasibly constructive proofs of succinct weak circuit lower bounds
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• Lower bounds: from circuits to QBF proof systems
• On the limit of some algorithmic approach to circuit lower bounds
• On Lower Bounds for Constant Width Arithmetic Circuits
• On Circuit-Size Complexity and the Low Hierarchy in NP
• scientific article; zbMATH DE number 4125345 (Why is no real title available?)
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
• On uniformity and circuit lower bounds
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• Proving Circuit Lower Bounds in High Uniform Classes
• On defining integers and proving arithmetic circuit lower bounds
• On the number of different variables required to define the n-density or the bounded n-width of Kripke frames with some consequences for Sahlqvist formulae

This page was built for publication:

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