Fall 2018

Monotone real circuits and real protocols

Wednesday, October 24th, 2018, 10:30 am12:00 pm

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.