Title: Communication Complexity and Linear Arrangements
Abstract: A communication protocol is an algorithm for two parties to compute a shared (Boolean) function when the input is split between them. Today I will prove a theorem of Forster et al., that randomized, unbounded error communication protocols have the exact same expressive capabilities as linear arrangements -- a method of encoding functions by intersections of homogeneous half-spaces.
Friday, March 22nd, 2024
12:00PM - 12:50 PM
Olin Hall 109
