On Extremal Properties of k-CNF: Capturing Threshold Functions

Mohit Gurumukhani, Marvin Künnemann, Ramamohan Paturi

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 assig…