Communication Complexity, Circuit Complexity, and Common Causes (C^2 x C^2 x C^2)
to November 14, 2025
Location: UPC - Facultat de Matemàtiques i Estadística (FME), classroom to be determined
Schedule
2 weeks, 3 sessions per week, 2 hours per session (with a short break)
Dates and times:
- Monday, 3 November 2025, 15:00–17:15
- Wednesday, 5 November 2025, 15:00–17:15
- Friday, 7 November 2025, 15:00–17:15
- Monday, 10 November 2025, 15:00–17:15
- Wednesday, 12 November 2025, 15:00–17:15
- Friday, 14 November 2025, 15:00–17:15
Location: UPC – Facultat de Matemàtiques i Estadística (FME), classroom to be determined
Introduction
The P vs. NP problem has been called a gift to mathematics from computer science by Field Medalist Steve Smale in year 2000. Also in year 2000 the problem was included as one of the seven Millenium Prize Problems of the Clay Institute of Mathematics. Besides the intrinsic elegance of its mathematical formulation, the significance of the P vs. NP problem lies in its profound philosophical implications be it resolved one way or the other. Further, for being arguably the defining problem of the theory of computation, the study of the P vs. NP problem will, with certainty, continue to inspire novel techonological advances of unpredictable potential impact in industry, the sciences, and the prospects of AI, beyond the impressive array of accomplishments already achieved.
Over the years since the problem was formulated by Steve Cook in 1971, several approaches have been proposed to attack the P vs. NP problem. The goal of this course is to present the foundations, as well as some of the recent advances, of a combinatorial approach to the P vs. NP problem that was proposed in the 1980’s. The underlying idea of the approach is to adopt an abstract view of computation as entailing a limited form of communication between two parties that on one hand have limited access to the data, but on the other enjoy all-powerful computing capabilities in compensation. This tradeoff between communication and computation has the effect of turning the questions of computation into purely combinatorial problems that do not depend on computational models are thus more amenable to the classic tools of mathematics. Concretely, in the first part of the course we will present the linear algebraic method to prove lower bounds on the communication complexity of explicit functions, and then discuss the celebrated Log-Rank Conjecture. We will also prove Razborov’s linear lower bound on the randomized communication complexity of the set disjointness problem using the modern tools of information theory. In the second part of the course we will introduce Karchmer-Wigderson games, which characterize Boolean circuit complexity in terms of communication.
We will use this methodology to prove linear lower bounds on the depth of monotone Boolean circuits that compute maximum matchings on graphs, and exponential lower bounds on the size of monotone Boolean circuits that compute maximum cliques or optimal colorings.
lecturers
Albert Atserias
Universitat Politècnica de Catalunya and Centre de Recerca Matemàtica
Albert Atserias completed two disjoint PhD theses in Computer Science, one at the Universitat Politècnica de Catalunya and another at the University of California, Santa Cruz. He was a Postdoctoral Fellow at Charles University in Prague and has held visiting research positions at the Isaac Newton Institute for the Mathematical Sciences in Cambridge and at the University of California, Berkeley. Since 2018, he has been a Full Professor in the Computer Science Department at the Universitat Politècnica de Catalunya, and he received an ICREA Academia award in 2023. He was also the principal investigator of an ERC Consolidator Grant.
His research interests include the theory of computation, the applications of mathematical logic to computer science, and the use of probabilistic methods in computer science and combinatorics.
Anup Rao
University of Washington
Anup Rao is a Full Professor at the Department of Computer Science and Engineering at the University of Washington (Seattle). He received his BS from the Georgia Institute of Technology, and his PhD from the University of Texas at Austin. He spent two years as a postdoctoral researcher at the Institute for Advanced Study. His research focuses on theoretical computer science, particularly on aspects related to computational complexity theory.
CONTENT
Week 1. Lecturer: Anup Rao
1. Deterministic and Randomized Communication Protocols (2 hours)
2. Rank and Information Theory Methods (2 hours)
3. Randomized Complexity of Disjointness (2 hours)
Week 2. Lecturer: Albert Atserias
4. Formulas, Circuits, and Karchmer-Wigderson Games (2 hours)
5. Monotone Circuit Depth Bounds from Disjointness (2 hour)
6. Monotone Circuit Size Bounds from Sunflowers and Lifting (2 hours)
Prerequisites:
A student having some basic knowledge of discrete mathematics that includes elementary counting and (discrete) probability theory will make most profit of the course.
BIBLIOGRAPHY
Anup Rao and Amir Yehudayoff.
Communication Complexity and Applications.
Cambridge University Press, 2020.
Stasys Jukna.
Boolean Function Complexity.
Springer, 2012.
LIST OF PARTICIPANTS
| Name | Institution |
|---|---|
| Ilario Bonacina | Universitat Politècnica de Catalunya |
| Ion Mikel Liberal | CSIC |
| Jordi Levy | CSIC |
 |
For inquiries about this event please contact the Scientific Events Coordinator Ms. Núria Hernández at nhernandez@crm.cat
|
scam warning
We are aware of a number of current scams targeting participants at CRM activities concerning registration or accommodation bookings. If you are approached by a third party (eg travellerpoint.org, Conference Committee, Global Travel Experts or Royal Visit) asking for booking or payment details, please ignore them.
Please remember:
i) CRM never uses third parties to do our administration for events: messages will come directly from CRM staff
ii) CRM will never ask participants for credit card or bank details
iii) If you have any doubt about an email you receive please get in touch