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

Research Publications [chronologically][by topic]

1. Testing Identity of Structured Distributions
I. Diakonikolas, D. Kane, V. Nikishkin
Manuscript, 2014

2. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
S. Chan, I. Diakonikolas, R. Servedio, X. Sun
Manuscript, 2014

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
Manuscript, 2013

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)

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)

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

Approximation of Multiobjective Optimization Problems [abstract] [pdf]
Ph.D. Thesis, Dept. of Computer Science, Columbia University, May 2011
Awarded with Distinction (for Best Ph.D. thesis in Computer Science)