default search action
Dimitris Achlioptas
Demetrios Achlioptas
Person information
- affiliation: University of Athens, Athens, Greece
- affiliation (former): University of California, Santa Cruz
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c56]Dimitris Achlioptas, Kostas Zampetakis:
Bounding Weakly Correlated Products from Below: Supermodularity is All You Need. ISIT 2024: 3035-3040 - 2022
- [c55]Dimitris Achlioptas, Kostas Zampetakis:
A Simpler Proof of the Four Functions Theorem and Some New Variants. ISIT 2022: 714-717 - [i21]Dimitris Achlioptas, Amrit Daswaney, Periklis A. Papakonstantinou:
Hide and Seek: Scaling Machine Learning for Combinatorial Optimization via the Probabilistic Method. CoRR abs/2211.15368 (2022) - 2021
- [j31]Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth
, Joon Lee
The number of satisfying assignments of random 2-SAT formulas. Random Struct. Algorithms 58(4): 609-647 (2021) - [c54]Dimitris Achlioptas, Kostas Zampetakis:
Local Approximations of the Independent Set Polynomial. ICALP 2021: 8:1-8:16 - [p2]Dimitris Achlioptas:
Random Satisfiabiliy. Handbook of Satisfiability 2021: 437-462 - [i20]Dimitris Achlioptas, Kostas Zampetakis:
The Lovász Local Lemma is Not About Probability. CoRR abs/2111.08837 (2021) - 2020
- [j30]Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas:
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018). SIAM J. Comput. 49(5) (2020) - [c53]Shengchao Liu, Dimitris S. Papailiopoulos, Dimitris Achlioptas:
Bad Global Minima Exist and SGD Can Reach Them. NeurIPS 2020 - [c52]Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos:
Simple Local Computation Algorithms for the General Lovász Local Lemma. SPAA 2020: 1-10 - [i19]Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck
The random 2-SAT partition function. CoRR abs/2002.03690 (2020)
2010 – 2019
- 2019
- [j29]Dimitris Achlioptas
Model counting with error-correcting codes. Constraints An Int. J. 24(2): 162-182 (2019) - [j28]Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov:
A Local Lemma for Focused Stochastic Algorithms. SIAM J. Comput. 48(5): 1583-1602 (2019) - [c51]Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair:
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications. FOCS 2019: 725-744 - [e1]Dimitris Achlioptas, László A. Végh:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA. LIPIcs 145, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2019, ISBN 978-3-95977-125-2 [contents] - [i18]Shengchao Liu, Dimitris S. Papailiopoulos, Dimitris Achlioptas:
Bad Global Minima Exist and SGD Can Reach Them. CoRR abs/1906.02613 (2019) - 2018
- [j27]Dimitris Achlioptas, Paris Siminelakis
Symmetric graph properties have independent edges. Inf. Comput. 261: 446-463 (2018) - [c50]Dimitris Achlioptas, Zayd S. Hammoudeh, Panos Theodoropoulos:
Fast Sampling of Perfectly Uniform Satisfying Assignments. SAT 2018: 135-147 - [c49]Dimitris Achlioptas, Zayd Hammoudeh, Panos Theodoropoulos:
Fast and Flexible Probabilistic Model Counting. SAT 2018: 148-164 - [i17]Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair:
A New Perspective on Stochastic Local Search and the Lovasz Local Lemma. CoRR abs/1805.02026 (2018) - [i16]Dimitris Achlioptas, Fotis Iliopoulos, Vladimir Kolmogorov:
A Local Lemma for Focused Stochastic Algorithms. CoRR abs/1809.01537 (2018) - [i15]Dimitris Achlioptas, Themis Gouleakis, Fotis Iliopoulos:
Local Computation Algorithms for the Lovász Local Lemma. CoRR abs/1809.07910 (2018) - 2017
- [c48]Alex Gittens, Dimitris Achlioptas, Michael W. Mahoney:
Skip-Gram - Zipf + Uniform = Vector Additivity. ACL (1) 2017: 69-76 - [c47]Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis:
Stochastic Control via Entropy Compression. ICALP 2017: 83:1-83:13 - [c46]Dimitris Achlioptas, S. Hamed Hassani, Wei Liu, Rüdiger L. Urbanke:
Time-invariant LDPC convolutional codes. ISIT 2017: 366-370 - [c45]Dimitris Achlioptas, Panos Theodoropoulos:
Probabilistic Model Counting with Short XORs. SAT 2017: 3-19 - [i14]Dimitris Achlioptas, Seyed Hamed Hassani, Wei Liu, Rüdiger L. Urbanke:
Time-Invariant LDPC Convolutional Codes. CoRR abs/1702.04539 (2017) - [i13]Dimitris Achlioptas, Panos Theodoropoulos:
Probabilistic Model Counting with Short XORs. CoRR abs/1707.09467 (2017) - 2016
- [j26]Dimitris Achlioptas, Fotis Iliopoulos:
Random Walks That Find Perfect Objects and the Lovász Local Lemma. J. ACM 63(3): 22:1-22:29 (2016) - [c44]Dimitris Achlioptas, Seyed Hamed Hassani, Nicolas Macris, Rüdiger L. Urbanke:
Bounds for Random Constraint Satisfaction Problems via Spatial Coupling. SODA 2016: 469-479 - [c43]Dimitris Achlioptas, Fotis Iliopoulos:
Focused Stochastic Local Search and the Lovász Local Lemma. SODA 2016: 2024-2038 - [i12]Dimitris Achlioptas, Fotis Iliopoulos, Nikos Vlassis:
Stochastic Control via Entropy Compression. CoRR abs/1607.06494 (2016) - 2015
- [j25]Dimitris Achlioptas, Michael Molloy:
The solution space geometry of random linear equations. Random Struct. Algorithms 46(2): 197-231 (2015) - [c42]Dimitris Achlioptas, Paris Siminelakis
Symmetric Graph Properties Have Independent Edges. ICALP (2) 2015: 467-478 - [c41]Dimitris Achlioptas, Pei Jiang:
Stochastic Integration via Error-Correcting Codes. UAI 2015: 22-31 - [c40]Dimitris Achlioptas, Paris Siminelakis
Navigability is a Robust Property. WAW 2015: 78-91 - [i11]Dimitris Achlioptas, Paris Siminelakis:
Navigability is a Robust Property. CoRR abs/1501.04931 (2015) - [i10]Dimitris Achlioptas, Paris Siminelakis:
Product Measure Approximation of Symmetric Graph Properties. CoRR abs/1502.07787 (2015) - [i9]Dimitris Achlioptas, Fotis Iliopoulos:
Focused Stochastic Local Search and the Lovász Local Lemma. CoRR abs/1507.07633 (2015) - 2014
- [c39]Dimitris Achlioptas, Fotis Iliopoulos:
Random Walks That Find Perfect Objects and the Lovasz Local Lemma. FOCS 2014: 494-503 - [c38]Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt:
Erasure Coding & Read/Write Separation in Flash Storage. INFLOW 2014 - [c37]Dimitris Skourtis, Dimitris Achlioptas, Noah Watkins, Carlos Maltzahn, Scott A. Brandt:
Flash on Rails: Consistent Flash Performance through Redundancy. USENIX ATC 2014: 463-474 - [i8]Dimitris Achlioptas, Fotis Iliopoulos:
The Lovász Local Lemma as a Random Walk. CoRR abs/1406.0242 (2014) - 2013
- [c36]Dimitris Achlioptas, Zohar Shay Karnin, Edo Liberty:
Near-Optimal Entrywise Sampling for Data Matrices. NIPS 2013: 1565-1573 - [c35]Dimitris Skourtis, Dimitris Achlioptas, Carlos Maltzahn, Scott A. Brandt:
High performance & low latency in solid-state drives through redundancy. INFLOW@SOSP 2013: 6:1-6:9 - [i7]Dimitris Achlioptas, Zohar Shay Karnin, Edo Liberty:
Near-Optimal Entrywise Sampling for Data Matrices. CoRR abs/1311.4643 (2013) - 2012
- [c34]Dimitris Achlioptas, Themis Gouleakis:
Algorithmic Improvements of the Lovász Local Lemma via Cluster Expansion . FSTTCS 2012: 16-23 - [c33]Dimitris Achlioptas, Ricardo Menchaca-Mendez
Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method. ICALP (1) 2012: 1-12 - [c32]Dimitris Achlioptas, Ricardo Menchaca-Mendez
Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas. SAT 2012: 327-340 - 2011
- [j24]Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi
On the solution-space geometry of random constraint satisfaction problems. Random Struct. Algorithms 38(3): 251-268 (2011) - [i6]Dimitris Achlioptas, Michael Molloy:
The solution space geometry of random linear equations. CoRR abs/1107.5550 (2011) - 2010
- [c31]Dimitris Achlioptas:
Algorithmic Barriers from Phase Transitions in Graphs. WG 2010: 1
2000 – 2009
- 2009
- [j23]Dimitris Achlioptas, Aaron Clauset
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM 56(4): 21:1-21:28 (2009) - [j22]Dimitris Achlioptas, Federico Ricci-Tersenghi
Random Formulas Have Frozen Variables. SIAM J. Comput. 39(1): 260-280 (2009) - [p1]Dimitris Achlioptas:
Random Satisfiability. Handbook of Satisfiability 2009: 245-270 - 2008
- [c30]Dimitris Achlioptas, Amin Coja-Oghlan:
Algorithmic Barriers from Phase Transitions. FOCS 2008: 793-802 - 2007
- [j21]Dimitris Achlioptas, Frank McSherry:
Fast computation of low-rank matrix approximations. J. ACM 54(2): 9 (2007) - [j20]Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the maximum satisfiability of random formulas. J. ACM 54(2): 10 (2007) - [j19]Dimitris Achlioptas, Vladlen Koltun:
Special Section on Foundations of Computer Science. SIAM J. Comput. 37(1): 165 (2007) - 2006
- [j18]Dimitris Achlioptas, Cristopher Moore
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. SIAM J. Comput. 36(3): 740-762 (2006) - [c29]Dimitris Achlioptas, Federico Ricci-Tersenghi:
On the solution-space geometry of random constraint satisfaction problems. STOC 2006: 130-139 - [i5]Dimitris Achlioptas, Federico Ricci-Tersenghi:
On the Solution-Space Geometry of Random Constraint Satisfaction Problems. CoRR abs/cs/0611052 (2006) - 2005
- [j17]Dimitris Achlioptas, Stefano Leonardi:
Special Issue on Algorithms and Models for the Web-Graph. Internet Math. 2(3): 249 (2005) - [j16]Dimitris Achlioptas, Haixia Jia, Cristopher Moore
Hiding Satisfying Assignments: Two are Better than One. J. Artif. Intell. Res. 24: 623-639 (2005) - [c28]Dimitris Achlioptas, Frank McSherry:
On Spectral Learning of Mixtures of Distributions. COLT 2005: 458-469 - [c27]Dimitris Achlioptas, Aaron Clauset
On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. STOC 2005: 694-703 - [i4]Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore:
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs. CoRR abs/cond-mat/0503087 (2005) - [i3]Dimitris Achlioptas, Haixia Jia, Cristopher Moore:
Hiding Satisfying Assignments: Two are Better than One. CoRR abs/cs/0503046 (2005) - 2004
- [j15]Yi-Min Wang, Lili Qiu, Chad Verbowski, Dimitris Achlioptas, Gautam Das
Summary-based routing for content-based event distribution networks. Comput. Commun. Rev. 34(5): 59-74 (2004) - [j14]Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy:
A sharp threshold in proof complexity yields lower bounds for satisfiability search. J. Comput. Syst. Sci. 68(2): 238-268 (2004) - [c26]Dimitris Achlioptas, Haixia Jia, Cristopher Moore:
Hiding Satisfying Assignments: Two Are Better than One. AAAI 2004: 131-136 - [c25]Dimitris Achlioptas, Cristopher Moore
The Chromatic Number of Random Regular Graphs. APPROX-RANDOM 2004: 219-228 - [c24]Dimitris Achlioptas:
Random Matrices in Data Analysis. ECML 2004: 1-7 - [c23]Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore
Sampling Grid Colorings with Fewer Colors. LATIN 2004: 80-89 - [c22]Dimitris Achlioptas:
Random Matrices in Data Analysis. PKDD 2004: 1-7 - [c21]Dimitris Achlioptas, Paul Beame, Michael Molloy:
Exponential bounds for DPLL below the satisfiability threshold. SODA 2004: 139-140 - [c20]Dimitris Achlioptas, Assaf Naor:
The two possible values of the chromatic number of a random graph. STOC 2004: 587-593 - 2003
- [j13]Dimitris Achlioptas:
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66(4): 671-687 (2003) - [j12]Dimitris Achlioptas, Cristopher Moore
Almost all graphs with average degree 4 are 3-colorable. J. Comput. Syst. Sci. 67(2): 441-471 (2003) - [c19]Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the Maximum Satisfiability of Random Formulas. FOCS 2003: 362-370 - [c18]Dimitris Achlioptas, Yuval Peres:
The threshold for random k-SAT is 2k (ln 2 - O(k)). STOC 2003: 223-231 - [i2]Dimitris Achlioptas, Cristopher Moore:
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold. CoRR cond-mat/0310227 (2003) - [i1]Dimitris Achlioptas, Yuval Peres:
The Threshold for Random k-SAT is 2kln2 - O(k). CoRR cs.CC/0305009 (2003) - 2002
- [j11]Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali:
Two-coloring random hypergraphs. Random Struct. Algorithms 20(2): 249-259 (2002) - [c17]Dimitris Achlioptas, Cristopher Moore:
The Asymptotic Order of the Random k -SAT Threshold. FOCS 2002: 779-788 - [c16]Dimitris Achlioptas, Cristopher Moore
On the 2-Colorability of Random Hypergraphs. RANDOM 2002: 78-90 - [c15]Dimitris Achlioptas, Cristopher Moore:
Almost all graphs with average degree 4 are 3-colorable. STOC 2002: 199-208 - 2001
- [j10]Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou
Random Constraint Satisfaction: A More Accurate Picture. Constraints An Int. J. 6(4): 329-344 (2001) - [j9]Henry A. Kautz
Balance and Filtering in Structured Satisfiable Problems (Preliminary Report). Electron. Notes Discret. Math. 9: 2-18 (2001) - [j8]Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis
Rigorous results for random (2+p)-SAT. Theor. Comput. Sci. 265(1-2): 109-129 (2001) - [j7]Dimitris Achlioptas:
Lower bounds for random 3-SAT via differential equations. Theor. Comput. Sci. 265(1-2): 159-185 (2001) - [c14]Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry:
Web Search via Hub Synthesis. FOCS 2001: 500-509 - [c13]Henry A. Kautz, Yongshao Ruan, Dimitris Achlioptas, Carla P. Gomes, Bart Selman, Mark E. Stickel:
Balance and Filtering in Structured Satisfiable Problems. IJCAI 2001: 351-358 - [c12]Dimitris Achlioptas, Frank McSherry, Bernhard Schölkopf:
Sampling Techniques for Kernel Methods. NIPS 2001: 335-342 - [c11]Dimitris Achlioptas:
Database-friendly random projections. PODS 2001 - [c10]Dimitris Achlioptas, Arthur D. Chtcherba, Gabriel Istrate, Cristopher Moore:
The phase transition in 1-in-k SAT and NAE 3-SAT. SODA 2001: 721-722 - [c9]Dimitris Achlioptas, Paul Beame
A sharp threshold in proof complexity. STOC 2001: 337-346 - [c8]Dimitris Achlioptas, Frank McSherry:
Fast computation of low rank matrix. STOC 2001: 611-618 - 2000
- [j6]Dimitris Achlioptas, Marek Chrobak, John Noga:
Competitive analysis of randomized paging algorithms. Theor. Comput. Sci. 234(1-2): 203-218 (2000) - [c7]Dimitris Achlioptas, Carla P. Gomes, Henry A. Kautz, Bart Selman:
Generating Satisfiable Problem Instances. AAAI/IAAI 2000: 256-261 - [c6]Dimitris Achlioptas, Gregory B. Sorkin
Optimal myopic algorithms for random 3-SAT. FOCS 2000: 590-600 - [c5]Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali:
Two-coloring Random Hypergraphs. ICALP Satellite Workshops 2000: 85-96 - [c4]Dimitris Achlioptas:
Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). STOC 2000: 28-37
1990 – 1999
- 1999
- [b1]Dimitris Achlioptas:
Threshold phenomena in random graph colouring and satisfiability. University of Toronto, Canada, 1999 - [j5]Dimitris Achlioptas, Michael Molloy:
Almost all graphs with 2.522 n edges are not 3-colorable. Electron. J. Comb. 6 (1999) - [j4]Dimitris Achlioptas, Ehud Friedgut:
A Sharp Threshold for k-Colorability. Random Struct. Algorithms 14(1): 63-70 (1999) - [j3]Jeff Edmonds, Chung Keung Poon
Tight Lower Bounds for st-Connectivity on the NNJAG Model. SIAM J. Comput. 28(6): 2257-2284 (1999) - 1998
- [j2]Dimitris Achlioptas, Jason I. Brown
The existence of uniquely -G colourable graphs. Discret. Math. 179(1-3): 1-11 (1998) - 1997
- [j1]Demetrios Achlioptas:
The complexity of G-free colourability. Discret. Math. 165-166: 21-30 (1997) - [c3]Dimitris Achlioptas, Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Michael S. O. Molloy, Yannis C. Stamatiou
Random Constraint Satisfaction: A More Accurate Picture. CP 1997: 107-120 - [c2]Dimitris Achlioptas, Michael S. O. Molloy:
The Analysis of a List-Coloring Algorithm on a Random Graph. FOCS 1997: 204-212 - 1996
- [c1]Dimitris Achlioptas, Marek Chrobak, John Noga:
Competive Analysis of Randomized Paging Algorithms. ESA 1996: 419-430
Coauthor Index
Michael Molloy 0001
aka: Michael S. O. Molloy
aka: Michael S. O. Molloy
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-12 23:00 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: