Query complexity of Boolean functions on slices. (English) Zbl 07840561
Summary: The \(k^{t h}\) slice \(\begin{pmatrix} [ n ] \\ k \end{pmatrix}\) of the Boolean cube \(\{ 0 , 1 \}^n\) is the set of all \(n\)-bit strings with Hamming weight \(k\). We study the deterministic query complexity of Boolean functions on slices of the Boolean cube. We show that there exists a function on the balanced slice \(\begin{pmatrix} [ n ] \\ n / 2 \end{pmatrix}\) requiring \(n - O(\log \log n)\) queries. We observe that there is an explicit function on the balanced slice requiring \(n - O(\log n)\) queries based on independent sets in Johnson graphs. We also consider the maximum query complexity on constant-weight slices and how it relates to Ramsey theorems.
References:
| [1] | Aaronson, S., Algorithms for Boolean function query properties, SIAM J. Comput., 32, 1140-1157, 2003 · Zbl 1026.68053 |
| [2] | Aaronson, S., Boolean function wizard, 2022 |
| [3] | Aaronson, S.; Ben-David, S.; Kothari, R.; Rao, S.; Tal, A., Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem, (Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021), 1330-1342 · Zbl 07765252 |
| [4] | Alon, N.; Spencer, J. H., The Probabilistic Method, 2016, John Wiley & Sons · Zbl 1333.05001 |
| [5] | Bollobás, B.; Leader, I.; Malvenuto, C., Daisies and other Turán problems, Comb. Probab. Comput., 20, 743-747, 2011 · Zbl 1293.05381 |
| [6] | Buhrman, H.; de Wolf, R., Complexity measures and decision tree complexity: a survey, Theor. Comput. Sci., 288, 21-43, 2002 · Zbl 1061.68058 |
| [7] | Campos, M.; Griffiths, S.; Morris, R.; Sahasrabudhe, J., An exponential improvement for diagonal Ramsey, 2023 |
| [8] | Erdös, P., Some remarks on the theory of graphs, Bull. Am. Math. Soc., 53, 292-294, 1947 · Zbl 0032.19203 |
| [9] | Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470, 1935 · JFM 61.0651.04 |
| [10] | Erdős, P.; Hajnal, A.; Rado, R., Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hung., 16, 93-196, 1965 · Zbl 0158.26603 |
| [11] | Filmus, Y., Friedgut-Kalai-Naor theorem for slices of the Boolean cube, Chic. J. Theor. Comput. Sci., 14, 1-17, 2016 · Zbl 1401.06014 |
| [12] | Filmus, Y.; Ihringer, F., Boolean constant degree functions on the slice are juntas, Discrete Math., 342, Article 111614 pp., 2019 · Zbl 1468.06032 |
| [13] | Filmus, Y.; Mossel, E., Harmonicity and invariance on slices of the boolean cube, Probab. Theory Relat. Fields, 175, 721-782, 2019 · Zbl 1423.60059 |
| [14] | Filmus, Y.; O’Donnell, R.; Wu, X., A Log-Sobolev inequality for the multislice, with applications, (10th Innovations in Theoretical Computer Science Conference (ITCS 2019), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018) · Zbl 07559077 |
| [15] | Gerbner, D.; Keszegh, B.; Nagy, D. T.; Nagy, K.; Pálvölgyi, D.; Patkós, B.; Wiener, G., Query complexity of boolean functions on the middle slice of the cube, 2023 |
| [16] | Graham, R.; Sloane, N., Lower bounds for constant weight codes, IEEE Trans. Inf. Theory, 26, 37-43, 1980 · Zbl 0441.94012 |
| [17] | Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory, vol. 20, 1991, John Wiley & Sons |
| [18] | Jukna, S., Boolean Function Complexity: Advances and Frontiers, vol. 5, 2012, Springer · Zbl 1235.94005 |
| [19] | Katona, G.; Makar-Limanov, L., A problem for Abelian groups, Asian-Eur. J. Math., 1, 237-241, 2008 · Zbl 1175.20046 |
| [20] | Keller, N.; Klein, O., A structure theorem for almost low-degree functions on the slice, Isr. J. Math., 240, 179-221, 2020 · Zbl 1484.06049 |
| [21] | Li, X., Two source extractors for asymptotically optimal entropy, and (many) more, 2023 |
| [22] | Pudlák, P.; Rödl, V.; Sales, M., On the Ramsey number of daisies I, 2022 |
| [23] | Ramsey, F. P., On a problem of formal logic, Proc. Lond. Math. Soc., s2-30, 264-286, 1930 · JFM 55.0032.04 |
| [24] | Sales, M., On the Ramsey number of daisies II, 2022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
