
-
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(...
read it
-
Explicit near-fully X-Ramanujan graphs
Let p(Y_1, …, Y_d, Z_1, …, Z_e) be a self-adjoint noncommutative polynom...
read it
-
Explicit near-Ramanujan graphs of every degree
For every constant d ≥ 3 and ϵ > 0, we give a deterministic poly(n)-time...
read it
-
The SDP value for random two-eigenvalue CSPs
We precisely determine the SDP value (equivalently, quantum value) of la...
read it
-
X-Ramanujan Graphs
Let X be an infinite graph of bounded degree; e.g., the Cayley graph of ...
read it
-
Sherali--Adams Strikes Back
Let G be any n-vertex graph whose random walk matrix has its nontrivial ...
read it
-
Learning sparse mixtures of rankings from noisy information
We study the problem of learning an unknown mixture of k rankings over n...
read it
-
A log-Sobolev inequality for the multislice, with applications
Let κ∈N_+^ℓ satisfy κ_1 + ... + κ_ℓ = n and let U_κ denote the "multisli...
read it
-
SOS lower bounds with hard constraints: think global, act local
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficie...
read it
-
Fooling Polytopes
We give a pseudorandom generator that fools m-facet polytopes over {0,1}...
read it
-
On closeness to k-wise uniformity
A probability distribution over -1, 1^n is (eps, k)-wise uniform if, rou...
read it
-
The threshold for SDP-refutation of random regular NAE-3SAT
Unlike its cousin 3SAT, the NAE-3SAT (not-all-equal-3SAT) problem has th...
read it