slideshow 3

Complexity seminar

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.