Samuel R. Buss

Sam Buss, Benedikt Löwe, Dag Normann, Ivan N. Soskov: Computability in Europe 2011. Ann. Pure Appl. Logic 164(5): 509-510 (2013)

Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe: Computability in Europe 2009. Ann. Pure Appl. Logic 163(5): 483-484 (2012)

Samuel R. Buss, Roman Kuznets: Lower complexity bounds in justification logic. Ann. Pure Appl. Logic 163(7): 888-905 (2012)

Samuel R. Buss: Towards NP-P via proof complexity and search. Ann. Pure Appl. Logic 163(7): 906-917 (2012)

Samuel R. Buss, Alan S. Johnson: Propositional proofs and reductions between NP search problems. Ann. Pure Appl. Logic 163(9): 1163-1182 (2012)

Samuel R. Buss: Sharpened lower bounds for cut elimination. J. Symb. Log. 77(2): 656-668 (2012)

Samuel R. Buss, Ryan Williams: Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. IEEE Conference on Computational Complexity 2012: 181-191

Maria Luisa Bonet, Samuel R. Buss: An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning. SAT 2012: 44-57

Maria Luisa Bonet, Samuel R. Buss: An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning. CoRR abs/1202.2296 (2012)

Maria Luisa Bonet, Sam Buss, Jan Johannsen: Improved Separations of Regular Resolution from Clause Learning Proof Systems. CoRR abs/1208.2469 (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): 1381-1402 (2011)

Arnold Beckmann, Samuel R. Buss: Corrected upper bounds for free-cut elimination. Theor. Comput. Sci. 412(39): 5433-5445 (2011)

Sam Buss, Ryan Williams: Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Electronic Colloquium on Computational Complexity (ECCC) 18: 31 (2011)

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)

Samuel R. Buss: Pool resolution is NP-hard to recognize. Arch. Math. Log. 48(8): 793-798 (2009)

Samuel R. Buss, S. Barry Cooper, Benedikt Löwe, Andrea Sorbi: Preface. Ann. Pure Appl. Logic 160(3): 229-230 (2009)

Samuel R. Buss, Roman Kuznets: The NP-Completeness of Reflected Fragments of Justification Logics. LFCS 2009: 122-136

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

Samuel R. Buss, Jan Hoffmann, Jan Johannsen: Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning. Logical Methods in Computer Science 4(4) (2008)

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)

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)

Samuel R. Buss: Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies. Theor. Comput. Sci. 357(1-3): 35-52 (2006)

Arnold Beckmann, Samuel R. Buss: Separation results for the size of constant-depth propositional proofs. Ann. Pure Appl. Logic 136(1-2): 30-55 (2005)

Samuel R. Buss, Jin-Su Kim: Selectively Damped Least Squares for Inverse Kinematics. J. Graphics Tools 10(3): 37-49 (2005)

Samuel R. Buss: Collision detection with relative screw motion. The Visual Computer 21(1-2): 41-58 (2005)

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)

Arnold Beckmann, Chris Pollett, Samuel R. Buss: Ordinal notations and well-orderings in bounded arithmetic. Ann. Pure Appl. Logic 120(1-3): 197-223 (2003)

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. Logic 123(1-3): 291- (2003)

Samuel R. Buss, Bruce M. Kapron: Resource-bounded continuity and sequentiality for type-two functionals. ACM Trans. Comput. Log. 3(3): 402-417 (2002)

Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS 2002: 604-

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)

Samuel R. Buss, Pavel Pudlák: On the computational content of intuitionistic propositional proofs. Ann. Pure Appl. Logic 109(1-2): 49-63 (2001)

Samuel R. Buss, Alexander S. Kechris, Anand Pillay, Richard A. Shore: The prospects for mathematical logic in the twenty-first century. Bulletin of Symbolic Logic 7(2): 169-196 (2001)

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)

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)

Samuel R. Buss, Jay P. Fillmore: Spherical averages and applications to spherical splines and interpolation. ACM Trans. Graph. 20(2): 95-126 (2001)

Samuel R. Buss, Grigore Rosu: Incompleteness of Behavioral Logics. Electr. Notes Theor. Comput. Sci. 33: 61-79 (2000)

Samuel R. Buss, Bruce M. Kapron: Resource-Bounded Continuity and Sequentiality for Type-Two Functionals. LICS 2000: 77-83

Samuel R. Buss: Bounded Arithmetic, Proof Complexity and Two Papers of Parikh. Ann. Pure Appl. Logic 96(1-3): 43-55 (1999)

Samuel R. Buss, Grigori Mints: The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic. Ann. Pure Appl. Logic 99(1-3): 93-104 (1999)

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). IEEE Conference on Computational Complexity 1999: 5

Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC 1999: 547-556

Samuel R. Buss, Toniann Pitassi: Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. J. Comput. Syst. Sci. 57(2): 162-171 (1998)

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)

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi: Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184

Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3): 256-298 (1997)

Samuel R. Buss, Toniann Pitassi: Resolution and the Weak Pigeonhole Principle. CSL 1997: 149-156

Samuel R. Buss: Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization. Kurt Gödel Colloquium 1997: 18-33

Samuel R. Buss, Peter Clote: Cutting planes, connectivity, and threshold logic. Arch. Math. Log. 35(1): 33-62 (1996)

Samuel R. Buss, Toniann Pitassi: Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. IEEE Conference on Computational Complexity 1996: 233-242

Samuel R. Buss: Some remarks on lengths of propositional proofs. Arch. Math. Log. 34(6): 377-394 (1995)

Samuel R. Buss, Aleksandar Ignjatovic: Unprovability of Consistency Statements in Fragments of Bounded Arithmetic. Ann. Pure Appl. Logic 74(3): 221-244 (1995)

Samuel R. Buss: Relating the Bounded Arithmetic and Polynomial Time Hierarchies. Ann. Pure Appl. Logic 75(1-2): 67-77 (1995)

Maria Luisa Bonet, Samuel R. Buss: The Serial Transitive Closure Problem for Trees. SIAM J. Comput. 24(1): 109-122 (1995)

Maria Luisa Bonet, Samuel R. Buss: Size-Depth Tradeoffs for Boolean Fomulae. Inf. Process. Lett. 49(3): 151-155 (1994)

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)

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

Samuel R. Buss: On Herbrand's Theorem. LCC 1994: 195-209

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

Samuel R. Buss: Intuitionistic Validity in T-Normal Kripke Structures. Ann. Pure Appl. Logic 59(3): 159-173 (1993)

Maria Luisa Bonet, Samuel R. Buss: The Deduction Rule and Linear and Near-Linear Proof Simulations. J. Symb. Log. 58(2): 688-709 (1993)

Samuel R. Buss: The Graph of Multiplication is Equivalent to Counting. Inf. Process. Lett. 41(4): 199-201 (1992)

Samuel R. Buss, S. Cook, A. Gupta, V. Ramachandran: An Optimal Parallel Algorithm for Formula Evaluation. SIAM J. Comput. 21(4): 755-780 (1992)

Samuel R. Buss: Propositional Consistency Proofs. Ann. Pure Appl. Logic 52(1-2): 3-29 (1991)

Samuel R. Buss: The Undecidability of k-Provability. Ann. Pure Appl. Logic 53(1): 75-102 (1991)

Samuel R. Buss, Louise Hay: On Truth-Table Reducibility to SAT. Inf. Comput. 91(1): 86-102 (1991)

Maria Luisa Bonet, Samuel R. Buss: On the Deduction Rule and the Number of Proof Lines. LICS 1991: 286-297

Samuel R. Buss: The Modal Logic of Pure Provability. Notre Dame Journal of Formal Logic 31(2): 225-231 (1990)

Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis: On the Predictability of Coupled Automata: An Allegory about Chaos. FOCS 1990: 788-793

Samuel R. Buss, György Turán: Resolution Proofs of Generalized Pigeonhole Principles. Theor. Comput. Sci. 62(3): 311-317 (1988)

Samuel R. Buss, Louise Hay: On truth-table reducibility to SAT and the difference hierarchy over NP. Structure in Complexity Theory Conference 1988: 224-233

Samuel R. Buss: Polynomial Size Proofs of the Propositional Pigeonhole Principle. J. Symb. Log. 52(4): 916-927 (1987)

Samuel R. Buss: The Boolean Formula Value Problem Is in ALOGTIME. STOC 1987: 123-131

Samuel R. Buss: The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic. Structure in Complexity Theory Conference 1986: 77-103

Samuel R. Buss: The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract). STOC 1985: 285-290