Events and Activities

A common tool in the construction of probabilistically checkable proofs is low degree encodings. Babai, Fortnow and Lund proved the local testability of the individual low degree code, and used it to provide a multi-prover interactive proof (MIP)...

We construct very efficient argument systems for proving the correctness of bounded-space computations, based on the existence of one-way functions. Our argument system applies to general computations running in time T and space S. The communication...

A central goal in complexity theory is to prove separations between randomized and deterministic models of computation. In communication complexity, a key challenge is to establish lower bounds for multiparty protocols in the number-on-forehead (NOF...

We consider the problem of explicitly constructing binary linear codes achieving the optimal rate-distance tradeoff.  In 2017, Ta-Shma gave an almost-optimal construction in the low-rate regime, i.e., he gave a construction of binary linear codes...