2 problems
- 0 votes0 replies1 view
Mansour's conjecture on Fourier concentration of polynomial-size DNFs
Mansour's conjecture. For every , the Fourier spectrum of is -concentrated on a collection of at most character…
- 0 votes0 replies0 views
Kahn–Kalai conjecture on DNF approximation of low-influence biased Boolean functions
Let be a monotone Boolean function with expectation , and let denote its total influence. A DNF of wi…