•  
    • 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
    • Pavel Pudlak
    • (IM CAS)
    • Read-once linear branching programs and the regular Res(lin) proof system, Part II
    • Abstract:
    • In this talk I will show the connection of a certain type of read-once linear branching programs and a certain type of the Res(lin) proof system. Further, I will present a construction of directional-derivative affine extractors.
    • 01.04.22   14:00
    • Pavel Pudlak
    • (IM, CAS)
    • Read-once linear branching programs and the regular Res(lin) proof system
    • Abstract:
    • We consider a version of read-once branching programs where queries are parities of the input bits. We define two kinds of these branching programs. For the more restricted version, we prove exponential lower bounds. For the less restricted version, we show that such a branching program finds a falsified clause in an unsatisfiable CNF iff there exists a Res(lin) refutation that has essentially the same size and satisfies a the same condition as read-once branching programs. Joint work with Svyatoslav Gryaznov and Navid Talebanfard.  
    • 25.03.22   14:00
    • Pavel Hrubes
    • (IM CAS)
    • Linear separation complexity of a random function
    • Abstract:
    • Linear separation complexity of a Boolean function is a measure of how hard it is to distinguish accepting and rejecting inputs by means of a linear program. I will discuss nontrivial upper and lower bounds on separation complexity of a random function. Joint work with Navid Talebanfard
    • 18.03.22   14:00
    • Michal Koucký
    • (MFF UK)
    • Data structure lower bounds and popular conjectures
    • Abstract:
    • We investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li and several data structure like problems such as non-adaptive function inversion of Hellman and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.  
    • 11.03.22   14:00

    Michal Koucky, Pavel Pudlak
    organizers

  •