Query complexity of Boolean functions on the middle slice of the cube

DOI10.1016/J.DAM.2024.11.018MaRDI QIDQ6657260zbMATH OpenFDO

Authors Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy, Dömötör Pálvölgyi, Balázs Patkós, Gábor Wiener

Publication date 6 January 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.11.018

zbMATH Keywords

Boolean functiondiscrepancygamequery complexity

Mathematics Subject Classification ID

Number theory (11-XX) Computer science (68-XX)

Recommendations

• Query complexity of Boolean functions on slices
• The complexity of central slice functions
• scientific article; zbMATH DE number 3889430
• Boolean constant degree functions on the slice are juntas
• Quantum query complexity of almost all functions with fixed on-set size

Cites work

• Bart--Moe games, JumbleG and discrepancy
• Combinatorial Games
• Discrepancy games
• scientific article; zbMATH DE number 3910184 (Why is no real title available?)
• KKL, Kruskal-Katona, and monotone nets
• Query complexity of Boolean functions on slices
• The Game of JumbleG

Cited in

(1)

• Query complexity of Boolean functions on slices

This page was built for publication: Query complexity of Boolean functions on the middle slice of the cube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6657260)