Fall 2018

Pathset formula lower bounds for st-connectivity

Wednesday, Oct. 10, 2018 10:30 am12:00 pm PDT

Add to Calendar


Benjamin Rossman


Room 116

“Pathset formulas” are a class of algorithms solving the average-case distance-k st-connectivity problem.  In this talk I will explain the model and sketch an n^Ω(log k) lower bound, with additional details on Friday for those interested.  This lower bound extends to AC^0 formulas and monotone formulas via reductions to the pathset setting (time permitting, I will describe these reductions on Friday).