Theory Seminar: Sidharth Iyer, "XOR Lemmas and a Lifting Theorem in Communication Complexity."
- Sponsor
- Research Area of Theory and Algorithms
- Speaker
- Sidharth Iyer
- Contact
- Makrand Sinha
- msinha@illinois.edu
- Views
- 11
- Originating Calendar
- Siebel School Speakers Calendar
Abstract: An XOR lemma states that if a Boolean function f is hard to compute then, computing the XOR of n copies of f is significantly harder. In this talk, I will discuss XOR lemmas for both randomized and deterministic communication complexity and a related lifting theorem for deterministic communication complexity. For randomized communication, we show that there is a constant c_0 such that if f(x,y) requires C >= c_0 bits to be computed with success probability 2/3 then, computing the XOR of n copies of f with probability 1/2 + exp(-Omega(n)) -- barely better than random guessing -- requires communication at least Omega(sqrt{n}.C/log(nC)).
For deterministic communication, we show that there exists a constant c_0 such that if f requires C >= c_0 bits to be computed then, computing the XOR of n copies of f requires Omega(n.sqrt{C}) bits. Lastly, I will discuss a lifting theorem, which generalizes the previous result and gives a lower bound on the communication required to compute the composition g(f(x_1,y_1),..,f(x_n,y_n)), where g is an arbitrary Boolean function. Here we show that there is a constant c_0 such that if f requires communication C >= c_0 then, to compute the composition of g with f, the communication required is at least Omega(min{s(g),deg(g)}. sqrt{C}), where s(g) and deg(g) are the sensitivity and the degree of g respectively. These results are based on joint works with Anup Rao.
Bio: Sidharth Iyer is a postdoc at the Institute of Mathematics in the Czech Academy of Sciences, hosted by Pavel Hrubeš. I received my PhD. from the University of Washington where I was very fortunate to be advised by Anup Rao. I am broadly interested in complexity theory and combinatorics.