slideshow 3

Complexity seminar

The seminar takes place in the seminar room of IM, rear building, ground floor, Friday  at  14:00 - 16:00
Chair: Michal Koucky, Pavel Pudlak
The programme is announced via the mailing list.

On Extremal Properties of k-CNF: Capturing Threshold Functions

Ramamohan Paturi
University of California, San Diego, USA
Friday, 29. April 2022 - 14:00 to 15:30

in IM, rear building, ground floor

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.
 

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.
 

Read-once linear branching programs and the regular Res(lin) proof system, Part II

Pavel Pudlak
IM CAS
Friday, 1. April 2022 - 14:00 to 15:30

in IM, rear building, ground floor

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.

Read-once linear branching programs and the regular Res(lin) proof system

Pavel Pudlak
IM, CAS
Friday, 25. March 2022 - 14:00 to 15:30

in IM, rear building, ground floor

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.
 

Pages