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
[1]
Hilfe
Suche: Author="Achlioptas, Dimitris"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
Algorithmic improvements of the Lovász local lemma via cluster expansion
Dimitris Achlioptas
,
Themis Gouleakis
Leibniz International Proceedings in Informatics (LIPIcs)
18
, 2012, pp. 16-23
Unsatisfiability bounds for random CSPs from an energetic interpolation method
Dimitris Achlioptas
,
Ricardo Menchaca-Mendez
Lecture Notes in Computer Science
7391
, 2012, pp. 1-12
Algorithmic barriers from phase transitions in graphs
Dimitris Achlioptas
Lecture Notes in Computer Science
6410
, 2010, pp. 1-1
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs
Dimitris Achlioptas
,
Aaron Clauset
,
David Kempe
,
Cristopher Moore
Journal of the ACM
56
(4), 2009, pp. 21: 1-28
Random formulas have frozen variables
Dimitris Achlioptas
,
Federico Ricci-Tersenghi
SIAM Journal on Computing
39
(1), 2009, pp. 260-280
Fast computation of low-rank matrix approximations
Dimitris Achlioptas
,
Frank McSherry
Journal of the ACM
54
(2), 2007, pp. 9: 1-19
On the maximum satisfiability of random formulas
Dimitris Achlioptas
,
Assaf Naor
,
Yuval Peres
Journal of the ACM
54
(2), 2007, pp. 10: 1-21
Random
k
-SAT: Two moments suffice to cross a sharp threshold
Dimitris Achlioptas
,
Cristopher Moore
SIAM Journal on Computing
36
(3), 2006, pp. 740-762
On the solution-space geometry of random constraint satisfaction problems
Dimitris Achlioptas
,
Federico Ricci-Tersenghi
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC'2006 (Seattle, Washington, USA, May 21-23, 2006)
, 2006, pp. 130-139
On the bias of traceroute sampling or, power-law degree distributions in regular graphs
Dimitris Achlioptas
,
Aaron Clauset
,
David Kempe
,
Cristopher Moore
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC'2005 (Baltimore, Maryland, USA, May 22-24, 2005)
, 2005, pp. 694-703
A sharp threshold in proof complexity yields lower bounds for satisfiability search
Dimitris Achlioptas
,
Paul Beame
,
Michael Molloy
Journal of Computer and System Sciences
68
(2), 2004, pp. 238-268
The two possible values of the chromatic number of a random graph
Dimitris Achlioptas
,
Assaf Naor
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC'2004 (Chicago, Illinois, USA, June 13-15, 2004)
, 2004, pp. 587-593
Almost all graphs with average degree 4 are 3-colorable
Dimitris Achlioptas
,
Cristopher Moore
Journal of Computer and System Sciences
67
(2), 2003, pp. 441-471
The threshold for random
k
-SAT is
2^k ln 2 - O(k)
Dimitris Achlioptas
,
Yuval Peres
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, STOC'2003 (San Diego, California, USA, June 9-11, 2003)
, 2003, pp. 223-231
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Dimitris Achlioptas
Journal of Computer and System Sciences
66
(4), 2003, pp. 671-687
The asymptotic order of the random
k
-SAT threshold
Dimitris Achlioptas
,
Cristopher Moore
Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS'2002 (Vancouver, BC, Canada, November 16-19, 2002)
, 2002, pp. 779-788
A sharp threshold in proof complexity
Dimitris Achlioptas
,
Paul Beame
,
Michael Molloy
Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC'2001 (Hersonissos, Crete, Greece, July 6-8, 2001)
, 2001, pp. 337-346
Rigorous results for random
(2+p)
-SAT
Dimitris Achlioptas
,
Lefteris M. Kirousis
,
Evangelos Kranakis
,
Danny Krizanc
Theoretical Computer Science
265
(1-2), 2001, pp. 109-129
Fast computation of low rank matrix approximation
Dimitris Achlioptas
,
Frank McSherry
Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, STOC'2001 (Hersonissos, Crete, Greece, July 6-8, 2001)
, 2001, pp. 611-618
Lower bounds for random 3-SAT via differential equations
Dimitris Achlioptas
Theoretical Computer Science
265
(1-2), 2001, pp. 159-185
Competitive analysis of randomized paging algorithms
Dimitris Achlioptas
,
Marek Chrobak
,
John Noga
Theoretical Computer Science
234
(1-2), 2000, pp. 203-218
Two-coloring random hypergraphs
Dimitris Achlioptas
,
Jeong Han Kim
,
Michael Krivelevich
,
Prasad Tetali
Proceedings in Informatics
8
, 2000, pp. 85-96
Setting 2 variables at a time yields a new lower bound for random 3-SAT
Dimitris Achlioptas
Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC'2000 (Portland, Oregon, May 21-23, 2000)
, 2000, pp. 28-37
Tight lower bounds for
st
-connectivity on the NNJAG model
Jeff Edmonds
,
Chung Keung Poon
,
Dimitris Achlioptas
SIAM Journal on Computing
28
(6), 1999, pp. 2257-2284
The analysis of a list-coloring algorithm on a random graph
Dimitris Achlioptas
,
Michael Molloy
Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, FOCS'97 (Miami Beach, Florida, October 20-22, 1997)
, 1997, pp. 204-212
Seiten 1
2
>