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 and sublinear computation in the context of machine learning. I also have strong interests in optimization and game theory.

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

News

Teaching


Ph.D. Student: Vladimir Nikishkin

Research Publications [chronologically][by topic]

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

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

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

  4. Inverse problems in approximate uniform generation. [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio.
    Manuscript, 2013.

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

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

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

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

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

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

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

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

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

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

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

  16. The Inverse Shapley Value Problem. [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio.
    Proceedings of the 39th Intl. Colloquium on Automata, Languages and Programming (ICALP 2012).

  17. 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, to appear. 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Other