Dot-Product Proofs and Their Applications

We introduce a new type of probabilistic proof-system, called a dot-product proof (DPP). In a DPP, the input statement x and the proof \pi are vectors over a finite field F, and the proof is verified by making a single dot-product query <q,(x\| \pi)> to the concatenation of x and \pi.

 

We will discuss constructions of DPPs and their applications, including:

1. Exponential hardness of approximation for MAXLIN.

2. Extremely succinct argument-systems.

 

Joint work with Nir Bitansky, Prahladh Harsha, Yuval Ishai and David Wu