research
∙
05/29/2023
Quantum chi-squared tomography and mutual information testing
For quantum state tomography on rank-r dimension-d states, we show that ...
share
research
∙
02/27/2023
Query-optimal estimation of unitary channels in diamond distance
We consider process tomography for unitary quantum channels. Given acces...
research
∙
08/16/2022
Mean estimation when you have the source code; or, quantum Monte Carlo methods
Suppose y is a real random variable, and one is given access to “the cod...
research
∙
03/07/2022
High-Dimensional Expanders from Chevalley Groups
Let Φ be an irreducible root system (other than G_2) of rank at least 2,...
research
∙
12/02/2021
Explicit Abelian Lifts and Quantum LDPC Codes
For an abelian group H acting on the set [ℓ], an (H,ℓ)-lift of a graph G...
research
∙
10/20/2021
Optimizing Strongly Interacting Fermionic Hamiltonians
The fundamental problem in much of physics and quantum chemistry is to o...
research
∙
08/02/2021
The SDP value of random 2CSPs
We consider a very wide class of models for sparse random Boolean 2CSPs;...
research
∙
05/21/2021
Analysis of Boolean Functions
The subject of this textbook is the analysis of Boolean functions. Rough...
research
∙
03/13/2021
Fooling Gaussian PTFs via Local Hyperconcentration
We give a pseudorandom generator that fools degree-d polynomial threshol...
research
∙
02/25/2021
Toward Instance-Optimal State Certification With Incoherent Measurements
We revisit the basic problem of quantum state certification: given copie...
research
∙
09/08/2020
Fiber Bundle Codes: Breaking the N^1/2polylog(N) Barrier for Quantum LDPC Codes
We present a quantum LDPC code family that has distance Ω(N^3/5/polylog(...
research
∙
09/05/2020
Explicit near-fully X-Ramanujan graphs
Let p(Y_1, …, Y_d, Z_1, …, Z_e) be a self-adjoint noncommutative polynom...
research
∙
09/16/2019
Explicit near-Ramanujan graphs of every degree
For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)-time...
research
∙
06/16/2019
The SDP value for random two-eigenvalue CSPs
We precisely determine the SDP value (equivalently, quantum value) of la...
research
∙
04/06/2019
X-Ramanujan Graphs
Let X be an infinite graph of bounded degree; e.g., the Cayley graph of ...
research
∙
12/24/2018
Sherali--Adams Strikes Back
Let G be any n-vertex graph whose random walk matrix has its nontrivial ...
research
∙
11/03/2018
Learning sparse mixtures of rankings from noisy information
We study the problem of learning an unknown mixture of k rankings over n...
research
∙
09/10/2018
A log-Sobolev inequality for the multislice, with applications
Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...
research
∙
09/04/2018
SOS lower bounds with hard constraints: think global, act local
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficie...
research
∙
08/13/2018
Fooling Polytopes
We give a pseudorandom generator that fools m-facet polytopes over {0,1}...
research
∙
06/10/2018
On closeness to k-wise uniformity
A probability distribution over -1, 1^n is (eps, k)-wise uniform if, rou...
research
∙
04/14/2018