Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
Hilfe
Suche: Author="Buss, Sam"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
Quasipolynomial size proofs of the propositional pigeonhole principle
Sam Buss
Theoretical Computer Science
576
, 2015, pp. 77-84
Unshuffling a square is NP-hard
Sam Buss
,
Michael Soltys
Journal of Computer and System Sciences
80
(4), 2014, pp. 766-776
Alternation trading proofs and their limitations
Sam Buss
Lecture Notes in Computer Science
8087
, 2013, pp. 1-7
Corrected upper bounds for free-cut elimination
Arnold Beckmann
,
Samuel R. Buss
Theoretical Computer Science
412
(39), 2011, pp. 5433-5445
The
NP
-hardness of finding a directed acyclic graph for regular resolution
Samuel R. Buss
,
Jan Hoffmann
Theoretical Computer Science
396
(1-3), 2008, pp. 271-276
Polynomial-size Frege and resolution proofs of
st
-connectivity and Hex tautologies
Samuel R. Buss
Theoretical Computer Science
357
(1-3), 2006, pp. 35-52
A switching lemma for small restrictions and lower bounds for
k
-DNF resolution
Nathan Segerlind
,
Sam Buss
,
Russell Impagliazzo
SIAM Journal on Computing
33
(5), 2004, pp. 1171-1200
A switching lemma for small restrictions and lower bounds for
k
-DNF resolution
Nathan Segerlind
,
Sam Buss
,
Russell Impagliazzo
Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS'2002 (Vancouver, BC, Canada, November 16-19, 2002)
, 2002, pp. 604-613
Linear gaps between degrees for the polynomial calculus modulo distinct primes
Sam Buss
,
Dima Grigoriev
,
Russell Impagliazzo
,
Toniann Pitassi
Journal of Computer and System Sciences
62
(2), 2001, pp. 267-289
Linear gaps beetween degrees for the polynomial calculus modulo distinct primes
Sam Buss
,
Dima Grigoriev
,
Russell Impagliazzo
,
Toniann Pitassi
Proceedings of the 14th Annual IEEE Conference on Computational Complexity (Atlanta, Georgia, May 4-6, 1999)
, 1999, pp. 5-5
Linear gaps between degrees for the polynomial calculus modulo distinct primes
Sam Buss
,
Dima Grigoriev
,
Russell Impagliazzo
,
Toniann Pitassi
Proceedings of the 31st Annual ACM Symposium on Theory of Computing, STOC'99 (Atlanta, Georgia, May 1-4, 1999)
, 1999, pp. 547-556
Minimum propositional proof length is
NP
-hard to linearly approximate
Michael Alekhnovich
,
Sam Buss
,
Shlomo Moran
,
Toniann Pitassi
Lecture Notes in Computer Science
1450
, 1998, pp. 176-184
Good degree bounds on Nullstellensatz refutations of the induction principle
Samuel R. Buss
,
Toniann Pitassi
Journal of Computer and System Sciences
57
(2), 1998, pp. 162-171
Linear and
O(n \log n)
time minimum-cost matching algorithms for quasi-convex tours
Samuel R. Buss
,
Peter N. Yianilos
SIAM Journal on Computing
27
(1), 1998, pp. 170-201
Complexity of proofs
Samuel R. Buss
Technical Report, 1997
Good degree bounds on Nullstellensatz refutations of the induction principle
Samuel R. Buss
,
Toniann Pitassi
Proceedings of the 11th Annual IEEE Conference on Computational Complexity (Philadelphia, Pennsylvania, May 24-27, 1996)
, 1996, pp. 233-242
The serial transitive closure problem for trees
Maria Luisa Bonet
,
Samuel R. Buss
SIAM Journal on Computing
24
(1), 1995, February, pp. 109-122
Bounded arithmetic and propositional proofs
Samuel R. Buss
misc, 1995
On Herbrand's theorem
Samuel R. Buss
Lecture Notes in Computer Science
960
, 1995, pp. 195-209
Size-depth tradeoffs for Boolean formulae
Maria Luisa Bonet
,
Samuel R. Buss
Information Processing Letters
49
, 1994, pp. 151-155
Linear and
O(n \log n)
time minimum-cost matching algorithms for quasi-convex tours
Samuel R. Buss
,
Peter N. Yianilos
Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'94 (Arlington, Virginia, January 23-25, 1994)
, 1994, pp. 65-76
The graph of multiplication is equivalent to counting
Samuel R. Buss
Information Processing Letters
41
, 1992, pp. 199-201
On truth-table reducibility to SAT
Samuel R. Buss
,
Louise Hay
Information and Computation
91
(1), 1991, March, pp. 86-102
Resolution proofs of generalized pigeonhole principles
Samuel R. Buss
,
György Turán
Theoretical Computer Science
62
, 1988, pp. 311-317