Year |
Citation |
Score |
2021 |
Achlioptas D, Coja‐Oghlan A, Hahn‐Klimroth M, Lee J, Müller N, Penschuck M, Zhou G. The number of satisfying assignments of random 2‐SAT formulas Random Structures & Algorithms. 58: 609-647. DOI: 10.1002/RSA.20993 |
0.305 |
|
2019 |
Achlioptas D, Iliopoulos F, Kolmogorov V. A Local Lemma for Focused Stochastic Algorithms Siam Journal On Computing. 48: 1583-1602. DOI: 10.1137/16M109332X |
0.365 |
|
2019 |
Achlioptas D, Theodoropoulos P. Model counting with error-correcting codes Constraints - An International Journal. 24: 162-182. DOI: 10.1007/S10601-018-9296-3 |
0.327 |
|
2016 |
Achlioptas D, Hassani SH, Maoris N, Urbanke R. Bounds for random constraint satisfaction problems via spatial coupling Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1: 469-479. |
0.328 |
|
2015 |
Achlioptas D, Siminelakis P. Symmetric graph properties have independent edges Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9135: 467-478. DOI: 10.1016/J.Ic.2018.02.017 |
0.382 |
|
2015 |
Achlioptas D, Molloy M. The solution space geometry of random linear equations Random Structures and Algorithms. 46: 197-231. DOI: 10.1002/Rsa.20494 |
0.346 |
|
2014 |
Achlioptas D, Iliopoulos F. Random walks that find perfect objects and the lovasz local lemma Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 494-503. DOI: 10.1145/2818352 |
0.455 |
|
2012 |
Achlioptas D, Menchaca-Mendez R. Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7317: 327-340. DOI: 10.1007/978-3-642-31612-8_25 |
0.607 |
|
2012 |
Achlioptas D, Menchaca-Mendez R. Unsatisfiability bounds for random CSPs from an energetic interpolation method Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7391: 1-12. DOI: 10.1007/978-3-642-31594-7_1 |
0.581 |
|
2009 |
Achlioptas D. Random satisfiability Frontiers in Artificial Intelligence and Applications. 185: 245-270. DOI: 10.3233/978-1-58603-929-5-245 |
0.41 |
|
2009 |
Achlioptas D, Clauset A, Kempe D, Moore C. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs Journal of the Acm. 56. DOI: 10.1145/1538902.1538905 |
0.347 |
|
2009 |
Achlioptas D, Ricci-Tersenghi F. Random formulas have frozen variables Siam Journal On Computing. 39: 260-280. DOI: 10.1137/070680382 |
0.43 |
|
2008 |
Achlioptas D. Solution clustering in random satisfiability European Physical Journal B. 64: 395-402. DOI: 10.1140/Epjb/E2008-00324-5 |
0.412 |
|
2008 |
Achlioptas D, Coja-Oghlan A. Algorithmic barriers from phase transitions Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 793-802. DOI: 10.1109/FOCS.2008.11 |
0.425 |
|
2007 |
Achlioptas D, Naor A, Peres Y. On the maximum satisfiability of random formulas Journal of the Acm. 54. DOI: 10.1145/1219092.1219098 |
0.363 |
|
2006 |
Achlioptas D, Moore C. Random k-SAT: Two moments suffice to cross a sharp threshold Siam Journal On Computing. 36: 740-762. DOI: 10.1137/S0097539703434231 |
0.43 |
|
2006 |
Achlioptas D, Ricci-Tersenghi F. On the solution-space geometry of random constraint satisfaction problems Proceedings of the Annual Acm Symposium On Theory of Computing. 2006: 130-139. DOI: 10.1002/Rsa.20323 |
0.427 |
|
2005 |
Achlioptas D, Naor A, Peres Y. Rigorous location of phase transitions in hard optimization problems. Nature. 435: 759-64. PMID 15944693 DOI: 10.1038/Nature03602 |
0.408 |
|
2005 |
Achlioptas D, Naor A. The two possible values of the chromatic number of a random graph Annals of Mathematics. 162: 1335-1351. DOI: 10.4007/Annals.2005.162.1335 |
0.357 |
|
2005 |
Achlioptas D, Jia H, Moore C. Hiding Satisfying Assignments: Two are Better than One Journal of Artificial Intelligence Research. 24: 623-639. DOI: 10.1613/Jair.1681 |
0.479 |
|
2004 |
Achlioptas D, Beame P, Molloy M. A sharp threshold in proof complexity yields lower bounds for satisfiability search Journal of Computer and System Sciences. 68: 238-268. DOI: 10.1016/J.Jcss.2003.07.011 |
0.396 |
|
2004 |
Achlioptas D, Beame P, Molloy M. Exponential Bounds for DPLL Below the Satisfiability Threshold Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 132-133. |
0.332 |
|
2003 |
Achlioptas D. Database-friendly random projections: Johnson-Lindenstrauss with binary coins Journal of Computer and System Sciences. 66: 671-687. DOI: 10.1016/S0022-0000(03)00025-4 |
0.354 |
|
2002 |
Achlioptas D, Kim JH, Krivelevich M, Tetali P. Two-coloring random hypergraphs Random Structures and Algorithms. 20: 249-259. DOI: 10.1002/Rsa.997.Abs |
0.331 |
|
2001 |
Achlioptas D, McSherry F. Fast computation of low rank matrix approximations Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 611-618. DOI: 10.1145/1219092.1219097 |
0.325 |
|
2001 |
Achlioptas D, Molloy MSO, Kirousis LM, Stamatiou YC, Kranakis E, Krizanc D. Random constraint satisfaction: A more accurate picture Constraints. 6: 329-344. DOI: 10.1023/A:1011402324562 |
0.383 |
|
2001 |
Kautz H, Ruan Y, Achlioptas D, Gomes C, Selman B, Stickel M. Balance and filtering in structured satisfiable problems (preliminary report) Electronic Notes in Discrete Mathematics. 9: 2-18. DOI: 10.1016/S1571-0653(04)00310-5 |
0.348 |
|
2001 |
Achlioptas D. Lower bounds for random 3-SAT via differential equations Theoretical Computer Science. 265: 159-185. DOI: 10.1016/S0304-3975(01)00159-1 |
0.476 |
|
2001 |
Achlioptas D, Kirousis LM, Kranakis E, Krizanc D. Rigorous results for random (2+p)-SAT Theoretical Computer Science. 265: 109-129. DOI: 10.1016/S0304-3975(01)00154-2 |
0.386 |
|
2001 |
Achlioptas D, Beame P, Molloy M. A sharp threshold in proof complexity Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 337-346. |
0.344 |
|
2000 |
Achlioptas D, Chrobak M, Noga J. Competitive analysis of randomized paging algorithms Theoretical Computer Science. 234: 203-218. DOI: 10.1016/S0304-3975(98)00116-9 |
0.409 |
|
2000 |
Achlioptas D, Chrobak M, Noga J. Competitive analysis of randomized paging algorithms Theoretical Computer Science. 234: 203-218. |
0.316 |
|
1999 |
Achlioptas D, Molloy M. Almost all graphs with $2.522 n$ edges are not 3-colorable Electronic Journal of Combinatorics. 6: 29. DOI: 10.37236/1461 |
0.409 |
|
1999 |
Edmonds J, Poon CK, Achlioptas D. Tight lower bounds for st-connectivity on the nnjag model Siam Journal On Computing. 28: 2257-2284. DOI: 10.1137/S0097539795295948 |
0.347 |
|
1999 |
Achlioptas D, Friedgut E. A sharp threshold for k-colorability Random Structures and Algorithms. 14: 63-70. DOI: 10.1002/(Sici)1098-2418(1999010)14:1<63::Aid-Rsa3>3.0.Co;2-7 |
0.331 |
|
1999 |
Achlioptas D, Molloy M. Almost all graphs with 2:522n edges are not 3-colorable Electronic Journal of Combinatorics. 6. |
0.316 |
|
1998 |
Achlioptas D, Brown JI, Corneil DG, Molloy MSO. The existence of uniquely -G colourable graphs Discrete Mathematics. 179: 1-11. DOI: 10.1016/S0012-365X(97)00022-8 |
0.331 |
|
1997 |
Achlioptas D. The complexity of G-free colourability Discrete Mathematics. 165: 21-30. |
0.314 |
|
Show low-probability matches. |