1 citations · 2 across the 30 of their papers we have counts for
6 papers · 2 filters
PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
This work studies information-computation gaps for statistical problems. A common approach for providing evidence of such gaps is to show sample complexity lower bounds (that are s…
Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination
Ilias Diakonikolas, Chao Gao, Daniel M. Kane +2
We study the task of noiseless linear regression under Gaussian covariates in the presence of additive oblivious contamination. Specifically, we are given i.i.d.\ samples from a di…
Linear Regression under Missing or Corrupted Coordinates
Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane +2
We study multivariate linear regression under Gaussian covariates in two settings, where data may be erased or corrupted by an adversary under a coordinate-wise budget. In the inco…
On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +3
We study the problem of distributed distinct element estimation, where servers each receive a subset of a universe and aim to compute a -approximation to…
Efficient Multivariate Robust Mean Estimation Under Mean-Shift Contamination
Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1
We study the algorithmic problem of robust mean estimation of an identity covariance Gaussian in the presence of mean-shift contamination. In this contamination model, we are given…
Entangled Mean Estimation in High-Dimensions
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu +1
We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. Specifically, given independent random points in …