Colloquium Details
Communication is Everything. Everything is Communication
Speaker: Raghuvansh R. Saxena, Microsoft
Location: 60 Fifth Avenue Room 150
Date: April 3, 2023, 2 p.m.
Host: Subhash Khot
Synopsis:
Communication complexity is the study of how two or more parties with private inputs compute a function that depends on all their inputs. The scarce resource is communication, or the number of bits exchanged between the parties. What is amazing about this field is that it has applications not only in areas where there is actual communication between parties, such as auction design and distributed computing, but also in areas which superficially may seem completely unrelated to communication, such as graph streaming and data structures. This is because bounds on communication can often be translated into bounds on other resources of interest, such as memory and the number of wires.
In this talk, I will cover my work in developing and applying new communication complexity tools to mechanism design, streaming algorithms, error-resilient circuits, and interactive coding, with a special focus on the latter. Specifically, I shall cover two of my recent results [EKS20a] and [EKSZ22], that develop new codes resilient to a larger fraction of noise than the previous state-of-the-art. In the case of [EKSZ22], I will also explain why our result opens a whole new paradigm for error correcting codes that was previously unexplored. No prior background will be assumed.
Speaker Bio:
Raghuvansh R. Saxena is a researcher with a wide interest in theoretical computer science, especially in developing new complexity theoretic tools for emergent problems in several areas of computing, such as interactive coding, streaming algorithms, and electronic markets. Many of his works are driven by his search for ‘efficient’ and ‘practical’ solutions to modern day problems. He did his PhD from Princeton University (2021) and his Bachelors from IIT Delhi (2016). Some of the honors that he has received are the Microsoft PhD Fellowship and a Siebel Scholarship in 2019 and the President’s Gold Medal (IIT Delhi) in 2016.
Notes:
In-person attendance only available to those with active NYU ID cards.