Ilias Diakonikolas

Sihan Liu

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

ReLU Regression with Massart Noise.

[BibT_eX]

[DOI]

Jongho Park

CoRR, 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]

Jong Ho 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

Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.

[BibT_eX]

[DOI]

J. ACM, 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

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

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

Bounded Independence Fools Halfspaces.

[BibT_eX]

[DOI]

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]