On Extremal Properties of k-CNF: Capturing Threshold Functions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915084386697216 |
|---|---|
| author | Gurumukhani, Mohit Künnemann, Marvin Paturi, Ramamohan |
| author_facet | Gurumukhani, Mohit Künnemann, Marvin Paturi, Ramamohan |
| contents | 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$? Among others, we provide the following results:
- While an optimal solution is known for $t \leq n/k$, the problem remains open 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20493 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Extremal Properties of k-CNF: Capturing Threshold Functions Gurumukhani, Mohit Künnemann, Marvin Paturi, Ramamohan Computational Complexity 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$? Among others, we provide the following results: - While an optimal solution is known for $t \leq n/k$, the problem remains open 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. |
| title | On Extremal Properties of k-CNF: Capturing Threshold Functions |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.20493 |