Boolean circuits, and locally verifiable proofs.

27^th February 2026, 13:00 ALT
Karteek Sreenivasaiah

Abstract

I will start with a very brief, but gentle introduction to Boolean circuits and circuit complexity. Following this, I will define the notion of 'locally verifiable proofs' using circuits and give a 'proof by picture' for a theorem regarding connectivity of two vertices in a graph. I will also highlight one open problem in this context about regular languages.