research
∙
08/23/2023
Explicit separations between randomized and deterministic Number-on-Forehead communication
We study the power of randomness in the Number-on-Forehead (NOF) model i...
share
research
∙
02/25/2023
Exponential Hardness of Reinforcement Learning with Linear Function Approximation
A fundamental question in reinforcement learning theory is: suppose the ...
research
∙
02/13/2023
Do PAC-Learners Learn the Marginal Distribution?
We study a foundational variant of Valiant and Vapnik and Chervonenkis' ...
research
∙
01/13/2023
Streaming Lower Bounds and Asymmetric Set-Disjointness
Frequency estimation in data streams is one of the classical problems in...
research
∙
05/02/2022
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets
Fast mixing of random walks on hypergraphs has led to myriad breakthroug...
research
∙
02/11/2022
Computational-Statistical Gaps in Reinforcement Learning
Reinforcement learning with function approximation has recently achieved...
research
∙
11/17/2021
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Hypercontractivity is one of the most powerful tools in Boolean function...
research
∙
11/08/2021
Realizable Learning is All You Need
The equivalence of realizable and agnostic learnability is a fundamental...
research
∙
03/19/2021
Bilinear Classes: A Structural Framework for Provable Generalization in RL
This work introduces Bilinear Classes, a new structural framework, which...
research
∙
02/09/2021
Bounded Memory Active Learning through Enriched Queries
The explosive growth of easily-accessible unlabeled data has lead to gro...
research
∙
11/09/2020
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games
Higher order random walks (HD-walks) on high dimensional expanders have ...
research
∙
10/22/2020
Codes over integers, and the singularity of random matrices with large entries
The prototypical construction of error correcting codes is based on line...
research
∙
10/18/2020
Log-rank and lifting for AND-functions
Let f: {0,1}^n →{0, 1} be a boolean function, and let f_ (x, y) = f(x y...
research
∙
08/04/2020
Fractional Pseudorandom Generators from Any Fourier Level
We prove new results on the polarizing random walk framework introduced ...
research
∙
04/23/2020
Point Location and Active Learning: Learning Halfspaces Almost Optimally
Given a finite set X ⊂ℝ^d and a binary linear classifier c: ℝ^d →{0,1}, ...
research
∙
02/08/2020
Towards a combinatorial characterization of bounded memory learning
Combinatorial dimensions play an important role in the theory of machine...
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
∙
09/24/2019
Decision list compression by mild random restrictions
A decision list is an ordered list of rules. Each rule is specified by a...
research
∙
08/22/2019
Improved bounds for the sunflower lemma
A sunflower with r petals is a collection of r sets so that the intersec...
research
∙
07/08/2019
The Power of Comparisons for Actively Learning Linear Classifiers
In the world of big data, large but costly to label datasets dominate ma...
research
∙
03/01/2019
From DNF compression to sunflower theorems via regularity
The sunflower conjecture is one of the most well-known open problems in ...
research
∙
09/24/2018
Optimality of Linear Sketching under Modular Updates
We study the relation between streaming algorithms and linear sketching ...
research
∙
04/23/2018
Generalized comparison trees for point-location problems
Let H be an arbitrary family of hyper-planes in d-dimensions. We show th...
research
∙
04/22/2018
Torus polynomials: an algebraic approach to ACC lower bounds
We propose an algebraic approach to proving circuit lower bounds for ACC...
research
∙
03/07/2018
MDS matrices over small fields: A proof of the GM-MDS conjecture
An MDS matrix is a matrix whose minors all have full rank. A question ar...
research
∙
03/07/2018