Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity

DOI10.1137/1.9781611973730.18MaRDI QIDQ5363030zbMATH OpenOpenAlexFDO

Authors Rahul Santhanam, Ryan Williams

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.18

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Publication:4828947
• The complexity of satisfiability of small depth circuits
• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• On the exact complexity of evaluating quantified k-CNF
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth

Cited in

(12)

• On the exact complexity of evaluating quantified \(k\)-\textsc{cnf}
• Scheduling lower bounds via AND subset sum
• Signatures of knowledge for Boolean circuits under standard assumptions
• Amplifying circuit lower bounds against polynomial time, with applications
• The complexity of satisfiability of small depth circuits
• Beating brute force for (quantified) satisfiability of circuits of bounded treewidth
• scientific article; zbMATH DE number 2119676 (Why is no real title available?)
• Signatures of Knowledge for Boolean Circuits Under Standard Assumptions
• Criticality of regular formulas
• Scheduling lower bounds via and subset sum
• Asymptotically best method for synthesis of Boolean recursive circuits
• An upper bound for the circuit complexity of existentially quantified Boolean formulas

This page was built for publication: Beating exhaustive search for quantified Boolean formulas and connections to circuit complexity

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