Events
Fall 2018

Pathset formula lower bounds for st-connectivity

Oct 10, 2018 10:30 am – 12:00 pm 

Add to Calendar

Speaker: 

Benjamin Rossman

Location: 

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