Low-degree functions without non-essential arguments

2024/12/05 by Denis S. Krotov, Krotov, Denis S.
Computer Science · #05B15 #06E30 #94D10 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2412.04461

openalex publication_date 2024/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For the Hamming graph H(n,q), where a q is a constant prime power and n grows, we construct perfect colorings without non-essential arguments such that n depends exponentially on the off-diagonal part of the quotient matrix. In particular, we construct unbalanced Boolean (q=2) functions such that the number of essential arguments depends exponentially on the degree of the function.

Related

• Eigenfunctions and minimum 1-perfect bitrades in the Hamming graph
• Minimal supports of eigenfunctions of Hamming graphs
• Sensitivity of m-ary functions and low degree partitions of Hamming graphs
• Sensitivity and Hamming graphs
• An upper bound on the number of relevant variables for Boolean functions on the Hamming graph