Pathset formula lower bounds for st-connectivity

“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).