דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Small Circuits Imply Efficient Arthur-Merlin Protocols
event speaker icon
מיכאל עזרא, הרצאה סמינריונית למגיסטר
event date icon
יום שלישי, 9.3.2021, 11:00
event location icon
Zoom Lecture: 5617822865
For password to lecture, please contact: michaelezra@cs.technion.ac.il
event speaker icon
מנחה:  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.
[בחזרה לאינדקס האירועים]