6 citations · 9 across the 3 of their papers we have counts for
4 papers
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Sumegha Garg, Songhua He, Yuanzhi Li +2
We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix and parameters…
Memorization capacity of deep ReLU neural networks characterized by width and depth
Xin Yang, Yunfei Yang
This paper studies the memorization capacity of deep neural networks with ReLU activation. Specifically, we investigate the minimal size of such networks to memorize any data p…
On the Bias of Reed-Muller Codes over Odd Prime Fields
Paul Beame, Shayan Oveis Gharan, Xin Yang
We study the bias of random bounded-degree polynomials over odd prime fields and show that, with probability exponentially close to 1, such polynomials have exponentially small bia…
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions
Paul Beame, Shayan Oveis Gharan, Xin Yang
We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where…