Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 31, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Trinh Huynh
Given an input domain I and an output domain Z, a search problem defines for every input i in I a subset of Z to be the valid outputs for i. In a two-player communication search problem with input domains X and Y and output domain Z, Alice is given an input x in X, Bob is given an input y in Y, and they need to communicate to find a valid output in Z for their joint input (x,y). Motivation for studying the communication complexity of search problems comes from their applications to circuit depth lower bounds, to rank and tree-like size lower bounds in propositional proof complexity, and as we observed, also to length-space tradeoffs in proof complexity.
In this talk, I will describe our new analysis technique to lower bound the communication complexity of a broad class of communication search problems in terms of the critical block-sensitivity of search problems, a new notion we introduced that generalizes the block sensitivity of functions. This new technique enables us to obtain the first strong length-space tradeoffs in the so-called Cutting Planes and Polynomial Calculus Resolution proof systems for refuting constant-width CNF formulas.
This is based on joint work with Jakob Nordstrom (KTH Stockholm).
Automatic MiSe System Software Version 1.4803M | admin login