Fall 2018

The Pathset Approach to Formula Lower Bounds

Friday, September 14th, 2018 10:00 am10:30 am

Add to Calendar


Ben Rossman (University of Toronto)

This talk will give a brief overview of the “pathset complexity” method, an approach to formula lower bounds for Distance-k Connectivity which has so far yielded results in the AC0 and monotone settings.  I will describe some recent progress and highlight a few open questions in this research program.