Improved upper-bound DNF compression conjecture
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 -close when under uniformly random . Improved upper-bound DNF compression conjecture. For every width- DNF and every , there exists a width- DNF such that for all , and are -close, and has size . This would match the known 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.