Dimitris Achlioptas

111 papers A* 27A 7B 6C 1Journal 51Unranked 15
YearRankTypeTitle / Venue / Authors
2024 B conf
Bounding Weakly Correlated Products from Below: Supermodularity is All You Need.
ISIT
Dimitris Achlioptas, Kostas Zampetakis
2022 B conf
A Simpler Proof of the Four Functions Theorem and Some New Variants.
ISIT
Dimitris Achlioptas, Kostas Zampetakis
2022 J jnl
Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method.
CoRR
Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou
2021 A* conf
Local Approximations of the Independent Set Polynomial.
ICALP
Dimitris Achlioptas, Kostas Zampetakis
2021 — ch.
Random Satisfiabiliy.
Handbook of Satisfiability
Dimitris Achlioptas
2021 J jnl
The Lovász Local Lemma is Not About Probability.
CoRR
Dimitris Achlioptas, Kostas Zampetakis
2021 J jnl
The number of satisfying assignments of random 2-SAT formulas.
Random Struct. Algorithms
Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck, Guangyan Zhou
2020 A* conf
Bad Global Minima Exist and SGD Can Reach Them.
NeurIPS
Shengchao Liu, Dimitris S. Papailiopoulos, Dimitris Achlioptas
2020 B conf
Simple Local Computation Algorithms for the General Lovász Local Lemma.
SPAA
Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos
2020 J jnl
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018).
SIAM J. Comput.
Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas
2020 J jnl
The random 2-SAT partition function.
CoRR
Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck, Guangyan Zhou
2019 J jnl
A Local Lemma for Focused Stochastic Algorithms.
SIAM J. Comput.
Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov
2019 — ed.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20-22, 2019
APPROX-RANDOM
Dimitris Achlioptas, László A. Végh
2019 J jnl
Bad Global Minima Exist and SGD Can Reach Them.
CoRR
Shengchao Liu, Dimitris S. Papailiopoulos, Dimitris Achlioptas
2019 A* conf
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications.
FOCS
Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair
2019 J jnl
Model counting with error-correcting codes.
Constraints An Int. J.
Dimitris Achlioptas, Panos Theodoropoulos
2018 J jnl
A Local Lemma for Focused Stochastic Algorithms.
CoRR
Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov
2018 J jnl
A New Perspective on Stochastic Local Search and the Lovasz Local Lemma.
CoRR
Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair
2018 A conf
Fast Sampling of Perfectly Uniform Satisfying Assignments.
SAT
Dimitris Achlioptas, Zayd S. Hammoudeh, Panos Theodoropoulos
2018 A conf
Fast and Flexible Probabilistic Model Counting.
SAT
Dimitris Achlioptas, Zayd Hammoudeh, Panos Theodoropoulos
2018 J jnl
Local Computation Algorithms for the Lovász Local Lemma.
CoRR
Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos
2018 J jnl
Symmetric graph properties have independent edges.
Inf. Comput.
Dimitris Achlioptas, Paris Siminelakis
2017 A conf
Probabilistic Model Counting with Short XORs.
SAT
Dimitris Achlioptas, Panos Theodoropoulos
2017 J jnl
Probabilistic Model Counting with Short XORs.
CoRR
Dimitris Achlioptas, Panos Theodoropoulos
2017 — conf
Skip-Gram - Zipf + Uniform = Vector Additivity.
ACL (1)
Alex Gittens, Dimitris Achlioptas, Michael W. Mahoney
2017 A* conf
Stochastic Control via Entropy Compression.
ICALP
Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis
2017 J jnl
Time-Invariant LDPC Convolutional Codes.
CoRR
Dimitris Achlioptas, Seyed Hamed Hassani, Wei Liu, Rüdiger L. Urbanke
2017 B conf
Time-invariant LDPC convolutional codes.
ISIT
Dimitris Achlioptas, S. Hamed Hassani, Wei Liu, Rüdiger L. Urbanke
2016 A* conf
Bounds for Random Constraint Satisfaction Problems via Spatial Coupling.
SODA
Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke
2016 A* conf
Focused Stochastic Local Search and the Lovász Local Lemma.
SODA
Dimitris Achlioptas, Fotis Iliopoulos
2016 J jnl
Random Walks That Find Perfect Objects and the Lovász Local Lemma.
J. ACM
Dimitris Achlioptas, Fotis Iliopoulos
2016 J jnl
Stochastic Control via Entropy Compression.
CoRR
Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis
2015 J jnl
Focused Stochastic Local Search and the Lovász Local Lemma.
CoRR
Dimitris Achlioptas, Fotis Iliopoulos
2015 C conf
Navigability is a Robust Property.
WAW
Dimitris Achlioptas, Paris Siminelakis
2015 J jnl
Navigability is a Robust Property.
CoRR
Dimitris Achlioptas, Paris Siminelakis
2015 J jnl
Product Measure Approximation of Symmetric Graph Properties.
CoRR
Dimitris Achlioptas, Paris Siminelakis
2015 A conf
Stochastic Integration via Error-Correcting Codes.
UAI
Dimitris Achlioptas, Pei Jiang
2015 — conf
Symmetric Graph Properties Have Independent Edges.
ICALP (2)
Dimitris Achlioptas, Paris Siminelakis
2015 J jnl
The solution space geometry of random linear equations.
Random Struct. Algorithms
Dimitris Achlioptas, Michael Molloy
2014 — conf
Erasure Coding & Read/Write Separation in Flash Storage.
INFLOW
Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt
2014 — conf
Flash on Rails: Consistent Flash Performance through Redundancy.
USENIX ATC
Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt
2014 A* conf
Random Walks That Find Perfect Objects and the Lovasz Local Lemma.
FOCS
Dimitris Achlioptas, Fotis Iliopoulos
2014 J jnl
The Lovász Local Lemma as a Random Walk.
CoRR
Dimitris Achlioptas, Fotis Iliopoulos
2013 — conf
High performance & low latency in solid-state drives through redundancy.
INFLOW@SOSP
Dimitris Skourtis, Dimitris Achlioptas, Carlos Maltzahn, Scott A. Brandt
2013 — conf
Near-Optimal Entrywise Sampling for Data Matrices.
NIPS
Dimitris Achlioptas, Zohar Shay Karnin, Edo Liberty
2013 J jnl
Near-Optimal Entrywise Sampling for Data Matrices.
CoRR
Dimitris Achlioptas, Zohar Shay Karnin, Edo Liberty
2012 — conf
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion .
FSTTCS
Dimitris Achlioptas, Themis Gouleakis
2012 A conf
Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas.
SAT
Dimitris Achlioptas, Ricardo Menchaca-Méndez
2012 — conf
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method.
ICALP (1)
Dimitris Achlioptas, Ricardo Menchaca-Méndez
2011 J jnl
On the solution-space geometry of random constraint satisfaction problems.
Random Struct. Algorithms
Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi
2011 J jnl
The solution space geometry of random linear equations
CoRR
Dimitris Achlioptas, Michael Molloy
2010 B conf
Algorithmic Barriers from Phase Transitions in Graphs.
WG
Dimitris Achlioptas
2009 J jnl
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs.
J. ACM
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
2009 J jnl
Random Formulas Have Frozen Variables.
SIAM J. Comput.
Dimitris Achlioptas, Federico Ricci-Tersenghi
2009 — ch.
Random Satisfiability.
Handbook of Satisfiability
Dimitris Achlioptas
2008 A* conf
Algorithmic Barriers from Phase Transitions.
FOCS
Dimitris Achlioptas, Amin Coja-Oghlan
2007 J jnl
Fast computation of low-rank matrix approximations.
J. ACM
Dimitris Achlioptas, Frank McSherry
2007 J jnl
On the maximum satisfiability of random formulas.
J. ACM
Dimitris Achlioptas, Assaf Naor, Yuval Peres
2007 J jnl
Special Section on Foundations of Computer Science.
SIAM J. Comput.
Dimitris Achlioptas, Vladlen Koltun
2006 J jnl
On the Solution-Space Geometry of Random Constraint Satisfaction Problems
CoRR
Dimitris Achlioptas, Federico Ricci-Tersenghi
2006 A* conf
On the solution-space geometry of random constraint satisfaction problems.
STOC
Dimitris Achlioptas, Federico Ricci-Tersenghi
2006 J jnl
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold.
SIAM J. Comput.
Dimitris Achlioptas, Cristopher Moore
2005 J jnl
Hiding Satisfying Assignments: Two are Better than One
CoRR
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
2005 J jnl
Hiding Satisfying Assignments: Two are Better than One.
J. Artif. Intell. Res.
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
2005 A* conf
On Spectral Learning of Mixtures of Distributions.
COLT
Dimitris Achlioptas, Frank McSherry
2005 J jnl
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
CoRR
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
2005 A* conf
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs.
STOC
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
2005 J jnl
Special Issue on Algorithms and Models for the Web-Graph.
Internet Math.
Dimitris Achlioptas, Stefano Leonardi
2004 J jnl
A sharp threshold in proof complexity yields lower bounds for satisfiability search.
J. Comput. Syst. Sci.
Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
2004 A* conf
Exponential bounds for DPLL below the satisfiability threshold.
SODA
Dimitris Achlioptas, Paul Beame, Michael Molloy
2004 A* conf
Hiding Satisfying Assignments: Two Are Better than One.
AAAI
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
2004 — conf
Random Matrices in Data Analysis.
ECML
Dimitris Achlioptas
2004 — conf
Random Matrices in Data Analysis.
PKDD
Dimitris Achlioptas
2004 B conf
Sampling Grid Colorings with Fewer Colors.
LATIN
Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel
2004 J jnl
Summary-based routing for content-based event distribution networks.
Comput. Commun. Rev.
Yi-Min Wang, Lili Qiu, Chad Verbowski, Dimitris Achlioptas, Gautam Das, Per-Åke Larson
2004 — conf
The Chromatic Number of Random Regular Graphs.
APPROX-RANDOM
Dimitris Achlioptas, Cristopher Moore
2004 A* conf
The two possible values of the chromatic number of a random graph.
STOC
Dimitris Achlioptas, Assaf Naor
2003 J jnl
Almost all graphs with average degree 4 are 3-colorable.
J. Comput. Syst. Sci.
Dimitris Achlioptas, Cristopher Moore
2003 J jnl
Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
J. Comput. Syst. Sci.
Dimitris Achlioptas
2003 A* conf
On the Maximum Satisfiability of Random Formulas.
FOCS
Dimitris Achlioptas, Assaf Naor, Yuval Peres
2003 J jnl
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold
CoRR
Dimitris Achlioptas, Cristopher Moore
2003 J jnl
The Threshold for Random k-SAT is 2
CoRR
Dimitris Achlioptas, Yuval Peres
2003 A* conf
The threshold for random k-SAT is 2
STOC
Dimitris Achlioptas, Yuval Peres
2002 A* conf
Almost all graphs with average degree 4 are 3-colorable.
STOC
Dimitris Achlioptas, Cristopher Moore
2002 — conf
On the 2-Colorability of Random Hypergraphs.
RANDOM
Dimitris Achlioptas, Cristopher Moore
2002 A* conf
The Asymptotic Order of the Random k -SAT Threshold.
FOCS
Dimitris Achlioptas, Cristopher Moore
2002 J jnl
Two-coloring random hypergraphs.
Random Struct. Algorithms
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
2001 A* conf
A sharp threshold in proof complexity.
STOC
Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy
2001 J jnl
Balance and Filtering in Structured Satisfiable Problems (Preliminary Report).
Electron. Notes Discret. Math.
Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel
2001 A* conf
Balance and Filtering in Structured Satisfiable Problems.
IJCAI
Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel
2001 A* conf
Database-friendly random projections.
PODS
Dimitris Achlioptas
2001 A* conf
Fast computation of low rank matrix.
STOC
Dimitris Achlioptas, Frank McSherry
2001 J jnl
Lower bounds for random 3-SAT via differential equations.
Theor. Comput. Sci.
Dimitris Achlioptas
2001 J jnl
Random Constraint Satisfaction: A More Accurate Picture.
Constraints An Int. J.
Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Krizanc
2001 J jnl
Rigorous results for random (2+p)-SAT.
Theor. Comput. Sci.
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc
2001 — conf
Sampling Techniques for Kernel Methods.
NIPS
Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf
2001 A* conf
The phase transition in 1-in-k SAT and NAE 3-SAT.
SODA
Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore
2001 A* conf
Web Search via Hub Synthesis.
FOCS
Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry
2000 J jnl
Competitive analysis of randomized paging algorithms.
Theor. Comput. Sci.
Dimitris Achlioptas, Marek Chrobak, John Noga
2000 — conf
Generating Satisfiable Problem Instances.
AAAI/IAAI
Dimitris Achlioptas, Carla P. Gomes, Henry A. Kautz, Bart Selman
2000 A* conf
Optimal myopic algorithms for random 3-SAT.
FOCS
Dimitris Achlioptas, Gregory B. Sorkin
2000 A* conf
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract).
STOC
Dimitris Achlioptas
2000 — conf
Two-coloring Random Hypergraphs.
ICALP Satellite Workshops
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
1999 J jnl
A Sharp Threshold for k-Colorability.
Random Struct. Algorithms
Dimitris Achlioptas, Ehud Friedgut
1999 J jnl
Almost all graphs with 2.522 n edges are not 3-colorable.
Electron. J. Comb.
Dimitris Achlioptas, Michael Molloy
1999 — —
Threshold phenomena in random graph colouring and satisfiability.
Dimitris Achlioptas
1999 J jnl
Tight Lower Bounds for st-Connectivity on the NNJAG Model.
SIAM J. Comput.
Jeff Edmonds, Chung Keung Poon, Dimitris Achlioptas
1998 J jnl
The existence of uniquely -G colourable graphs.
Discret. Math.
Dimitris Achlioptas, Jason I. Brown, Derek G. Corneil, Michael Molloy
1997 A conf
Random Constraint Satisfaction: A More Accurate Picture.
CP
Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. O. Molloy, Yannis C. Stamatiou
1997 A* conf
The Analysis of a List-Coloring Algorithm on a Random Graph.
FOCS
Dimitris Achlioptas, Michael S. O. Molloy
1996 A conf
Competive Analysis of Randomized Paging Algorithms.
ESA
Dimitris Achlioptas, Marek Chrobak, John Noga