Michael Ezra, M.Sc. Thesis Seminar
For password to lecture, please contact: firstname.lastname@example.org
Advisor: Dr. Ron Rothblum
We show a new connection between circuit lower bounds and interactive proofs in restricted computational models.
Specifically, we focus on the frontier problem of whether a DNF augmented with an additional layer of parity (XOR) gates, can approximate the inner product function.
We show that the existence of such a small circuit, would have unexpected general implications for interactive variants of the Data Streaming and Communication Complexity models.