Low-degree functions without non-essential arguments
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912145911840768 |
|---|---|
| author | Krotov, Denis S. |
| author_facet | Krotov, Denis S. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04461 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-degree functions without non-essential arguments Krotov, Denis S. Combinatorics 94D10, 06E30, 05B15 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. |
| title | Low-degree functions without non-essential arguments |
| topic | Combinatorics 94D10, 06E30, 05B15 |
| url | https://arxiv.org/abs/2412.04461 |