Events
Fall 2018
Monotone real circuits and real protocols
Wednesday, October 24th, 2018, 10:30 am–12:00 pm
Parent Program:
Speaker:
Pavel Pudlák
Location:
Room 116
We will show that monotone real circuits can be polynomially simulated by circuits that only use addition and some monotone unary functions. This holds true for circuits with at most k-ary gates where k is a constant, hence k-ary monotone circuits can be simulated by binary.
We also show that one can construct a monotone real circuits for f from a DAG-like real communication protocol for the KW problem for f.
Joint work with Pavel Hrubes.