Samuel R. Buss

According to our database1, Samuel R. Buss authored at least 102 papers between 1985 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2020
2-D Tucker is PPA complete.
J. Comput. Syst. Sci., 2020

Lower Bounds on OBDD Proofs with Several Orders.
Electron. Colloquium Comput. Complex., 2020

Proof Complexity of Systems of (Non-Deterministic) Decision Trees and Branching Programs.
Proceedings of the 28th EACSL Annual Conference on Computer Science Logic, 2020

2019
DRAT and Propagation Redundancy Proofs Without New Variables.
CoRR, 2019

Feasible set functions have small circuits.
Comput., 2019

On transformations of constant depth propositional proofs.
Ann. Pure Appl. Log., 2019

Strategies for Stable Merge Sorting.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

DRMaxSAT with MaxHS: First Contact.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

DRAT Proofs, Propagation Redundancy, and Extended Resolution.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

2018
Short refutations for an equivalence-chain principle for constant-depth formulas.
Math. Log. Q., 2018

Short proofs of the Kneser-Lovász coloring principle.
Inf. Comput., 2018

Reordering Rule Makes OBDD Proof Systems Stronger.
Electron. Colloquium Comput. Complex., 2018

MaxSAT Resolution With the Dual Rail Encoding.
Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017
The NP Search Problems of Frege and Extended Frege Proofs.
ACM Trans. Comput. Log., 2017

Uniform proofs of ACC representations.
Arch. Math. Log., 2017

Expander Construction in VNC1.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Injection Structures Specified by Finite State Transducers.
Proceedings of the Computability and Complexity, 2017

2016
Quasipolynomial Size Frege Proofs of Frankl's Theorem on the Trace of Sets.
J. Symb. Log., 2016

On Linear Resolution.
J. Satisf. Boolean Model. Comput., 2016

Expander Construction in VNC<sup>1</sup>.
Electron. Colloquium Comput. Complex., 2016

Cobham recursive set functions.
Ann. Pure Appl. Log., 2016

2015
Quasipolynomial size proofs of the propositional pigeonhole principle.
Theor. Comput. Sci., 2015

Book Review: Matthias Baaz and Alexander Leitsch, Methods of Cut-Elimination.
Stud Logica, 2015

Safe Recursive Set Functions.
J. Symb. Log., 2015

Limits on Alternation Trading Proofs for Time-Space Lower Bounds.
Comput. Complex., 2015

Propositional Proofs in Frege and Extended Frege Systems (Abstract).
Proceedings of the Computer Science - Theory and Applications, 2015

2014
Improved witnessing and local improvement principles for second-order bounded arithmetic.
ACM Trans. Comput. Log., 2014

Fragments of Approximate Counting.
J. Symb. Log., 2014

Unshuffling a square is NP-hard.
J. Comput. Syst. Sci., 2014

Improved Separations of Regular Resolution from Clause Learning Proof Systems.
J. Artif. Intell. Res., 2014

Small Stone in Pool.
Log. Methods Comput. Sci., 2014

Sub-computable Boundedness Randomness.
Log. Methods Comput. Sci., 2014

2013
Probabilistic algorithmic randomness.
J. Symb. Log., 2013

Computability in Europe 2011.
Ann. Pure Appl. Log., 2013

Alternation Trading Proofs and Their Limitations.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning (Extended Abstract).
Proceedings of the IJCAI 2013, 2013

3-D Computer Graphics.
Cambridge University Press, ISBN: 978-0-521-82103-2, 2013

2012
Sharpened lower bounds for cut elimination.
J. Symb. Log., 2012

Lower complexity bounds in justification logic.
Ann. Pure Appl. Log., 2012

Propositional proofs and reductions between NP search problems.
Ann. Pure Appl. Log., 2012

Towards NP-P via proof complexity and search.
Ann. Pure Appl. Log., 2012

Computability in Europe 2009.
Ann. Pure Appl. Log., 2012

An Improved Separation of Regular Resolution from Pool Resolution and Clause Learning.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

2011
Corrected upper bounds for free-cut elimination.
Theor. Comput. Sci., 2011

Strong isomorphism reductions in complexity theory.
J. Symb. Log., 2011

2010
The quantifier complexity of polynomial-size iterated definitions in first-order logic.
Math. Log. Q., 2010

2009
Polynomial Local Search in the Polynomial Hierarchy and Witnessing in Fragments of Bounded Arithmetic.
J. Math. Log., 2009

Preface.
Ann. Pure Appl. Log., 2009

Pool resolution is NP-hard to recognize.
Arch. Math. Log., 2009

Efficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal.
Proceedings of the IEEE Virtual Reality Conference 2009 (VR 2009), 2009

The NP-Completeness of Reflected Fragments of Justification Logics.
Proceedings of the Logical Foundations of Computer Science, International Symposium, 2009

2008
The NP-hardness of finding a directed acyclic graph for regular resolution.
Theor. Comput. Sci., 2008

Resolution Trees with Lemmas: Resolution Refinements that Characterize DLL Algorithms with Clause Learning.
Log. Methods Comput. Sci., 2008

2006
Polynomial-size Frege and resolution proofs of <i>st</i>-connectivity and Hex tautologies.
Theor. Comput. Sci., 2006

2005
Collision detection with relative screw motion.
Vis. Comput., 2005

Selectively Damped Least Squares for Inverse Kinematics.
J. Graph. Tools, 2005

Separation results for the size of constant-depth propositional proofs.
Ann. Pure Appl. Log., 2005

2004
A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution.
SIAM J. Comput., 2004

2003
Ordinal notations and well-orderings in bounded arithmetic.
Ann. Pure Appl. Log., 2003

Erratum to "Ordinal notations and well-orderings in bounded arithmetic" [Annals of Pure and Applied Logic 120 (2003) 197-223].
Ann. Pure Appl. Log., 2003

2002
Resource-bounded continuity and sequentiality for type-two functionals.
ACM Trans. Comput. Log., 2002

2001
Spherical averages and applications to spherical splines and interpolation.
ACM Trans. Graph., 2001

Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.
J. Comput. Syst. Sci., 2001

The prospects for mathematical logic in the twenty-first century.
Bull. Symb. Log., 2001

On the computational content of intuitionistic propositional proofs.
Ann. Pure Appl. Log., 2001

2000
Incompleteness of Behavioral Logics.
Proceedings of the Coalgebraic Methods in Computer Science, 2000

1999
The Complexity of the Disjunction and Existential Properties in Intuitionistic Logic.
Ann. Pure Appl. Log., 1999

Bounded Arithmetic, Proof Complexity and Two Papers of Parikh.
Ann. Pure Appl. Log., 1999

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
Linear and <i>O</i>(<i>n</i> log <i>n</i>) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
SIAM J. Comput., 1998

Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
J. Comput. Syst. Sci., 1998

1997
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Comput. Complex., 1997

Alogtime Algorithms for Tree Isomorphism, Comparison, and Canonization.
Proceedings of the Computational Logic and Proof Theory, 5th Kurt Gödel Colloquium, 1997

Resolution and the Weak Pigeonhole Principle.
Proceedings of the Computer Science Logic, 11th International Workshop, 1997

1996
Cutting planes, connectivity, and threshold logic.
Arch. Math. Log., 1996

Lower bounds on Nullstellensatz proofs via designs.
Proceedings of the Proof Complexity and Feasible Arithmetics, 1996

1995
The Serial Transitive Closure Problem for Trees.
SIAM J. Comput., 1995

Unprovability of Consistency Statements in Fragments of Bounded Arithmetic.
Ann. Pure Appl. Log., 1995

Relating the Bounded Arithmetic and Polynomial Time Hierarchies.
Ann. Pure Appl. Log., 1995

Some remarks on lengths of propositional proofs.
Arch. Math. Log., 1995

1994
On Gödel's Theorems on Lenghts of Proofs I: Number of Lines and Speedup for Arithmetics.
J. Symb. Log., 1994

Size-Depth Tradeoffs for Boolean Fomulae.
Inf. Process. Lett., 1994

Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

On Herbrand's Theorem.
Proceedings of the Logical and Computational Complexity. Selected Papers. Logic and Computational Complexity, 1994

How to Lie Without Being (Easily) Convicted and the Length of Proofs in Propositional Calculus.
Proceedings of the Computer Science Logic, 8th International Workshop, 1994

1993
The Deduction Rule and Linear and Near-Linear Proof Simulations.
J. Symb. Log., 1993

Intuitionistic Validity in T-Normal Kripke Structures.
Ann. Pure Appl. Log., 1993

1992
An Optimal Parallel Algorithm for Formula Evaluation.
SIAM J. Comput., 1992

The Graph of Multiplication is Equivalent to Counting.
Inf. Process. Lett., 1992

1991
On Truth-Table Reducibility to SAT
Inf. Comput., March, 1991

On the Predictability of Coupled Automata: An Allegory about Chaos.
Complex Syst., 1991

The Undecidability of k-Provability.
Ann. Pure Appl. Log., 1991

Propositional Consistency Proofs.
Ann. Pure Appl. Log., 1991

On the Deduction Rule and the Number of Proof Lines
Proceedings of the Sixth Annual Symposium on Logic in Computer Science (LICS '91), 1991

1990
The Modal Logic of Pure Provability.
Notre Dame J. Formal Log., 1990

1988
Resolution Proofs of Generalized Pigeonhole Principles.
Theor. Comput. Sci., 1988

On truth-table reducibility to SAT and the difference hierarchy over NP.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Polynomial Size Proofs of the Propositional Pigeonhole Principle.
J. Symb. Log., 1987

The Boolean Formula Value Problem Is in ALOGTIME
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
The Polynomial Hierarchy and Intuitionistic Bounded Arithmetic.
Proceedings of the Structure in Complexity Theory, 1986

1985
The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract)
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985


  Loading...