We prove that level-$\ell$ Kikuchi graphs of random $2r$-uniform hypergraphs spectrally approximate Kikuchi graph of the complete $2r$-uniform hypergraph at a sampling rate that is sharp up to a logarithmic factor, in the regime $r\leq \ell \leq n/2$. Our proof is based on the matrix Bernstein inequality, but, unlike prior ... more >>>

Modern cryptography relies on the intractability of computational problems. We present an approach to build cryptography from a new source of hardness: proving mathematical theorems.

Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under standard derandomization (prBPP = prP) and cryptographic assumptions (LWE and SXDH), ... more >>>

The symmetric determinantal complexity $\sdc(f)$ of a polynomial $f$ is the
least $m$ such that $f=\Det(M)$ for an $m\times m$ symmetric matrix $M$ of
affine-linear forms. We prove, over $\CC$, that
\[
\sdc\!\left(\sum_{i=1}^n x_i^n\right)
\ge \left(\frac{1}{2e}-o(1)\right)n^2 .
\]
The result is a symmetric companion to the author's non-symmetric ... more >>>