Faculty Recruiting Support CICS

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

25 Oct
Tuesday, 10/25/2022 4:00pm to 5:00pm
Computer Science Building, Room 140
Theory Seminar
Abstract: We investigate randomized LEARN-uniformity, which captures the power of randomness and equivalence queries (EQ) in the construction of Boolean circuits for an explicit problem. This is an intermediate notion between P-uniformity and non-uniformity motivated by connections to learning, complexity, and logic. We establish the first unconditional lower bounds against LEARN-uniform circuits.

We then employ these LEARN-uniform circuit *lower bounds* to investigate the provability of non-uniform circuit *upper bounds* in formal systems that capture "efficient" reasoning: theories of bounded arithmetic. By extracting computational information from proofs via a direct translation of "proof" into "LEARN-uniformity", we establish robust unprovability theorems that unify, simplify, and extend nearly all previous results along these lines (Krajicek-Oliveira (2017), Muller-Bydzovsky (2020), and Bydzovsky-Krajicek-Oliveira (2020)).

This is joint work with Valentine Kabanets, Antonina Kolokolova, and Igor Carboni Oliveira, appearing in FOCS 2021. The preprint is available on ECCC.

Bio: TBA

The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.