Dimitris Achlioptas

2007
53	EE	Dimitris Achlioptas, Frank McSherry: Fast computation of low-rank matrix approximations. J. ACM 54(2): (2007)
52	EE	Dimitris Achlioptas, Assaf Naor, Yuval Peres: On the maximum satisfiability of random formulas. J. ACM 54(2): (2007)
51		Dimitris Achlioptas, Vladlen Koltun: Special Section on Foundations of Computer Science. SIAM J. Comput. 37(1): 165 (2007)
2006
50	EE	Dimitris Achlioptas, Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. STOC 2006: 130-139
49	EE	Dimitris Achlioptas, Federico Ricci-Tersenghi: On the Solution-Space Geometry of Random Constraint Satisfaction Problems CoRR abs/cs/0611052: (2006)
48	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
47	EE	Dimitris Achlioptas, Frank McSherry: On Spectral Learning of Mixtures of Distributions. COLT 2005: 458-469
46	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
45	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)
44	EE	Dimitris Achlioptas, Haixia Jia, Cristopher Moore: Hiding Satisfying Assignments: Two are Better than One CoRR abs/cs/0503046: (2005)
43		Dimitris Achlioptas, Stefano Leonardi: Special Issue on Algorithms and Models for the Web-Graph. Internet Mathematics 2(3): (2005)
42	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
41		Dimitris Achlioptas, Haixia Jia, Cristopher Moore: Hiding Satisfying Assignments: Two Are Better than One. AAAI 2004: 131-136
40	EE	Dimitris Achlioptas, Cristopher Moore: The Chromatic Number of Random Regular Graphs. APPROX-RANDOM 2004: 219-228
39	EE	Dimitris Achlioptas: Random Matrices in Data Analysis. ECML 2004: 1-7
38	EE	Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel: Sampling Grid Colorings with Fewer Colors. LATIN 2004: 80-89
37	EE	Dimitris Achlioptas: Random Matrices in Data Analysis. PKDD 2004: 1-7
36	EE	Dimitris Achlioptas, Paul Beame, Michael Molloy: Exponential bounds for DPLL below the satisfiability threshold. SODA 2004: 139-140
35	EE	Dimitris Achlioptas, Assaf Naor: The two possible values of the chromatic number of a random graph. STOC 2004: 587-593
34	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)
33	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
32	EE	Dimitris Achlioptas, Assaf Naor, Yuval Peres: On the Maximum Satisfiability of Random Formulas. FOCS 2003: 362-
31	EE	Dimitris Achlioptas, Yuval Peres: The threshold for random k-SAT is 2k (ln 2 - O(k)). STOC 2003: 223-231
30	EE	Dimitris Achlioptas, Cristopher Moore: Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold CoRR cond-mat/0310227: (2003)
29	EE	Dimitris Achlioptas, Yuval Peres: The Threshold for Random k-SAT is 2kln2 - O(k) CoRR cs.CC/0305009: (2003)
28	EE	Dimitris Achlioptas: Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4): 671-687 (2003)
27	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
26	EE	Dimitris Achlioptas, Cristopher Moore: The Asymptotic Order of the Random k -SAT Threshold. FOCS 2002: 779-788
25	EE	Dimitris Achlioptas, Cristopher Moore: On the 2-Colorability of Random Hypergraphs. RANDOM 2002: 78-90
24	EE	Dimitris Achlioptas, Cristopher Moore: Almost all graphs with average degree 4 are 3-colorable. STOC 2002: 199-208
23		Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali: Two-coloring random hypergraphs. Random Struct. Algorithms 20(2): 249-259 (2002)
2001
22		Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry: Web Search via Hub Synthesis. FOCS 2001: 500-509
21		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
20	EE	Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf: Sampling Techniques for Kernel Methods. NIPS 2001: 335-342
19	EE	Dimitris Achlioptas: Database-friendly random projections. PODS 2001
18	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
17	EE	Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy: A sharp threshold in proof complexity. STOC 2001: 337-346
16	EE	Dimitris Achlioptas, Frank McSherry: Fast computation of low rank matrix. STOC 2001: 611-618
15		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)
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	[17] [33] [36]
2	Jason I. Brown	[4]
3	Frank Van Bussel	[38]
4	Marek Chrobak	[1] [8]
5	Arthur D. Chtcherba	[18]
6	Aaron Clauset	[45] [46]
7	Derek G. Corneil	[4]
8	Gautam Das	[34]
9	Jeff Edmonds	[5]
10	Amos Fiat	[22]
11	Ehud Friedgut	[6]
12	Carla P. Gomes	[12] [21]
13	Gabriel Istrate	[18]
14	Haixia Jia	[41] [42] [44]
15	Anna R. Karlin	[22]
16	Henry A. Kautz	[12] [21]
17	David Kempe	[45] [46]
18	Jeong Han Kim	[10] [23]
19	Lefteris M. Kirousis	[3] [14] [15]
20	Vladlen Koltun	[51]
21	Evangelos Kranakis	[3] [14] [15]
22	Michael Krivelevich	[10] [23]
23	Danny Krizanc	[3] [14] [15]
24	Per-Åke Larson (Paul Larson)	[34]
25	Stefano Leonardi	[43]
26	Frank McSherry	[16] [20] [22] [47] [53]
27	Michael Molloy (Michael S. O. Molloy)	[2] [3] [4] [7] [15] [17] [33] [36] [38]
28	Cristopher Moore	[18] [24] [25] [26] [27] [30] [38] [40] [41] [42] [44] [45] [46] [48]
29	Assaf Naor	[32] [35] [52]
30	John Noga	[1] [8]
31	Yuval Peres	[29] [31] [32] [52]
32	Chung Keung Poon	[5]
33	Lili Qiu	[34]
34	Federico Ricci-Tersenghi	[49] [50]
35	Yongshao Ruan	[21]
36	Bernhard Schölkopf	[20]
37	Bart Selman	[12] [21]
38	Gregory B. Sorkin	[11]
39	Yannis C. Stamatiou	[3] [15]
40	Mark E. Stickel	[21]
41	Prasad Tetali	[10] [23]
42	Chad Verbowski	[34]
43	Yi-Min Wang	[34]

Colors in the list of coauthors