Junta threshold for low degree Boolean functions on the slice

DOI10.37236/11115MaRDI QIDQ2699646zbMATH OpenOpenAlexFDO

Authors Yuval Filmus

Publication date 19 April 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.04760

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Boolean functions (06E30) Boolean functions (94D10)

Review text

Summary: We show that a Boolean degree \(d\) function on the slice \(\binom{[n]}{k}\) is a junta if \(k \geqslant 2d\), and that this bound is sharp. We prove a similar result for \(A\)-valued degree \(d\) functions for arbitrary finite \(A\), and for functions on an infinite analog of the slice.

Recommendations

• Boolean constant degree functions on the slice are juntas
• On the functional separability of Boolean threshold functions
• A note on lattice variant of thresholdness of Boolean functions
• A lower bound for the affinity level for almost all Boolean functions
• scientific article; zbMATH DE number 7250146
• On Boolean threshold functions with minimum specification number
• On the complexity of the disjunctive normal form of threshold functions
• A threshold property of quadratic Boolean functions
• scientific article; zbMATH DE number 850396
• A Lower Bound of the Number of Threshold Functions

Cites work

• An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Boolean constant degree functions on the slice are juntas
• Boolean degree 1 functions on some classical association schemes
• Harmonicity and invariance on slices of the Boolean cube
• On the degree of Boolean functions as real polynomials
• Polynomials with two values

Cited in

(10)

• An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
• A structure theorem for almost low-degree functions on the slice
• Boolean constant degree functions on the slice are juntas
• Junta threshold for low degree Boolean functions on the slice
• Sparse juntas on the biased hypercube
• The classification of Boolean degree 1 functions in high-dimensional finite vector spaces
• An upper bound on the number of relevant variables for Boolean functions on the Hamming graph
• Stability of large rainbow intersecting families with product measure
• The degree of functions in the Johnson and q-Johnson schemes
• Eigenvalue bounds for symmetric Markov chains on multislices with applications

This page was built for publication: Junta threshold for low degree Boolean functions on the slice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2699646)