Samuel R. Buss

Publication Activity (10 Years)

Years Active: 1985-2015
Publications (10 Years): 2

Top Topics

Search Problems

Top Venues

Ann. Pure Appl. Log.

Publications

Samuel R. Buss, Ryan Williams
Limits on Alternation Trading Proofs for Time-Space Lower Bounds. Comput. Complex. 24 (3) (2015)
Arnold Beckmann, Samuel R. Buss, Sy-David Friedman
Safe Recursive Set Functions. J. Symb. Log. 80 (3) (2015)
Arnold Beckmann, Samuel R. Buss
Improved witnessing and local improvement principles for second-order bounded arithmetic. ACM Trans. Comput. Log. 15 (1) (2014)
Samuel R. Buss, Leszek Aleksander Kolodziejczyk, Neil Thapen
Fragments of Approximate Counting. J. Symb. Log. 79 (2) (2014)
Samuel R. Buss, Leszek Aleksander Kolodziejczyk
Small Stone in Pool. Log. Methods Comput. Sci. 10 (2) (2014)
Samuel R. Buss, Alan S. Johnson
Propositional proofs and reductions between NP search problems. Ann. Pure Appl. Log. 163 (9) (2012)
Samuel R. Buss
Towards NP-P via proof complexity and search. Ann. Pure Appl. Log. 163 (7) (2012)
Maria Luisa Bonet, Samuel R. Buss
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning CoRR (2012)
Maria Luisa Bonet, Samuel R. Buss
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning. SAT (2012)
Samuel R. Buss, Ryan Williams
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. Computational Complexity Conference (2012)
Klaus Ambos-Spies, Arnold Beckmann, Samuel R. Buss, Benedikt Löwe
Computability in Europe 2009. Ann. Pure Appl. Log. 163 (5) (2012)
Samuel R. Buss
Sharpened lower bounds for cut elimination. J. Symb. Log. 77 (2) (2012)
Samuel R. Buss, Roman Kuznets
Lower complexity bounds in justification logic. Ann. Pure Appl. Log. 163 (7) (2012)
Arnold Beckmann, Samuel R. Buss
Corrected upper bounds for free-cut elimination. Theor. Comput. Sci. 412 (39) (2011)
Samuel R. Buss, Alan S. Johnson
The quantifier complexity of polynomial-size iterated definitions in first-order logic. Math. Log. Q. 56 (6) (2010)
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)
Samuel R. Buss
Pool resolution is NP-hard to recognize. Arch. Math. Log. 48 (8) (2009)
Samuel R. Buss, Roman Kuznets
The NP-Completeness of Reflected Fragments of Justification Logics. LFCS (2009)
Samuel R. Buss, S. Barry Cooper, Benedikt Löwe, Andrea Sorbi
Preface. Ann. Pure Appl. Log. 160 (3) (2009)
Daniel J. Tracy, Samuel R. Buss, Bryan M. Woods
Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal. VR (2009)
Samuel R. Buss, Jan Hoffmann, Jan Johannsen
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning CoRR (2008)
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)
Samuel R. Buss, Jan Hoffmann
The NP-hardness of finding a directed acyclic graph for regular resolution. Theor. Comput. Sci. 396 (1-3) (2008)
Samuel R. Buss
-connectivity and Hex tautologies. Theor. Comput. Sci. 357 (1-3) (2006)
Samuel R. Buss, Jin-Su Kim
Selectively Damped Least Squares for Inverse Kinematics. J. Graph. Tools 10 (3) (2005)
Arnold Beckmann, Samuel R. Buss
Separation results for the size of constant-depth propositional proofs. Ann. Pure Appl. Log. 136 (1-2) (2005)
Samuel R. Buss
Collision detection with relative screw motion. Vis. Comput. 21 (1-2) (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) (2004)
Arnold Beckmann, Chris Pollett, Samuel R. Buss
Ordinal notations and well-orderings in bounded arithmetic. Ann. Pure Appl. Log. 120 (1-3) (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. Log. 123 (1-3) (2003)
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. FOCS (2002)
Samuel R. Buss, Alexander S. Kechris, Anand Pillay, Richard A. Shore
The prospects for mathematical logic in the twenty-first century CoRR (2002)
Samuel R. Buss, Bruce M. Kapron
Resource-bounded continuity and sequentiality for type-two functionals. ACM Trans. Comput. Log. 3 (3) (2002)
Samuel R. Buss, Pavel Pudlák
On the computational content of intuitionistic propositional proofs. Ann. Pure Appl. Log. 109 (1-2) (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) (2001)
Samuel R. Buss, Jay P. Fillmore
Spherical averages and applications to spherical splines and interpolation. ACM Trans. Graph. 20 (2) (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) (2001)
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) (2001)
Samuel R. Buss, Bruce M. Kapron
Resource-Bounded Continuity and Sequentiality for Type-Two Functionals. LICS (2000)
Samuel R. Buss, Grigore Rosu
Incompleteness of Behavioral Logics. CMCS (2000)
Samuel R. Buss
Bounded Arithmetic, Proof Complexity and Two Papers of Parikh. Ann. Pure Appl. Log. 96 (1-3) (1999)
Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). Computational Complexity Conference (1999)
Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. STOC (1999)
Samuel R. Buss, Grigori Mints
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic. Ann. Pure Appl. Log. 99 (1-3) (1999)
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS (1998)
Samuel R. Buss, Toniann Pitassi
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. J. Comput. Syst. Sci. 57 (2) (1998)
Samuel R. Buss, Peter N. Yianilos
) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. SIAM J. Comput. 27 (1) (1998)
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) (1997)
Samuel R. Buss
Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization. Kurt Gödel Colloquium (1997)
Samuel R. Buss, Toniann Pitassi
Resolution and the Weak Pigeonhole Principle. CSL (1997)
Samuel R. Buss
Lower bounds on Nullstellensatz proofs via designs. Proof Complexity and Feasible Arithmetics (1996)
Samuel R. Buss, Peter Clote
Cutting planes, connectivity, and threshold logic. Arch. Math. Log. 35 (1) (1996)
Samuel R. Buss, Toniann Pitassi
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. Computational Complexity Conference (1996)
Samuel R. Buss
Relating the Bounded Arithmetic and Polynomial Time Hierarchies. Ann. Pure Appl. Log. 75 (1-2) (1995)
Maria Luisa Bonet, Samuel R. Buss
The Serial Transitive Closure Problem for Trees. SIAM J. Comput. 24 (1) (1995)
Samuel R. Buss, Aleksandar Ignjatovic
Unprovability of Consistency Statements in Fragments of Bounded Arithmetic. Ann. Pure Appl. Log. 74 (3) (1995)
Samuel R. Buss
Some remarks on lengths of propositional proofs. Arch. Math. Log. 34 (6) (1995)
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) (1994)
Maria Luisa Bonet, Samuel R. Buss
Size-Depth Tradeoffs for Boolean Fomulae. Inf. Process. Lett. 49 (3) (1994)
Samuel R. Buss, Peter N. Yianilos
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours. SODA (1994)
Samuel R. Buss
On Herbrand's Theorem. LCC (1994)
Pavel Pudlák, Samuel R. Buss
How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus. CSL (1994)
Samuel R. Buss
Intuitionistic Validity in T-Normal Kripke Structures. Ann. Pure Appl. Log. 59 (3) (1993)
Maria Luisa Bonet, Samuel R. Buss
The Deduction Rule and Linear and Near-Linear Proof Simulations. J. Symb. Log. 58 (2) (1993)
Samuel R. Buss, Stephen A. Cook, A. Gupta, V. Ramachandran
An Optimal Parallel Algorithm for Formula Evaluation. SIAM J. Comput. 21 (4) (1992)
Samuel R. Buss
The Graph of Multiplication is Equivalent to Counting. Inf. Process. Lett. 41 (4) (1992)
Samuel R. Buss
Propositional Consistency Proofs. Ann. Pure Appl. Log. 52 (1-2) (1991)
Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis
On the Predictability of Coupled Automata: An Allegory about Chaos. Complex Syst. 5 (5) (1991)
Samuel R. Buss, Louise Hay
On Truth-Table Reducibility to SAT Inf. Comput. 91 (1) (1991)
Samuel R. Buss
The Undecidability of k-Provability. Ann. Pure Appl. Log. 53 (1) (1991)
Maria Luisa Bonet, Samuel R. Buss
On the Deduction Rule and the Number of Proof Lines LICS (1991)
Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis
On the Predictability of Coupled Automata: An Allegory about Chaos FOCS (1990)
Samuel R. Buss
The Modal Logic of Pure Provability. Notre Dame J. Formal Log. 31 (2) (1990)
Samuel R. Buss, György Turán
Resolution Proofs of Generalized Pigeonhole Principles. Theor. Comput. Sci. 62 (3) (1988)
Samuel R. Buss, Louise Hay
On truth-table reducibility to SAT and the difference hierarchy over NP. Computational Complexity Conference (1988)
Samuel R. Buss
The Boolean Formula Value Problem Is in ALOGTIME STOC (1987)
Samuel R. Buss
Polynomial Size Proofs of the Propositional Pigeonhole Principle. J. Symb. Log. 52 (4) (1987)
Samuel R. Buss
The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic. Computational Complexity Conference (1986)
Samuel R. Buss
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract) STOC (1985)