Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

List of Publications

Journals 

  1. C. Efthymiou, T. Hayes, D. Stefankovic, E.Vigoda and Y. Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. Accepted, to appear in SIAM Journal on Computing (special issue).

  2. A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang and T. Kapetanopoulos. Charting the Replica Symmetry Phase. In Communications in Mathematical Physics (CIMP) 359(2), pp 603-698, 2018.

  3. A. Coja-Oghlan, C. Efthymiou and N. Jafaari. Local convergence of random graph colorings. In Combinatorica 38(2), pp 341-380, 2018.

  4. V. Bapst, A. Coja-Oghlan and C. Efthymiou. Planting colorings silently. In Combinatorics Probability and Computing (CPC), 26 (3), pp 338-366, 2017.

  5. C. Efthymiou. A simple algorithm for sampling colourings of G(n,d/n) up to Uniqueness threshold. In SIAM Journal on Computing (SICOMP), 45 (6), pp 2087-2116, 2016.

  6. A. Coja-Oghlan, C. Efthymiou and S. Hetterich. On the chromatic number of random regular graphs. In Journal of Combinatorial Theory Series B (JCTB), 116, pp 367-439, 2016.

  7. A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. In Random Structures and Algorithms (RSA), 47 (3) pp. 436-486, 2015.

  8. C. Efthymiou and P. G. Spirakis. Sharp Thresholds for Hamiltonicity in Random Intersection Graphs. In Theoretical Computer Science (TCS), 411, pp 3714-3730, 2010.

  9. C. Efthymiou and P. G. Spirakis. Random sampling of colourings of sparse random graphs with a constant number of colours. In Theoretical Computer Science (TCS), 407, pp. 134-154, 2008.

  10. C. Efthymiou, S. Nikoletseas and J. Rolim. Energy Balanced Data Propagation in Wireless Sensor Networks. Invited paper in Wireless Networks Journal (WINET), Special Issue, 12 (6) pp 691-707, 2006.

Conferences

  1. C. Efthymiou, T. Hayes, D. Stefankovic and E.Vigoda. Sampling Random Colorings of Sparse Random Graphs. In 29th Symposium on Discrete Algorithms (SODA'18), pp 1759 - 1771, 2018.

  2. A. Coja-Oghlan, C. Efthymiou, N. Jaafari, M. Kang and T. Kapetanopoulos. Charting the Replica Symmetry Phase. In RANDOM-APPROX'17, pp 40:1-40:17, 2017.

  3. C. Efthymiou, T. Hayes, D. Stefankovic, E.Vigoda and Y. Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. In 57th Symposium on Foundations of Computer Science (FOCS'16), pp 704-713, 2016.

  4. C. Efthymiou. Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees. In  RANDOM-APPROX'15, pp 756-774, 2015.

  5. A. Coja-Oghlan, C. Efthymiou and N. Jafaari. Local convergence of random graph colorings. In RANDOM-APPROX'15, pp 726-737, 2015.

  6. C. Efthymiou. Switching colourings of G(n,d/n) for sampling up to Gibbs Uniqueness Threshold. In 22nd European Symposium on Algorithms (ESA'14), pp 371-381, 2014.

  7. C. Efthymiou. MCMC sampling colourings and independent sets of G(n,d/n) near the uniqueness threshold. In 25th Symposium on Discrete Algorithms (SODA'14), pp 305-316, 2014.

  8. C. Efthymiou. A simple algorithm for random colouring G(n, d/n) using (2+ε)d colours. In 23rd Symposium on Discrete Algorithms (SODA'12), pp 272-280, 2012.

  9. A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. In 22nd Symposium on Discrete Algorithms (SODA'11), pp 136-144, 2011.

  10. C. Efthymiou and P.G. Spirakis. On the Existence of Hamilton Cycles in Random Intersection Graphs. In 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), pp 690-701, 2005.

  11. C. Efthymiou, S. Nikoletseas and J. Rolim. Energy Balanced Data Propagation in Wireless Sensor Networks. In 4th Int. Workshop on Algorithms for Wireless Mobile Ad-Hoc and Sensor Networks (WMAN'04), IPDPS 2004, p.225, 2004.

Misc.

  1. C. Efthymiou. Random Instances of problems in NP - Algorithms and Statistical Physics. In Algorithms, Probability, Networks, and Games, Springer LNCS, pp 196-222, 2015.

  2. C. Efthymiou and P. G. Spirakis.On the Existence of Hamilton Cycles in Random Intersection Graphs. In Encyclopaedia of Algorithms (Editor Ming-Yang Kao), Springer, 2008.