PreviousNext

__
TR22-111
| 1st August 2022
__

Robert Andrews#### On Matrix Multiplication and Polynomial Identity Testing

__
TR22-110
| 1st August 2022
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves

__
TR22-109
| 27th July 2022
__

Siddharth Iyer, Michael Whitmeyer#### Searching for Regularity in Bounded Functions

PreviousNext

Robert Andrews

We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting $\underline{R}(n)$ denote the border rank of $n \times n \times n$ matrix multiplication, we construct a hitting set generator with seed length $O(\sqrt{n} \cdot ... more >>>

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known ... more >>>

Siddharth Iyer, Michael Whitmeyer

Given a function $f:\mathbb F_2^n \to [-1,1]$, this work seeks to find a large affine subspace $\mathcal U$ such that $f$, when restricted to $\mathcal U$, has small nontrivial Fourier coefficients.

We show that for any function $f:\mathbb F_2^n \to [-1,1]$ with Fourier degree $d$, there exists an affine subspace ... more >>>

PreviousNext