The unreasonable effectiveness of communication complexity - Professor Or Meir
Event details
-
Wednesday 6 May 2026 - 5:00pm to 7:00pm
The Diamond, Lecture Theatre 02, The University of Sheffield, 32 Leavygreave Road, Sheffield, S3 7RD
Description
Abstract: Communication complexity is an area of theoretical computer science that studies the amount of communication needed to solve various problems. Quite surprisingly, this area turned out to have applications to many other theoretical areas, including the data structures and algorithms, distributed computing, algorithmic game theory and computational economics, and most recently, understanding the limitations of transformers and deep networks. In this lecture, I will give a brief introduction to communication, and demonstrate its applicability to various other areas.
Bio: Prof. Meir completed his Phd at the Weizmann Institute of Science under the supervision of Oded Goldreich. He was then a postdoc at Stanford (hosted by Luca Trevisan), the Institute for Advanced Study (hosted by Avi Wigderson), and the Weizmann Institute of Science (hosted by Irit Dinur). In 2015 he became a faculty member at the University of Haifa, before joining the University of Sheffield in September 2025. Prof Meir's research area is theoretical computer science, and specifically complexity theory. These days, he is particularly interested in circuit complexity, communication complexity, and derandomization. In the past, he also worked on probabilistic proof systems and error-correcting codes.
FINAL DATE TO REGISTER: TUESDAY 21 APRIL