Complexity seminar

Towards stability arguments in circuit lower bounds

Navid Talebanfard

IM CAS

Friday, 8. April 2022 - 14:00 to 15:30

in IM, rear building, ground floor

Stability theorems in extremal combinatorics generalize uniqueness of extremal instances. For example, it is well-known that triangle-free graphs with many edges structurally resemble the Turan graph, which is the unique triangle-free with maximum number of edges.

Does a similar phenomenon hold in circuit complexity? Do small circuits computing a particular function have to have a specific structure? We will show that in some situations regarding depth-3 circuits, this seems to be the only way to prove a lower bound. We will also show a theorem which makes some progress with this flavor towards settling the exact complexity of the inner product function.

Does a similar phenomenon hold in circuit complexity? Do small circuits computing a particular function have to have a specific structure? We will show that in some situations regarding depth-3 circuits, this seems to be the only way to prove a lower bound. We will also show a theorem which makes some progress with this flavor towards settling the exact complexity of the inner product function.