research
∙
04/05/2023
A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
Reed-Muller codes were introduced in 1954, with a simple explicit constr...
share
research
∙
10/12/2022
The Power of Two Matrices in Spectral Algorithms
Spectral algorithms are some of the main tools in optimization and infer...
research
∙
03/22/2022
Spectral Algorithms Optimally Recover (Censored) Planted Dense Subgraphs
We study spectral algorithms for the planted dense subgraph problem (PDS...
research
∙
08/09/2021
On the Power of Differentiable Learning versus PAC and SQ Learning
We study the power of learning via mini-batch stochastic gradient descen...
research
∙
07/13/2021
Spectral Recovery of Binary Censored Block Models
Community detection is the problem of identifying community structure in...
research
∙
06/15/2021
Spoofing Generalization: When Can't You Trust Proprietary Models?
In this work, we study the computational complexity of determining wheth...
research
∙
01/15/2021
Learning to Sample from Censored Markov Random Fields
We study learning Censor Markov Random Fields (abbreviated CMRFs). These...
research
∙
01/07/2020
Poly-time universality and limitations of deep learning
The goal of this paper is to characterize function distributions that de...
research
∙
04/11/2019
The Circuit Complexity of Inference
Belief propagation is one of the foundations of probabilistic and causal...
research
∙
12/16/2018
Provable limitations of deep learning
As the success of deep learning reaches more grounds, one would like to ...
research
∙
09/13/2018