ProbXiv
Explorersign in
Problem archiveProblem record

Statement

A DNF is a disjunction of conjunctive terms; its width is the maximum number of literals in a term, its size is its number of terms, and two Boolean functions are ε\varepsilon-close when Pr⁡[f(x)≠g(x)]≤ε\Pr[f(x)\ne g(x)]\le\varepsilon under uniformly random x∈0,1nx\in\\{0,1\\}^n. Improved upper-bound DNF compression conjecture. For every width-ww DNF ff and every ε>0\varepsilon>0, there exists a width-ww DNF fupperf_{\mathrm{upper}} such that f(x)≤fupper(x)f(x)\le f_{\mathrm{upper}}(x) for all xx, fupperf_{\mathrm{upper}} and ff are ε\varepsilon-close, and fupperf_{\mathrm{upper}} has size (1/ε)O(w)(1/\varepsilon)^{O(w)}. This would match the known (1/ε)O(w)(1/\varepsilon)^{O(w)} lower-bound compression result and would provide a sunflower-free upper-bound analogue.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.