Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Small Circuits Imply Efficient Arthur-Merlin Protocols
event speaker icon
Michael Ezra (M.Sc. Thesis Seminar)
event date icon
Tuesday, 09.03.2021, 11:00
event location icon
Zoom Lecture: 5617822865
For password to lecture, please contact: michaelezra@cs.technion.ac.il
event speaker icon
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.