Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by ... more >>>

Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols.

State-of-the-art ... more >>>

Time-bounded conditional Kolmogorov complexity of a string $x$ given $y$, $K^t(x\mid y)$, is the length of a shortest program that, given $y$, prints $x$ within $t$ steps. The Chain Rule for conditional $K^t$ with error $e$ is the following hypothesis: there is a constant $c\in\mathbb{N}$ such that, for any strings ... more >>>