Sam Buss

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 43

Top Topics

Clause Learning

Top Venues

Electron. Colloquium Comput. Complex.

Ann. Pure Appl. Log.

J. Comput. Syst. Sci.

Publications

Sam Buss, Emre Yolcu
Regular resolution effectively simulates resolution. CoRR (2024)
Sam Buss, Emre Yolcu
Regular resolution effectively simulates resolution. Electron. Colloquium Comput. Complex. (2024)
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria
Redundancy for MaxSAT. Electron. Colloquium Comput. Complex. (2024)
Sam Buss, Neil Thapen
A Simple Supercritical Tradeoff between Size and Height in Resolution. Electron. Colloquium Comput. Complex. (2024)
Sam Buss, Jonathan Chung, Vijay Ganesh, Albert Oliveras
Extended Resolution Clause Learning via Dual Implication Points. CoRR (2024)
Albert Atserias, Sam Buss, Moritz Müller
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. CoRR (2023)
Albert Atserias, Sam Buss, Moritz Müller
On the Consistency of Circuit Lower Bounds for Non-deterministic Time. STOC (2023)
Sam Buss, Noah Fleming, Russell Impagliazzo
TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS (2023)
Sam Buss, Noah Fleming, Russell Impagliazzo
TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. (2022)
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
Lower Bounds on OBDD Proofs with Several Orders. ACM Trans. Comput. Log. 22 (4) (2021)
Sam Buss, Neil Thapen
DRAT and Propagation Redundancy Proofs Without New Variables. Log. Methods Comput. Sci. 17 (2) (2021)
Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, António Morgado, João Marques-Silva
Propositional proof systems based on maximum satisfiability. Artif. Intell. 300 (2021)
Sam Buss, Anupam Das, Alexander Knop
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs. CSL (2020)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Ann. Pure Appl. Log. 171 (7) (2020)
Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov
Lower Bounds on OBDD Proofs with Several Orders. Electron. Colloquium Comput. Complex. 27 (2020)
James Aisenberg, Maria Luisa Bonet, Sam Buss
2-D Tucker is PPA complete. J. Comput. Syst. Sci. 108 (2020)
António Morgado, Alexey Ignatiev, Maria Luisa Bonet, João Marques-Silva, Sam Buss
DRMaxSAT with MaxHS: First Contact. SAT (2019)
Sam Buss, Alexander Knop
Strategies for Stable Merge Sorting. SODA (2019)
Arnold Beckmann, Sam Buss
On transformations of constant depth propositional proofs. Ann. Pure Appl. Log. 170 (10) (2019)
Sam Buss, Anupam Das, Alexander Knop
Proof complexity of systems of (non-deterministic) decision trees and branching programs. CoRR (2019)
Sam Buss, Neil Thapen
DRAT Proofs, Propagation Redundancy, and Extended Resolution. SAT (2019)
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen
Feasible set functions have small circuits. Comput. 8 (1) (2019)
Sam Buss, Neil Thapen
DRAT and Propagation Redundancy Proofs Without New Variables. CoRR (2019)
Sam Buss, Ramyaa Ramyaa
Short refutations for an equivalence-chain principle for constant-depth formulas. Math. Log. Q. 64 (6) (2018)
Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, João Marques-Silva, António Morgado
MaxSAT Resolution With the Dual Rail Encoding. AAAI (2018)
James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate
Short proofs of the Kneser-Lovász coloring principle. Inf. Comput. 261 (2018)
Sam Buss, Alexander Knop
Strategies for Stable Merge Sorting. CoRR (2018)
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Reordering Rule Makes OBDD Proof Systems Stronger. Computational Complexity Conference (2018)
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov
Reordering Rule Makes OBDD Proof Systems Stronger. Electron. Colloquium Comput. Complex. 25 (2018)
Sam Buss, Douglas Cenzer, Mia Minnes, Jeffrey B. Remmel
Injection Structures Specified by Finite State Transducers. Computability and Complexity (2017)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
Expander Construction in VNC1. ITCS (2017)
Sam Buss
Uniform proofs of ACC representations. Arch. Math. Log. 56 (5-6) (2017)
Arnold Beckmann, Sam Buss
The NP Search Problems of Frege and Extended Frege Proofs. ACM Trans. Comput. Log. 18 (2) (2017)
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen
Cobham recursive set functions. Ann. Pure Appl. Log. 167 (3) (2016)
Sam Buss, Jan Johannsen
On Linear Resolution. J. Satisf. Boolean Model. Comput. 10 (1) (2016)
James Aisenberg, Maria Luisa Bonet, Sam Buss
Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Sets. J. Symb. Log. 81 (2) (2016)
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký
. Electron. Colloquium Comput. Complex. 23 (2016)
James Aisenberg, Maria Luisa Bonet, Sam Buss
2-D Tucker is PPA complete. Electron. Colloquium Comput. Complex. 22 (2015)
Sam Buss
Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination. Stud Logica 103 (3) (2015)
Sam Buss
Propositional Proofs in Frege and Extended Frege Systems (Abstract). CSR (2015)
Sam Buss
Quasipolynomial size proofs of the propositional pigeonhole principle. Theor. Comput. Sci. 576 (2015)
James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate
Short Proofs of the Kneser-Lovász Coloring Principle. CoRR (2015)
James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate
Short Proofs of the Kneser-Lovász Coloring Principle. ICALP (2) (2015)
Maria Luisa Bonet, Sam Buss, Jan Johannsen
Improved Separations of Regular Resolution from Clause Learning Proof Systems. J. Artif. Intell. Res. 49 (2014)
Sam Buss, Michael Soltys
Unshuffling a square is NP-hard. J. Comput. Syst. Sci. 80 (4) (2014)
Sam Buss, Douglas Cenzer, Jeffrey B. Remmel
Sub-computable Boundedness Randomness. Log. Methods Comput. Sci. 10 (4) (2014)
Sam Buss, Benedikt Löwe, Dag Normann, Ivan N. Soskov
Computability in Europe 2011. Ann. Pure Appl. Log. 164 (5) (2013)
Sam Buss, Mia Minnes
Probabilistic algorithmic randomness. J. Symb. Log. 78 (2) (2013)
Maria Luisa Bonet, Sam Buss
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning (Extended Abstract). IJCAI (2013)
Sam Buss
Alternation Trading Proofs and Their Limitations. MFCS (2013)
Maria Luisa Bonet, Sam Buss, Jan Johannsen
Improved Separations of Regular Resolution from Clause Learning Proof Systems CoRR (2012)
Sam Buss, Michael Soltys
Unshuffling a Square is NP-Hard. CoRR (2012)
Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman, Moritz Müller
Strong isomorphism reductions in complexity theory. J. Symb. Log. 76 (4) (2011)
Sam Buss, Ryan Williams
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electron. Colloquium Comput. Complex. 18 (2011)