Gerbner, Dániel and Keszegh, Balázs and Nagy, Dániel and Nagy, Kartal and Pálvölgyi, Dömötör and Patkós, Balázs and Wiener, Gábor (2025) Query complexity of Boolean functions on the middle slice of the cube. DISCRETE APPLIED MATHEMATICS, 362. pp. 43-49. ISSN 0166-218X
|
Text
1-s2.0-S0166218X24004888-main.pdf - Published Version Available under License Creative Commons Attribution. Download (386kB) | Preview |
Abstract
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0’s and 1’s in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.
| Item Type: | Article |
|---|---|
| Additional Information: | HUN-REN Alfréd Rényi Institute of Mathematics, Hungary ELTE Eötvös Loránd University, Hungary Budapest University of Technology and Economics, Department of Computer Science and Information Theory, Hungary Export Date: 29 November 2024 CODEN: DAMAD Correspondence Address: Nagy, D.T.; ELTE Eötvös Loránd UniversityHungary; email: nagytdaniel@inf.elte.hu Funding details: Magyar Tudományos Akadémia, MTA Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, PD 137779, FK 132060, K 132696, KKP-133819 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH Funding details: European Research Council, ERC, TKP2021-NKTA-62, ÚNKP-23-5, TKP2021, BME-NVA-02 Funding details: European Research Council, ERC Funding text 1: Research of B. Keszegh, D.T. Nagy and D. P\\u00E1lv\\u00F6lgyi was also supported by the J\\u00E1nos Bolyai Research Scholarship of the Hungarian Academy of Sciences . Funding text 2: Research supported by the National Research, Development and Innovation Office - NKFIH under the grants FK 132060 , PD 137779 , KKP-133819 , K 132696 . Funding text 3: Research of B. Keszegh and D. P\\u00E1lv\\u00F6lgyi was also supported by the ERC Advanced Grant \\u201CERMiD\\u201D and by the New National Excellence Program \\u00DANKP-23-5 and by the Thematic Excellence Program TKP2021-NKTA-62 of the National Research, Development and Innovation Office. Funding text 4: We would like to thank Farzan Byramji for discussions and Krist\\u00F3f Z\\u00F3lomy for calling our attention to an error in an earlier version of our paper. Research supported by the National Research, Development and Innovation Office - NKFIH under the grants FK 132060, PD 137779, KKP-133819, K 132696. Research of B. Keszegh, D.T. Nagy and D. P\\u00E1lv\\u00F6lgyi was also supported by the J\\u00E1nos Bolyai Research Scholarship of the Hungarian Academy of Sciences. Research of B. Keszegh and D. P\\u00E1lv\\u00F6lgyi was also supported by the ERC Advanced Grant \\u201CERMiD\\u201D and by the New National Excellence Program \\u00DANKP-23-5 and by the Thematic Excellence Program TKP2021-NKTA-62 of the National Research, Development and Innovation Office. Research of G. Wiener was supported by the Research, Development and Innovation Fund, financed under the TKP2021 (project no. BME-NVA-02) funding scheme. Funding text 5: Research of G. Wiener was supported by the Research, Development and Innovation Fund, financed under the TKP2021 (project no. BME-NVA-02 ) funding scheme. |
| Uncontrolled Keywords: | Query complexity, Boolean function, Discrepancy, Game |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 23 Jan 2026 06:23 |
| Last Modified: | 23 Jan 2026 06:23 |
| URI: | https://real.mtak.hu/id/eprint/232495 |
Actions (login required)
 |
Edit Item |
