Optimal thresholds for monotone non-Boolean functions
Abstract
Abstract Let left bracket q right bracket equals StartSet 0 comma 1 comma ellipsis comma q minus 1 EndSet [ q ] = { 0 , 1 , … , q − 1 } $[q] = \{0,1,\ldots ,q-1\}$ , let normal upper Delta left bracket q right bracket Δ [ q ] $\Delta [q]$ denote the simplex of probability measures on left bracket q right bracket [ q ] $[q]$ , and let gamma γ $\gamma$ denote the Lebesgue measure normalized on normal upper Delta left bracket q right bracket Δ [ q ] $\Delta [q]$ . We prove that for any symmetric monotone function f colon left bracket q right bracket Superscript n Baseline right arrow left bracket q right bracket f : [ q ] n → [ q ] ${\kern1pt}f \colon{\kern-1pt} [q]^n \to [q]$ and any a element of left bracket q right bracket a ∈ [ q ] $a \in [q]$ , we have
Fields of Study & Subjects
Random Matrices and Applications
Advanced Combinatorial Mathematics
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Combinatorics Probability Computing
- Publisher
- Cambridge University Press (CUP)
- Volume
- 35
- Issue
- 5
- Pages
- 1–13
- Publication date
- 21 July 2026
- Language
- EN