- Laboratoire d’informatique

RSS

TCS Watchparty

Mercredi 11 juin 2025
Irit Dinur (IAS)

Suppose you are given a noisy collection of partial views of an object — how much can you recover just by checking how often these views agree with each other? Agreement testing theorems show that under certain conditions, remarkably, local consistency can guarantee the existence of a coherent global object.

These agreement tests (also known as direct product tests) are central tools in the proofs of PCP theorems, low-degree tests, and more general locally testable codes. In this talk, I will describe recent advances in agreement testing on high-dimensional expanders — powerful combinatorial structures that provide robust frameworks for local-to- global inference — and show how they open new doors for constructing efficient, highly resilient systems.


Plus d'informations ici …