About me
I am an Assistant Professor at Yale University, in the Department of Statistics and Data Science.
I am searching for highly motivated PhD students.
If you are interested to work with me, apply to our PhD program and mention my name.
Currently teaching (Spring 2024): S&DS 351 01 Stochastic Processes Canvas Link
Research Interests
My research lies broadly in the interface of high dimensional statistics, the theory of machine learning, the theory of computation, and probability theory. A lot of my work has the goal to build and use mathematical tools to bring insights into the computational and statistical challenges of modern machine learning tasks.
Four directions that I have been recently focusing on are:
 Computationalstatistical tradeoffs in inference (see papers 4, 12, 16, 20, 22, 24, 27, 30 below).
 Phase transition phenomena (e.g. the "AllorNothing phenomenon") (see papers 9, 11, 13, 17, 19, 27, 28, 29 below).
 The power of latticebased methods in inference (see papers 7, 18, 20 below).
 The cost of (differential) privacy in statistics (see papers 6, 14, 21 below).
Short Bio (prior to current position)
From September 2021 to August 2023 I was a postdoctoral researcher at
Massachussets Institute of Technology (MIT),
Mathematics Department, where I worked under the wonderful mentorship of
Elchanan Mossel and
Nike Sun, as a member of the NSF/Simons program
Collaboration on the Theoretical Foundations of Deep Learning.
Prior to this, from September 2019 to August 2021 I was a postdoctoral fellow at the
Center for Data Science of
New York University and a member of it's
Math and Data (MaD) group.
I received my PhD on September 2019 from the
Operations Research Center of
MIT , where I was very fortunate to be advised by Prof.
David Gamarnik. A copy of my PhD thesis can be found
here.
From June 2017 to August 2017 I was an intern at the
Microsoft Research Lab in New England, mentored by
Jennifer Chayes and
Christian Borgs . Prior joining MIT, I completed a Master of Advanced Studies in Mathematics (Part III of the Mathematical Tripos) at the
University of Cambridge and a BA in Mathematics from the Mathematics Department at the
University of Athens.
Some recent recorded talks
 (1hour) "Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem."
BIRS workshop on "Learning in Networks: Performance Limits and Algorithms", November 2022
 (40mins) "On the Second KahnKalai conjecture"
Simons workshop on Graph Limits: Nonparametric Models, and Estimation, September 2022.
 (1 hour) "On the Cryptographic Hardness of Learning Single Periodic Neurons."
Simons workshop on "AverageCase Complexity: From Cryptography to Statistical Learning", November 2021.
 (40mins) "The Surprising Power of the LenstraLenstraLovasz Algorithm for Noiseless Inference."
Simons joint IFML/CCSI Symposium, November 2021.
 (25mins) "The Overlap Gap Property For Inference: Power And Limitations."
Simons workshop on "Rigorous Evidence for InformationComputation Tradeoffs", September 2021.
 (25mins) "The AllorNothing Phenomenon: the case of Sparse Tensor PCA."
BIRS workshop on "Random Graphs and Statistical Inference: New Methods and Applications", August 2021
 (45mins) "MCMC Lower Bounds for Sparse PCA."
New York Colloquium on Algorithms and Complexity (NYCAC), March 2021.
 (15mins) "The Landscape of the Planted Clique Model".
19th Northeast Probability Seminar, November 2020.
 (15mins) "Computational Barriers in High Dimensional Inference. Insights from Statistical Physics."
INFORMS Annual Meeting, November 2020.
Research papers (published or submitted)
(Note: the order of the authors is alphabetical, unless denoted by (*))
2024+

Counting Stars is ConstantDegree Optimal For Detecting Any Planted Subgraph
ArXiv preprint
Xifan Yu, Ilias Zadik, Peiyuan Zhang.

Transfer Learning Beyond Bounded Density Ratios
ArXiv preprint
Alkis Kalavasis, Ilias Zadik, Manolis Zampetakis.

Sharp Thresholds Imply Circuit Lower Bounds: from random 2SAT to Planted Clique
ArXiv preprint
David Gamarnik, Elchanan Mossel, Ilias Zadik.

A Second Moment Proof of the Spread Lemma
ArXiv preprint
Elchanan Mossel, Jonathan NilesWeed, Nike Sun, Ilias Zadik.

On the Second KahnKalai Conjecture (45mins video  Simons workshop)
ArXiv preprint
Elchanan Mossel, Jonathan NilesWeed, Nike Sun, Ilias Zadik.

The Landscape of the Planted Clique Problem: Dense Subgraphs and the Overlap Gap Property ( 1hr video  NYU Probability Seminar)
Annals of Applied Probability, 2024+
David Gamarnik, Ilias Zadik.

Stationary Points of Shallow Neural Networks with Quadratic Activation Function (30mins video by Eren  MIT MLTea)
Mathematics of Operations Research, 2024
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik.
2023

Sharp thresholds in inference of planted subgraphs
Proceedings of the Conference on Learning Theory (COLT), 2023
Elchanan Mossel, Jonathan NilesWeed, Youngtak Sohn, Nike Sun, Ilias Zadik.

AlmostLinear Planted Cliques Elude the Metropolis Process (1h video  BIRS workshop)
Proceedings of the Symposium on Discrete Algorithms (SODA), 2023
Zongchen Chen, Elchanan Mossel, Ilias Zadik.

Shapes and recession cones in mixedinteger convex representability
Mathematical Programming, 2023
Ilias Zadik, Miles Lubin, Juan Pablo Vielma. (*)
2022

The FranzParisi Criterion and Computational Tradeoffs in High Dimensional Statistics (5mins video  NeurIPS)
Advances in Neural Information Processing Systems, (NeurIPS), 2022
Selected for an Oral Presentation.
Afonso Bandeira, Ahmed El Alaoui, Sam Hopkins, Tselil Schramm, Alex Wein, Ilias Zadik.

Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions
(5mins video by Dan  NeurIPS,)
Advances in Neural Information Processing Systems, (NeurIPS), 2022
Omri BenEliezer, Dan Mikulincer, Ilias Zadik.

LatticeBased Methods Surpass SumofSquares in Clustering (20mins video by Min Jae  COLT)
Proceedings of the Conference on Learning Theory (COLT), 2022
Ilias Zadik, Min Jae Song, Alex Wein, Joan Bruna. (*)

Statistical and Computational Phase Transitions in Group Testing (20mins video  COLT)
Proceedings of the Conference on Learning Theory (COLT), 2022
Amin CojaOghlan, Oliver Gebhard, Max HahnKlimroth, Alex Wein, Ilias Zadik.
2021

On the Cryptographic Hardness of Learning Single Periodic Neurons (20 mins video  Deep Learning Theory Symposium, Simons)
Advances in Neural Information Processing Systems, (NeurIPS), 2021
Min Jae Song, Ilias Zadik, Joan Bruna. (*)

It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels (18mins video  COLT)
IEEE Transactions of Information Theory, 2023
Conference version in Proceedings of the Conference on Learning Theory (COLT), 2021
Jonathan NilesWeed, Ilias Zadik.

Group testing and local search: is there a computationalstatistical gap? (2hrs video by Fotis  IAS)
Proceedings of the Conference on Learning Theory (COLT), 2021
Fotis Iliopoulos, Ilias Zadik.

SelfRegularity of NonNegative Output Weights for Overparameterized TwoLayer Neural Networks
IEEE Transactions of Signal Processing, 2021
Conference version in Proceedings of the International Symposium on Information Theory (ISIT), 2021
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik.
2020

Optimal Private Median Estimation under Minimal Distributional Assumptions (10mins video by Manolis  NeurIPS spotlight)
Advances in Neural Information Processing Systems, (NeurIPS), 2020
Selected for a Spotlight Presentation (~5% of submitted papers).
Christos Tzamos, Manolis Vlatakis, Ilias Zadik.

The AllorNothing Phenomenon in Sparse Tensor PCA (Poster, ( 25mins video  BIRS workshop)
Advances in Neural Information Processing Systems, (NeurIPS), 2020
Jonathan NilesWeed, Ilias Zadik.

Free Energy Wells and the Overlap Gap Property in Sparse PCA ( 25mins video  Simons workshop)
Communications on Pure and Applied Mathematics, 2023
Conference version in Proceedings of the Conference of Learning Theory (COLT), 2020
Gèrard Ben Arous, Alex Wein, Ilias Zadik.
2019

The AllorNothing Phenomenon in Sparse Linear Regression (Slides, Poster)
Mathematical Statistics and Learning, 2021
Conference version in the Proceedings of the Conference on Learning Theory (COLT), 2019
Galen Reeves, Jiaming Xu, Ilias Zadik.

AllorNothing Phenomena: From SingleLetter to High Dimensions
Proceedings of the International Workshop on Computational Advances in MultiSensor Adaptive Processing (CAMSAP), 2019
Galen Reeves, Jiaming Xu, Ilias Zadik.

Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities
Proceedings of the International Symposium on Information Theory (ISIT), 2019
Ilias Zadik, Christos Thrampoulidis, Yury Polyanskiy. (*)

A simple bound on the BER of the MAP decoder for massive MIMO systems
Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2019
Christos Thrampoulidis, Ilias Zadik, Yury Polyanskiy. (*)
2018

Inference in HighDimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
IEEE Transactions of Information Theory, 2021
Conference version with David Gamarnik, in Advances in Neural Information Processing Systems, (NeurIPS), 2018
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik.

Revealing Network Structure, Confidentially: Improved Rates for NodePrivate Graphon Estimation (Slides, 1h video by Adam Simons)
Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2018
Christian Borgs, Jennifer Chayes, Adam Smith, Ilias Zadik.

Orthogonal Machine Learning: Power and Limitations (Slides, Poster, Code)
Proceedings of International Conference of Machine Learning (ICML), 2018 (20 minute Presentation)
Lester Mackey, Vasilis Syrgkanis, Ilias Zadik.
2017

Sparse HighDimensional Linear Regression. Estimating Squared Error and a Phase Transition.
Annals of Statistics, 2022
David Gamarnik, Ilias Zadik.
This paper merges:
(a) HighDimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition (Slides, Poster, 20mins video)
Proceedings of the Conference on Learning Theory (COLT), 2017 (20 minutes Presentation)
(b) Sparse HighDimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm
arXiv preprint, 2017

Mixed integer convex representability (Slides)
Mathematics of Operations Research, 2021
Conference version in Proceedings of the International Conference of Integer Programming and Combinatorial Optimization (IPCO), 2017
Miles Lubin, Juan Pablo Vielma, Ilias Zadik.
Pre2017 (complex analysis):

Universal Padé approximants and their behaviour on the boundary
Monatshefte für Mathematik, Vol. 182, p.p. 173–193, 2017
Ilias Zadik.

Pade approximants, density of rational functions in A^(infinity)(V) and smoothness of the integration operator
Journal of Mathematical Analysis and Applications; Vol. 423, p.p. 1514–1539, 2015
Vassili Nestoridis, Ilias Zadik.
Thesis/Notes/Survey Articles

Computational and Statistical Challenges in High Dimensional Statistical Models
PhD Thesis, Operations Research Center, Massachussets Institute of Technology, 2019

Private Algorithms Can Always Be Extended
Note on the extension of private algorithms
Christian Borgs, Jennifer Chayes, Adam Smith, Ilias Zadik.

Noise Sensitivity with applications to Percolation and Social Choice Theory
Part III Essay, 2014
Advised by Béla Bollobás

A Note on the Density of Rational Functions in Α^{∞ }(Ω)
A complex analysis note on the density of rational functions
New Trends in Approximation Theory; vol 81, p.p. 2735
Javier Falcó, Vassili Nestoridis, Ilias Zadik
Service
 From Spring 2020 to Spring 2021 I had the pleasure to be among the organizers of the virtual MaD+ seminar, which run during the COVID19 pandemic.
 I have served as a reviewer for Annals of Statistics, Operations Research, Probability Theory and Related Fields, Mathematical Programming, SIAM Journal of Discrete Mathematics, SIAM Journal of Optimization, Combinatorica, IEEE Journal on Selected Areas in Information Theory, and for the conferences COLT, NeurIPS, FOCS, STOC, ITCS, ISIT, ICALP and SODA.
 Program Committees: COLT 2023, COLT 2022 and COLT 2021.
Past teaching
Instructor
 Fall 2023, S&DS 688 01, (Yale): S&DS 688 01: Computational and statistical tradeoffs in high dimensional statistics
Newly designed stateoftheart reseerch level course on computationalstatistical tradeoffs (see link for scribe notes and details).
 Fall 2020, DSGA 1005, (NYU): Inference and Representation. (Coinstructor: Joan Bruna)
Codesigned and taught an advanced graduatelevel course on modern theoretical aspects of statistics and machine learning.
 Fall 2019, DSGA 1002 (NYU): Probability and Statistics for Data Science. (Coinstructor: Carlos FernandezGranda )
Introductory graduatelevel course on probability and statistics.
Teaching Assistant
 Spring 2017, 6.265/15.070 (MIT): Modern Discrete Probability. (Instructors: Guy Bresler, Yury Polyanskiy)
Advanced graduatelevel course on discrete probability and modern applications to computer science.
 Fall 2016, 6.436J/15.085J (MIT): Fundamentals of Probability. (Instructor: David Gamarnik )
Introductory graduatelevel course on probability.
Some awards

Honorable Mention for MIT Operations Research Center Best Student Paper Award, 2017
Paper (no. 4 above): HighDimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition.

Senior Scholarship from Trinity College, University of Cambridge, 2014.
Awarded for achieving "distinction" (ranked 13th out of 247 students) in Part III examination in Mathematics.

The Onassis Foundation Scholarship for Master Studies, 20132014
Partially supported my Master studies in the University of Cambridge.

The Cambridge Home and European Scholarship Scheme (CHESS) award, 20132014.
Partially supported my Master studies in the University of Cambridge.

International Mathematics Competition for University Students (IMC)
First Prize, 2011, Second Prize, 2010.

South Eastern European Mathematics Olympiad for University Students (SEEMOUS)
Gold Medal (first place, scored 39.5/40), 2011, Silver Medal, 2010.