•  
    • Ramamohan Paturi
    • (University of California, San Diego, USA)
    • On Extremal Properties of k-CNF: Capturing Threshold Functions
    • Abstract:
    • We consider a basic question on the expressiveness of k-CNF formulas: How well can k-CNF formulas capture threshold functions? Specifically, what is the largest number of assignments (of Hamming weight t) accepted by a k-CNF formula that only accepts assignments of weight at least t? We discuss the following results: We present optimal solutions for t<= n/k. For t > n/k. we formulate a (monotone) version of the problem as an extremal hypergraph problem and show that for t = n ? k, the problem is exactly the Turán problem. For t = ?n with constant ?, we provide a construction and show its optimality for 2-CNF. Optimality of the construction for k > 2 would give improved lower bounds for depth-3 circuits.  
    • 29.04.22   14:00
    • Navid Talebanfard
    • (IM CAS)
    • Towards stability arguments in circuit lower bounds
    • Abstract:
    • 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.  
    • 08.04.22   14:00

    Michal Koucky, Pavel Pudlak
    organizers

  •