Tata Institute of Fundamental Research
Efficient PCPs from High-Dimensional Expanders
STCS Seminar
Speaker:
Mitali Bafna (University of Washington)
Organiser:
Prahladh Harsha
Date:
Friday, 20 Feb 2026, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a fundamental result in computer science with far-reaching consequences in hardness of approximation, cryptography, and blockchain technology. A PCP has two important parameters: 1) the size of the encoding, and 2) soundness, which is the probability that the verifier accepts an incorrect proof, both of which we wish to minimize.
In 2005, Dinur gave a surprisingly elementary and purely combinatorial proof of the PCP theorem that relies only on tools such as graph expansion, while also giving the first construction of 2-query PCPs with quasi-linear size and constant soundness (close to 1). Our work improves upon Dinur's PCP and constructs 2-query, quasi-linear size PCPs with arbitrarily small constant soundness, using high-dimensional expanders (HDX). As a direct consequence, assuming the exponential time hypothesis, we get that no approximation algorithm for 3-SAT can achieve an approximation ratio significantly better than 7/8 in time 2^{n/polylog n}.
In this talk, I will discuss the main components of our PCP, without assuming any familiarity with PCPs or HDX. This is based on joint works with Noam Lifshitz, Dor Minzer, Nikhil Vyas and Zhiwei Yun.
Short Bio:
Mitali Bafna is a theoretical computer scientist and an Assistant Professor in the Allen School of Computer Science & Engineering at the University of Washington. Her research explores complexity theory and algorithms, particularly approximation algorithms, probabilistically checkable proofs, and high-dimensional expanders.
She received her undergraduate degree from IIT Madras and her Ph.D. in Computer Science from Harvard University in 2022, advised by Prof. Madhu Sudan. After that, she was a postdoc at CMU, hosted by Professors Aayush Jain and Pravesh Kothari, followed by a postdoc in the MIT Department of Mathematics.
| Speaker: | Mitali Bafna (University of Washington) |
| Organiser: | Prahladh Harsha |
| Date: | Friday, 20 Feb 2026, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The theory of probabilistically checkable proofs (PCPs) shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. The PCP Theorem [ALMSS] is a fundamental result in computer science with far-reaching consequences in hardness of approximation, cryptography, and blockchain technology. A PCP has two important parameters: 1) the size of the encoding, and 2) soundness, which is the probability that the verifier accepts an incorrect proof, both of which we wish to minimize.
In 2005, Dinur gave a surprisingly elementary and purely combinatorial proof of the PCP theorem that relies only on tools such as graph expansion, while also giving the first construction of 2-query PCPs with quasi-linear size and constant soundness (close to 1). Our work improves upon Dinur's PCP and constructs 2-query, quasi-linear size PCPs with arbitrarily small constant soundness, using high-dimensional expanders (HDX). As a direct consequence, assuming the exponential time hypothesis, we get that no approximation algorithm for 3-SAT can achieve an approximation ratio significantly better than 7/8 in time 2^{n/polylog n}.
In this talk, I will discuss the main components of our PCP, without assuming any familiarity with PCPs or HDX. This is based on joint works with Noam Lifshitz, Dor Minzer, Nikhil Vyas and Zhiwei Yun.
Short Bio:
Mitali Bafna is a theoretical computer scientist and an Assistant Professor in the Allen School of Computer Science & Engineering at the University of Washington. Her research explores complexity theory and algorithms, particularly approximation algorithms, probabilistically checkable proofs, and high-dimensional expanders.
She received her undergraduate degree from IIT Madras and her Ph.D. in Computer Science from Harvard University in 2022, advised by Prof. Madhu Sudan. After that, she was a postdoc at CMU, hosted by Professors Aayush Jain and Pravesh Kothari, followed by a postdoc in the MIT Department of Mathematics.