The lexicographic minimization conjecture for noisy Boolean functions
Statement
Let be i.i.d. Bernoulli, let be i.i.d. Bernoulli independently of , where , and let . Write and . A Boolean function is lex when is the initial segment of the lexicographic ordering having cardinality . For fixed and fixed , the lexicographic minimization conjecture. The conditional entropy
is minimized when is lex. This is proposed as a refinement of the mutual-information conjecture and concerns the extremal behavior of Boolean functions under binary symmetric noise; it remains open in the supplied text.
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.