AF: Small: The Power of Randomness in Decision and Verification

The ability to make random choices seems to simplify several computational tasks. For example, in order to decide whether two formulas like x*x-y*y and (x+y)*(x-y) are equivalent, one can merely plug in random values for x and y and verify whether the two formulas yield the same value. Even for complicated formulas, this is a reliable strategy, easier than manipulating the abstract formulas. A more involved use of randomness consists of a way to spot-check computations that requires significantly less effort than performing the computations themselves---a feature of paramount importance in the day and age of delegating computations to the cloud. This project investigates the potential of achieving similar efficiency in decision and verification without randomness. It incorporates graduate and undergraduate training and education, and includes the development of a textbook that makes computational thinking and the area of quantum algorithms more accessible to a broader public. The project explores two new directions in the area of derandomization. In the setting of polynomial-time decision procedures with bounded error (i.e., bounded-error probabilistic polynomial time class, BPP), the investigators propose a principled approach towards derandomizing Polynomial Identity Testing (PIT) based on the notion of a vanishing ideal. PIT captures the above formula equivalence problem and plays a central role in the area of derandomization as known results suggest that derandomizing PIT may enable derandomizing all of BPP. The investigators already characterized the vanishing ideal of a widely used pseudorandom generator for PIT, plan to develop the approach for other generators, and to research the ramifications. In the setting of polynomial-time interactive verification processes known as Arthur-Merlin (AM) protocols, the investigators want to further develop the connections between lower bounds and derandomization, in particular by adapting to the setting of AM the instance-wise connection that was recently established for the setting of BPP. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.