Fall 2018

Circuit Lower Bounds (and More) via the Fusion Method

Monday, Sep. 10, 2018 10:00 am11:00 am

Add to Calendar


I will review (and hope to revive) a collection of old works, surveyed in [1], which suggest obtaining circuit lower bounds by "fusing'' many correct computations (of a circuit too small) into an incorrect computation. This framework may be viewed as a generalization of both the "approximation method'' of Razborov, and the "finite limit'' approach of Sipser. This framework offers a "static" view of computation, which may eliminate the (problematic) need of progress measures in "dynamic" lower bound arguments (whether top-down or bottom-up). It further yields natural combinatorial and algebraic set-cover problems, whose solution *characterizes* the size of surprisingly many computational models (indeed, it gives rise to new ones: Span Programs were born this way!). In a couple of models, this viewpoint led to (slight) superlinear lower bounds, which nonetheless have not been improved upon for 25 years.

[1] Wigderson, Avi. "The fusion method for lower bounds in circuit complexity." Combinatorics, Paul Erdos is Eighty 1.453-468 (1993): 68.