research
∙
02/25/2023
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
A fundamental question in reinforcement learning theory is: suppose the ...
share
research
∙
03/06/2022
Coresets for Data Discretization and Sine Wave Fitting
In the monitoring problem, the input is an unbounded stream P=p_1,p_2⋯ o...
research
∙
02/11/2022
Computational-Statistical Gaps in Reinforcement Learning
Reinforcement learning with function approximation has recently achieved...
research
∙
11/08/2021
Realizable Learning is All You Need
The equivalence of realizable and agnostic learnability is a fundamental...
research
∙
06/14/2021
Boosting in the Presence of Massart Noise
We study the problem of boosting the accuracy of a weak learner in the (...
research
∙
03/13/2021
Fooling Gaussian PTFs via Local Hyperconcentration
We give a pseudorandom generator that fools degree-d polynomial threshol...
research
∙
02/09/2021
Bounded Memory Active Learning through Enriched Queries
The explosive growth of easily-accessible unlabeled data has lead to gro...
research
∙
01/06/2021
Highway: Efficient Consensus with Flexible Finality
There has been recently a lot of progress in designing efficient partial...
research
∙
05/13/2020
Robustly Learning any Clusterable Mixture of Gaussians
We study the efficient learnability of high-dimensional Gaussian mixture...
research
∙
01/15/2020
Noise-tolerant, Reliable Active Classification with Comparison Queries
With the explosion of massive, widely available unlabeled data in the pa...
research
∙
11/19/2019
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
We study high-dimensional sparse estimation tasks in a robust setting wh...
research
∙
02/10/2019
The Optimal Approximation Factor in Density Estimation
Consider the following problem: given two arbitrary densities q_1,q_2 an...
research
∙
11/06/2018
The entropy of lies: playing twenty questions with a liar
`Twenty questions' is a guessing game played by two players: Bob thinks ...
research
∙
09/15/2017
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
In the Orthogonal Vectors (OV) problem, we wish to determine if there is...
research
∙
06/23/2016
Robust Learning of Fixed-Structure Bayesian Networks
We investigate the problem of learning Bayesian networks in an agnostic ...
research
∙
04/21/2016