Dimitris Achlioptas

According to our database1, Dimitris Achlioptas authored at least 73 papers between 1996 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

2019
Model counting with error-correcting codes.
Constraints, 2019

2018
Fast and Flexible Probabilistic Model Counting.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

Fast Sampling of Perfectly Uniform Satisfying Assignments.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2018, 2018

2017
Probabilistic Model Counting with Short XORs.
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.
Proceedings of the 2017 IEEE International Symposium on Information Theory, 2017

Stochastic Control via Entropy Compression.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Skip-Gram - Zipf + Uniform = Vector Additivity.
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.
J. ACM, 2016

Focused Stochastic Local Search and the Lovász Local Lemma.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Bounds for Random Constraint Satisfaction Problems via Spatial Coupling.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015
The solution space geometry of random linear equations.
Random Struct. Algorithms, 2015

Navigability is a Robust Property.
Proceedings of the Algorithms and Models for the Web Graph - 12th International Workshop, 2015

Stochastic Integration via Error-Correcting Codes.
Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, 2015

Symmetric Graph Properties Have Independent Edges.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Flash on Rails: Consistent Flash Performance through Redundancy.
Proceedings of the 2014 USENIX Annual Technical Conference, 2014

Erasure Coding & Read/Write Separation in Flash Storage.
Proceedings of the 2nd Workshop on Interactions of NVM/Flash with Operating Systems and Workloads, 2014

Random Walks That Find Perfect Objects and the Lovasz Local Lemma.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
High performance & low latency in solid-state drives through redundancy.
Proceedings of the 1st Workshop on Interactions of NVM/FLASH with Operating Systems and Workloads, 2013

Near-Optimal Entrywise Sampling for Data Matrices.
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.
Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2012, 2012

Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion .
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.
Random Struct. Algorithms, 2011

2010
Algorithmic Barriers from Phase Transitions in Graphs.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

2009
Random Satisfiability.
Proceedings of the Handbook of Satisfiability, 2009

Random Formulas Have Frozen Variables.
SIAM J. Comput., 2009

2008
Algorithmic Barriers from Phase Transitions.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
Special Section on Foundations of Computer Science.
SIAM J. Comput., 2007

Fast computation of low-rank matrix approximations.
J. ACM, 2007

2006
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold.
SIAM J. Comput., 2006

On the solution-space geometry of random constraint satisfaction problems.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

2005
Special Issue on Algorithms and Models for the Web-Graph.
Internet Mathematics, 2005

On the bias of traceroute sampling: or, power-law degree distributions in regular graphs.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

On Spectral Learning of Mixtures of Distributions.
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.
J. Comput. Syst. Sci., 2004

Summary-based routing for content-based event distribution networks.
Computer Communication Review, 2004

The two possible values of the chromatic number of a random graph.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Exponential bounds for DPLL below the satisfiability threshold.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Random Matrices in Data Analysis.
Proceedings of the Knowledge Discovery in Databases: PKDD 2004, 2004

Sampling Grid Colorings with Fewer Colors.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Random Matrices in Data Analysis.
Proceedings of the Machine Learning: ECML 2004, 2004

The Chromatic Number of Random Regular Graphs.
Proceedings of the Approximation, 2004

Hiding Satisfying Assignments: Two Are Better than One.
Proceedings of the Nineteenth National Conference on Artificial Intelligence, 2004

2003
Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
J. Comput. Syst. Sci., 2003

The threshold for random k-SAT is 2k (ln 2 - O(k)).
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

On the Maximum Satisfiability of Random Formulas.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Almost all graphs with average degree 4 are 3-colorable.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

On the 2-Colorability of Random Hypergraphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

The Asymptotic Order of the Random k -SAT Threshold.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Rigorous results for random (2+p)-SAT.
Theor. Comput. Sci., 2001

Lower bounds for random 3-SAT via differential equations.
Theor. Comput. Sci., 2001

Balance and Filtering in Structured Satisfiable Problems (Preliminary Report).
Electronic Notes in Discrete Mathematics, 2001

Random Constraint Satisfaction: A More Accurate Picture.
Constraints, 2001

Fast computation of low rank matrix.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A sharp threshold in proof complexity.
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.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

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

Sampling Techniques for Kernel Methods.
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.
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001

Web Search via Hub Synthesis.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Competitive analysis of randomized paging algorithms.
Theor. Comput. Sci., 2000

Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Two-coloring Random Hypergraphs.
Proceedings of the ICALP Workshops 2000, 2000

Optimal myopic algorithms for random 3-SAT.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Generating Satisfiable Problem Instances.
Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, July 30, 2000

1999
Tight Lower Bounds for st-Connectivity on the NNJAG Model.
SIAM J. Comput., 1999

A Sharp Threshold for k-Colorability.
Random Struct. Algorithms, 1999

Almost all graphs with 2.522 n edges are not 3-colorable.
Electr. J. Comb., 1999

1998
The existence of uniquely -G colourable graphs.
Discrete Mathematics, 1998

1997
The complexity of G-free colourability.
Discrete Mathematics, 1997

The Analysis of a List-Coloring Algorithm on a Random Graph.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Random Constraint Satisfaction: A More Accurate Picture.
Proceedings of the Principles and Practice of Constraint Programming - CP97, Third International Conference, Linz, Austria, October 29, 1997

1996
Competive Analysis of Randomized Paging Algorithms.
Proceedings of the Algorithms, 1996


  Loading...