Samuel R. Buss

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