|
+
PDF
Chat
|
A Near-optimal Algorithm for Learning Margin Halfspaces with Massart
Noise
|
2025
|
Ilias Diakonikolas
Nikos Zarifis
|
|
+
PDF
Chat
|
Entangled Mean Estimation in High-Dimensions
|
2025
|
Ilias Diakonikolas
Daniel M. Kane
Sihan Liu
Thanasis Pittas
|
|
+
PDF
Chat
|
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
|
2025
|
Ilias Diakonikolas
Daniel M. Kane
Jasper C. H. Lee
Thanasis Pittas
|
|
+
PDF
Chat
|
Active Learning of General Halfspaces: Label Queries vs Membership
Queries
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Mingchen Ma
|
|
+
PDF
Chat
|
SoS Certificates for Sparse Singular Values and Their Applications:
Robust Statistics, Subspace Distortion, and More
|
2024
|
Ilias Diakonikolas
Samuel B. Hopkins
Ankit Pensia
Stefan Tiegel
|
|
+
PDF
Chat
|
Implicit High-Order Moment Tensor Estimation and Learning Latent
Variable Models
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
PDF
Chat
|
Reliable Learning of Halfspaces under Gaussian Marginals
|
2024
|
Ilias Diakonikolas
Lisheng Ren
Nikos Zarifis
|
|
+
PDF
Chat
|
Learning a Single Neuron Robustly to Distributional Shifts and
Adversarial Label Noise
|
2024
|
Shuyao Li
Sushrut Karmalkar
Ilias Diakonikolas
Jelena Diakonikolas
|
|
+
PDF
Chat
|
Sample and Computationally Efficient Robust Learning of Gaussian
Single-Index Models
|
2024
|
Puqian Wang
Nikos Zarifis
Ilias Diakonikolas
Jelena Diakonikolas
|
|
+
PDF
Chat
|
SoS Certifiability of Subgaussian Distributions and its Algorithmic
Applications
|
2024
|
Ilias Diakonikolas
Samuel B. Hopkins
Ankit Pensia
Stefan Tiegel
|
|
+
PDF
Chat
|
Sum-of-squares lower bounds for Non-Gaussian Component Analysis
|
2024
|
Ilias Diakonikolas
Sushrut Karmalkar
Shuo Pang
Aaron Potechin
|
|
+
PDF
Chat
|
Efficient Testable Learning of General Halfspaces with Adversarial Label
Noise
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Sihan Liu
Nikos Zarifis
|
|
+
PDF
Chat
|
First Order Stochastic Optimization with Oblivious Noise
|
2024
|
Ilias Diakonikolas
Sushrut Karmalkar
Jong-Ho Park
Christos Tzamos
|
|
+
|
Super Non-singular Decompositions of Polynomials and Their Application to Robustly Learning Low-Degree PTFs
|
2024
|
Ilias Diakonikolas
D. Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
|
|
+
|
Testing Closeness of Multivariate Distributions via Ramsey Theory
|
2024
|
Ilias Diakonikolas
D. Kane
Sihan Liu
|
|
+
PDF
Chat
|
Online Learning of Halfspaces with Massart Noise
|
2024
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
PDF
Chat
|
Super Non-singular Decompositions of Polynomials and their Application
to Robustly Learning Low-degree PTFs
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
|
|
+
PDF
Chat
|
Robust Sparse Estimation for Gaussians with Optimal Error under Huber
Contamination
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Sushrut Karmalkar
Ankit Pensia
Thanasis Pittas
|
|
+
PDF
Chat
|
Robust Second-Order Nonconvex Optimization and Its Application to Low
Rank Matrix Sensing
|
2024
|
Shuyao Li
Yu Cheng
Ilias Diakonikolas
Jelena Diakonikolas
Rong Ge
Stephen J. Wright
|
|
+
PDF
Chat
|
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker
Assumptions
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Lisheng Ren
Yuxin Sun
|
|
+
PDF
Chat
|
Statistical Query Lower Bounds for Learning Truncated Gaussians
|
2024
|
Ilias Diakonikolas
Daniel M. Kane
Thanasis Pittas
Nikos Zarifis
|
|
+
PDF
Chat
|
Robustly Learning Single-Index Models via Alignment Sharpness
|
2024
|
Nikos Zarifis
Puqian Wang
Ilias Diakonikolas
Jelena Diakonikolas
|
|
+
PDF
Chat
|
How Does Unlabeled Data Provably Help Out-of-Distribution Detection?
|
2024
|
Xuefeng Du
Zhen Fang
Ilias Diakonikolas
Yixuan Li
|
|
+
PDF
Chat
|
Online Robust Mean Estimation
|
2024
|
Daniel M. Kane
Ilias Diakonikolas
Hanshen Xiao
Sihan Liu
|
|
+
|
Algorithmic High-Dimensional Robust Statistics
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
A Strongly Polynomial Algorithm for Approximate Forster Transforms and Its Application to Halfspace Learning
|
2023
|
Ilias Diakonikolas
Christos Tzamos
Daniel M. Kane
|
|
+
PDF
Chat
|
Gaussian Mean Testing Made Simple
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
|
|
+
|
Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Lisheng Ren
|
|
+
|
Efficient Testable Learning of Halfspaces with Adversarial Label Noise
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Sihan Liu
Nikos Zarifis
|
|
+
|
A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Jasper C. H. Lee
Ankit Pensia
Thanasis Pittas
|
|
+
|
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
Thanasis Pittas
|
|
+
|
Robustly Learning a Single Neuron via Sharpness
|
2023
|
Puqian Wang
Nikos Zarifis
Ilias Diakonikolas
Jelena Diakonikolas
|
|
+
|
SQ Lower Bounds for Learning Bounded Covariance GMMs
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Thanasis Pittas
Nikos Zarifis
|
|
+
|
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise
|
2023
|
Ilias Diakonikolas
Jelena Diakonikolas
Daniel M. Kane
Puqian Wang
Nikos Zarifis
|
|
+
|
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise
|
2023
|
Ilias Diakonikolas
Jelena Diakonikolas
Daniel M. Kane
Puqian Wang
Nikos Zarifis
|
|
+
|
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Self-Directed Linear Classification
|
2023
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
|
2023
|
Ilias Diakonikolas
Sushrut Karmalkar
Jong-Ho Park
Christos Tzamos
|
|
+
|
SQ Lower Bounds for Learning Mixtures of Linear Classifiers
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Yuxin Sun
|
|
+
|
Online Robust Mean Estimation
|
2023
|
Daniel M. Kane
Ilias Diakonikolas
Hanshen Xiao
Sihan Liu
|
|
+
|
Testing Closeness of Multivariate Distributions via Ramsey Theory
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Sihan Liu
|
|
+
|
Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
Thanasis Pittas
|
|
+
|
Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Jasper C. H. Lee
Thanasis Pittas
|
|
+
|
Agnostically Learning Multi-index Models with Queries
|
2023
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
PDF
Chat
|
Clustering mixture models in almost-linear time via list-decodable mean estimation
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
Jerry Li
Kevin Tian
|
|
+
PDF
Chat
|
Learning general halfspaces with general Massart noise under the Gaussian distribution
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Streaming Algorithms for High-Dimensional Robust Statistics
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
Thanasis Pittas
|
|
+
|
Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Yuxin Sun
|
|
+
|
Robust Sparse Mean Estimation via Sum of Squares
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Sushrut Karmalkar
Ankit Pensia
Thanasis Pittas
|
|
+
|
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Sushrut Karmalkar
Ankit Pensia
Thanasis Pittas
|
|
+
|
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
|
2022
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Near-Optimal Bounds for Testing Histogram Distributions
|
2022
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Sihan Liu
|
|
+
|
Cryptographic Hardness of Learning Halfspaces with Massart Noise
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Pasin Manurangsi
Lisheng Ren
|
|
+
|
SQ Lower Bounds for Learning Single Neurons with Massart Noise
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Lisheng Ren
Yuxin Sun
|
|
+
|
Gaussian Mean Testing Made Simple
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
|
|
+
|
Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions
|
2022
|
Ilias Diakonikolas
Daniel M. Kane
Jasper C. H. Lee
Ankit Pensia
|
|
+
|
A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning
|
2022
|
Ilias Diakonikolas
Christos Tzamos
Daniel M. Kane
|
|
+
|
A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points
|
2022
|
Daniel M. Kane
Ilias Diakonikolas
|
|
+
|
Forster Decomposition and Learning Halfspaces with Noise
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Christos Tzamos
|
|
+
|
ReLU Regression with Massart Noise
|
2021
|
Ilias Diakonikolas
Jongho Park
Christos Tzamos
|
|
+
|
ReLU Regression with Massart Noise
|
2021
|
Ilias Diakonikolas
Jong-Ho Park
Christos Tzamos
|
|
+
|
Threshold Phenomena in Learning Halfspaces with Massart Noise
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
Yuxin Sun
|
|
+
|
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Thanasis Pittas
Nikos Zarifis
|
|
+
|
The Sample Complexity of Robust Covariance Testing
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
PDF
Chat
|
Optimal testing of discrete distributions with high probability
|
2021
|
Ilias Diakonikolas
Themis Gouleakis
Daniel M. Kane
John Peebles
Eric Price
|
|
+
PDF
Chat
|
Robustness meets algorithms
|
2021
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
PDF
Chat
|
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees
|
2021
|
Stephen Macke
Maryam Aliakbarpour
Ilias Diakonikolas
Aditya Parameswaran
Ronitt Rubinfeld
|
|
+
|
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Thanasis Pittas
Nikos Zarifis
|
|
+
|
Outlier-Robust Learning of Ising Models Under Dobrushin's Condition
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
Yuxin Sun
|
|
+
|
Forster Decomposition and Learning Halfspaces with Noise
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Christos Tzamos
|
|
+
|
Outlier-Robust Sparse Estimation via Non-Convex Optimization
|
2021
|
Yu Cheng
Ilias Diakonikolas
Daniel M. Kane
Rong Ge
Shivam Gupta
Mahdi Soltanolkotabi
|
|
+
|
Non-Gaussian Component Analysis via Lattice Basis Reduction
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
ReLU Regression with Massart Noise
|
2021
|
Ilias Diakonikolas
Jong-Ho Park
Christos Tzamos
|
|
+
|
Learning General Halfspaces with General Massart Noise under the Gaussian Distribution
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Boosting in the Presence of Massart Noise
|
2021
|
Ilias Diakonikolas
Russell Impagliazzo
Daniel M. Kane
Rex Lei
Jessica Sorrell
Christos Tzamos
|
|
+
|
Agnostic Proper Learning of Halfspaces under Gaussian Marginals
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Statistical Query Lower Bounds for List-Decodable Linear Regression
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
Thanasis Pittas
Alistair Stewart
|
|
+
|
Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation
|
2021
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
Jerry Li
Kevin Tian
|
|
+
|
The Sample Complexity of Robust Covariance Testing
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Hardness of Learning Halfspaces with Massart Noise.
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Robust High-Dimensional Statistics
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
List-Decodable Mean Estimation in Nearly-PCA Time
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
Jerry Li
Kevin Tian
|
|
+
PDF
Chat
|
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures
|
2020
|
Ainesh Bakshi
Ilias Diakonikolas
Samuel B. Hopkins
Daniel M. Kane
Sushrut Karmalkar
Pravesh K. Kothari
|
|
+
|
Optimal Testing of Discrete Distributions with High Probability
|
2020
|
Ilias Diakonikolas
Themis Gouleakis
Daniel M. Kane
John Peebles
Eric Price
|
|
+
|
Outlier Robust Mean Estimation with Subgaussian Rates via Stability
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
|
|
+
|
Outlier Robust Mean Estimation with Subgaussian Rates via Stability
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
|
|
+
|
Approximation Schemes for ReLU Regression
|
2020
|
Ilias Diakonikolas
Surbhi Goel
Sushrut Karmalkar
Adam R. Klivans
Mahdi Soltanolkotabi
|
|
+
|
Learning Halfspaces with Tsybakov Noise.
|
2020
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Robustly Learning any Clusterable Mixture of Gaussians.
|
2020
|
Ilias Diakonikolas
Samuel B. Hopkins
Daniel M. Kane
Sushrut Karmalkar
|
|
+
PDF
Chat
|
Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs
|
2020
|
David Johnson
Lee Breslau
Ilias Diakonikolas
Nick Duffield
Yu Gu
MohammadTaghi Hajiaghayi
Howard Karloff
MaurĂcio G. C. Resende
Subhabrata Sen
|
|
+
|
Learning Halfspaces with Massart Noise Under Structured Distributions
|
2020
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
PDF
Chat
|
Testing Bayesian Networks
|
2020
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Efficient Algorithms for Multidimensional Segmented Regression
|
2020
|
Ilias Diakonikolas
Jerry Li
Anastasia Voloshinov
|
|
+
|
High-Dimensional Robust Mean Estimation via Gradient Descent
|
2020
|
Yu Cheng
Ilias Diakonikolas
Rong Ge
Mahdi Soltanolkotabi
|
|
+
|
Efficiently Learning Adversarially Robust Halfspaces with Noise
|
2020
|
Omar Montasser
Surbhi Goel
Ilias Diakonikolas
Nathan Srebro
|
|
+
|
Approximation Schemes for ReLU Regression
|
2020
|
Ilias Diakonikolas
Surbhi Goel
Sushrut Karmalkar
Adam R. Klivans
Mahdi Soltanolkotabi
|
|
+
|
Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
|
2020
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
List-Decodable Mean Estimation via Iterative Multi-Filtering
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
|
|
+
|
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Nikos Zarifis
|
|
+
|
Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Nikos Zarifis
|
|
+
|
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Pasin Manurangsi
|
|
+
|
Learning Halfspaces with Massart Noise Under Structured Distributions
|
2020
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
List-Decodable Mean Estimation via Iterative Multi-Filtering
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
|
|
+
|
Optimal Testing of Discrete Distributions with High Probability.
|
2020
|
Ilias Diakonikolas
Themis Gouleakis
Daniel M. Kane
John Peebles
Eric Price
|
|
+
|
List-Decodable Mean Estimation in Nearly-PCA Time
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Daniel Kongsgaard
Jerry Li
Kevin Tian
|
|
+
|
The Sample Complexity of Robust Covariance Testing
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Robustly Learning Mixtures of $k$ Arbitrary Gaussians
|
2020
|
Ainesh Bakshi
Ilias Diakonikolas
Jia He
Daniel M. Kane
Pravesh K. Kothari
Santosh Vempala
|
|
+
|
Optimal Testing of Discrete Distributions with High Probability
|
2020
|
Ilias Diakonikolas
Themis Gouleakis
Daniel M. Kane
John Peebles
Eric Price
|
|
+
|
Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees
|
2020
|
Stephen Macke
Maryam Aliakbarpour
Ilias Diakonikolas
Aditya Parameswaran
Ronitt Rubinfeld
|
|
+
|
Outlier Robust Mean Estimation with Subgaussian Rates via Stability
|
2020
|
Ilias Diakonikolas
Daniel M. Kane
Ankit Pensia
|
|
+
|
Robustly Learning any Clusterable Mixture of Gaussians
|
2020
|
Ilias Diakonikolas
Samuel B. Hopkins
Daniel M. Kane
Sushrut Karmalkar
|
|
+
|
Learning Halfspaces with Tsybakov Noise
|
2020
|
Ilias Diakonikolas
Vasilis Kontonis
Christos Tzamos
Nikos Zarifis
|
|
+
|
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
|
2019
|
Ilias Diakonikolas
Daniel M. Kane
Sushrut Karmalkar
Eric Price
Alistair Stewart
|
|
+
|
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
|
2019
|
Ilias Diakonikolas
Daniel M. Kane
Pasin Manurangsi
|
|
+
PDF
Chat
|
On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
|
2019
|
Ilias Diakonikolas
Chrystalla Pavlou
|
|
+
PDF
Chat
|
Degree-đť‘‘ chow parameters robustly determine degree-đť‘‘ PTFs (and algorithmic applications)
|
2019
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Faster Algorithms for High-Dimensional Robust Covariance Estimation
|
2019
|
Yu Cheng
Ilias Diakonikolas
Rong Ge
David P. Woodruff
|
|
+
|
Robust Estimators in High-Dimensions Without the Computational Intractability
|
2019
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
PDF
Chat
|
Efficient Algorithms and Lower Bounds for Robust Linear Regression
|
2019
|
Ilias Diakonikolas
Weihao Kong
Alistair Stewart
|
|
+
PDF
Chat
|
Robust Estimators in High-Dimensions Without the Computational Intractability
|
2019
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Equipping Experts/Bandits with Long-term Memory
|
2019
|
Kai Zheng
Haipeng Luo
Ilias Diakonikolas
Liwei Wang
|
|
+
|
Distribution-Independent PAC Learning of Halfspaces with Massart Noise
|
2019
|
Ilias Diakonikolas
Themis Gouleakis
Christos Tzamos
|
|
+
|
Faster Algorithms for High-Dimensional Robust Covariance Estimation
|
2019
|
Yu Cheng
Ilias Diakonikolas
Rong Ge
David P. Woodruff
|
|
+
PDF
Chat
|
High-Dimensional Robust Mean Estimation in Nearly-Linear Time
|
2019
|
Yu Cheng
Ilias Diakonikolas
Rong Ge
|
|
+
|
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
|
2019
|
Brian Axelrod
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
Gregory Valiant
|
|
+
|
Communication and Memory Efficient Testing of Discrete Distributions
|
2019
|
Ilias Diakonikolas
Themis Gouleakis
Daniel M. Kane
Sankeerth Rao
|
|
+
|
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
|
2019
|
Brian Axelrod
Ilias Diakonikolas
Alistair Stewart
Anastasios Sidiropoulos
Gregory Valiant
|
|
+
|
Distribution-Independent PAC Learning of Halfspaces with Massart Noise
|
2019
|
Ilias Diakonikolas
Themis Gouleakis
Christos Tzamos
|
|
+
|
Recent Advances in Algorithmic High-Dimensional Robust Statistics
|
2019
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
|
2019
|
Ilias Diakonikolas
Sushrut Karmalkar
Daniel M. Kane
Eric Price
Alistair Stewart
|
|
+
|
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
|
2019
|
Ilias Diakonikolas
Daniel M. Kane
Pasin Manurangsi
|
|
+
|
On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
|
2018
|
Ilias Diakonikolas
Chrystalla Pavlou
|
|
+
|
A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities.
|
2018
|
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
|
|
+
|
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)
|
2018
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
|
2018
|
Timothy S. Carpenter
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
|
|
+
|
Testing conditional independence of discrete distributions
|
2018
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Learning geometric concepts with nasty noise
|
2018
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
List-decodable robust mean estimation and learning mixtures of spherical gaussians
|
2018
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
|
2018
|
Timothy S. Carpenter
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
|
|
+
|
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
|
2018
|
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
|
Testing Conditional Independence of Discrete Distributions
|
2018
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Sever: A Robust Meta-Algorithm for Stochastic Optimization
|
2018
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Jacob Steinhardt
Alistair Stewart
|
|
+
|
Testing Identity of Multidimensional Histograms
|
2018
|
Ilias Diakonikolas
Daniel M. Kane
John Peebles
|
|
+
|
Testing for Families of Distributions via the Fourier Transform
|
2018
|
Clément L. Canonne
Ilias Diakonikolas
Alistair Stewart
|
|
+
PDF
Chat
|
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
|
2018
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Robust Learning of Fixed-Structure Bayesian Networks
|
2018
|
Yu Cheng
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games
|
2018
|
Ilias Diakonikolas
Chrystalla Pavlou
|
|
+
|
A Polynomial Time Algorithm for Maximum Likelihood Estimation of Multivariate Log-concave Densities
|
2018
|
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
|
|
+
|
Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)
|
2018
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
|
2018
|
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
|
Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities
|
2018
|
Timothy S. Carpenter
Ilias Diakonikolas
Anastasios Sidiropoulos
Alistair Stewart
|
|
+
|
Efficient Algorithms and Lower Bounds for Robust Linear Regression
|
2018
|
Ilias Diakonikolas
Weihao Kong
Alistair Stewart
|
|
+
|
High-Dimensional Robust Mean Estimation in Nearly-Linear Time
|
2018
|
Yu Cheng
Ilias Diakonikolas
Rong Ge
|
|
+
|
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Sample-Optimal Identity Testing with High Probability
|
2017
|
Ilias Diakonikolas
Themis Gouleakis
John Peebles
Eric Price
|
|
+
PDF
Chat
|
The Inverse Shapley value problem
|
2017
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Being Robust (in High Dimensions) Can Be Practical
|
2017
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Learning Geometric Concepts with Nasty Noise
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
Testing Shape Restrictions of Discrete Distributions
|
2017
|
Clément L. Canonne
Ilias Diakonikolas
Themis Gouleakis
Ronitt Rubinfeld
|
|
+
|
Fourier-Based Testing for Families of Distributions
|
2017
|
Clément L. Canonne
Ilias Diakonikolas
Alistair Stewart
|
|
+
|
Testing Bayesian Networks
|
2017
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
|
2017
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Near-Optimal Closeness Testing of Discrete Histogram Distributions
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Being Robust (in High Dimensions) Can Be Practical
|
2017
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Sample-Optimal Density Estimation in Nearly-Linear Time
|
2017
|
Jayadev Acharya
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
|
Differentially Private Identity and Closeness Testing of Discrete Distributions
|
2017
|
Maryam Aliakbarpour
Ilias Diakonikolas
Ronitt Rubinfeld
|
|
+
|
Sharp Bounds for Generalized Uniformity Testing
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Testing Conditional Independence of Discrete Distributions
|
2017
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Sharp Bounds for Generalized Uniformity Testing.
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Optimal Identity Testing with High Probability
|
2017
|
Ilias Diakonikolas
Themis Gouleakis
John Peebles
Eric Price
|
|
+
|
Playing Anonymous Games using Simple Strategies
|
2017
|
Yu Cheng
Ilias Diakonikolas
Alistair Stewart
|
|
+
|
List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Being Robust (in High Dimensions) Can Be Practical
|
2017
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Near-Optimal Closeness Testing of Discrete Histogram Distributions
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Fourier-Based Testing for Families of Distributions
|
2017
|
Clément L. Canonne
Ilias Diakonikolas
Alistair Stewart
|
|
+
|
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
|
2017
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Learning Geometric Concepts with Nasty Noise
|
2017
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Testing Bayesian Networks
|
2016
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Collision-based Testers are Optimal for Uniformity and Closeness
|
2016
|
Ilias Diakonikolas
Themis Gouleakis
John Peebles
Eric Price
|
|
+
|
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
A New Approach for Testing Properties of Discrete Distributions
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
PDF
Chat
|
Robust Estimators in High Dimensions without the Computational Intractability
|
2016
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Playing Anonymous Games using Simple Strategies
|
2016
|
Yu Cheng
Ilias Diakonikolas
Alistair Stewart
|
|
+
|
Fast algorithms for segmented regression
|
2016
|
Jayadev Acharya
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
PDF
Chat
|
The fourier transform of poisson multinomial distributions and its algorithmic applications
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Robust Estimators in High Dimensions without the Computational Intractability
|
2016
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Testing Shape Restrictions of Discrete Distributions
|
2016
|
Clément L. Canonne
Ilias Diakonikolas
Themistoklis Gouleakis
Ronitt Rubinfeld
|
|
+
|
Learning Multivariate Log-concave Distributions
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
|
2016
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Efficient Robust Proper Learning of Log-concave Distributions
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Robust Learning of Fixed-Structure Bayesian Networks
|
2016
|
Yu Cheng
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Fast Algorithms for Segmented Regression
|
2016
|
Jayadev Acharya
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
|
Near-Optimal Disjoint-Path Facility Location Through Set Cover by Pairs
|
2016
|
David S. Johnson
Lee Breslau
Ilias Diakonikolas
Nick Duffield
Yu Gu
MohammadTaghi Hajiaghayi
Howard Karloff
MaurĂcio G. C. Resende
Subhabrata Sen
|
|
+
PDF
Chat
|
How Good is the Chord Algorithm?
|
2016
|
Constantinos Daskalakis
Ilias Diakonikolas
Mihalis Yannakakis
|
|
+
|
Learning Multivariate Log-concave Distributions.
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Playing Anonymous Games using Simple Strategies
|
2016
|
Yu Cheng
Ilias Diakonikolas
Alistair Stewart
|
|
+
|
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Collision-based Testers are Optimal for Uniformity and Closeness
|
2016
|
Ilias Diakonikolas
Themis Gouleakis
John Peebles
Eric Price
|
|
+
|
Robust Estimators in High Dimensions without the Computational Intractability
|
2016
|
Ilias Diakonikolas
Gautam Kamath
Daniel M. Kane
Jerry Li
Ankur Moitra
Alistair Stewart
|
|
+
|
Testing Bayesian Networks
|
2016
|
Clément L. Canonne
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
A New Approach for Testing Properties of Discrete Distributions
|
2016
|
Ilias Diakonikolas
Daniel M. Kane
|
|
+
|
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Testing Shape Restrictions of Discrete Distributions
|
2015
|
Clément L. Canonne
Ilias Diakonikolas
Themis Gouleakis
Ronitt Rubinfeld
|
|
+
PDF
Chat
|
Learning Poisson Binomial Distributions
|
2015
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
PDF
Chat
|
None
|
2015
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Sample-Optimal Density Estimation in Nearly-Linear Time
|
2015
|
Jayadev Acharya
Ilias Diakonikolas
Jerry Li
Ludwig Schmidt
|
|
+
|
Testing Shape Restrictions of Discrete Distributions
|
2015
|
Clément L. Canonne
Ilias Diakonikolas
Themis Gouleakis
Ronitt Rubinfeld
|
|
+
|
The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables
|
2015
|
Ilias Diakonikolas
Daniel M. Kane
Alistair Stewart
|
|
+
|
Testing Identity of Structured Distributions
|
2014
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
|
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
|
2014
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
PDF
Chat
|
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions
|
2014
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Efficient density estimation via piecewise polynomial approximation
|
2014
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
PDF
Chat
|
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
|
2014
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
PDF
Chat
|
None
|
2014
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
|
2014
|
Siu On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
|
Testing Identity of Structured Distributions
|
2014
|
Ilias Diakonikolas
Daniel M. Kane
Vladimir Nikishkin
|
|
+
PDF
Chat
|
Optimal Algorithms for Testing Closeness of Discrete Distributions
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Paul Valiant
Gregory Valiant
|
|
+
PDF
Chat
|
The Complexity of Optimal Multidimensional Pricing
|
2013
|
Xi Chen
Ilias Diakonikolas
Dimitris Paparas
Xiaorui Sun
Mihalis Yannakakis
|
|
+
PDF
Chat
|
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
|
2013
|
Constantinos Daskalakis
Anindya De
Ilias Diakonikolas
Ankur Moitra
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
How good is the Chord algorithm
|
2013
|
Constantinos Daskalakis
Ilias Diakonikolas
Mihalis Yannakakis
|
|
+
|
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning mixtures of structured distributions over discrete domains
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Xiaorui Sun
Rocco A. Servedio
|
|
+
PDF
Chat
|
Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions
|
2013
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
Gregory Valiant
Paul Valiant
|
|
+
PDF
Chat
|
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Optimal Algorithms for Testing Closeness of Discrete Distributions
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Gregory Valiant
Paul Valiant
|
|
+
|
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Efficient Density Estimation via Piecewise Polynomial Approximation
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
|
How good is the Chord algorithm?
|
2013
|
Constantinos Daskalakis
Ilias Diakonikolas
Mihalis Yannakakis
|
|
+
|
The Complexity of Optimal Multidimensional Pricing
|
2013
|
Xi Chen
Ilias Diakonikolas
Dimitris Paparas
Xiaorui Sun
Mihalis Yannakakis
|
|
+
|
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
|
2013
|
Constantinos Daskalakis
Anindya De
Ilias Diakonikolas
Ankur Moitra
Rocco A. Servedio
|
|
+
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Improved Approximation of Linear Threshold Functions
|
2012
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
|
2012
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning poisson binomial distributions
|
2012
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Efficiency-Revenue Trade-offs in Auctions
|
2012
|
Ilias Diakonikolas
Christos H. Papadimitriou
George Pierrakos
Yaron Singer
|
|
+
|
On the Distribution of the Fourier Spectrum of Halfspaces
|
2012
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
PDF
Chat
|
Learning <i>k</i>-Modal Distributions via Testing
|
2012
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Inverse problems in approximate uniform generation
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Efficiency-Revenue Trade-Offs in Auctions
|
2012
|
Ilias Diakonikolas
Christos H. Papadimitriou
George Pierrakos
Yaron Singer
|
|
+
PDF
Chat
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
A robust Khintchine-Kahane
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces
|
2012
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
|
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Learning mixtures of structured distributions over discrete domains
|
2012
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
|
On the Distribution of the Fourier Spectrum of Halfspaces
|
2012
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Efficiency-Revenue Trade-offs in Auctions
|
2012
|
Ilias Diakonikolas
Christos Papadimitriou
George Pierrakos
Yaron Singer
|
|
+
|
Learning Poisson Binomial Distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
|
2011
|
Ilias Diakonikolas
Ryan O’Donnell
Rocco A. Servedio
Yi Wu
|
|
+
|
Learning transformed product distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Learning transformed product distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
Gregory Valiant
Paul Valiant
|
|
+
|
Learning $k$-Modal Distributions via Testing
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Learning Poisson Binomial Distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Bounded Independence Fools Degree-2 Threshold Functions
|
2010
|
Ilias Diakonikolas
Daniel M. Kane
Jelani Nelson
|
|
+
PDF
Chat
|
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
|
2010
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
How good is the Chord algorithm?
|
2010
|
Constantinos Daskalakis
Ilias Diakonikolas
Mihalis Yannakakis
|
|
+
|
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
|
2010
|
Ilias Diakonikolas
Ryan O’Donnell
Rocco A. Servedio
Yi Wu
|
|
+
|
Bounded Independence Fools Degree-2 Threshold Functions
|
2009
|
Ilias Diakonikolas
Daniel M. Kane
Jelani Nelson
|
|
+
PDF
Chat
|
Improved Approximation of Linear Threshold Functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Improved Approximation of Linear Threshold Functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Average sensitivity and noise sensitivity of polynomial threshold functions
|
2009
|
Ilias Diakonikolas
Prasad Raghavendra
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Bounded Independence Fools Halfspaces
|
2009
|
Ilias Diakonikolas
Parikshit Gopalan
Ragesh Jaiswal
Rocco A. Servedio
Emanuele Viola
|
|
+
PDF
Chat
|
Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Bounded Independence Fools Degree-2 Threshold Functions
|
2009
|
Ilias Diakonikolas
Daniel M. Kane
Jelani Nelson
|
|
+
PDF
Chat
|
Efficiently Testing Sparse GF(2) Polynomials
|
2008
|
Ilias Diakonikolas
Homin K. Lee
Kevin Matulef
Rocco A. Servedio
Andrew Wan
|
|
+
|
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
|
2008
|
Ilias Diakonikolas
Mihalis Yannakakis
|
|
+
|
Efficiently Testing Sparse GF(2) Polynomials
|
2008
|
Ilias Diakonikolas
Homin K. Lee
Kevin Matulef
Rocco A. Servedio
Andrew Wan
|
|
+
PDF
Chat
|
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
|
2007
|
Ilias Diakonikolas
Mihalis Yannakakis
|