Ilias Diakonikolas

Sihan Liu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Online Robust Mean Estimation.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Robustly Learning Single-Index Models via Alignment Sharpness.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Fast Co-Training under Weak Dependence via Stream-Based Active Learning.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

How Does Unlabeled Data Provably Help Out-of-Distribution Detection?

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Statistical Query Lower Bounds for Learning Truncated Gaussians.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Testable Learning of General Halfspaces with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Efficiently Learning One-Hidden-Layer ReLU Networks via SchurPolynomials.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Agnostically Learning Multi-index Models with Queries.

[BibT_eX]

[DOI]

CoRR, 2023

Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation.

[BibT_eX]

[DOI]

CoRR, 2023

Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials.

[BibT_eX]

[DOI]

CoRR, 2023

SQ Lower Bounds for Learning Bounded Covariance GMMs.

[BibT_eX]

[DOI]

CoRR, 2023

Gaussian Mean Testing Made Simple.

[BibT_eX]

[DOI]

Ankit Pensia

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

SQ Lower Bounds for Learning Mixtures of Linear Classifiers.

[BibT_eX]

[DOI]

Yuxin Sun

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

First Order Stochastic Optimization with Oblivious Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Efficient Testable Learning of Halfspaces with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Robustly Learning a Single Neuron via Sharpness.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.

[BibT_eX]

[DOI]

Lisheng Ren

Proceedings of the International Conference on Machine Learning, 2023

Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Self-Directed Linear Classification.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Statistical and Computational Limits for Tensor-on-Tensor Association Detection.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Near-Optimal Bounds for Testing Histogram Distributions.

[BibT_eX]

[DOI]

CoRR, 2022

Learning general halfspaces with general Massart noise under the Gaussian distribution.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Clustering mixture models in almost-linear time via list-decodable mean estimation.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Robustly learning mixtures of k arbitrary Gaussians.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

SQ Lower Bounds for Learning Single Neurons with Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Cryptographic Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Nearly-Tight Bounds for Testing Histogram Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Outlier-Robust Sparse Estimation via Non-Convex Optimization.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Streaming Algorithms for High-Dimensional Robust Statistics.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Learning a Single Neuron with Adversarial Label Noise via Gradient Descent.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models.

[BibT_eX]

[DOI]

Yuxin Sun

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Robust Sparse Mean Estimation via Sum of Squares.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Non-Gaussian Component Analysis via Lattice Basis Reduction.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Efficient Approximation Algorithms for the Inverse Semivalue Problem.

[BibT_eX]

[DOI]

Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, 2022

Hardness of Learning a Single Neuron with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Threshold Phenomena in Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

CoRR, 2021

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals.

[BibT_eX]

[DOI]

CoRR, 2021

Robustness meets algorithms.

[BibT_eX]

[DOI]

Commun. ACM, 2021

Efficiently learning halfspaces with Tsybakov noise.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

ReLU Regression with Massart Noise.

[BibT_eX]

[DOI]

Jongho Park

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Forster Decomposition and Learning Halfspaces with Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Statistical Query Lower Bounds for List-Decodable Linear Regression.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

List-Decodable Mean Estimation in Nearly-PCA Time.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Learning Online Algorithms with Distributional Advice.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees.

[BibT_eX]

[DOI]

Stephen Macke

Maryam Aliakbarpour

Aditya G. Parameswaran

Ronitt Rubinfeld

Proceedings of the 37th IEEE International Conference on Data Engineering, 2021

Outlier-Robust Learning of Ising Models Under Dobrushin's Condition.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Agnostic Proper Learning of Halfspaces under Gaussian Marginals.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

The Sample Complexity of Robust Covariance Testing.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Boosting in the Presence of Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Testing Bayesian Networks.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs.

[BibT_eX]

[DOI]

MohammadTaghi Hajiaghayi

Howard J. Karloff

Mauricio G. C. Resende

Subhabrata Sen

Oper. Res., 2020

Optimal Testing of Discrete Distributions with High Probability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Robustly Learning Mixtures of k Arbitrary Gaussians.

[BibT_eX]

[DOI]

CoRR, 2020

A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Learning Halfspaces with Tsybakov Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Robustly Learning any Clusterable Mixture of Gaussians.

[BibT_eX]

[DOI]

CoRR, 2020

Efficient Algorithms for Multidimensional Segmented Regression.

[BibT_eX]

[DOI]

Jerry Li

Anastasia Voloshinov

CoRR, 2020

Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals.

[BibT_eX]

[DOI]

Nikos Zarifis

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Non-Convex SGD Learns Halfspaces with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Outlier Robust Mean Estimation with Subgaussian Rates via Stability.

[BibT_eX]

[DOI]

Ankit Pensia

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

List-Decodable Mean Estimation via Iterative Multi-Filtering.

[BibT_eX]

[DOI]

Daniel Kongsgaard

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Efficiently Learning Adversarially Robust Halfspaces with Noise.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

High-dimensional Robust Mean Estimation via Gradient Descent.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Learning Halfspaces with Massart Noise Under Structured Distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Approximation Schemes for ReLU Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Robust High-Dimensional Statistics.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Robust Estimators in High-Dimensions Without the Computational Intractability.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Recent Advances in Algorithmic High-Dimensional Robust Statistics.

[BibT_eX]

[DOI]

CoRR, 2019

Collision-Based Testers are Optimal for Uniformity and Closeness.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2019

Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications).

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Efficient Algorithms and Lower Bounds for Robust Linear Regression.

[BibT_eX]

[DOI]

Weihao Kong

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

High-Dimensional Robust Mean Estimation in Nearly-Linear Time.

[BibT_eX]

[DOI]

Yu Cheng

Rong Ge

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Equipping Experts/Bandits with Long-term Memory.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Distribution-Independent PAC Learning of Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

Themis Gouleakis

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families.

[BibT_eX]

[DOI]

Brian Axelrod

Anastasios Sidiropoulos

Gregory Valiant

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Testing of Distributions via Sample Permutations.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Sever: A Robust Meta-Algorithm for Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Testing Identity of Multidimensional Histograms.

[BibT_eX]

[DOI]

John Peebles

Proceedings of the Conference on Learning Theory, 2019

Communication and Memory Efficient Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Faster Algorithms for High-Dimensional Robust Covariance Estimation.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games.

[BibT_eX]

[DOI]

Chrystalla Pavlou

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Testing Shape Restrictions of Discrete Distributions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

The complexity of optimal multidimensional pricing for a unit-demand buyer.

[BibT_eX]

[DOI]

Games Econ. Behav., 2018

Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities.

[BibT_eX]

[DOI]

Anastasios Sidiropoulos

CoRR, 2018

Learning geometric concepts with nasty noise.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

List-decodable robust mean estimation and learning mixtures of spherical gaussians.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Testing conditional independence of discrete distributions.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Testing for Families of Distributions via the Fourier Transform.

[BibT_eX]

[DOI]

Clément L. Canonne

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Robust Learning of Fixed-Structure Bayesian Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Differentially Private Identity and Equivalence Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Maryam Aliakbarpour

Ronitt Rubinfeld

Proceedings of the 35th International Conference on Machine Learning, 2018

Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms.

[BibT_eX]

[DOI]

Jerry Li

Ludwig Schmidt

Proceedings of the Conference On Learning Theory, 2018

Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities.

[BibT_eX]

[DOI]

Timothy Carpenter

Anastasios Sidiropoulos

Proceedings of the Conference On Learning Theory, 2018

2017

Sharp Bounds for Generalized Uniformity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Sample-Optimal Identity Testing with High Probability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Fourier-Based Testing for Families of Distributions.

[BibT_eX]

[DOI]

Clément L. Canonne

Electron. Colloquium Comput. Complex., 2017

Differentially Private Identity and Closeness Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Maryam Aliakbarpour

Ronitt Rubinfeld

CoRR, 2017

Playing Anonymous Games using Simple Strategies.

[BibT_eX]

[DOI]

Yu Cheng

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Sample-Optimal Density Estimation in Nearly-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Communication-Efficient Distributed Learning of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Being Robust (in High Dimensions) Can Be Practical.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Near-Optimal Closeness Testing of Discrete Histogram Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Learning Multivariate Log-concave Distributions.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

2016

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

How Good is the Chord Algorithm?

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

A New Approach for Testing Properties of Discrete Distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Efficient Robust Proper Learning of Log-concave Distributions.

[BibT_eX]

[DOI]

CoRR, 2016

The fourier transform of poisson multinomial distributions and its algorithmic applications.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Fast Algorithms for Segmented Regression.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

Learning Structured Distributions.

[BibT_eX]

[DOI]

Proceedings of the Handbook of Big Data., 2016

2015

Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

CoRR, 2015

Noise Stable Halfspaces are Close to Very Small Juntas.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2015

Learning Poisson Binomial Distributions.

[BibT_eX]

[DOI]

Algorithmica, 2015

Testing Identity of Structured Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Learning from satisfying assignments.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms.

[BibT_eX]

[DOI]

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

Differentially Private Learning of Structured Discrete Distributions.

[BibT_eX]

[DOI]

Moritz Hardt

Ludwig Schmidt

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Theory Comput., 2014

Learning k-Modal Distributions via Testing.

[BibT_eX]

[DOI]

Theory Comput., 2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Efficient density estimation via piecewise polynomial approximation.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

The Complexity of Optimal Multidimensional Pricing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Optimal Algorithms for Testing Closeness of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

2013

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Improved Approximation of Linear Threshold Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2013

Testing k-Modal Distributions: Optimal Algorithms via Reductions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Learning mixtures of structured distributions over discrete domains.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Learning Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The Inverse Shapley Value Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Inverse Problems in Approximate Uniform Generation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the Distribution of the Fourier Spectrum of Halfspaces

[BibT_eX]

[DOI]

CoRR, 2012

Efficiency-Revenue Trade-Offs in Auctions.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

George Pierrakos

Yaron Singer

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Approximation of Multiobjective Optimization Problems.

[BibT_eX]

[DOI]

PhD thesis, 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

[BibT_eX]

[DOI]

CoRR, 2011

Learning $k$-Modal Distributions via Testing

[BibT_eX]

[DOI]

CoRR, 2011

Learning transformed product distributions

[BibT_eX]

[DOI]

Mohammad Taghi Hajiaghayi

CoRR, 2011

Efficiently Testing Sparse GF(2) Polynomials.

[BibT_eX]

[DOI]

Algorithmica, 2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Supervised design space exploration by compositional approximation of Pareto sets.

[BibT_eX]

[DOI]

Proceedings of the 48th Design Automation Conference, 2011

Disjoint-Path Facility Location: Theory and Practice.

[BibT_eX]

[DOI]

David S. Johnson

Howard J. Karloff

Mauricio G. C. Resende

Subhabrata Sen

Proceedings of the Thirteenth Workshop on Algorithm Engineering and Experiments, 2011

2010

Bounded Independence Fools Halfspaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Bounded Independence Fools Degree-2 Threshold Functions.

[BibT_eX]

[DOI]

Jelani Nelson

Electron. Colloquium Comput. Complex., 2009

2008

Succinct approximate convex pareto curves.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Efficiently Testing Sparse GF(2) Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Testing for Concise Representations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems.

[BibT_eX]

[DOI]