Ilias Diakonikolas

I am an Assistant Professor in the School of Informatics at the University of Edinburgh.

I moved to Edinburgh in the Fall of 2012 after spending two years at UC Berkeley as the Simons Postdoctoral Fellow in Theoretical Computer Science. I obtained my Ph.D. in Computer Science at Columbia University, advised by Mihalis Yannakakis. Before that, I did my undergraduate studies in Greece, at the National Technical University of Athens.

Research: My main research interests are in algorithms, learning, statistics, and applied probability. The current focus of my work is on big data algorithmics for machine learning. I also have strong interests in optimization and game theory.

Interested in working with me? Apply to our Ph.D. program or our newly founded Data Science doctoral program.

Informatics Forum, Room 5.18
University of Edinburgh
10 Crichton Street
Edinburgh EH8 9AB, Scotland, UK
ilias.d_at_ed.ac.uk

News

Research Publications [chronologically][by topic]

  1. Testing Identity of Structured Distributions [abstract] [pdf]
    I. Diakonikolas, D. Kane, V. Nikishkin
    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), to appear

  2. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Advances in Neural Information Processing Systems (NIPS 2014), to appear

  3. Efficient Density Estimation via Piecewise Polynomial Approximation [abstract] [pdf]
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)

  4. Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC 2014)

  5. Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Manuscript, 2013. Available as ECCC technical report [link]

  6. Learning from Satisfying Assignments [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), to appear

  7. An Optimal Algorithm for the Efficient Approximation of Convex Pareto Curves
    I. Diakonikolas, M. Yannakakis
    Manuscript, 2013

  8. On the relation of total variation and Kolmogorov distance between Poisson Binomial distributions
    C. Daskalakis, I. Diakonikolas, R. Servedio
    Manuscript, 2013

  9. On the distribution of the Fourier spectrum of halfspaces [abstract] [pdf]
    I. Diakonikolas, R. Jaiswal, R. Servedio, L.-Y.Tan, A. Wan
    Manuscript, 2012

  10. The Complexity of Optimal Multidimensional Pricing [abstract] [pdf]
    X. Chen, I. Diakonikolas, D. Paparas, X. Sun, M. Yannakakis
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)

  11. Optimal Algorithms for Testing Closeness of Discrete Distributions [abstract] [pdf]
    S. Chan, I. Diakonikolas, G. Valiant, P. Valiant
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    Blog post about this work: Property Testing Review

  12. A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage [abstract] [pdf]
    C. Daskalakis, A. De, I. Diakonikolas, A. Moitra, R. Servedio
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    Featured in Abstract Talk. Podcast is here

  13. Learning Sums of Independent Integer Random Variables [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. O'Donnell, R. Servedio, L-Y. Tan
    Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
    Blog post about this work: MIT theory student blog

  14. A robust Khintchine Inequality and computing optimal constants in Fourier analysis and high-dimensional geometry [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Proceedings of the 40th Intl. Colloquium on Automata, Languages and Programming (ICALP 2013)

  15. Learning Mixtures of Structured Distributions over Discrete Domains [abstract] [pdf]
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

  16. Testing $k$-modal Distributions: Optimal Algorithms via Reductions [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio, G. Valiant, P. Valiant
    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

  17. Efficiency-Revenue Tradeoffs in Auctions [abstract] [pdf]
    I. Diakonikolas, C.H. Papadimitriou, G. Pierrakos, Y. Singer
    Proceedings of the 39th Intl. Colloquium on Automata, Languages and Programming (ICALP 2012)

  18. The Inverse Shapley Value Problem [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Games and Economic Behavior, accepted with minor revisions
    Proceedings of the 39th Intl. Colloquium on Automata, Languages and Programming (ICALP 2012)

  19. Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces [abstract] [pdf]
    A. De, I. Diakonikolas, V. Feldman, R. Servedio
    Journal of the ACM, 61(2), 2014. Invited to Theory of Computing special issue on Analysis of Boolean functions (declined)
    Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)

  20. Learning Poisson Binomial distributions [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio
    Invited to Algorithmica special issue on Machine Learning
    Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)

  21. Learning $k$-modal distributions via testing [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio
    Theory of Computing, to appear
    Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
    Oded Goldreich's Choices #72

  22. Supervised Design Space Exploration by Compositional Approximation of Pareto sets [abstract] [pdf]
    H.-Y. Liu, I. Diakonikolas, M. Petracca, L.P. Carloni
    Proceedings of the 48th Design Automation Conference (DAC 2011)

  23. Disjoint-Path Facility Location: Theory and Practice [abstract] [pdf]
    L. Breslau, I. Diakonikolas, N. Duffield, Y.Gu, M.T. Hajiaghayi, D.S. Johnson, H. Karloff, M. Resende, S.Sen
    Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011)

  24. Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. O'Donnell, R. Servedio, Y.Wu
    Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)

  25. Bounded Independence Fools Degree-$2$ Threshold Functions [abstract] [pdf]
    I. Diakonikolas, D. Kane, J. Nelson
    Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)

  26. Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, P. Raghavendra, R. Servedio, L.-Y. Tan
    SIAM Journal on Computing, 43(1), 231-253 (2014)
    Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010) (Conference version merged with this paper by Harsha, Klivans and Meka)

  27. A Regularity Lemma, and Low-weight Approximators, for low-degree Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. Servedio, L.-Y. Tan, A. Wan
    Theory of Computing, 10(2), 27-53 (2014)
    Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC 2010)

  28. How Good is the Chord Algorithm? [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, M. Yannakakis
    Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)

  29. Bounded Independence Fools Halfspaces [abstract] [pdf]
    I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, E. Viola
    SIAM Journal on Computing, 39(8), 3441-3462 (2010)
    Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)

  30. Improved Approximation of Linear Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. Servedio
    Computational Complexity, 22(3), 623-677 (2013)
    Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009)

  31. Efficiently Testing Sparse $GF(2)$ Polynomials [abstract] [pdf]
    I. Diakonikolas, H. Lee, K. Matulef, R. Servedio, A. Wan
    Algorithmica, 61(3), 580-605 (2011)
    Proceedings of the 35th Intl. Colloquium on Automata, Languages and Programming (ICALP 2008)

  32. Succinct Approximate Convex Pareto Curves [abstract] [pdf]
    I. Diakonikolas, M. Yannakakis
    Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008)

  33. Testing for Concise Representations [abstract] [pdf]
    I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, A. Wan
    Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)
    Oded Goldreich's Choices #39

  34. Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems [abstract] [pdf]
    I. Diakonikolas, M. Yannakakis
    SIAM Journal on Computing, 39(4), 1340-1371 (2009)
    Proceedings of the 10th Intl. Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX 2007)
    Honorable Mention, George Nicholson student paper competition INFORMS society, 2009

Thesis


Teaching

Advising

  • PhD student: Vladimir Nikishkin (September 2013 - present)
  • Postdoc: Alistair Stewart (Summer 2014 - present)
  • MSc students: Paul Carter, Evgeniya Sotirova (2014, ongoing)

Other