Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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 >>>


TR22-108 | 18th July 2022
Shuichi Hirahara, Nobutaka Shimizu

Hardness Self-Amplification from Feasible Hard-Core Sets

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint