Dimitris Achlioptas

According to our database, Dimitris Achlioptas authored at least 89 papers between 1996 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Bounding Weakly Correlated Products from Below: Supermodularity is All You Need.

Dimitris Achlioptas, Kostas Zampetakis

Proceedings of the IEEE International Symposium on Information Theory, 2024

2022

Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method.

Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou

CoRR, 2022

A Simpler Proof of the Four Functions Theorem and Some New Variants.

Dimitris Achlioptas, Kostas Zampetakis

Proceedings of the IEEE International Symposium on Information Theory, 2022

2021

Random Satisfiabiliy.

Dimitris Achlioptas

Proceedings of the Handbook of Satisfiability - Second Edition, 2021

The number of satisfying assignments of random 2-SAT formulas.

Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck, Guangyan Zhou

Random Struct. Algorithms, 2021

The Lovász Local Lemma is Not About Probability.

Dimitris Achlioptas, Kostas Zampetakis

CoRR, 2021

Local Approximations of the Independent Set Polynomial.

Dimitris Achlioptas, Kostas Zampetakis

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018).

Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas

SIAM J. Comput., 2020

The random 2-SAT partition function.

Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck, Guangyan Zhou

CoRR, 2020

Simple Local Computation Algorithms for the General Lovász Local Lemma.

Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Bad Global Minima Exist and SGD Can Reach Them.

Shengchao Liu, Dimitris S. Papailiopoulos, Dimitris Achlioptas

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

A Local Lemma for Focused Stochastic Algorithms.

Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov

SIAM J. Comput., 2019

Model counting with error-correcting codes.

Dimitris Achlioptas, Panos Theodoropoulos

Constraints An Int. J., 2019

Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications.

Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Symmetric graph properties have independent edges.

Dimitris Achlioptas, Paris Siminelakis

Inf. Comput., 2018

Local Computation Algorithms for the Lovász Local Lemma.

Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos

CoRR, 2018

A New Perspective on Stochastic Local Search and the Lovasz Local Lemma.

Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair

CoRR, 2018

Fast and Flexible Probabilistic Model Counting.

Dimitris Achlioptas, Zayd Hammoudeh, Panos Theodoropoulos

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

Fast Sampling of Perfectly Uniform Satisfying Assignments.

Dimitris Achlioptas, Zayd S. Hammoudeh, Panos Theodoropoulos

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

2017

Probabilistic Model Counting with Short XORs.

Dimitris Achlioptas, Panos Theodoropoulos

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28, 2017

Time-invariant LDPC convolutional codes.

Dimitris Achlioptas, S. Hamed Hassani, Wei Liu, Rüdiger L. Urbanke

Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Stochastic Control via Entropy Compression.

Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Skip-Gram - Zipf + Uniform = Vector Additivity.

Alex Gittens, Dimitris Achlioptas, Michael W. Mahoney

Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, 2017

2016

Random Walks That Find Perfect Objects and the Lovász Local Lemma.

Dimitris Achlioptas, Fotis Iliopoulos

J. ACM, 2016

Focused Stochastic Local Search and the Lovász Local Lemma.

Dimitris Achlioptas, Fotis Iliopoulos

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling.

Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

The solution space geometry of random linear equations.

Dimitris Achlioptas, Michael Molloy

Random Struct. Algorithms, 2015

Product Measure Approximation of Symmetric Graph Properties.

Dimitris Achlioptas, Paris Siminelakis

CoRR, 2015

Navigability is a Robust Property.

Dimitris Achlioptas, Paris Siminelakis

Proceedings of the Algorithms and Models for the Web Graph - 12th International Workshop, 2015

Stochastic Integration via Error-Correcting Codes.

Dimitris Achlioptas, Pei Jiang

Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

2014

The Lovász Local Lemma as a Random Walk.

Dimitris Achlioptas, Fotis Iliopoulos

CoRR, 2014

Flash on Rails: Consistent Flash Performance through Redundancy.

Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt

Proceedings of the 2014 USENIX Annual Technical Conference, 2014

Erasure Coding & Read/Write Separation in Flash Storage.

Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt

Proceedings of the 2nd Workshop on Interactions of NVM/Flash with Operating Systems and Workloads, 2014

2013

High performance & low latency in solid-state drives through redundancy.

Dimitris Skourtis, Dimitris Achlioptas, Carlos Maltzahn, Scott A. Brandt

Proceedings of the 1st Workshop on Interactions of NVM/FLASH with Operating Systems and Workloads, 2013

Near-Optimal Entrywise Sampling for Data Matrices.

Dimitris Achlioptas, Zohar Shay Karnin, Edo Liberty

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

2012

Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas.

Dimitris Achlioptas, Ricardo Menchaca-Mendez

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method.

Dimitris Achlioptas, Ricardo Menchaca-Mendez

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion .

Dimitris Achlioptas, Themis Gouleakis

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

On the solution-space geometry of random constraint satisfaction problems.

Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi

Random Struct. Algorithms, 2011

2010

Algorithmic Barriers from Phase Transitions in Graphs.

Dimitris Achlioptas

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

2009

Random Satisfiability.

Dimitris Achlioptas

Proceedings of the Handbook of Satisfiability, 2009

Random Formulas Have Frozen Variables.

Dimitris Achlioptas, Federico Ricci-Tersenghi

SIAM J. Comput., 2009

On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs.

Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore

J. ACM, 2009

2008

Algorithmic Barriers from Phase Transitions.

Dimitris Achlioptas, Amin Coja-Oghlan

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Special Section on Foundations of Computer Science.

Dimitris Achlioptas, Vladlen Koltun

SIAM J. Comput., 2007

On the maximum satisfiability of random formulas.

Dimitris Achlioptas, Assaf Naor, Yuval Peres

J. ACM, 2007

Fast computation of low-rank matrix approximations.

Dimitris Achlioptas, Frank McSherry

J. ACM, 2007

2006

Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold.

Dimitris Achlioptas, Cristopher Moore

SIAM J. Comput., 2006

On the solution-space geometry of random constraint satisfaction problems.

Dimitris Achlioptas, Federico Ricci-Tersenghi

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005

Hiding Satisfying Assignments: Two are Better than One.

Dimitris Achlioptas, Haixia Jia, Cristopher Moore

J. Artif. Intell. Res., 2005

Special Issue on Algorithms and Models for the Web-Graph.

Dimitris Achlioptas, Stefano Leonardi

Internet Math., 2005

On Spectral Learning of Mixtures of Distributions.

Dimitris Achlioptas, Frank McSherry

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004

A sharp threshold in proof complexity yields lower bounds for satisfiability search.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

J. Comput. Syst. Sci., 2004

Summary-based routing for content-based event distribution networks.

Yi-Min Wang, Lili Qiu, Chad Verbowski, Dimitris Achlioptas, Gautam Das, Per-Åke Larson

Comput. Commun. Rev., 2004

The two possible values of the chromatic number of a random graph.

Dimitris Achlioptas, Assaf Naor

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Exponential bounds for DPLL below the satisfiability threshold.

Dimitris Achlioptas, Paul Beame, Michael Molloy

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Random Matrices in Data Analysis.

Dimitris Achlioptas

Proceedings of the Knowledge Discovery in Databases: PKDD 2004, 2004

Sampling Grid Colorings with Fewer Colors.

Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

The Chromatic Number of Random Regular Graphs.

Dimitris Achlioptas, Cristopher Moore

Proceedings of the Approximation, 2004

2003

Almost all graphs with average degree 4 are 3-colorable.

Dimitris Achlioptas, Cristopher Moore

J. Comput. Syst. Sci., 2003

Database-friendly random projections: Johnson-Lindenstrauss with binary coins.

Dimitris Achlioptas

J. Comput. Syst. Sci., 2003

The Threshold for Random k-SAT is 2^kln2 - O(k)

Dimitris Achlioptas, Yuval Peres

CoRR, 2003

The threshold for random k-SAT is 2^k (ln 2 - O(k)).

Dimitris Achlioptas, Yuval Peres

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Two-coloring random hypergraphs.

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali

Random Struct. Algorithms, 2002

On the 2-Colorability of Random Hypergraphs.

Dimitris Achlioptas, Cristopher Moore

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

The Asymptotic Order of the Random k -SAT Threshold.

Dimitris Achlioptas, Cristopher Moore

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Rigorous results for random (2+p)-SAT.

Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc

Theor. Comput. Sci., 2001

Lower bounds for random 3-SAT via differential equations.

Dimitris Achlioptas

Theor. Comput. Sci., 2001

Balance and Filtering in Structured Satisfiable Problems (Preliminary Report).

Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel

Electron. Notes Discret. Math., 2001

Random Constraint Satisfaction: A More Accurate Picture.

Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Krizanc

Constraints An Int. J., 2001

Fast computation of low rank matrix.

Dimitris Achlioptas, Frank McSherry

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A sharp threshold in proof complexity.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

The phase transition in 1-in-k SAT and NAE 3-SAT.

Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Database-friendly random projections.

Dimitris Achlioptas

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Sampling Techniques for Kernel Methods.

Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf

Proceedings of the Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, 2001

Balance and Filtering in Structured Satisfiable Problems.

Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel

Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001

Web Search via Hub Synthesis.

Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Competitive analysis of randomized paging algorithms.

Dimitris Achlioptas, Marek Chrobak, John Noga

Theor. Comput. Sci., 2000

Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract).

Dimitris Achlioptas

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Optimal myopic algorithms for random 3-SAT.

Dimitris Achlioptas, Gregory B. Sorkin

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Generating Satisfiable Problem Instances.

Dimitris Achlioptas, Carla P. Gomes, Henry A. Kautz, Bart Selman

Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30, 2000

1999

Threshold phenomena in random graph colouring and satisfiability.

Dimitris Achlioptas

PhD thesis, 1999

Tight Lower Bounds for st-Connectivity on the NNJAG Model.

Jeff Edmonds, Chung Keung Poon, Dimitris Achlioptas

SIAM J. Comput., 1999

A Sharp Threshold for k-Colorability.

Dimitris Achlioptas, Ehud Friedgut

Random Struct. Algorithms, 1999

Almost all graphs with 2.522 n edges are not 3-colorable.

Dimitris Achlioptas, Michael Molloy

Electron. J. Comb., 1999

1998

The existence of uniquely -G colourable graphs.

Dimitris Achlioptas, Jason I. Brown, Derek G. Corneil, Michael Molloy

Discret. Math., 1998

1997

The complexity of G-free colourability.

Demetrios Achlioptas

Discret. Math., 1997

The Analysis of a List-Coloring Algorithm on a Random Graph.

Dimitris Achlioptas, Michael S. O. Molloy

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Competive Analysis of Randomized Paging Algorithms.

Dimitris Achlioptas, Marek Chrobak, John Noga

Proceedings of the Algorithms, 1996