Low degree functions without non essential arguments 2412 04461v1

Potcast by Google NotebookLM(20241207토)

Subjects: Combinatorics (math.CO)

Briefing Doc: Low-Degree Functions Without Non-Essential Arguments

Author: Denis S. Krotov

Cast of Characters

Denis S. Krotov: The author of the research paper. He is affiliated with the Sobolev Institute of Mathematics in Novosibirsk, Russia. His work is funded by the Russian Science Foundation.
Alexandr Valyuzhenich: Acknowledged by Krotov for helpful discussions related to the research. No further information about their affiliation or specific contributions is provided.
Other researchers cited in the paper: The paper references work by various researchers in the field of coding theory and graph theory. Some key mentions include:

E. F. Assmus Jr. and J. D. Key: Authors of "Designs and Their Codes," a book cited in the context of generalized Reed-Muller codes.
E. A. Bespalov: Co-author of several papers cited throughout, focusing on perfect colorings, completely regular codes, and Doob graphs.
J. Chiarelli, P. Hatami, and M. Saks: Authors of a paper establishing an asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function.
D. G. Fon-Der-Flaass: Author of a paper on perfect 2-colorings of hypercubes.
O. Heden: Author of a paper discussing perfect codes over non-prime power alphabets.
V. N. Potapov: Co-author with Krotov of a paper on completely regular codes and equitable partitions.
A. M. Romanov: Author of a paper on the number of q-ary quasi-perfect codes with a covering radius of 2.
M. Shi: Co-author with Krotov of a paper enumerating 1-perfect ternary codes.
I. Wegener: Author of "The Complexity of Boolean Functions," cited in connection with the Simon-Wegener theorem.

Main Themes:

Perfect colorings of Hamming graphs
Minimizing the number of essential arguments in Boolean functions
Connections between graph eigenvalues and coloring properties
Construction of unbalanced Boolean functions with specific properties

Most Important Ideas and Facts:

Non-essential arguments: The paper investigates the problem of constructing perfect colorings of Hamming graphs without non-essential arguments. This means that every argument (input variable in the case of Boolean functions) is essential for determining the output color.
"An arbitrary surjective function from the vertex set of a graph G onto a finite set K (of colors) of cardinality k is called a (vertex) coloring, or k-coloring, of G. A k-coloring is called perfect if there is a k-by-k matrix {Si,j}i,j∈K (the quotient matrix) such that every vertex of color i has exactly Si,j neighbors of color j."
Eigenvalue connection: The author leverages the relationship between the eigenvalues of the Hamming graph and the quotient matrix of a perfect coloring. This connection allows for analysis of the coloring's properties.
"For a perfect coloring of a graph, the characteristic functions of each of the colors is the sum of eigenfunctions of the graph corresponding to eigenvalues of the quotient matrix. Moreover, every eigenvalue of the quotient matrix is an eigenvalue of the graph."
Uniform collections: The concept of "uniform collections" of perfect colorings is introduced and used as a key building block in the construction of desired functions.
"We say that a collection (C0, . . . , CM−1) of colorings of H(n, q) is uniform if the multiset of colors {C0(x̄), . . . , CM−1(x̄)} does not depend on the vertex x̄ of H(n, q)."
Partitions into RM-like codes: The existence of perfect colorings of H(M, q) with specific parameters, based on partitions into "RM-like codes", is established and utilized in the main construction.
"For every prime power q and M = qs, where s is a positive integer, there is a perfect Mq-coloring E of H(M, q) with the quotient matrix T = (Ti,j), where Ti,j = { 0, if i ≡ j mod q, 1, if i ̸≡ j mod q }."
Recursive construction: The main result (Theorem 1) provides a recursive method to construct perfect colorings with desired properties. The off-diagonal part of the quotient matrix grows linearly, while the diagonal part grows exponentially, leading to functions with a large number of essential arguments relative to their degree.
Application to Boolean functions: The paper demonstrates how the results can be applied to construct unbalanced Boolean functions (functions with a specific density of ones).
"If ρ = r/s, where s is a power of 2 and r is odd, 0 larger r larger s, then for every e there exists a Boolean function of degree es/2 in n = (2s− 1)2e−1 − s essential variables with density ρ of ones."

[u_s.e.r]

why it stopped uploading?
there is nothing to put me to sleep now🥹