Refine search
Actions for selected content:
1 results
Optimal thresholds for monotone non-Boolean functions
- Part of
-
- Journal:
- Combinatorics, Probability and Computing / Volume 35 / Issue 5 / September 2026
- Published online by Cambridge University Press:
- 21 July 2026, pp. 734-746
-
- Article
-
- You have access
- HTML
- Export citation
-
Let
$[q] = \{0,1,\ldots ,q-1\}$, let 
$\Delta [q]$ denote the simplex of probability measures on 
$[q]$, and let 
$\gamma$ denote the Lebesgue measure normalized on 
$\Delta [q]$. We prove that for any symmetric monotone function 
${\kern1pt}f \colon{\kern-1pt} [q]^n \to [q]$ and any 
$a \in [q]$, we have
\begin{equation*} \gamma (\{\mu \in \Delta [q]\;\vert \;\mathbb{P}_{x\sim \mu ^{\otimes n}}[\,f(x)=a] \in (\varepsilon ,1-\varepsilon )\}) = O(1/\log n)\text{.} \end{equation*}We also show that this bound is tight. This improves Kalai and Mossel's previous bound of
$O(\!\log \log n/\log n)$ and answers their question completely.
