# Ilias Diakonikolas

 I am an Assistant Professor and Andrew and Erna Viterbi Early Career Chair in the Department of Computer Science at the University of Southern California. I am member of the CS Theory group and the Machine Learning center. Prior to joining USC's faculty, I spent two years at UC Berkeley as the Simons Postdoctoral Fellow in Theoretical Computer Science, and then I was a faculty member at the University of Edinburgh. 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. A major goal of my work is to understand the tradeoff between statistical efficiency, computational efficiency, and robustness for fundamental problems in machine learning. I also have strong interests in optimization, game theory, and their connections to learning. My research has been supported by an NSF Career Award, a Sloan Research Fellowship, a Google Faculty Research Award, a Marie Curie Career Integration Grant, and an EPSRC grant. Interested in working with me? Apply to our Ph.D. program. University of Southern California Department of Computer Science 941 Bloom Walk, SAL 220 Los Angeles, CA 90089-0781 diakonik_at_usc.edu

## Book Chapter

Learning Structured Distributions [abstract]
Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC, February 2016.

## Research Publications [chronologically][by topic]

1. Learning Geometric Concepts with Nasty Noise
I. Diakonikolas, D. Kane, A. Stewart
Manuscript

2. Fourier-based Testing for Families of Distributions [abstract] [eccc]
C. Canonne, I. Diakonikolas, A. Stewart
Manuscript

3. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently [abstract] [arxiv]
I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
Manuscript

4. Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures [abstract] [eccc] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Manuscript

5. Collision-based Testers are Optimal for Uniformity and Closeness [abstract] [eccc]
I. Diakonikolas, T. Gouleakis, J. Peebles, E. Price
Manuscript

6. Efficient Robust Proper Learning of Log-concave Distributions [abstract] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Manuscript

7. Robust Learning of Fixed-Structure Bayesian Networks [abstract] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Manuscript

8. Being Robust (in High Dimensions) Can be Practical [abstract] [arxiv]
I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
Proceedings of the 34th International Conference on Machine Learning (ICML 2017)

9. Testing Bayesian Networks [abstract] [arxiv]
C. Canonne, I. Diakonikolas, D. Kane, A. Stewart
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)

10. Learning Multivariate Log-concave Distributions [abstract] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)

11. Near-optimal Closeness Testing of Discrete Histogram Distributions [abstract] [arxiv]
I. Diakonikolas, D. Kane, V. Nikishkin
Proceedings of the 44th Intl. Colloquium on Automata, Languages and Programming (ICALP 2017)

12. Playing Anonymous Games using Simple Strategies [abstract] [arxiv]
Y. Cheng, I. Diakonikolas, A. Stewart
Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

13. Sample Optimal Density Estimation in Nearly-Linear Time [abstract] [pdf] [code]
J. Acharya, I. Diakonikolas, J. Li, L. Schmidt
Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

14. Robust Estimators in High Dimensions without the Computational Intractability [abstract] [arxiv]
I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
Invited to the SIAM Journal on Computing Special Issue for FOCS 2016

15. A New Approach for Testing Properties of Discrete Distributions [abstract] [pdf] [arxiv]
I. Diakonikolas, D. Kane
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
Also see the comments in Oded Goldreich's Choices #188 and #195, and Oded's very nice exposition of our framework here

16. Fast Algorithms for Segmented Regression [abstract] [pdf] [code]
J. Acharya, I. Diakonikolas, J. Li, L. Schmidt
Proceedings of the 33rd International Conference on Machine Learning (ICML 2016)

17. Properly Learning Poisson Binomial Distributions in Almost Polynomial Time [abstract] [pdf] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)

18. Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables [abstract] [pdf] [arxiv] [notes]
I. Diakonikolas, D. Kane, A. Stewart
Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)

19. The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications [abstract] [pdf] [arxiv]
I. Diakonikolas, D. Kane, A. Stewart
Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)

20. Testing Shape Restrictions of Discrete Distributions [abstract] [pdf]
C. Canonne, I. Diakonikolas, T. Gouleakis, R. Rubinfeld
Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Invited to Special Issue for STACS 2016

21. Differentially Private Learning of Structured Discrete Distributions [abstract] [pdf] [code]
I. Diakonikolas, M. Hardt, L. Schmidt
Advances in Neural Information Processing Systems (NIPS 2015)

22. Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions [abstract] [pdf]
I. Diakonikolas, D. Kane, V. Nikishkin
Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

23. On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms [abstract] [pdf]
X. Chen, I. Diakonikolas, A. Orfanou, D. Paparas, X. Sun, M. Yannakakis
Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

24. Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms [abstract] [pdf]
J. Acharya, I. Diakonikolas, C. Hegde, J. Li, L. Schmidt
Proceedings of the 34th Annual ACM Symposium on Principles of Database Systems (PODS 2015)

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

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

27. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms [abstract] [pdf]
S. Chan, I. Diakonikolas, R. Servedio, X. Sun
Advances in Neural Information Processing Systems (NIPS 2014)

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

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

30. The Complexity of Optimal Multidimensional Pricing [abstract] [pdf]
X. Chen, I. Diakonikolas, D. Paparas, X. Sun, M. Yannakakis
Games and Economic Behavior, accepted with minor revisions
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)

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

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

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

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

35. A robust Khintchine Inequality and computing optimal constants in Fourier analysis and high-dimensional geometry [abstract] [pdf]
A. De, I. Diakonikolas, R. Servedio
SIAM Journal on Discrete Mathematics, 30-2 (2016), pp. 1058-1094
Proceedings of the 40th Intl. Colloquium on Automata, Languages and Programming (ICALP 2013)

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

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

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

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

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

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

42. 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)
IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper Award

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

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

45. Noise Stable Halfspaces are Close to Very Small Juntas [abstract] [pdf]
I. Diakonikolas, R. Jaiswal, R. Servedio, L.-Y.Tan, A. Wan
Chicago Journal of Theoretical Computer Science, 2015

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

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

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

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

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

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

52. How Good is the Chord Algorithm? [abstract] [pdf]
C. Daskalakis, I. Diakonikolas, M. Yannakakis
SIAM Journal on Computing, 45(3), pp. 811-858, 2016
Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)

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

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

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

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

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

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