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.

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.

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

Professional Activities


Survey Article


Research Publications [chronologically][by topic]

  1. Robust Estimators in High Dimensions without the Computational Intractability [abstract] [arxiv]
    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
    Manuscript

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

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

  4. A New Approach for Testing Properties of Discrete Distributions [abstract] [pdf] [arxiv]
    I. Diakonikolas, D. Kane
    Manuscript
    Oded Goldreich's Choices #195

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

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

  7. Sample Optimal Density Estimation in Nearly-Linear Time [abstract] [pdf]
    J. Acharya, I. Diakonikolas, J. Li, L. Schmidt
    Manuscript

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Current Teaching

Advising

  • PhD students: Vladimir Nikishkin (September 2013 - present), Chrystalla Pavlou (October 2015 - present)
  • Postdoc: Alistair Stewart (September 2014 - present)
  • MSc students: Paul Carter (2014), Evgeniya Sotirova (2014), Michael Zhang (2015)