| Publication | Date of Publication | Type |
|---|
| Online robust mean estimation | 2024-11-28 | Paper |
| A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning | 2024-05-08 | Paper |
Learning general halfspaces with general Massart noise under the Gaussian distribution
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Robustly learning mixtures of k arbitrary Gaussians
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Clustering mixture models in almost-linear time via list-decodable mean estimation
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Optimal testing of discrete distributions with high probability
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Efficiently learning halfspaces with Tsybakov noise
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
| Algorithmic High-Dimensional Robust Statistics | 2023-07-03 | Paper |
| A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points | 2022-12-21 | Paper |
| Gaussian Mean Testing Made Simple | 2022-10-24 | Paper |
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
SIAM Journal on Computing | 2022-05-31 | Paper |
| Robust High-Dimensional Statistics | 2022-02-04 | Paper |
Sample-optimal identity testing with high probability
(available as arXiv preprint) | 2021-07-28 | Paper |
| Outlier-Robust Learning of Ising Models Under Dobrushin's Condition | 2021-02-03 | Paper |
| Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models | 2020-12-14 | Paper |
Near-optimal disjoint-path facility location through set cover by pairs
Operations Research | 2020-11-04 | Paper |
Testing Bayesian Networks
IEEE Transactions on Information Theory | 2020-09-29 | Paper |
Near-Optimal Closeness Testing of Discrete Histogram Distributions
(available as arXiv preprint) | 2020-05-27 | Paper |
Degree-𝑑 chow parameters robustly determine degree-𝑑 PTFs (and algorithmic applications)
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
High-dimensional robust mean estimation in nearly-linear time
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Efficient algorithms and lower bounds for robust linear regression
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Disjoint-path facility location: theory and practice
2011 Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-12 | Paper |
Collision-based Testers are Optimal for Uniformity and Closeness
Chicago Journal of Theoretical Computer Science | 2019-09-12 | Paper |
Testing conditional independence of discrete distributions
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
List-decodable robust mean estimation and learning mixtures of spherical Gaussians
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Learning geometric concepts with nasty noise
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Optimal algorithms for testing closeness of discrete distributions
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Optimal algorithms for testing closeness of discrete distributions
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
A polynomial-time approximation scheme for fault-tolerant distributed storage
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
The complexity of optimal multidimensional pricing
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Learning mixtures of structured distributions over discrete domains
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Testing \(k\)-modal distributions: optimal algorithms via reductions
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Learning \(k\)-modal distributions via testing | 2019-05-10 | Paper |
Robust estimators in high-dimensions without the computational intractability
SIAM Journal on Computing | 2019-05-07 | Paper |
Playing anonymous games using simple strategies
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Sample-optimal density estimation in nearly-linear time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
The complexity of optimal multidimensional pricing for a unit-demand buyer
Games and Economic Behavior | 2018-07-12 | Paper |
| Robustly learning a Gaussian: getting optimal error, efficiently | 2018-03-15 | Paper |
Robustly learning a Gaussian: getting optimal error, efficiently
(available as arXiv preprint) | 2018-03-15 | Paper |
Testing shape restrictions of discrete distributions
Theory of Computing Systems | 2018-03-01 | Paper |
Testing shape restrictions of discrete distributions
Theory of Computing Systems | 2018-03-01 | Paper |
| Testing shape restrictions of discrete distributions | 2018-01-24 | Paper |
The inverse Shapley value problem
Games and Economic Behavior | 2017-10-24 | Paper |
Testing identity of structured distributions
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Learning from satisfying assignments
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
The Fourier transform of Poisson multinomial distributions and its algorithmic applications
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| Hardness results for agnostically learning low-degree polynomial threshold functions | 2017-09-29 | Paper |
Hardness results for agnostically learning low-degree polynomial threshold functions
(available as arXiv preprint) | 2017-09-29 | Paper |
| Fourier-Based Testing for Families of Distributions | 2017-06-18 | Paper |
How good is the Chord algorithm?
SIAM Journal on Computing | 2016-07-04 | Paper |
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
SIAM Journal on Discrete Mathematics | 2016-05-26 | Paper |
scientific article; zbMATH DE number 6537946 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2016-02-01 | Paper |
Efficient density estimation via piecewise polynomial approximation
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Learning Poisson binomial distributions
Algorithmica | 2015-05-21 | Paper |
Learning \(k\)-modal distributions via testing
Theory of Computing | 2015-02-03 | Paper |
A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
Theory of Computing | 2014-10-06 | Paper |
Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces
Journal of the ACM | 2014-09-12 | Paper |
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Bounded Independence Fools Halfspaces
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Average sensitivity and noise sensitivity of polynomial threshold functions
SIAM Journal on Computing | 2014-06-04 | Paper |
How good is the chord algorithm?
(available as arXiv preprint) | 2014-05-22 | Paper |
Learning Poisson binomial distributions
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
| Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions | 2013-11-27 | Paper |
| Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions | 2013-11-27 | Paper |
Improved approximation of linear threshold functions
Computational Complexity | 2013-09-30 | Paper |
The inverse Shapley value problem
Lecture Notes in Computer Science | 2013-08-12 | Paper |
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
Lecture Notes in Computer Science | 2013-08-06 | Paper |
Efficiency-revenue trade-offs in auctions
Automata, Languages, and Programming | 2012-11-01 | Paper |
| On the Distribution of the Fourier Spectrum of Halfspaces | 2012-02-29 | Paper |
Efficiently testing sparse \(\text{GF}(2)\) polynomials
Algorithmica | 2011-11-07 | Paper |
Bounded Independence Fools Halfspaces
SIAM Journal on Computing | 2011-04-04 | Paper |
Small approximate Pareto sets for biobjective shortest paths and other problems
SIAM Journal on Computing | 2010-09-06 | Paper |
| scientific article; zbMATH DE number 5764846 (Why is no real title available?) | 2010-08-06 | Paper |
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Efficiently Testing Sparse GF(2) Polynomials
Automata, Languages and Programming | 2008-08-28 | Paper |
