research unit 1
 

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit Aigaion.nl.SourceForge.hetLogo

Achlioptas, Dimitris    

Firstname:Dimitris 
Surname:Achlioptas 
Email:optas@cs.ucsc.edu 
Institute:RACTI 
Homepage:http://ru1.cti.gr/index.php/pe... 
Is RU1 member:YES 

15 publications (0 read)

11 Keywords relate to this author

Algorithms
Computational complexity
Constraint satisfaction problems
K-SAT
Lov{\'a}sz Local Lemma
Phase transitions
Probabilistic Method
Random formulas
Random structures
Satisfiability
Statistical mechanics




Publications as Author



2012

[RACTI-RU1-2012-19] Achlioptas, Dimitris and Menchaca-Mendez, Ricardo, Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas, in: SAT, pages 327-340, 15th International Conference, Trento, Italy, June 17-20, 2012., 2012. [DOI]
 
[RACTI-RU1-2012-18] Achlioptas, Dimitris and Menchaca-Mendez, Ricardo, Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method, in: ICALP (1), pages 1-12, Springer Berlin Heidelberg, 39th International Colloquium, ICALP 2012, July 9-13, 2012, Proceedings, Part I, Warwick, UK, 2012. [DOI]
 
[RACTI-RU1-2012-17] Achlioptas, Dimitris and Gouleakis, Themis, Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion, in: FSTTCS, pages 16-23, 2012.
 

2011

[RACTI-RU1-2011-51] Achlioptas, Dimitris, Coja-Oghlan, A. and Ricci-Tersenghi, F., On the solution-space geometry of random constraint satisfaction problems, in: Random Struct. Algorithms, volume 38, number 3, pages 251-268, 2011.
 
[RACTI-RU1-2011-50] Achlioptas, Dimitris and Molloy, M, The solution space geometry of random linear equations, in: CoRR, volume abs/1107.5550, 2011.
 

2010

[RACTI-RU1-2010-45] Achlioptas, Dimitris, Algorithmic Barriers from Phase Transitions in Graphs, in: 36th International Workshop on Graph Theoretic, 2010.
 
[RACTI-RU1-2010-27] Achlioptas, Dimitris, Coja-Oghlan, A. and Ricci-Tersenghi, F., On the solution-space geometry of random constraint satisfaction problems, in: Random Structures and Algorithms, 2010.
 

2009

[RACTI-RU1-2009-71] Achlioptas, Dimitris and Ricci-Tersenghi, F., Random formulas have frozen variables, in: SIAM: Journal on Computing, volume 39, pages 260-280, 2009.
 
[RACTI-RU1-2009-70] Achlioptas, Dimitris, Souza, D. and Spencer, J., Explosive percolation in random networks, in: Science, volume 323, pages 1453-1455, 2009.
 
[RACTI-RU1-2009-68] Achlioptas, Dimitris, Clauset, Aaron, Kempe, David and Moore, Chris, On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs, in: Journal of the ACM, volume 56, 2009.
 
[RACTI-RU1-2009-66] Achlioptas, Dimitris, Random Satisfiability, pages 245-270, chapter in the book: Handbook of Satisfiability, IOS Press 2009, 2009.
 

2008

[RACTI-RU1-2008-82] Achlioptas, Dimitris, Solution clustering in random satisfiability, in: European Physics Journal B, volume 64, pages 395-402, 2008.
 
[RACTI-RU1-2008-81] Achlioptas, Dimitris and Coja-Oghlan, A., Algorithmic Barriers from Phase Transitions, in: In 49th Ann. Symp. on Foundations of Computer Science (FOCS 2008), pages 793-802, 2008.
 

2001

[RACTI-RU1-2001-3] Achlioptas, Dimitris, Kirousis, Lefteris, Kranakis, Evangelos, Krizanc, Danny, Molloy, M and Stamatiou, Yannis, Random constraint satisfaction: a more accurate picture, in: Constraints, volume 6, number 4, pages 329-344, 2001.
 
[RACTI-RU1-2001-2] Achlioptas, Dimitris, Kirousis, Lefteris, Kranakis, Evangelos and Krizanc, Danny, Rigorous results for random (2 + p)-SAT, in: Theoretical Computer Science (TCS), volume 265, pages 109-129, 2001.