2 problems

0 votes0 replies0 views
Verbin–Servedio–Tan approximate junta conjecture for monotone Boolean functions
Verbin–Servedio–Tan conjecture. If $f$ is monotone and $\operatorname{DT}(f)=d$ , then $f$ must be $\varepsilon$ -close to a $\operatorname{poly}_{\varepsilon}(d)$ -junta. This would…
Conjectureopenboolean-functions decision-tree-complexity juntasarXiv posted 2 days ago
0 votes0 replies1 view
Rivest's non-evasiveness conjecture for string patterns
Rivest's non-evasiveness conjecture. Every pattern is non-evasive. This conjecture was later disproved by Tuza, so not all patterns satisfy the stated property.
Conjecturerefutedcombinatorics-on-words decision-tree-complexity string-matchingarXiv posted 2 days ago

Verbin–Servedio–Tan approximate junta conjecture for monotone Boolean functions