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="van Melkebeek, Dieter"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Holger Dell
,
Dieter van Melkebeek
Journal of the ACM
61
(4), 2014, pp. 23: 1-27
Locality from circuit lower bounds
Matthew Anderson
,
Dieter van Melkebeek
,
Nicile Schweikardt
,
Luc Segoufin
SIAM Journal on Computing
41
(6), 2012, pp. 1481-1523
On derandomization and average-case complexity of monotone functions
George Karakostas
,
Jeff Kinne
,
Dieter van Melkebeek
Theoretical Computer Science
434
, 2012, pp. 35-44
Locality of queries definable in invariant first-order logic with arbitrary built-in predicates
Matthew Anderson
,
Dieter van Melkebeek
,
Nicole Schweikardt
,
Luc Segoufin
Lecture Notes in Computer Science
6756
, 2011, pp. 368-379
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
Holger Dell
,
Dieter van Melkebeek
Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC'2010 (Cambridge, Massachusetts, June 5-8, 2010)
, 2010, pp. 251-260
An improved time-space lower bound for tautologies
Scott Diehl
,
Dieter van Melkebeek
,
Ryan Williams
Lecture Notes in Computer Science
5609
, 2009, pp. 429-438
Space hierarchy results for randomized models
Jeff Kinne
,
Dieter van Melkebeek
Leibniz International Proceedings in Informatics (LIPIcs)
1
, 2008, pp. 433-444
Power from random strings
Eric Allender
,
Harry Buhrman
,
Michal Koucký
,
Dieter van Melkebeek
,
Detlef Ronneburger
SIAM Journal on Computing
35
(6), 2006, pp. 1467-1493
Computational depth: Concept and applications
Luis Antunes
,
Lance Fortnow
,
Dieter van Melkebeek
,
N.V. Vinodchandran
Theoretical Computer Science
354
(3), 2006, pp. 391-404
Time-space tradeoff in derandomizing probabilistic logspace
Jin-Yi Cai
,
Venkatesan T. Chakaravarthy
,
Dieter van Melkebeek
Theory of Computing Systems
39
(1), 2006, pp. 189-208
Time-space lower bounds for the polynomial-time hierarchy on randomized machines
Scott Diehl
,
Dieter van Melkebeek
SIAM Journal on Computing
36
(3), 2006, pp. 563-594
Time-space lower bounds for the polynomial-time hierarchy on randomized machines
Scott Diehl
,
Dieter van Melkebeek
Lecture Notes in Computer Science
3580
, 2005, pp. 982-993
Time-space lower bounds for satisfiability
Lance Fortnow
,
Richard Lipton
,
Dieter van Melkebeek
,
Anastasios Viglas
Journal of the ACM
52
(6), 2005, pp. 835-865
A time lower bound for satisfiability
Dieter van Melkebeek
,
Ran Raz
Theoretical Computer Science
348
(2-3), 2005, pp. 311-320
Holographic proofs and derandomization
Dieter van Melkebeek
,
Rahul Santhanam
SIAM Journal on Computing
35
(1), 2005, pp. 59-90
Time-space tradeoff in derandomizing probabilistic logspace
Jin-Yi Cai
,
Venkatesan T. Chakaravarthy
,
Dieter van Melkebeek
Lecture Notes in Computer Science
2996
, 2004, pp. 571-583
A time lower bound for satisfiability
Dieter van Melkebeek
,
Ran Raz
Lecture Notes in Computer Science
3142
, 2004, pp. 971-982
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
Adam R. Klivans
,
Dieter van Melkebeek
SIAM Journal on Computing
31
(5), 2002, pp. 1501-1526
Separating complexity classes using autoreducibility
Harry Buhrman
,
Lance Fortnow
,
Dieter van Melkebeek
,
Leen Torenvliet
SIAM Journal on Computing
29
(5), 2000, pp. 1497-1520
A generalization of resource-bounded measure, with application to the BPP vs. EXP problem
Harry Buhrman
,
Dieter van Melkebeek
,
Kenneth W. Regan
,
D. Sivakumar
,
Martin Strauss
SIAM Journal on Computing
30
(2), 2000, pp. 576-601
The zero-one law holds for
\cal BPP
Dieter van Melkebeek
Theoretical Computer Science
244
(1-2), 2000, pp. 283-288
Deterministic and randomized bounded truth-table reductions of
P
,
NL
, and
L
to sparse sets
Dieter van Melkebeek
Journal of Computer and System Sciences
57
(2), 1998, pp. 213-232
Reducing
P
to a sparse set using a constant number of queries collapses
P
to
L
Dieter van Melkebeek
Proceedings of the 11th Annual IEEE Conference on Computational Complexity (Philadelphia, Pennsylvania, May 24-27, 1996)
, 1996, pp. 88-96