Samuel R Buss
University of California San Diego
Faculty Member, Mathematics
United States
My co-authors include
Arnold Beckmann
My Publications
Feasible set functions have small circuits
Computability
December 2018
SAFE RECURSIVE SET FUNCTIONS
Journal of Symbolic Logic
July 2015
Limits on Alternation Trading Proofs for Time–Space Lower Bounds
Computational Complexity
May 2015
Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination
Studia Logica
May 2015
Quasipolynomial size proofs of the propositional pigeonhole principle
Theoretical Computer Science
April 2015
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
Transactions of the American Mathematical Society
February 2015
Propositional Proofs in Frege and Extended Frege Systems (Abstract)
January 2015
Short Proofs of the Kneser-Lovász Coloring Principle
January 2015
Sub-computable Boundedness Randomness
Logical Methods in Computer Science
December 2014
Small Stone in Pool
Logical Methods in Computer Science
June 2014
FRAGMENTS OF APPROXIMATE COUNTING
Journal of Symbolic Logic
June 2014
Unshuffling a square is NP-hard
Journal of Computer and System Sciences
June 2014
Improved witnessing and local improvement principles for second-order bounded arithmetic
ACM Transactions on Computational Logic
March 2014
Probabilistic Algorithmic Randomness
Journal of Symbolic Logic
June 2013
Alternation Trading Proofs and Their Limitations
January 2013
Towards <mml:math altimg="si1.gif" display="inline" overflow="scroll" xmlns:xocs="http:...
Annals of Pure and Applied Logic
July 2012
Lower complexity bounds in justification logic
Annals of Pure and Applied Logic
July 2012
Sharpened lower bounds for cut elimination
Journal of Symbolic Logic
June 2012
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
June 2012
An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning
January 2012
Strong isomorphism reductions in complexity theory
Journal of Symbolic Logic
December 2011
Corrected upper bounds for free-cut elimination
Theoretical Computer Science
September 2011
The quantifier complexity of polynomial-size iterated definitions in first-order logic
November 2010
Pool resolution is NP-hard to recognize
Archive for Mathematical Logic
September 2009
POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUN...
Journal of Mathematical Logic
June 2009
Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms w...
Logical Methods in Computer Science
December 2008
The NP-hardness of finding a directed acyclic graph for regular resolution
Theoretical Computer Science
May 2008
Bounded Arithmetic, Cryptography and Complexity
Theoria
February 2008
The Computational Power of Bounded Arithmetic from the Predicative Viewpoint
January 2008
The NP-Completeness of Reflected Fragments of Justification Logics
January 2008
Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies
Theoretical Computer Science
July 2006
Separation results for the size of constant-depth propositional proofs
Annals of Pure and Applied Logic
October 2005
Collision detection with relative screw motion
The Visual Computer
February 2005
Selectively Damped Least Squares for Inverse Kinematics
Journal of Graphics Tools
January 2005
Solving the Fisher-Wright and coalescence problems with a discrete Markov chain analysis
Advances in Applied Probability
December 2004
A Switching Lemma for Small Restrictions and Lower Bounds for k -DNF Resolution
SIAM Journal on Computing
January 2004
Erratum to “Ordinal notations and well-orderings in bounded arithmetic” [Annals of Pure...
Annals of Pure and Applied Logic
October 2003
Ordinal notations and well-orderings in bounded arithmetic
Annals of Pure and Applied Logic
April 2003
3-D Computer Graphics
January 2003
Resource-bounded continuity and sequentiality for type-two functionals
ACM Transactions on Computational Logic
July 2002
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate
Bulletin of Symbolic Logic
June 2002
Michael Alekhnovich, Sam Buss, Shlomo Moran, and Toniann Pitassi. Minimum propositional...
Bulletin of Symbolic Logic
June 2002
The Prospects for Mathematical Logic in the Twenty-First Century
Bulletin of Symbolic Logic
June 2001
On the computational content of intuitionistic propositional proofs
Annals of Pure and Applied Logic
May 2001
Spherical averages and applications to spherical splines and interpolation
ACM Transactions on Graphics
April 2001
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes
Journal of Computer and System Sciences
March 2001
Minimum propositional proof length is NP-hard to linearly approximate
Journal of Symbolic Logic
March 2001
Samuel R. Buss. An introduction to proof theory. Handbook of proof theory, edited by Sa...
Bulletin of Symbolic Logic
December 2000
Samuel R. Buss. First-order proof theory of arithmetic. Handbook of proof theory, edite...
Bulletin of Symbolic Logic
December 2000
Accurate and Efficient Simulation of Rigid-Body Rotations
Journal of Computational Physics
November 2000
Incompleteness of Behavioral Logics
Electronic Notes in Theoretical Computer Science
January 2000
The complexity of the disjunction and existential properties in intuitionistic logic
Annals of Pure and Applied Logic
August 1999
Bounded arithmetic, proof complexity and two papers of Parikh
Annals of Pure and Applied Logic
March 1999
Propositional Proof Complexity an Introduction
January 1999
Linear gaps between degrees for the polynomial calculus modulo distinct primes
January 1999
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle
Journal of Computer and System Sciences
October 1998
Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
SIAM Journal on Computing
February 1998
An Introduction to Proof Theory
January 1998
First-Order Proof Theory of Arithmetic
January 1998
Resolution and the weak pigeonhole principle
January 1998
Minimum propositional proof length is NP-hard to linearly approximate
January 1998
Samuel R. Buss. The undecidability of k-provability. Annals of pure and applied logic, ...
Journal of Symbolic Logic
December 1997
Bounded Arithmetic and Propositional Proof Complexity
January 1997
Alogtime algorithms for tree isomorphism, comparison, and canonization
January 1997
Cutting planes, connectivity, and threshold logic
Archive for Mathematical Logic
January 1996
Cutting planes, connectivity, and threshold logic
Archive for Mathematical Logic
January 1996
Some remarks on lengths of propositional proofs
Archive for Mathematical Logic
December 1995
Relating the bounded arithmetic and polynomial time hierarchies
Annals of Pure and Applied Logic
September 1995
Unprovability of consistency statements in fragments of bounded arithmetic
Annals of Pure and Applied Logic
August 1995
The Serial Transitive Closure Problem for Trees
SIAM Journal on Computing
February 1995
On Herbrand's theorem
January 1995
Are there Hard Examples for Frege Systems?
January 1995
On Gödel’s Theorems on Lengths of Proofs II: Lower Bounds for Recognizing k Symbol Prov...
January 1995
How to lie without being (easily) convicted and the lengths of proofs in propositional ...
January 1995
The witness function method and provably recursive functions of peano arithmetic
January 1995
On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
Journal of Symbolic Logic
September 1994
Size-depth tradeoffs for Boolean formulae
Information Processing Letters
February 1994
The deduction rule and linear and near-linear proof simulations
Journal of Symbolic Logic
June 1993
Intuitionistic validity in T-normal Kripke structures
Annals of Pure and Applied Logic
February 1993
The graph of multiplication is equivalent to counting
Information Processing Letters
March 1992
The undecidability of k-provability
Annals of Pure and Applied Logic
July 1991
Samuel R. Buss. Bounded arithmetic. Studies in proof theory. Lecture notes, no. 3. Bibl...
Journal of Symbolic Logic
June 1991
Propositional consistency proofs
Annals of Pure and Applied Logic
April 1991
On truth-table reducibility to SAT
Information and Computation
March 1991
The modal logic of pure provability.
Notre Dame Journal of Formal Logic
March 1990
Feasible Mathematics
January 1990
Axiomatizations and conservation results for fragments of bounded arithmetic
January 1990
On Model Theory for Intuitionistic Bounded Arithmetic with Applications to Independence...
January 1990
Resolution proofs of generalized pigeonhole principles
Theoretical Computer Science
December 1988
Polynomial size proofs of the propositional pigeonhole principle
Journal of Symbolic Logic
December 1987
A Conservation Result Concerning Bounded Theories and the Collection Axiom
Proceedings of the American Mathematical Society
August 1987
A conservation result concerning bounded theories and the collection axiom
Proceedings of the American Mathematical Society
April 1987
The polynomial hierarchy and intuitionistic Bounded Arithmetic
January 1986
Characterising Definable Search Problems in Bounded Arithmetic via Proof Notations
Chapter Eight. Nelson's Work on Logic and Foundations and Other Reflections on the Foun...
A note on bootstrapping intuitionistic bounded arithmetic