% csauthors.net - beta - BibTeX bibliography of Samuel R. Buss
@inproceedings{conf/stoc/Buss85,
title = {The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract)},
year = {1985},
booktitle = {STOC},
author = {{Samuel R. Buss}},
publisher = {ACM},
booktitle = {Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA}
}
@inproceedings{conf/coco/Buss86a,
title = {The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.},
year = {1986},
booktitle = {SCT},
author = {{Samuel R. Buss}},
publisher = {Springer},
booktitle = {Structure in Complexity Theory, Proceedings of the Conference hold at the University of California, Berkeley, California, USA, June 2-5, 1986}
}
@inproceedings{conf/stoc/Buss87,
title = {The Boolean Formula Value Problem Is in ALOGTIME},
year = {1987},
booktitle = {STOC},
author = {{Samuel R. Buss}},
publisher = {ACM},
booktitle = {Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA}
}
@article{journals/jsyml/Buss87,
title = {Polynomial Size Proofs of the Propositional Pigeonhole Principle.},
year = {1987},
journal = {J. Symb. Log.},
author = {{Samuel R. Buss}}
}
@inproceedings{conf/coco/BussH88,
title = {On truth-table reducibility to SAT and the difference hierarchy over NP.},
year = {1988},
booktitle = {SCT},
author = {{Samuel R. Buss} and {Louise Hay}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988}
}
@article{journals/tcs/BussT88,
title = {Resolution Proofs of Generalized Pigeonhole Principles.},
year = {1988},
journal = {Theor. Comput. Sci.},
author = {{Samuel R. Buss} and {György Turán}}
}
@article{journals/ndjfl/Buss90,
title = {The Modal Logic of Pure Provability.},
year = {1990},
journal = {Notre Dame J. Formal Log.},
author = {{Samuel R. Buss}}
}
@inproceedings{conf/lics/BonetB91,
title = {On the Deduction Rule and the Number of Proof Lines},
year = {1991},
booktitle = {LICS},
author = {{Maria Luisa Bonet} and {Samuel R. Buss}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS '91), Amsterdam, The Netherlands, July 15-18, 1991}
}
@article{journals/apal/Buss91,
title = {Propositional Consistency Proofs.},
year = {1991},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/Buss91a,
title = {The Undecidability of k-Provability.},
year = {1991},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/compsys/BussPT91,
title = {On the Predictability of Coupled Automata: An Allegory about Chaos.},
year = {1991},
journal = {Complex Syst.},
author = {{Samuel R. Buss} and {Christos H. Papadimitriou} and {John N. Tsitsiklis}}
}
@article{journals/iandc/BussH91,
title = {On Truth-Table Reducibility to SAT},
year = {1991},
month = {March},
journal = {Inf. Comput.},
author = {{Samuel R. Buss} and {Louise Hay}}
}
@article{journals/ipl/Buss92,
title = {The Graph of Multiplication is Equivalent to Counting.},
year = {1992},
journal = {Inf. Process. Lett.},
author = {{Samuel R. Buss}}
}
@article{journals/siamcomp/BussCGR92,
title = {An Optimal Parallel Algorithm for Formula Evaluation.},
year = {1992},
journal = {SIAM J. Comput.},
author = {{Samuel R. Buss} and {Stephen A. Cook} and {A. Gupta} and {V. Ramachandran}}
}
@article{journals/apal/Buss93,
title = {Intuitionistic Validity in T-Normal Kripke Structures.},
year = {1993},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/jsyml/BonetB93,
title = {The Deduction Rule and Linear and Near-Linear Proof Simulations.},
year = {1993},
journal = {J. Symb. Log.},
author = {{Maria Luisa Bonet} and {Samuel R. Buss}}
}
@inproceedings{conf/csl/PudlakB94,
title = {How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus.},
year = {1994},
booktitle = {CSL},
author = {{Pavel Pudlák} and {Samuel R. Buss}},
publisher = {Springer},
booktitle = {Computer Science Logic, 8th International Workshop, CSL '94, Kazimierz, Poland, September 25-30, 1994, Selected Papers}
}
@inproceedings{conf/lcc/Buss94,
title = {On Herbrand's Theorem.},
year = {1994},
booktitle = {LCC},
author = {{Samuel R. Buss}},
publisher = {Springer},
booktitle = {Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, International Workshop LCC '94, Indianapolis, Indiana, USA, 13-16 October 1994}
}
@inproceedings{conf/soda/BussY94,
title = {Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.},
year = {1994},
booktitle = {SODA},
author = {{Samuel R. Buss} and {Peter N. Yianilos}},
publisher = {ACM/SIAM},
booktitle = {Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA.}
}
@article{journals/ipl/BonetB94,
title = {Size-Depth Tradeoffs for Boolean Fomulae.},
year = {1994},
journal = {Inf. Process. Lett.},
author = {{Maria Luisa Bonet} and {Samuel R. Buss}}
}
@article{journals/jsyml/Buss94,
title = {On Gödel's Theorems on Lenghts of Proofs I: Number of Lines and Speedup for Arithmetics.},
year = {1994},
journal = {J. Symb. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/aml/Buss95,
title = {Some remarks on lengths of propositional proofs.},
year = {1995},
journal = {Arch. Math. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/Buss95,
title = {Relating the Bounded Arithmetic and Polynomial Time Hierarchies.},
year = {1995},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/BussI95,
title = {Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.},
year = {1995},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {Aleksandar Ignjatovic}}
}
@article{journals/siamcomp/BonetB95,
title = {The Serial Transitive Closure Problem for Trees.},
year = {1995},
journal = {SIAM J. Comput.},
author = {{Maria Luisa Bonet} and {Samuel R. Buss}}
}
@inproceedings{conf/dimacs/Buss96,
title = {Lower bounds on Nullstellensatz proofs via designs.},
year = {1996},
booktitle = {Proof Complexity and Feasible Arithmetics},
author = {{Samuel R. Buss}},
publisher = {DIMACS/AMS},
booktitle = {Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996}
}
@article{journals/aml/BussC96,
title = {Cutting planes, connectivity, and threshold logic.},
year = {1996},
journal = {Arch. Math. Log.},
author = {{Samuel R. Buss} and {Peter Clote}}
}
@inproceedings{conf/csl/BussP97,
title = {Resolution and the Weak Pigeonhole Principle.},
year = {1997},
booktitle = {CSL},
author = {{Samuel R. Buss} and {Toniann Pitassi}},
publisher = {Springer},
booktitle = {Computer Science Logic, 11th International Workshop, CSL '97, Annual Conference of the EACSL, Aarhus, Denmark, August 23-29, 1997, Selected Papers}
}
@inproceedings{conf/kgc/Buss97,
title = {Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization.},
year = {1997},
booktitle = {Kurt Gödel Colloquium},
author = {{Samuel R. Buss}},
publisher = {Springer},
booktitle = {Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, KGC'97, Vienna, Austria, August 25-29, 1997, Proceedings}
}
@article{journals/cc/BussIPRS97,
title = {Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.},
year = {1997},
journal = {Comput. Complex.},
author = {{Samuel R. Buss} and {Russell Impagliazzo} and {Jan Krajícek} and {Pavel Pudlák} and {Alexander A. Razborov} and {Jirí Sgall}}
}
@article{journals/jcss/BussP98,
title = {Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.},
year = {1998},
journal = {J. Comput. Syst. Sci.},
author = {{Samuel R. Buss} and {Toniann Pitassi}}
}
@article{journals/siamcomp/BussY98,
title = {Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.},
year = {1998},
journal = {SIAM J. Comput.},
author = {{Samuel R. Buss} and {Peter N. Yianilos}}
}
@inproceedings{conf/coco/BussGIP99,
title = {Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).},
year = {1999},
booktitle = {CCC},
author = {{Samuel R. Buss} and {Dima Grigoriev} and {Russell Impagliazzo} and {Toniann Pitassi}},
publisher = {IEEE Computer Society},
booktitle = {Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999}
}
@article{journals/apal/Buss99,
title = {Bounded Arithmetic, Proof Complexity and Two Papers of Parikh.},
year = {1999},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/BussM99,
title = {The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic.},
year = {1999},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {Grigori Mints}}
}
@inproceedings{journals/entcs/BussR00,
title = {Incompleteness of Behavioral Logics.},
year = {2000},
booktitle = {CMCS},
author = {{Samuel R. Buss} and {Grigore Rosu}},
publisher = {Elsevier},
booktitle = {Coalgebraic Methods in Computer Science, CMCS 2000, Berlin, Germany, March 25-26, 2000}
}
@article{journals/apal/BussP01,
title = {On the computational content of intuitionistic propositional proofs.},
year = {2001},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {Pavel Pudlák}}
}
@article{journals/bsl/BussKPS01,
title = {The prospects for mathematical logic in the twenty-first century.},
year = {2001},
journal = {Bull. Symb. Log.},
author = {{Samuel R. Buss} and {Alexander S. Kechris} and {Anand Pillay} and {Richard A. Shore}}
}
@article{journals/jcss/BussGIP01,
title = {Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.},
year = {2001},
journal = {J. Comput. Syst. Sci.},
author = {{Samuel R. Buss} and {Dima Grigoriev} and {Russell Impagliazzo} and {Toniann Pitassi}}
}
@article{journals/jsyml/AlekhnovichBMP01,
title = {Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.},
year = {2001},
journal = {J. Symb. Log.},
author = {{Michael Alekhnovich} and {Samuel R. Buss} and {Shlomo Moran} and {Toniann Pitassi}}
}
@article{journals/tog/BussF01,
title = {Spherical averages and applications to spherical splines and interpolation.},
year = {2001},
journal = {ACM Trans. Graph.},
author = {{Samuel R. Buss} and {Jay P. Fillmore}}
}
@article{journals/tocl/BussK02,
title = {Resource-bounded continuity and sequentiality for type-two functionals.},
year = {2002},
journal = {ACM Trans. Comput. Log.},
author = {{Samuel R. Buss} and {Bruce M. Kapron}}
}
@article{journals/apal/BeckmannBP03,
title = {Erratum to "Ordinal notations and well-orderings in bounded arithmetic" [Annals of Pure and Applied Logic 120 (2003) 197-223].},
year = {2003},
journal = {Ann. Pure Appl. Log.},
author = {{Arnold Beckmann} and {Samuel R. Buss} and {Chris Pollett}}
}
@article{journals/apal/BeckmannPB03,
title = {Ordinal notations and well-orderings in bounded arithmetic.},
year = {2003},
journal = {Ann. Pure Appl. Log.},
author = {{Arnold Beckmann} and {Chris Pollett} and {Samuel R. Buss}}
}
@article{journals/siamcomp/SegerlindBI04,
title = {A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.},
year = {2004},
journal = {SIAM J. Comput.},
author = {{Nathan Segerlind} and {Samuel R. Buss} and {Russell Impagliazzo}}
}
@article{journals/apal/BeckmannB05,
title = {Separation results for the size of constant-depth propositional proofs.},
year = {2005},
journal = {Ann. Pure Appl. Log.},
author = {{Arnold Beckmann} and {Samuel R. Buss}}
}
@article{journals/jgtools/BussK05,
title = {Selectively Damped Least Squares for Inverse Kinematics.},
year = {2005},
journal = {J. Graph. Tools},
author = {{Samuel R. Buss} and {Jin-Su Kim}}
}
@article{journals/vc/Buss05,
title = {Collision detection with relative screw motion.},
year = {2005},
journal = {Vis. Comput.},
author = {{Samuel R. Buss}}
}
@article{journals/tcs/Buss06,
title = {Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies.},
year = {2006},
journal = {Theor. Comput. Sci.},
author = {{Samuel R. Buss}}
}
@article{journals/lmcs/BussHJ08,
title = {Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning.},
year = {2008},
journal = {Log. Methods Comput. Sci.},
author = {{Samuel R. Buss} and {Jan Hoffmann 002} and {Jan Johannsen}}
}
@article{journals/tcs/BussH08,
title = {The NP-hardness of finding a directed acyclic graph for regular resolution.},
year = {2008},
journal = {Theor. Comput. Sci.},
author = {{Samuel R. Buss} and {Jan Hoffmann 002}}
}
@inproceedings{conf/lfcs/BussK09,
title = {The NP-Completeness of Reflected Fragments of Justification Logics.},
year = {2009},
booktitle = {LFCS},
author = {{Samuel R. Buss} and {Roman Kuznets}},
publisher = {Springer},
booktitle = {Logical Foundations of Computer Science, International Symposium, LFCS 2009, Deerfield Beach, FL, USA, January 3-6, 2009. Proceedings}
}
@inproceedings{conf/vr/TracyBW09,
title = {Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal.},
year = {2009},
booktitle = {VR},
author = {{Daniel J. Tracy} and {Samuel R. Buss} and {Bryan M. Woods}},
publisher = {IEEE Computer Society},
booktitle = {IEEE Virtual Reality Conference 2009 (VR 2009), 14-18 March 2009, Lafayette, Louisiana, USA, Proceedings}
}
@article{journals/aml/Buss09,
title = {Pool resolution is NP-hard to recognize.},
year = {2009},
journal = {Arch. Math. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/BussCLS09,
title = {Preface.},
year = {2009},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {S. Barry Cooper} and {Benedikt Löwe} and {Andrea Sorbi}}
}
@article{journals/jml/BeckmannB09,
title = {Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic.},
year = {2009},
journal = {J. Math. Log.},
author = {{Arnold Beckmann} and {Samuel R. Buss}}
}
@article{journals/mlq/BussJ10,
title = {The quantifier complexity of polynomial-size iterated definitions in first-order logic.},
year = {2010},
journal = {Math. Log. Q.},
author = {{Samuel R. Buss} and {Alan S. Johnson}}
}
@article{journals/jsyml/BussCFFM11,
title = {Strong isomorphism reductions in complexity theory.},
year = {2011},
journal = {J. Symb. Log.},
author = {{Sam Buss} and {Yijia Chen} and {Jörg Flum} and {Sy-David Friedman} and {Moritz Müller}}
}
@article{journals/tcs/BeckmannB11,
title = {Corrected upper bounds for free-cut elimination.},
year = {2011},
journal = {Theor. Comput. Sci.},
author = {{Arnold Beckmann} and {Samuel R. Buss}}
}
@inproceedings{conf/sat/BonetB12,
title = {An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning.},
year = {2012},
booktitle = {SAT},
author = {{Maria Luisa Bonet} and {Samuel R. Buss}},
publisher = {Springer},
booktitle = {Theory and Applications of Satisfiability Testing - SAT 2012 - 15th International Conference, Trento, Italy, June 17-20, 2012. Proceedings}
}
@article{journals/apal/Ambos-SpiesBBL12,
title = {Computability in Europe 2009.},
year = {2012},
journal = {Ann. Pure Appl. Log.},
author = {{Klaus Ambos-Spies} and {Arnold Beckmann} and {Samuel R. Buss} and {Benedikt Löwe}}
}
@article{journals/apal/Buss12,
title = {Towards NP-P via proof complexity and search.},
year = {2012},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss}}
}
@article{journals/apal/BussJ12,
title = {Propositional proofs and reductions between NP search problems.},
year = {2012},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {Alan S. Johnson}}
}
@article{journals/apal/BussK12,
title = {Lower complexity bounds in justification logic.},
year = {2012},
journal = {Ann. Pure Appl. Log.},
author = {{Samuel R. Buss} and {Roman Kuznets}}
}
@article{journals/jsyml/Buss12,
title = {Sharpened lower bounds for cut elimination.},
year = {2012},
journal = {J. Symb. Log.},
author = {{Samuel R. Buss}}
}
@book{books/daglib/0033748,
title = {3-D Computer Graphics.},
year = {2013},
isbn = {978-0-521-82103-2},
publisher = {Cambridge University Press},
author = {{Samuel R. Buss}}
}
@inproceedings{conf/ijcai/BonetB13,
title = {An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning (Extended Abstract).},
year = {2013},
booktitle = {IJCAI},
author = {{Maria Luisa Bonet} and {Sam Buss}},
publisher = {IJCAI/AAAI},
booktitle = {IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013}
}
@inproceedings{conf/mfcs/Buss13,
title = {Alternation Trading Proofs and Their Limitations.},
year = {2013},
booktitle = {MFCS},
author = {{Sam Buss}},
publisher = {Springer},
booktitle = {Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings}
}
@article{journals/apal/BussLNS13,
title = {Computability in Europe 2011.},
year = {2013},
journal = {Ann. Pure Appl. Log.},
author = {{Sam Buss} and {Benedikt Löwe} and {Dag Normann} and {Ivan N. Soskov}}
}
@article{journals/jsyml/BussM13,
title = {Probabilistic algorithmic randomness.},
year = {2013},
journal = {J. Symb. Log.},
author = {{Sam Buss} and {Mia Minnes}}
}
@article{journals/corr/BussCR14,
title = {Sub-computable Boundedness Randomness.},
year = {2014},
journal = {Log. Methods Comput. Sci.},
author = {{Sam Buss} and {Douglas Cenzer} and {Jeffrey B. Remmel}}
}
@article{journals/corr/BussK14,
title = {Small Stone in Pool.},
year = {2014},
journal = {Log. Methods Comput. Sci.},
author = {{Samuel R. Buss} and {Leszek Aleksander Kolodziejczyk}}
}
@article{journals/jair/BonetBJ14,
title = {Improved Separations of Regular Resolution from Clause Learning Proof Systems.},
year = {2014},
journal = {J. Artif. Intell. Res.},
author = {{Maria Luisa Bonet} and {Sam Buss} and {Jan Johannsen}}
}
@article{journals/jcss/BussS14,
title = {Unshuffling a square is NP-hard.},
year = {2014},
journal = {J. Comput. Syst. Sci.},
author = {{Sam Buss} and {Michael Soltys}}
}
@article{journals/jsyml/BussKT14,
title = {Fragments of Approximate Counting.},
year = {2014},
journal = {J. Symb. Log.},
author = {{Samuel R. Buss} and {Leszek Aleksander Kolodziejczyk} and {Neil Thapen}}
}
@article{journals/tocl/BeckmannB14,
title = {Improved witnessing and local improvement principles for second-order bounded arithmetic.},
year = {2014},
journal = {ACM Trans. Comput. Log.},
author = {{Arnold Beckmann} and {Samuel R. Buss}}
}
@inproceedings{conf/csr/Buss15,
title = {Propositional Proofs in Frege and Extended Frege Systems (Abstract).},
year = {2015},
booktitle = {CSR},
author = {{Sam Buss}},
publisher = {Springer},
booktitle = {Computer Science - Theory and Applications - 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings}
}
@article{journals/cc/BussW15,
title = {Limits on Alternation Trading Proofs for Time-Space Lower Bounds.},
year = {2015},
journal = {Comput. Complex.},
author = {{Samuel R. Buss} and {Ryan Williams 001}}
}
@article{journals/jsyml/BeckmannBF15,
title = {Safe Recursive Set Functions.},
year = {2015},
journal = {J. Symb. Log.},
author = {{Arnold Beckmann} and {Samuel R. Buss} and {Sy-David Friedman}}
}
@article{journals/sLogica/Buss15,
title = {Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination.},
year = {2015},
journal = {Stud Logica},
author = {{Sam Buss}}
}
@article{journals/tcs/Buss15,
title = {Quasipolynomial size proofs of the propositional pigeonhole principle.},
year = {2015},
journal = {Theor. Comput. Sci.},
author = {{Sam Buss}}
}
@article{journals/apal/BeckmannBFMT16,
title = {Cobham recursive set functions.},
year = {2016},
journal = {Ann. Pure Appl. Log.},
author = {{Arnold Beckmann} and {Sam Buss} and {Sy-David Friedman} and {Moritz Müller} and {Neil Thapen}}
}
@article{journals/eccc/BussKKK16,
title = {Expander Construction in VNC1.},
year = {2016},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Sam Buss} and {Valentine Kabanets} and {Antonina Kolokolova} and {Michal Koucký 001}}
}
@article{journals/jsat/BussJ16,
title = {On Linear Resolution.},
year = {2016},
journal = {J. Satisf. Boolean Model. Comput.},
author = {{Sam Buss} and {Jan Johannsen}}
}
@article{journals/jsyml/AisenbergBB16,
title = {Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Sets.},
year = {2016},
journal = {J. Symb. Log.},
author = {{James Aisenberg} and {Maria Luisa Bonet} and {Sam Buss}}
}
@inproceedings{conf/birthday/BussCMR17,
title = {Injection Structures Specified by Finite State Transducers.},
year = {2017},
booktitle = {Computability and Complexity},
author = {{Sam Buss} and {Douglas Cenzer} and {Mia Minnes} and {Jeffrey B. Remmel}},
publisher = {Springer},
booktitle = {Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday}
}
@inproceedings{conf/innovations/BussKKK17,
title = {Expander Construction in VNC1.},
year = {2017},
booktitle = {ITCS},
author = {{Sam Buss} and {Valentine Kabanets} and {Antonina Kolokolova} and {Michal Koucký 001}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA}
}
@article{journals/aml/Buss17,
title = {Uniform proofs of ACC representations.},
year = {2017},
journal = {Arch. Math. Log.},
author = {{Sam Buss}}
}
@article{journals/tocl/BeckmannB17,
title = {The NP Search Problems of Frege and Extended Frege Proofs.},
year = {2017},
journal = {ACM Trans. Comput. Log.},
author = {{Arnold Beckmann} and {Sam Buss}}
}
@inproceedings{conf/aaai/BonetBIMM18,
title = {MaxSAT Resolution With the Dual Rail Encoding.},
year = {2018},
booktitle = {AAAI},
author = {{Maria Luisa Bonet} and {Sam Buss} and {Alexey Ignatiev} and {João Marques-Silva 001} and {António Morgado 001}},
publisher = {AAAI Press},
booktitle = {Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018}
}
@article{journals/eccc/BussIKS18,
title = {Reordering Rule Makes OBDD Proof Systems Stronger.},
year = {2018},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Sam Buss} and {Dmitry Itsykson} and {Alexander Knop} and {Dmitry Sokolov 001}}
}
@article{journals/iandc/AisenbergBBCI18,
title = {Short proofs of the Kneser-Lovász coloring principle.},
year = {2018},
journal = {Inf. Comput.},
author = {{James Aisenberg} and {Maria Luisa Bonet} and {Sam Buss} and {Adrian Craciun} and {Gabriel Istrate}}
}
@article{journals/mlq/BussR18,
title = {Short refutations for an equivalence-chain principle for constant-depth formulas.},
year = {2018},
journal = {Math. Log. Q.},
author = {{Sam Buss} and {Ramyaa Ramyaa}}
}
@inproceedings{conf/sat/BussT19,
title = {DRAT Proofs, Propagation Redundancy, and Extended Resolution.},
year = {2019},
booktitle = {SAT},
author = {{Sam Buss} and {Neil Thapen}},
publisher = {Springer},
booktitle = {Theory and Applications of Satisfiability Testing - SAT 2019 - 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings}
}
@inproceedings{conf/sat/MorgadoIBMB19,
title = {DRMaxSAT with MaxHS: First Contact.},
year = {2019},
booktitle = {SAT},
author = {{António Morgado 001} and {Alexey Ignatiev} and {Maria Luisa Bonet} and {João Marques-Silva 001} and {Sam Buss}},
publisher = {Springer},
booktitle = {Theory and Applications of Satisfiability Testing - SAT 2019 - 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings}
}
@inproceedings{conf/soda/BussK19,
title = {Strategies for Stable Merge Sorting.},
year = {2019},
booktitle = {SODA},
author = {{Sam Buss} and {Alexander Knop}},
publisher = {SIAM},
booktitle = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019}
}
@article{journals/apal/BeckmannB19,
title = {On transformations of constant depth propositional proofs.},
year = {2019},
journal = {Ann. Pure Appl. Log.},
author = {{Arnold Beckmann} and {Sam Buss}}
}
@article{journals/computability/BeckmannBFMT19,
title = {Feasible set functions have small circuits.},
year = {2019},
journal = {Comput.},
author = {{Arnold Beckmann} and {Sam Buss} and {Sy-David Friedman} and {Moritz Müller} and {Neil Thapen}}
}
@inproceedings{conf/csl/Buss0K20,
title = {Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs.},
year = {2020},
booktitle = {CSL},
author = {{Sam Buss} and {Anupam Das 002} and {Alexander Knop}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain.}
}
@article{journals/jcss/AisenbergBB20,
title = {2-D Tucker is PPA complete.},
year = {2020},
journal = {J. Comput. Syst. Sci.},
author = {{James Aisenberg} and {Maria Luisa Bonet} and {Sam Buss}}
}
@article{journals/ai/BonetBIMM21,
title = {Propositional proof systems based on maximum satisfiability.},
year = {2021},
journal = {Artif. Intell.},
author = {{Maria Luisa Bonet} and {Sam Buss} and {Alexey Ignatiev} and {António Morgado 001} and {João Marques-Silva 001}}
}
@article{journals/lmcs/BussT21,
title = {DRAT and Propagation Redundancy Proofs Without New Variables.},
year = {2021},
journal = {Log. Methods Comput. Sci.},
author = {{Sam Buss} and {Neil Thapen}}
}
@article{journals/tocl/BussIKRS21,
title = {Lower Bounds on OBDD Proofs with Several Orders.},
year = {2021},
journal = {ACM Trans. Comput. Log.},
author = {{Sam Buss} and {Dmitry Itsykson} and {Alexander Knop} and {Artur Riazanov} and {Dmitry Sokolov 001}}
}
@incollection{series/faia/BussN21,
title = {Proof Complexity and SAT Solving.},
year = {2021},
booktitle = {Handbook of Satisfiability},
author = {{Sam Buss} and {Jakob Nordström}},
publisher = {IOS Press},
booktitle = {Handbook of Satisfiability - Second Edition}
}
@article{journals/eccc/BussFI22,
title = {TFNP Characterizations of Proof Systems and Monotone Circuits.},
year = {2022},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Sam Buss} and {Noah Fleming} and {Russell Impagliazzo}}
}
@incollection{books/acm/23/Buss23,
title = {Polynomially Verifiable Arithmetic.},
year = {2023},
booktitle = {Logic, Automata, and Computational Complexity},
author = {{Sam Buss}},
publisher = {ACM},
booktitle = {Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook}
}
@inproceedings{conf/stoc/AtseriasBM23,
title = {On the Consistency of Circuit Lower Bounds for Non-deterministic Time.},
year = {2023},
booktitle = {STOC},
author = {{Albert Atserias} and {Sam Buss} and {Moritz Müller}},
publisher = {ACM},
booktitle = {Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023}
}
@article{journals/eccc/BussT24,
title = {A Simple Supercritical Tradeoff between Size and Height in Resolution.},
year = {2024},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Sam Buss} and {Neil Thapen}}
}
@article{journals/eccc/BussY24,
title = {Regular resolution effectively simulates resolution.},
year = {2024},
journal = {Electron. Colloquium Comput. Complex.},
author = {{Sam Buss} and {Emre Yolcu}}
}