default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSamuel R. Buss
Sam Buss
Person information
- affiliation: University of California, San Diego, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j76]Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. Inf. Process. Lett. 186: 106489 (2024)- [i21]Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. CoRR abs/2402.15871 (2024) - [i20]Sam Buss, Jonathan Chung, Vijay Ganesh, Albert Oliveras:
Extended Resolution Clause Learning via Dual Implication Points. CoRR abs/2406.14190 (2024) - [i19]Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria:
Redundancy for MaxSAT. Electron. Colloquium Comput. Complex. TR24 (2024) - [i18]Sam Buss, Neil Thapen:
A Simple Supercritical Tradeoff between Size and Height in Resolution. Electron. Colloquium Comput. Complex. TR24 (2024) - [i17]Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c37]Sam Buss, Noah Fleming, Russell Impagliazzo
:
TFNP Characterizations of Proof Systems and Monotone Circuits. ITCS 2023: 30:1-30:40 - [c36]Albert Atserias, Sam Buss, Moritz Müller:
On the Consistency of Circuit Lower Bounds for Non-deterministic Time. STOC 2023: 1257-1270 - [p2]Sam Buss:
Polynomially Verifiable Arithmetic. Logic, Automata, and Computational Complexity 2023: 95-106 - [i16]Albert Atserias, Sam Buss, Moritz Müller:
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. CoRR abs/2303.01016 (2023) - 2022
- [i15]Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j75]Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, António Morgado, João Marques-Silva:
Propositional proof systems based on maximum satisfiability. Artif. Intell. 300: 103552 (2021) - [j74]Sam Buss, Neil Thapen:
DRAT and Propagation Redundancy Proofs Without New Variables. Log. Methods Comput. Sci. 17(2) (2021) - [j73]Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. ACM Trans. Comput. Log. 22(4): 26:1-26:30 (2021) - [p1]Sam Buss, Jakob Nordström:
Proof Complexity and SAT Solving. Handbook of Satisfiability 2021: 233-350 - 2020
- [j72]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander construction in VNC1. Ann. Pure Appl. Log. 171(7): 102796 (2020) - [j71]James Aisenberg, Maria Luisa Bonet, Sam Buss:
2-D Tucker is PPA complete. J. Comput. Syst. Sci. 108: 92-103 (2020) - [c35]Sam Buss, Anupam Das, Alexander Knop:
Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs. CSL 2020: 12:1-12:17 - [i14]Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j70]Arnold Beckmann, Sam Buss:
On transformations of constant depth propositional proofs. Ann. Pure Appl. Log. 170(10): 1176-1187 (2019) - [j69]Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen:
Feasible set functions have small circuits. Comput. 8(1): 67-98 (2019) - [c34]Sam Buss, Neil Thapen:
DRAT Proofs, Propagation Redundancy, and Extended Resolution. SAT 2019: 71-89 - [c33]António Morgado, Alexey Ignatiev, Maria Luisa Bonet, João Marques-Silva, Sam Buss:
DRMaxSAT with MaxHS: First Contact. SAT 2019: 239-249 - [c32]Sam Buss, Alexander Knop:
Strategies for Stable Merge Sorting. SODA 2019: 1272-1290 - [i13]Sam Buss, Neil Thapen:
DRAT and Propagation Redundancy Proofs Without New Variables. CoRR abs/1909.00520 (2019) - [i12]Sam Buss, Anupam Das, Alexander Knop:
Proof complexity of systems of (non-deterministic) decision trees and branching programs. CoRR abs/1910.08503 (2019) - 2018
- [j68]James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate:
Short proofs of the Kneser-Lovász coloring principle. Inf. Comput. 261: 296-310 (2018) - [j67]Sam Buss, Ramyaa Ramyaa:
Short refutations for an equivalence-chain principle for constant-depth formulas. Math. Log. Q. 64(6): 505-513 (2018) - [c31]Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, João Marques-Silva, António Morgado:
MaxSAT Resolution With the Dual Rail Encoding. AAAI 2018: 6565-6572 - [c30]Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Reordering Rule Makes OBDD Proof Systems Stronger. CCC 2018: 16:1-16:24 - [i11]Sam Buss, Alexander Knop:
Strategies for Stable Merge Sorting. CoRR abs/1801.04641 (2018) - [i10]Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Reordering Rule Makes OBDD Proof Systems Stronger. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j66]Sam Buss:
Uniform proofs of ACC representations. Arch. Math. Log. 56(5-6): 639-669 (2017) - [j65]Arnold Beckmann, Sam Buss:
The NP Search Problems of Frege and Extended Frege Proofs. ACM Trans. Comput. Log. 18(2): 11:1-11:19 (2017) - [c29]Sam Buss, Douglas Cenzer, Mia Minnes, Jeffrey B. Remmel:
Injection Structures Specified by Finite State Transducers. Computability and Complexity 2017: 394-417 - [c28]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. ITCS 2017: 31:1-31:26 - 2016
- [j64]Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen:
Cobham recursive set functions. Ann. Pure Appl. Log. 167(3): 335-369 (2016) - [j63]Sam Buss, Jan Johannsen:
On Linear Resolution. J. Satisf. Boolean Model. Comput. 10(1): 23-35 (2016) - [j62]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): 687-710 (2016) - [i9]Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j61]Samuel R. Buss, Ryan Williams:
Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex. 24(3): 533-600 (2015) - [j60]Arnold Beckmann, Samuel R. Buss, Sy-David Friedman:
Safe Recursive Set Functions. J. Symb. Log. 80(3): 730-762 (2015) - [j59]Sam Buss:
Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination. Stud Logica 103(3): 663-667 (2015) - [j58]Sam Buss:
Quasipolynomial size proofs of the propositional pigeonhole principle. Theor. Comput. Sci. 576: 77-84 (2015) - [c27]Sam Buss:
Propositional Proofs in Frege and Extended Frege Systems (Abstract). CSR 2015: 1-6 - [c26]James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate:
Short Proofs of the Kneser-Lovász Coloring Principle. ICALP (2) 2015: 44-55 - [i8]James Aisenberg, Maria Luisa Bonet, Sam Buss, Adrian Craciun, Gabriel Istrate:
Short Proofs of the Kneser-Lovász Coloring Principle. CoRR abs/1505.05531 (2015) - [i7]James Aisenberg, Maria Luisa Bonet, Sam Buss:
2-D Tucker is PPA complete. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j57]Samuel R. Buss, Leszek Aleksander Kolodziejczyk:
Small Stone in Pool. Log. Methods Comput. Sci. 10(2) (2014) - [j56]Sam Buss, Douglas Cenzer, Jeffrey B. Remmel:
Sub-computable Boundedness Randomness. Log. Methods Comput. Sci. 10(4) (2014) - [j55]Maria Luisa Bonet, Sam Buss, Jan Johannsen:
Improved Separations of Regular Resolution from Clause Learning Proof Systems. J. Artif. Intell. Res. 49: 669-703 (2014) - [j54]Sam Buss, Michael Soltys:
Unshuffling a square is NP-hard. J. Comput. Syst. Sci. 80(4): 766-776 (2014) - [j53]Samuel R. Buss, Leszek Aleksander Kolodziejczyk, Neil Thapen:
Fragments of Approximate Counting. J. Symb. Log. 79(2): 496-525 (2014) - [j52]Arnold Beckmann, Samuel R. Buss:
Improved witnessing and local improvement principles for second-order bounded arithmetic. ACM Trans. Comput. Log. 15(1): 2:1-2:35 (2014) - 2013
- [b1]Samuel R. Buss:
3-D Computer Graphics. Cambridge University Press 2013, ISBN 978-0-521-82103-2, pp. I-XVI, 1-371 - [j51]Sam Buss, Benedikt Löwe, Dag Normann, Ivan N. Soskov:
Computability in Europe 2011. Ann. Pure Appl. Log. 164(5): 509-510 (2013) - [j50]Sam Buss, Mia Minnes:
Probabilistic algorithmic randomness. J. Symb. Log. 78(2): 579-601 (2013) - [c25]Maria Luisa Bonet, Sam Buss:
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning (Extended Abstract). IJCAI 2013: 2972-2976 - [c24]Sam Buss:
Alternation Trading Proofs and Their Limitations. MFCS 2013: 1-7 - 2012
- [j49]Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe:
Computability in Europe 2009. Ann. Pure Appl. Log. 163(5): 483-484 (2012) - [j48]Samuel R. Buss, Roman Kuznets:
Lower complexity bounds in justification logic. Ann. Pure Appl. Log. 163(7): 888-905 (2012) - [j47]Samuel R. Buss:
Towards NP-P via proof complexity and search. Ann. Pure Appl. Log. 163(7): 906-917 (2012) - [j46]Samuel R. Buss, Alan S. Johnson:
Propositional proofs and reductions between NP search problems. Ann. Pure Appl. Log. 163(9): 1163-1182 (2012) - [j45]Samuel R. Buss:
Sharpened lower bounds for cut elimination. J. Symb. Log. 77(2): 656-668 (2012) - [c23]Samuel R. Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. CCC 2012: 181-191 - [c22]Maria Luisa Bonet, Samuel R. Buss:
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning. SAT 2012: 44-57 - [i6]Maria Luisa Bonet, Samuel R. Buss:
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning. CoRR abs/1202.2296 (2012) - [i5]Maria Luisa Bonet, Sam Buss, Jan Johannsen:
Improved Separations of Regular Resolution from Clause Learning Proof Systems. CoRR abs/1208.2469 (2012) - [i4]Sam Buss, Michael Soltys:
Unshuffling a Square is NP-Hard. CoRR abs/1211.7161 (2012) - 2011
- [j44]Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman, Moritz Müller:
Strong isomorphism reductions in complexity theory. J. Symb. Log. 76(4): 1381-1402 (2011) - [j43]Arnold Beckmann, Samuel R. Buss:
Corrected upper bounds for free-cut elimination. Theor. Comput. Sci. 412(39): 5433-5445 (2011) - [i3]Sam Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j42]Samuel R. Buss, Alan S. Johnson:
The quantifier complexity of polynomial-size iterated definitions in first-order logic. Math. Log. Q. 56(6): 573-590 (2010)
2000 – 2009
- 2009
- [j41]Samuel R. Buss:
Pool resolution is NP-hard to recognize. Arch. Math. Log. 48(8): 793-798 (2009) - [j40]Samuel R. Buss, S. Barry Cooper, Benedikt Löwe, Andrea Sorbi:
Preface. Ann. Pure Appl. Log. 160(3): 229-230 (2009) - [j39]Arnold Beckmann, Samuel R. Buss:
Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic. J. Math. Log. 9(1) (2009) - [c21]Samuel R. Buss, Roman Kuznets:
The NP-Completeness of Reflected Fragments of Justification Logics. LFCS 2009: 122-136 - [c20]Daniel J. Tracy, Samuel R. Buss, Bryan M. Woods:
Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal. VR 2009: 191-198 - 2008
- [j38]Samuel R. Buss, Jan Hoffmann, Jan Johannsen:
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning. Log. Methods Comput. Sci. 4(4) (2008) - [j37]Samuel R. Buss, Jan Hoffmann:
The NP-hardness of finding a directed acyclic graph for regular resolution. Theor. Comput. Sci. 396(1-3): 271-276 (2008) - [i2]Samuel R. Buss, Jan Hoffmann, Jan Johannsen:
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning. CoRR abs/0811.1075 (2008) - 2006
- [j36]Samuel R. Buss:
Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies. Theor. Comput. Sci. 357(1-3): 35-52 (2006) - 2005
- [j35]Arnold Beckmann, Samuel R. Buss:
Separation results for the size of constant-depth propositional proofs. Ann. Pure Appl. Log. 136(1-2): 30-55 (2005) - [j34]Samuel R. Buss, Jin-Su Kim:
Selectively Damped Least Squares for Inverse Kinematics. J. Graph. Tools 10(3): 37-49 (2005) - [j33]Samuel R. Buss:
Collision detection with relative screw motion. Vis. Comput. 21(1-2): 41-58 (2005) - 2004
- [j32]Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution. SIAM J. Comput. 33(5): 1171-1200 (2004) - 2003
- [j31]Arnold Beckmann, Chris Pollett, Samuel R. Buss:
Ordinal notations and well-orderings in bounded arithmetic. Ann. Pure Appl. Log. 120(1-3): 197-223 (2003) - [j30]Arnold Beckmann, Samuel R. Buss, Chris Pollett:
Erratum to "Ordinal notations and well-orderings in bounded arithmetic" [Annals of Pure and Applied Logic 120 (2003) 197-223]. Ann. Pure Appl. Log. 123(1-3): 291- (2003) - 2002
- [j29]Samuel R. Buss, Bruce M. Kapron:
Resource-bounded continuity and sequentiality for type-two functionals. ACM Trans. Comput. Log. 3(3): 402-417 (2002) - [c19]Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604- - [i1]Samuel R. Buss, Alexander S. Kechris, Anand Pillay, Richard A. Shore:
The prospects for mathematical logic in the twenty-first century. CoRR cs.LO/0205003 (2002) - 2001
- [j28]Samuel R. Buss, Pavel Pudlák:
On the computational content of intuitionistic propositional proofs. Ann. Pure Appl. Log. 109(1-2): 49-63 (2001) - [j27]Samuel R. Buss, Alexander S. Kechris, Anand Pillay, Richard A. Shore:
The prospects for mathematical logic in the twenty-first century. Bull. Symb. Log. 7(2): 169-196 (2001) - [j26]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes. J. Comput. Syst. Sci. 62(2): 267-289 (2001) - [j25]Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. 66(1): 171-191 (2001) - [j24]Samuel R. Buss, Jay P. Fillmore:
Spherical averages and applications to spherical splines and interpolation. ACM Trans. Graph. 20(2): 95-126 (2001) - 2000
- [c18]Samuel R. Buss, Bruce M. Kapron:
Resource-Bounded Continuity and Sequentiality for Type-Two Functionals. LICS 2000: 77-83 - [c17]Samuel R. Buss, Grigore Rosu:
Incompleteness of Behavioral Logics. CMCS 2000: 61-79
1990 – 1999
- 1999
- [j23]Samuel R. Buss:
Bounded Arithmetic, Proof Complexity and Two Papers of Parikh. Ann. Pure Appl. Log. 96(1-3): 43-55 (1999) - [j22]Samuel R. Buss, Grigori Mints:
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic. Ann. Pure Appl. Log. 99(1-3): 93-104 (1999) - [c16]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). CCC 1999: 5 - [c15]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556 - 1998
- [j21]Samuel R. Buss, Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. J. Comput. Syst. Sci. 57(2): 162-171 (1998) - [j20]Samuel R. Buss, Peter N. Yianilos:
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. SIAM J. Comput. 27(1): 170-201 (1998) - [c14]Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184 - [e1]Paul Beame, Samuel R. Buss:
Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 39, DIMACS/AMS 1998, ISBN 978-0-8218-0577-0 [contents] - 1997
- [j19]Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall:
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6(3): 256-298 (1997) - [c13]Samuel R. Buss, Toniann Pitassi:
Resolution and the Weak Pigeonhole Principle. CSL 1997: 149-156 - [c12]Samuel R. Buss:
Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization. Kurt Gödel Colloquium 1997: 18-33 - 1996
- [j18]Samuel R. Buss, Peter Clote:
Cutting planes, connectivity, and threshold logic. Arch. Math. Log. 35(1): 33-62 (1996) - [c11]Samuel R. Buss, Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. CCC 1996: 233-242 - [c10]Samuel R. Buss:
Lower bounds on Nullstellensatz proofs via designs. Proof Complexity and Feasible Arithmetics 1996: 59-71 - 1995
- [j17]Samuel R. Buss:
Some remarks on lengths of propositional proofs. Arch. Math. Log. 34(6): 377-394 (1995) - [j16]Samuel R. Buss, Aleksandar Ignjatovic:
Unprovability of Consistency Statements in Fragments of Bounded Arithmetic. Ann. Pure Appl. Log. 74(3): 221-244 (1995) - [j15]Samuel R. Buss:
Relating the Bounded Arithmetic and Polynomial Time Hierarchies. Ann. Pure Appl. Log. 75(1-2): 67-77 (1995) - [j14]Maria Luisa Bonet, Samuel R. Buss:
The Serial Transitive Closure Problem for Trees. SIAM J. Comput. 24(1): 109-122 (1995) - 1994
- [j13]Maria Luisa Bonet, Samuel R. Buss:
Size-Depth Tradeoffs for Boolean Fomulae. Inf. Process. Lett. 49(3): 151-155 (1994) - [j12]Samuel R. Buss:
On Gödel's Theorems on Lenghts of Proofs I: Number of Lines and Speedup for Arithmetics. J. Symb. Log. 59(3): 737-756 (1994) - [c9]Pavel Pudlák, Samuel R. Buss:
How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus. CSL 1994: 151-162 - [c8]Samuel R. Buss:
On Herbrand's Theorem. LCC 1994: 195-209 - [c7]Samuel R. Buss, Peter N. Yianilos:
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. SODA 1994: 65-76 - 1993
- [j11]