This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

This article surveys quantum computational complexity, with a focus on three fundamental
notions: polynomial-time quantum computations, the efficient verification of quantum proofs …

We present a methodology to construct preprocessing zkSNARKs where the structured
reference string (SRS) is universal and updatable. This exploits a novel use of holography …

Human dignity demands that personal information, like medical and forensic data, be hidden
from the public. But veils of secrecy designed to preserve privacy may also be abused to …

We design, implement, and evaluate a zero knowledge succinct non-interactive argument
(SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language …

This paper introduces Spartan, a new family of zero-knowledge succinct non-interactive
arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (R1CS), an NP …

We design and implement a simple zero-knowledge argument protocol for NP whose
communication complexity is proportional to the square-root of the verification circuit size …

We initiate the study of a proof system model that naturally combines interactive proofs (IPs)
and probabilistically-checkable proofs (PCPs), and generalizes interactive PCPs (which …

Abstract The family of Reed-Solomon (RS) codes plays a prominent role in the construction
of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) …

In the classical transformer attention scheme, we are given three $ n\times d $ size matrices
$ Q, K, V $(the query, key, and value tokens), and the goal is to compute a new $ n\times d …