Dimitris Achlioptas

2008
55	EE	Dimitris Achlioptas, Amin Coja-Oghlan: Algorithmic Barriers from Phase Transitions. FOCS 2008: 793-802
2007
54	EE	Dimitris Achlioptas, Frank McSherry: Fast computation of low-rank matrix approximations. J. ACM 54(2): (2007)
53	EE	Dimitris Achlioptas, Assaf Naor, Yuval Peres: On the maximum satisfiability of random formulas. J. ACM 54(2): (2007)
52		Dimitris Achlioptas, Vladlen Koltun: Special Section on Foundations of Computer Science. SIAM J. Comput. 37(1): 165 (2007)
2006
51	EE	Dimitris Achlioptas, Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. STOC 2006: 130-139
50	EE	Dimitris Achlioptas, Federico Ricci-Tersenghi: On the Solution-Space Geometry of Random Constraint Satisfaction Problems CoRR abs/cs/0611052: (2006)
49	EE	Dimitris Achlioptas, Cristopher Moore: Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. SIAM J. Comput. 36(3): 740-762 (2006)
2005
48	EE	Dimitris Achlioptas, Frank McSherry: On Spectral Learning of Mixtures of Distributions. COLT 2005: 458-469
47	EE	Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore: On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. STOC 2005: 694-703
46	EE	Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore: On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs CoRR abs/cond-mat/0503087: (2005)
45	EE	Dimitris Achlioptas, Haixia Jia, Cristopher Moore: Hiding Satisfying Assignments: Two are Better than One CoRR abs/cs/0503046: (2005)
44		Dimitris Achlioptas, Stefano Leonardi: Special Issue on Algorithms and Models for the Web-Graph. Internet Mathematics 2(3): (2005)
43	EE	Dimitris Achlioptas, Haixia Jia, Cristopher Moore: Hiding Satisfying Assignments: Two are Better than One. J. Artif. Intell. Res. (JAIR) 24: 623-639 (2005)
2004
42		Dimitris Achlioptas, Haixia Jia, Cristopher Moore: Hiding Satisfying Assignments: Two Are Better than One. AAAI 2004: 131-136
41	EE	Dimitris Achlioptas, Cristopher Moore: The Chromatic Number of Random Regular Graphs. APPROX-RANDOM 2004: 219-228
40	EE	Dimitris Achlioptas: Random Matrices in Data Analysis. ECML 2004: 1-7
39	EE	Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel: Sampling Grid Colorings with Fewer Colors. LATIN 2004: 80-89
38	EE	Dimitris Achlioptas: Random Matrices in Data Analysis. PKDD 2004: 1-7
37	EE	Dimitris Achlioptas, Paul Beame, Michael Molloy: Exponential bounds for DPLL below the satisfiability threshold. SODA 2004: 139-140
36	EE	Dimitris Achlioptas, Assaf Naor: The two possible values of the chromatic number of a random graph. STOC 2004: 587-593
35	EE	Yi-Min Wang, Lili Qiu, Chad Verbowski, Dimitris Achlioptas, Gautam Das, Per-Åke Larson: Summary-based routing for content-based event distribution networks. Computer Communication Review 34(5): 59-74 (2004)
34	EE	Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy: A sharp threshold in proof complexity yields lower bounds for satisfiability search. J. Comput. Syst. Sci. 68(2): 238-268 (2004)
2003
33	EE	Dimitris Achlioptas, Assaf Naor, Yuval Peres: On the Maximum Satisfiability of Random Formulas. FOCS 2003: 362-
32	EE	Dimitris Achlioptas, Yuval Peres: The threshold for random k-SAT is 2k (ln 2 - O(k)). STOC 2003: 223-231
31	EE	Dimitris Achlioptas, Cristopher Moore: Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold CoRR cond-mat/0310227: (2003)
30	EE	Dimitris Achlioptas, Yuval Peres: The Threshold for Random k-SAT is 2kln2 - O(k) CoRR cs.CC/0305009: (2003)
29	EE	Dimitris Achlioptas: Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4): 671-687 (2003)
28	EE	Dimitris Achlioptas, Cristopher Moore: Almost all graphs with average degree 4 are 3-colorable. J. Comput. Syst. Sci. 67(2): 441-471 (2003)
2002
27	EE	Dimitris Achlioptas, Cristopher Moore: The Asymptotic Order of the Random k -SAT Threshold. FOCS 2002: 779-788
26	EE	Dimitris Achlioptas, Cristopher Moore: On the 2-Colorability of Random Hypergraphs. RANDOM 2002: 78-90
25	EE	Dimitris Achlioptas, Cristopher Moore: Almost all graphs with average degree 4 are 3-colorable. STOC 2002: 199-208
24		Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali: Two-coloring random hypergraphs. Random Struct. Algorithms 20(2): 249-259 (2002)
2001
23		Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry: Web Search via Hub Synthesis. FOCS 2001: 500-509
22		Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel: Balance and Filtering in Structured Satisfiable Problems. IJCAI 2001: 351-358
21	EE	Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf: Sampling Techniques for Kernel Methods. NIPS 2001: 335-342
20	EE	Dimitris Achlioptas: Database-friendly random projections. PODS 2001
19	EE	Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore: The phase transition in 1-in-k SAT and NAE 3-SAT. SODA 2001: 721-722
18	EE	Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy: A sharp threshold in proof complexity. STOC 2001: 337-346
17	EE	Dimitris Achlioptas, Frank McSherry: Fast computation of low rank matrix. STOC 2001: 611-618
16		Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Krizanc: Random Constraint Satisfaction: A More Accurate Picture. Constraints 6(4): 329-344 (2001)
15	EE	Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel: Balance and Filtering in Structured Satisfiable Problems (Preliminary Report). Electronic Notes in Discrete Mathematics 9: 2-18 (2001)
14	EE	Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc: Rigorous results for random (2+p)-SAT. Theor. Comput. Sci. 265(1-2): 109-129 (2001)
13	EE	Dimitris Achlioptas: Lower bounds for random 3-SAT via differential equations. Theor. Comput. Sci. 265(1-2): 159-185 (2001)
2000
12		Dimitris Achlioptas, Carla P. Gomes, Henry A. Kautz, Bart Selman: Generating Satisfiable Problem Instances. AAAI/IAAI 2000: 256-261
11		Dimitris Achlioptas, Gregory B. Sorkin: Optimal myopic algorithms for random 3-SAT. FOCS 2000: 590-600
10		Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali: Two-coloring Random Hypergraphs. ICALP Satellite Workshops 2000: 85-96
9	EE	Dimitris Achlioptas: Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). STOC 2000: 28-37
8	EE	Dimitris Achlioptas, Marek Chrobak, John Noga: Competitive analysis of randomized paging algorithms. Theor. Comput. Sci. 234(1-2): 203-218 (2000)
1999
7	EE	Dimitris Achlioptas, Michael Molloy: Almost all graphs with 2.522 n edges are not 3-colorable. Electr. J. Comb. 6: (1999)
6		Dimitris Achlioptas, Ehud Friedgut: A Sharp Threshold for k-Colorability. Random Struct. Algorithms 14(1): 63-70 (1999)
5		Jeff Edmonds, Chung Keung Poon, Dimitris Achlioptas: Tight Lower Bounds for st-Connectivity on the NNJAG Model. SIAM J. Comput. 28(6): 2257-2284 (1999)
1998
4	EE	Dimitris Achlioptas, Jason I. Brown, Derek G. Corneil, Michael S. O. Molloy: The existence of uniquely -G colourable graphs. Discrete Mathematics 179(1-3): 1-11 (1998)
1997
3		Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. O. Molloy, Yannis C. Stamatiou: Random Constraint Satisfaction: A More Accurate Picture. CP 1997: 107-120
2	EE	Dimitris Achlioptas, Michael S. O. Molloy: The Analysis of a List-Coloring Algorithm on a Random Graph. FOCS 1997: 204-212
1996
1		Dimitris Achlioptas, Marek Chrobak, John Noga: Competive Analysis of Randomized Paging Algorithms. ESA 1996: 419-430

Coauthor Index

1	Paul Beame	[18] [34] [37]
2	Jason I. Brown	[4]
3	Frank Van Bussel	[39]
4	Marek Chrobak	[1] [8]
5	Arthur D. Chtcherba	[19]
6	Aaron Clauset	[46] [47]
7	Amin Coja-Oghlan	[55]
8	Derek G. Corneil	[4]
9	Gautam Das	[35]
10	Jeff Edmonds	[5]
11	Amos Fiat	[23]
12	Ehud Friedgut	[6]
13	Carla P. Gomes	[12] [15] [22]
14	Gabriel Istrate	[19]
15	Haixia Jia	[42] [43] [45]
16	Anna R. Karlin	[23]
17	Henry A. Kautz	[12] [15] [22]
18	David Kempe	[46] [47]
19	Jeong Han Kim	[10] [24]
20	Lefteris M. Kirousis	[3] [14] [16]
21	Vladlen Koltun	[52]
22	Evangelos Kranakis	[3] [14] [16]
23	Michael Krivelevich	[10] [24]
24	Danny Krizanc	[3] [14] [16]
25	Per-Åke Larson (Paul Larson)	[35]
26	Stefano Leonardi	[44]
27	Frank McSherry	[17] [21] [23] [48] [54]
28	Michael Molloy (Michael S. O. Molloy)	[2] [3] [4] [7] [16] [18] [34] [37] [39]
29	Cristopher Moore	[19] [25] [26] [27] [28] [31] [39] [41] [42] [43] [45] [46] [47] [49]
30	Assaf Naor	[33] [36] [53]
31	John Noga	[1] [8]
32	Yuval Peres	[30] [32] [33] [53]
33	Chung Keung Poon	[5]
34	Lili Qiu	[35]
35	Federico Ricci-Tersenghi	[50] [51]
36	Yongshao Ruan	[15] [22]
37	Bernhard Schölkopf	[21]
38	Bart Selman	[12] [15] [22]
39	Gregory B. Sorkin	[11]
40	Yannis C. Stamatiou	[3] [16]
41	Mark E. Stickel	[15] [22]
42	Prasad Tetali	[10] [24]
43	Chad Verbowski	[35]
44	Yi-Min Wang	[35]

Colors in the list of coauthors