Query complexity of Boolean functions on the middle slice of the cube
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916278256533504 |
|---|---|
| author | Gerbner, Dániel Keszegh, Balázs Nagy, Dániel T. Nagy, Kartal Pálvölgyi, Dömötör Patkós, Balázs Wiener, Gábor |
| author_facet | Gerbner, Dániel Keszegh, Balázs Nagy, Dániel T. Nagy, Kartal Pálvölgyi, Dömötör Patkós, Balázs Wiener, Gábor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_13678 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Query complexity of Boolean functions on the middle slice of the cube Gerbner, Dániel Keszegh, Balázs Nagy, Dániel T. Nagy, Kartal Pálvölgyi, Dömötör Patkós, Balázs Wiener, Gábor Combinatorics Computational Complexity 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. |
| title | Query complexity of Boolean functions on the middle slice of the cube |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2309.13678 |