Travelled to:1 × Canada
1 × Greece
1 × Italy
1 × Japan
1 × United Kingdom
8 × USA
Collaborated with:R.Menchaca-Mendez ∅ C.Moore P.Siminelakis F.Ricci-Tersenghi A.Naor Y.Peres C.Moore F.McSherry P.Beame M.S.O.Molloy A.Clauset D.Kempe H.A.Kautz Y.Ruan C.P.Gomes B.Selman M.E.Stickel
Talks about:random (7) graph (4) bound (3) threshold (2) satisfact (2) satisfi (2) problem (2) lower (2) degre (2) sat (2)
Person: Dimitris Achlioptas
DBLP: Achlioptas:Dimitris
Contributed to:
20152012
2012
200620052004200320022002
2001200120012000Wrote 14 papers:
- ICALP-v2-2015-AchlioptasS #graph #independence #symmetry
- Symmetric Graph Properties Have Independent Edges (DA, PS), pp. 467–478.
- ICALP-v1-2012-AchlioptasM #bound #random #satisfiability
- Unsatisfiability Bounds for Random CSPs from an Energetic Interpolation Method (DA, RMM), pp. 1–12.
- SAT-2012-AchlioptasM #algorithm #bound #exponential #random #satisfiability
- Exponential Lower Bounds for DPLL Algorithms on Satisfiable Random 3-CNF Formulas (DA, RMM), pp. 327–340.
- STOC-2006-AchlioptasR #constraints #geometry #on the #problem #random
- On the solution-space geometry of random constraint satisfaction problems (DA, FRT), pp. 130–139.
- STOC-2005-AchlioptasCKM #bias #graph #on the
- On the bias of traceroute sampling: or, power-law degree distributions in regular graphs (DA, AC, DK, CM), pp. 694–703.
- STOC-2004-AchlioptasN #graph #random
- The two possible values of the chromatic number of a random graph (DA, AN), pp. 587–593.
- STOC-2003-AchlioptasP #random #satisfiability
- The threshold for random k-SAT is 2k (ln 2 — O(k)) (DA, YP), pp. 223–231.
- SAT-2002-AchlioptasM
- A bit of abstinence (provably) promotes satisfaction (DA, CM), p. 25.
- STOC-2002-AchlioptasM #graph
- Almost all graphs with average degree 4 are 3-colorable (DA, CM), pp. 199–208.
- PODS-2001-Achlioptas #random
- Database-friendly random projections (DA).
- SAT-2001-KautzRAGSS #problem #satisfiability
- Balance and Filtering in Structured Satisfiable Problems (HAK, YR, DA, CPG, BS, MES), pp. 2–18.
- STOC-2001-AchlioptasBM #complexity #proving
- A sharp threshold in proof complexity (DA, PB, MSOM), pp. 337–346.
- STOC-2001-AchlioptasM #matrix #performance #rank
- Fast computation of low rank matrix (DA, FM), pp. 611–618.
- STOC-2000-Achlioptas #bound #random #satisfiability
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (DA), pp. 28–37.