Articles under category:
SAT
SAT
Vol 14, Article 9 (pp 1-55)
[CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan |
Vol 11, Article 17 (pp 413-443)
[APRX-RND13 Spec Issue]
Conditional Random Fields, Planted Constraint Satisfaction, and Entropy Concentration by Emmanuel Abbe and Andrea Montanari |
Vol 10, Article 12 (pp 297-339)
Width-Parametrized SAT: Time--Space Tradeoffs by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang |
Vol 9, Article 19 (pp 617-651)
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems by Uriel Feige, Elchanan Mossel, and Dan Vilenchik |
Vol 8, Article 11 (pp 239-267)
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set by Venkatesan Guruswami and Yuan Zhou |
Vol 8, Article 1 (pp 1-51)
Time-Space Efficient Simulations of Quantum Computations by Dieter van Melkebeek and Thomas Watson |
Vol 5, Article 1 (pp 1-42)
The Power of Unentanglement by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor |
Vol 3, Article 3 (pp 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma |
Vol 3, Article 2 (pp 25-43)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek |
Vol 2, Article 4 (pp 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi |