Under the auspices of the Computational Complexity Foundation (CCF)

LATEST > REPORTS:
PreviousNext

TR22-111 | 1st August 2022
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 >>> 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 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 >>> TR22-109 | 27th July 2022 Siddharth Iyer, Michael Whitmeyer #### Searching for Regularity in Bounded Functions 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

ISSN 1433-8092 | Imprint