Skip to main content Skip to navigation

Department of Computer Science

List of Publications

Journals 

  1. C. Efthymiou, T. P. Hayes, D. Stefankovic and E. Vigoda. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. (To appear in CPC)

  2. 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 SIAM Journal on Computing (SICOMP), 48(2), pp. 581-643, 2019 (special issue).

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

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

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

  6. 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.

  7. 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.

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

  9. C. Efthymiou.
Deterministic counting of graph colourings using sequences of subgraphs. In Combinatorics Probability and Computing (CPC), 29(4), pp. 555-586, 2020.

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

  11. 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.

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

Conferences (peer reviewed)

  1. C. Efthymiou and K. Zampetakis. On sampling diluted Spin Glasses using Glauber dynamics. In the proc. of the 37th Annual Conference on Learning Theory (COLT 2024), pp 1501-1515, 2024.
  2. C. Efthymiou, T. P. Hayes, D. Stefankovic and E. Vigoda. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. In the proc. of RANDOM-APPROX'23, pp 33:1-33:16, 2023.
  3. C. Efthymiou and K. Zampetakis. Broadcasting with Random Matrices. In the proc. of the 50th International Colloquium on Automata, Languages and Programming (ICALP), pp. 55:1-55:14, 2023.
  4. C. Efthymiou and W. Feng. On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n). In the proc. of the 50th International Colloquium on Automata, Languages and Programming (ICALP), pp. 54:1-54:17, 2023.
  5. C. Efthymiou. On sampling symmetric Gibbs distributions on sparse random graphs and hypergraphs. In the proc. of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), pp 57:1-57:16, 2022.
  6. C. Efthymiou, A. Galanis, T. P. Hayes, D. Stefankovic and E. Vigoda. Improved Strong Spatial Mixing for Colorings on Trees. In the proc. of APPROX-RANDOM'19, pp. 48:1-48:16, 2019.

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

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

  9. 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 the proc. of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 704-713, 2016.

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

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

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

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

  14. C. Efthymiou. A simple algorithm for random colouring G(n, d/n) using (2+ε)d colours. In the proc. of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 272-280, 2012.

  15. A. Coja-Oghlan and C. Efthymiou. On independent sets in random graphs. In the proc. of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 136-144, 2011.

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

  17. C. Efthymiou, S. Nikoletseas and J. Rolim. Energy Balanced Data Propagation in Wireless Sensor Networks. In the proc. of the 4th Int. Workshop on Algorithms for Wireless Mobile Ad-Hoc and Sensor Networks (WMAN), 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.