Title: Uniform Circuit Lower Bounds Using Logical Pebble Games

Speaker: Marco Carmosino, Hampshire College

Abstract: This talk will explain how lower bounds for uniform circuit
classes are possible using pebble games. Winning strategies for these
games give insight into how a circuit class operates. We will explain
how to win the game that corresponds to a very uniform (more uniform
than DLOGTIME) subset of ACC; deriving this strategy has been our work
for the past semester. We will give a brief overview of other methods
used to lower-bound assorted subsets of ACC, and note how pebble game
strategies fit in to the bigger picture of attempts to lower bound
circuit classes.