Fall 2018

Monotone real circuits and real protocols

Wednesday, Oct. 24, 2018 10:30 am12:00 pm PDT

Add to Calendar


Pavel Pudlák


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.