[Proof Complexity] MIAO seminar Thu Dec 11 at 10:15 CET with Siddharth Iyer: XOR lemmas and lifting in communication complexity

[Jakob Nordström]

Dear all,

With apologies for the short notice, this message is to announce that on Thursday December 11 at 10:15 (note the time!), we will have the pleasure of listening to a presentation by Siddharth Iyer from the Institute of Mathematics of the Czech Academy of Sciences, who will give a talk titled "XOR lemmas and lifting in communication complexity". You find the abstract at the bottom of this message.

We will run this as a MIAO hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to the new location of the Algorithms and Complexity Section at Vibenshuset, Lyngbyvej 2, while other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827. Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

In other news, we continue to have fairly sparse programming in the MIAO seminar series while focusing on the course "Proof Complexity as a Computational Lens", which mixes timeless pearls with recent highlights in proof complexity. More information about the course can be found at the course webpage https://jakobnordstrom.se/teaching/proofcplx25/, and the lectures are streamed via the MIAO seminar meeting link and are posted on the MIAO Research YouTube channel. As usual, more information about MIAO seminars proper can be found at https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk<mailto:jn at di.ku.dk>.

Best regards,
Jakob Nordström

**********

Thursday Dec 11 at 10:15 (note the time!) at the Algorithms and Complexity Section at the University of Copenhagen, Vibenshuset, Lyngbyvej 2, and on Zoom
XOR lemmas and lifting in communication complexity
(Siddharth Iyer, Institute of Mathematics of the Czech Academy of Sciences)

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(-Ω(n)) — barely better than random guessing — requires communication at least Ω(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 Ω(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. We show that there is a constant c_0 such that if f requires communication C ≥ c_0, then the communication required to compute the composition of g with f is at least Ω(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.

In the first part of the talk, I will give an overview of the lifting theorem and in the second part, I will discuss the randomized XOR lemma.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se