Query complexity of Boolean functions on slices

DOI10.1016/J.DISC.2024.113954MaRDI QIDQ6418937zbMATH OpenOpenAlexFDO

Authors Farzan Byramji

Publication date 29 November 2022

Full work available at URL https://doi.org/10.1016/j.disc.2024.113954

Mathematics Subject Classification ID

Boolean functions (06E30) Theory of computing (68Qxx)

Abstract: We study the deterministic query complexity of Boolean functions on slices of the hypercube. The $k^{th}$ slice $$ of the hypercube ${0,1}^n$ is the set of all $n$-bit strings with Hamming weight $k$. We show that there exists a function on the balanced slice $$ requiring $n-O(loglogn)$ queries. We give an explicit function on the balanced slice requiring $n-O(logn)$ queries based on independent sets in Johnson graphs. On the weight-2 slice, we show that hard functions are closely related to Ramsey graphs. Further we describe a simple way of transforming functions on the hypercube to functions on the balanced slice while preserving several complexity measures.

Recommendations

• Query complexity of Boolean functions on the middle slice of the cube
• Boolean constant degree functions on the slice are juntas
• The complexity of central slice functions
• Graph complexity and slice functions
• scientific article; zbMATH DE number 3889430

Cited in

(1)

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

This page was built for publication: Query complexity of Boolean functions on slices

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