×

zbMATH — the first resource for mathematics

Achlioptas, Dimitris

Compute Distance To:
Author ID: achlioptas.dimitris Recent zbMATH articles by "Achlioptas, Dimitris"
Published as: Achlioptas, D.; Achlioptas, Demetrios; Achlioptas, Dimitris
Homepage: https://achlioptas.org/
External Links: MGP · dblp
Documents Indexed: 60 Publications since 1996, including 1 Book

Publications by Year

Citations contained in zbMATH

51 Publications have been cited 722 times in 502 Documents Cited by Year
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
79
2003
The threshold for random \(k\)-SAT is \(2^k\log 2-O(k)\). Zbl 1093.68075
Achlioptas, Dimitris; Peres, Yuval
46
2004
The two possible values of the chromatic number of a random graph. Zbl 1094.05048
Achlioptas, Dimitris; Naor, Assaf
43
2005
Random \(k\)-SAT: Two moments suffice to cross a sharp threshold. Zbl 1120.68096
Achlioptas, Dimitris; Moore, Cristopher
38
2006
Explosive percolation in random networks. Zbl 1226.05221
Achlioptas, Dimitris; D’Souza, Raissa M.; Spencer, Joel
36
2009
Competitive analysis of randomized paging algorithms. Zbl 0944.68194
Achlioptas, D.; Chrobak, M.; Noga, J.
34
2000
Random constraint satisfaction: A more accurate picture. Zbl 0984.68085
Achlioptas, Dimitris; Molloy, Michael S. O.; Kirousis, Lefteris M.; Stamatiou, Yannis C.; Kranakis, Evangelos; Krizanc, Danny
31
2001
Fast computation of low-rank matrix approximations. Zbl 1311.94031
Achlioptas, Dimitris; McSherry, Frank
30
2007
A sharp threshold for \(k\)-colorability. Zbl 0962.05055
Achlioptas, Dimitris; Friedgut, Ehud
30
1999
Fast computation of low rank matrix approximations. Zbl 1311.94032
Achlioptas, Dimitris; McSherry, Frank
28
2001
On the solution-space geometry of random constraint satisfaction problems. Zbl 1301.68190
Achlioptas, Dimitris; Ricci-Tersenghi, Federico
27
2006
Lower bounds for random 3-SAT via differential equations. Zbl 0983.68079
Achlioptas, D.
26
2001
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). Zbl 1296.68062
Achlioptas, Dimitris
23
2000
On the solution-space geometry of random constraint satisfaction problems. Zbl 1217.68156
Achlioptas, Dimitris; Coja-Oghlan, Amin; Ricci-Tersenghi, Federico
22
2011
Rigorous results for random (\(2+p)\)-SAT. Zbl 0992.68073
Achlioptas, D.; Kirousis, L. M.; Kranakis, E.; Krizanc, D.
17
2001
On spectral learning of mixtures of distributions. Zbl 1137.68512
Achlioptas, Dimitris; McSherry, Frank
14
2005
On the bias of traceroute sampling or, power-law degree distributions in regular graphs. Zbl 1192.68065
Achlioptas, Dimitris; Clauset, Aaron; Kempe, David; Moore, Cristopher
13
2005
Two-coloring random hypergraphs. Zbl 1001.05059
Achlioptas, Dimitris; Kim, Jeong Han; Krivelevich, Michael; Tetali, Prasad
13
2002
The threshold for random \(k\)-SAT is \(2^k(\ln 2-O(k))\). Zbl 1192.68333
Achlioptas, Dimitris; Peres, Yuval
12
2003
The phase transition in 1-in-\(k\) SAT and NAE 3-SAT. Zbl 0991.68032
Achlioptas, Dimitris; Chtcherba, Arthur; Istrate, Gabriel; Moore, Cristopher
12
2001
Balance and filtering in structured satisfiable problems. (Preliminary report). Zbl 0985.90509
Kautz, Henry; Ruan, Yongshao; Achlioptas, Dimitris; Gomes, Carla; Selman, Bart; Stickel, Mark
11
2001
The complexity of \(G\)-free colourability. Zbl 0904.05030
Achlioptas, Demetrios
11
1997
The chromatic number of random regular graphs. Zbl 1105.05063
Achlioptas, Dimitris; Moore, Cristopher
10
2004
Random formulas have frozen variables. Zbl 1185.68508
Achlioptas, Dimitris; Ricci-Tersenghi, Federico
9
2009
On the 2-colorability of random hypergraphs. Zbl 1030.05084
Achlioptas, Dimitris; Moore, Cristopher
9
2002
A sharp threshold in proof complexity. Zbl 1323.03088
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
9
2001
Almost all graphs with average degree 4 are 3-colorable. Zbl 1072.68076
Achlioptas, Dimitris; Moore, Cristopher
7
2003
Hiding satisfying assignments: two are better than one. Zbl 1080.68653
Achlioptas, D.; Jia, H.; Moore, C.
6
2005
A sharp threshold in proof complexity yields lower bounds for satisfiability search. Zbl 1093.03033
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
6
2004
Tight lower bounds for st-connectivity on the NNJAG model. Zbl 0943.68069
Edmonds, Jeff; Poon, Chung Keung; Achlioptas, Dimitris
6
1999
Random walks that find perfect objects and the Lovász local lemma. Zbl 1426.05154
Achlioptas, Dimitris; Iliopoulos, Fotis
5
2016
Focused stochastic local search and the Lovász local lemma. Zbl 1410.68338
Achlioptas, Dimitris; Iliopoulos, Fotis
5
2016
On the maximum satisfiability of random formulas. Zbl 1291.68175
Achlioptas, Dimitris; Naor, Assaf; Peres, Yuval
5
2007
Almost all graphs with average degree 4 are 3-colorable. Zbl 1192.05042
Achlioptas, Dimitris; Moore, Cristopher
5
2002
Competitive analysis of randomized paging algorithms. Zbl 1379.68376
Achlioptas, Dimitris; Chrobak, Marek; Noga, John
5
1996
On the bias of traceroute sampling, or, power-law degree distributions in regular graphs. Zbl 1325.68165
Achlioptas, Dimitris; Clauset, Aaron; Kempe, David; Moore, Cristopher
4
2009
Exponential bounds for DPLL below the satisfiability threshold. Zbl 1317.68060
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
4
2004
The two possible values of the chromatic number of a random graph. Zbl 1192.05140
Achlioptas, Dimitris; Naor, Assaf
4
2004
Almost all graphs with 2. 522\(n\) edges are not 3-colorable. Zbl 0919.05056
Achlioptas, Dimitris; Molloy, Michael
4
1999
Bounds for random constraint satisfaction problems via spatial coupling. Zbl 1410.68137
Achlioptas, Dimitris; Hassani, S. Hamed; Macris, Nicolas; Urbanke, Rudiger
3
2016
Navigability is a robust property. Zbl 1342.05150
Achlioptas, Dimitris; Siminelakis, Paris
3
2015
The solution space geometry of random linear equations. Zbl 1309.05129
Achlioptas, Dimitris; Molloy, Michael
3
2015
Sampling grid colorings with fewer colors. Zbl 1196.05027
Achlioptas, Dimitris; Molloy, Mike; Moore, Cristopher; Bussel, Frank Van
3
2004
The existence of uniquely \(-G\) colourable graphs. Zbl 0885.05062
Achlioptas, D.; Brown, J. I.; Corneil, D. G.; Molloy, M. S. O.
3
1998
Rapid mixing for lattice colourings with fewer colours. Zbl 07077849
Achlioptas, Dimitris; Molloy, Mike; Moore, Cristopher; Van Bussel, Frank
2
2005
Fast and flexible probabilistic model counting. Zbl 06916305
Achlioptas, Dimitris; Hammoudeh, Zayd; Theodoropoulos, Panos
1
2018
Symmetric graph properties have independent edges. Zbl 1394.05110
Achlioptas, Dimitris; Siminelakis, Paris
1
2018
Probabilistic model counting with short XORs. Zbl 06807215
Achlioptas, Dimitris; Theodoropoulos, Panos
1
2017
Symmetric graph properties have independent edges. Zbl 1395.05148
Achlioptas, Dimitris; Siminelakis, Paris
1
2015
Algorithmic improvements of the Lovász local lemma via cluster expansion. Zbl 1354.68206
Achlioptas, Dimitris; Gouleakis, Themis
1
2012
Solution clustering in random satisfiability. Zbl 1189.82043
Achlioptas, D.
1
2008
Fast and flexible probabilistic model counting. Zbl 06916305
Achlioptas, Dimitris; Hammoudeh, Zayd; Theodoropoulos, Panos
1
2018
Symmetric graph properties have independent edges. Zbl 1394.05110
Achlioptas, Dimitris; Siminelakis, Paris
1
2018
Probabilistic model counting with short XORs. Zbl 06807215
Achlioptas, Dimitris; Theodoropoulos, Panos
1
2017
Random walks that find perfect objects and the Lovász local lemma. Zbl 1426.05154
Achlioptas, Dimitris; Iliopoulos, Fotis
5
2016
Focused stochastic local search and the Lovász local lemma. Zbl 1410.68338
Achlioptas, Dimitris; Iliopoulos, Fotis
5
2016
Bounds for random constraint satisfaction problems via spatial coupling. Zbl 1410.68137
Achlioptas, Dimitris; Hassani, S. Hamed; Macris, Nicolas; Urbanke, Rudiger
3
2016
Navigability is a robust property. Zbl 1342.05150
Achlioptas, Dimitris; Siminelakis, Paris
3
2015
The solution space geometry of random linear equations. Zbl 1309.05129
Achlioptas, Dimitris; Molloy, Michael
3
2015
Symmetric graph properties have independent edges. Zbl 1395.05148
Achlioptas, Dimitris; Siminelakis, Paris
1
2015
Algorithmic improvements of the Lovász local lemma via cluster expansion. Zbl 1354.68206
Achlioptas, Dimitris; Gouleakis, Themis
1
2012
On the solution-space geometry of random constraint satisfaction problems. Zbl 1217.68156
Achlioptas, Dimitris; Coja-Oghlan, Amin; Ricci-Tersenghi, Federico
22
2011
Explosive percolation in random networks. Zbl 1226.05221
Achlioptas, Dimitris; D’Souza, Raissa M.; Spencer, Joel
36
2009
Random formulas have frozen variables. Zbl 1185.68508
Achlioptas, Dimitris; Ricci-Tersenghi, Federico
9
2009
On the bias of traceroute sampling, or, power-law degree distributions in regular graphs. Zbl 1325.68165
Achlioptas, Dimitris; Clauset, Aaron; Kempe, David; Moore, Cristopher
4
2009
Solution clustering in random satisfiability. Zbl 1189.82043
Achlioptas, D.
1
2008
Fast computation of low-rank matrix approximations. Zbl 1311.94031
Achlioptas, Dimitris; McSherry, Frank
30
2007
On the maximum satisfiability of random formulas. Zbl 1291.68175
Achlioptas, Dimitris; Naor, Assaf; Peres, Yuval
5
2007
Random \(k\)-SAT: Two moments suffice to cross a sharp threshold. Zbl 1120.68096
Achlioptas, Dimitris; Moore, Cristopher
38
2006
On the solution-space geometry of random constraint satisfaction problems. Zbl 1301.68190
Achlioptas, Dimitris; Ricci-Tersenghi, Federico
27
2006
The two possible values of the chromatic number of a random graph. Zbl 1094.05048
Achlioptas, Dimitris; Naor, Assaf
43
2005
On spectral learning of mixtures of distributions. Zbl 1137.68512
Achlioptas, Dimitris; McSherry, Frank
14
2005
On the bias of traceroute sampling or, power-law degree distributions in regular graphs. Zbl 1192.68065
Achlioptas, Dimitris; Clauset, Aaron; Kempe, David; Moore, Cristopher
13
2005
Hiding satisfying assignments: two are better than one. Zbl 1080.68653
Achlioptas, D.; Jia, H.; Moore, C.
6
2005
Rapid mixing for lattice colourings with fewer colours. Zbl 07077849
Achlioptas, Dimitris; Molloy, Mike; Moore, Cristopher; Van Bussel, Frank
2
2005
The threshold for random \(k\)-SAT is \(2^k\log 2-O(k)\). Zbl 1093.68075
Achlioptas, Dimitris; Peres, Yuval
46
2004
The chromatic number of random regular graphs. Zbl 1105.05063
Achlioptas, Dimitris; Moore, Cristopher
10
2004
A sharp threshold in proof complexity yields lower bounds for satisfiability search. Zbl 1093.03033
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
6
2004
Exponential bounds for DPLL below the satisfiability threshold. Zbl 1317.68060
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
4
2004
The two possible values of the chromatic number of a random graph. Zbl 1192.05140
Achlioptas, Dimitris; Naor, Assaf
4
2004
Sampling grid colorings with fewer colors. Zbl 1196.05027
Achlioptas, Dimitris; Molloy, Mike; Moore, Cristopher; Bussel, Frank Van
3
2004
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
79
2003
The threshold for random \(k\)-SAT is \(2^k(\ln 2-O(k))\). Zbl 1192.68333
Achlioptas, Dimitris; Peres, Yuval
12
2003
Almost all graphs with average degree 4 are 3-colorable. Zbl 1072.68076
Achlioptas, Dimitris; Moore, Cristopher
7
2003
Two-coloring random hypergraphs. Zbl 1001.05059
Achlioptas, Dimitris; Kim, Jeong Han; Krivelevich, Michael; Tetali, Prasad
13
2002
On the 2-colorability of random hypergraphs. Zbl 1030.05084
Achlioptas, Dimitris; Moore, Cristopher
9
2002
Almost all graphs with average degree 4 are 3-colorable. Zbl 1192.05042
Achlioptas, Dimitris; Moore, Cristopher
5
2002
Random constraint satisfaction: A more accurate picture. Zbl 0984.68085
Achlioptas, Dimitris; Molloy, Michael S. O.; Kirousis, Lefteris M.; Stamatiou, Yannis C.; Kranakis, Evangelos; Krizanc, Danny
31
2001
Fast computation of low rank matrix approximations. Zbl 1311.94032
Achlioptas, Dimitris; McSherry, Frank
28
2001
Lower bounds for random 3-SAT via differential equations. Zbl 0983.68079
Achlioptas, D.
26
2001
Rigorous results for random (\(2+p)\)-SAT. Zbl 0992.68073
Achlioptas, D.; Kirousis, L. M.; Kranakis, E.; Krizanc, D.
17
2001
The phase transition in 1-in-\(k\) SAT and NAE 3-SAT. Zbl 0991.68032
Achlioptas, Dimitris; Chtcherba, Arthur; Istrate, Gabriel; Moore, Cristopher
12
2001
Balance and filtering in structured satisfiable problems. (Preliminary report). Zbl 0985.90509
Kautz, Henry; Ruan, Yongshao; Achlioptas, Dimitris; Gomes, Carla; Selman, Bart; Stickel, Mark
11
2001
A sharp threshold in proof complexity. Zbl 1323.03088
Achlioptas, Dimitris; Beame, Paul; Molloy, Michael
9
2001
Competitive analysis of randomized paging algorithms. Zbl 0944.68194
Achlioptas, D.; Chrobak, M.; Noga, J.
34
2000
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). Zbl 1296.68062
Achlioptas, Dimitris
23
2000
A sharp threshold for \(k\)-colorability. Zbl 0962.05055
Achlioptas, Dimitris; Friedgut, Ehud
30
1999
Tight lower bounds for st-connectivity on the NNJAG model. Zbl 0943.68069
Edmonds, Jeff; Poon, Chung Keung; Achlioptas, Dimitris
6
1999
Almost all graphs with 2. 522\(n\) edges are not 3-colorable. Zbl 0919.05056
Achlioptas, Dimitris; Molloy, Michael
4
1999
The existence of uniquely \(-G\) colourable graphs. Zbl 0885.05062
Achlioptas, D.; Brown, J. I.; Corneil, D. G.; Molloy, M. S. O.
3
1998
The complexity of \(G\)-free colourability. Zbl 0904.05030
Achlioptas, Demetrios
11
1997
Competitive analysis of randomized paging algorithms. Zbl 1379.68376
Achlioptas, Dimitris; Chrobak, Marek; Noga, John
5
1996
all top 5

Cited by 925 Authors

25 Coja-Oghlan, Amin
12 Achlioptas, Dimitris
9 Shabanov, Dmitry A.
7 Bhamidi, Shankar
7 Efthymiou, Charilaos
7 Gao, Yong
7 Larmore, Lawrence L.
7 Montanari, Andrea
7 Zhou, Guangyan
6 Drineas, Petros
6 Gao, Zongsheng
6 Kirousis, Lefteris Miltiades
6 Krivelevich, Michael
6 Molloy, Michael S. O.
6 Moore, Cristopher
6 Rachkovskii, D. A.
6 Semerjian, Guilhem
6 Warnke, Lutz
6 Xu, Ke
5 Bein, Wolfgang W.
5 Gamarnik, David
5 Needell, Deanna
5 Perkins, Will
4 Bapst, Victor
4 Budhiraja, Amarjit S.
4 Chrobak, Marek
4 Culberson, Joseph C.
4 Epstein, Leah
4 Frieze, Alan Michael
4 Istrate, Gabriel I.
4 Liberti, Leo
4 Moruz, Gabriel
4 Negoescu, Andrei
4 Nelson, Jelani
4 Panagiotou, Konstantinos D.
4 Riordan, Oliver Maxim
4 Selman, Bart
4 Wormald, Nicholas Charles
4 Zdeborová, Lenka
3 Averbuch, Amir Z.
3 Boccaletti, Stefano
3 Bolla, Marianna
3 Daudé, Hervé
3 Díaz, Josep
3 Fernández, César C.
3 Gimbel, John G.
3 Greenhill, Catherine S.
3 Hetterich, Samuel
3 Kane, Daniel M.
3 Kaporis, Alexis C.
3 Liberty, Edo
3 Mézard, Marc
3 Mora, Thierry
3 Mossel, Elchanan
3 Nightingale, Peter W.
3 Poirion, Pierre-Louis
3 Raßmann, Felicia
3 Ricci-Tersenghi, Federico
3 Sabelfeld, Karl Karlovich
3 Schmid, Stefan
3 Sgall, Jiří
3 Shen, Jing
3 Sorkin, Gregory B.
3 Steger, Angelika
3 Van Leeuwen, Erik Jan
3 Vilenchik, Dan
3 Vu, Ky Khac
3 Vybíral, Jan
3 Wang, Xuan
3 Ward, Rachel A.
3 Yang, Chun
2 Abbe, Emmanuel
2 Ailon, Nir
2 Aizenbud, Yariv
2 Ansótegui, Carlos
2 Applebaum, Benny
2 Balogh, József
2 Bartal, Yair
2 Beame, Paul W.
2 Béjar, Ramón
2 Bienkowski, Marcin
2 Bollobás, Béla
2 Boufkhad, Yacine
2 Budzynski, Louise
2 Cambazard, Hadrien
2 Chakraborty, Sankardeep
2 Çivril, Ali
2 Cocco, Simona
2 Creignou, Nadia
2 Dalmau, Víctor
2 d’Aspremont, Alexandre
2 Dembo, Amir
2 Ding, Jian
2 Dirksen, Sjoerd
2 Dubois, Olivier
2 Durrant, Robert J.
2 Dyer, Martin E.
2 Faloutsos, Christos
2 Fan, Yun
2 Franco, John V.
...and 825 more Authors
all top 5

Cited in 151 Serials

32 Theoretical Computer Science
27 Random Structures & Algorithms
17 Discrete Mathematics
16 Discrete Applied Mathematics
12 Journal of Computer and System Sciences
12 SIAM Journal on Computing
12 Journal of Statistical Mechanics: Theory and Experiment
11 Artificial Intelligence
11 Algorithmica
11 Combinatorics, Probability and Computing
10 The Annals of Applied Probability
9 Information Processing Letters
9 SIAM Journal on Discrete Mathematics
8 Journal of Combinatorial Optimization
7 European Journal of Combinatorics
7 Theory of Computing Systems
7 Journal of Machine Learning Research (JMLR)
6 Journal of Statistical Physics
6 Journal of Combinatorial Theory. Series B
6 Cybernetics and Systems Analysis
6 Annals of Mathematics and Artificial Intelligence
6 Chaos
6 Electronic Journal of Statistics
5 Communications in Mathematical Physics
5 The Annals of Statistics
5 Linear Algebra and its Applications
5 Constraints
4 Physics Reports
4 Probability Theory and Related Fields
4 Journal of Automated Reasoning
4 Data Mining and Knowledge Discovery
4 Statistical Analysis and Data Mining
4 Information and Inference
4 Computer Science Review
3 Advances in Mathematics
3 Combinatorica
3 Information and Computation
3 Machine Learning
3 International Journal of Foundations of Computer Science
3 Pattern Recognition
3 Distributed Computing
3 Applied and Computational Harmonic Analysis
3 The European Physical Journal B. Condensed Matter and Complex Systems
2 Israel Journal of Mathematics
2 Journal of Computational Physics
2 Acta Mathematica
2 The Annals of Probability
2 Information Sciences
2 Journal of Applied Probability
2 Journal of Econometrics
2 Journal of Graph Theory
2 Journal of Multivariate Analysis
2 Statistics & Probability Letters
2 Graphs and Combinatorics
2 Discrete & Computational Geometry
2 Journal of the American Mathematical Society
2 SIAM Journal on Matrix Analysis and Applications
2 JETAI. Journal of Experimental & Theoretical Artificial Intelligence
2 Journal of Global Optimization
2 Mathematical Programming. Series A. Series B
2 Journal of Mathematical Imaging and Vision
2 Journal of Mathematical Sciences (New York)
2 Journal of the ACM
2 Journal of Discrete Mathematical Sciences & Cryptography
2 Foundations of Computational Mathematics
2 ACM Journal of Experimental Algorithmics
2 Acta Numerica
2 Mathematical Statistics and Learning
1 ACM Computing Surveys
1 The Canadian Journal of Statistics
1 Computers & Mathematics with Applications
1 Indian Journal of Pure & Applied Mathematics
1 Journal of Mathematical Analysis and Applications
1 Linear and Multilinear Algebra
1 Mathematical Notes
1 Physica A
1 Russian Mathematical Surveys
1 Theoretical and Mathematical Physics
1 Arkiv för Matematik
1 Theory of Probability and its Applications
1 Applied Mathematics and Computation
1 Automatica
1 Biometrics
1 Journal of the American Statistical Association
1 Journal of Approximation Theory
1 Journal of Combinatorial Theory. Series A
1 Journal of Computational and Applied Mathematics
1 Journal of Functional Analysis
1 Mathematics and Computers in Simulation
1 Mathematics of Operations Research
1 Memoirs of the American Mathematical Society
1 Operations Research
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Systems & Control Letters
1 Physica D
1 Acta Mathematicae Applicatae Sinica. English Series
1 Constructive Approximation
1 Journal of Cryptology
1 Neural Networks
...and 51 more Serials

Citations by Year