Instance complexity of Boolean functions

[2309.15026] Instance complexity of Boolean functions Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Computational Complexity arXiv:2309.15026 (cs) [Submitted on 26 Sep 2023 ( v1 ), last revised 12 Jun 2026 (this version, v4)] Title: Instance complexity of Boolean functions Authors: Alison Hsiang-Hsuan Liu , Nikhil S. Mande View a PDF of the paper titled Instance complexity of Boolean functions, by Alison Hsiang-Hsuan Liu and Nikhil S. Mande View PDF HTML (experimental) Abstract: In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the competitive ratio, we consider a different cost measure for query algorithms for Boolean functions that captures the ratio of the cost of the algorithm and the cost of an optimal algorithm that knows the input in advance. The cost of an algorithm is its largest cost over all inputs. Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean functions, and dubbed it instance complexity. Grossman et al. showed, among other results, that monotone Boolean functions with instance complexity 1 are precisely those that depend on one or two variables. We complement the above-mentioned result of Grossman et al. by completely characterizing the instance complexity of symmetric Boolean functions. As a corollary we conclude that the only symmetric Boolean functions with instance complexity 1 are the Parity function and its complement. We also study the instance complexity of some graph properties like Connectivity and k-clique containment. In all the Boolean functions we study above, and those studied by Grossman et al., the instance complexity turns out to be the ratio of query complexity to minimum certificate complexity. It is a natural question to ask if this is the correct bound for all Boolean functions. We show a negative answer in a very strong sense, by analyzing the instance complexity of the Greater-Than and Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the input size for both of these functions, while we exhibit algorithms for which the instance complexity is a constant. Comments: Journal (DMTCS) version Subjects: Computational Complexity (cs.CC) Cite as: arXiv:2309.15026 [cs.CC] (or arXiv:2309.15026v4 [cs.CC] for this version) https://doi.org/10.48550/arXiv.2309.15026 Focus to learn more arXiv-issued DOI via DataCite Journal reference: Discrete Mathematics & Theoretical Computer Science, vol. 28:2, Discrete Algorithms (June 21, 2026) dmtcs:15917 Related DOI : https://doi.org/10.46298/dmtcs.15917 Focus to learn more DOI(s) linking to related resources Submission history From: Nikhil Mande [ view email ] [v1] Tue, 26 Sep 2023 15:56:14 UTC (13 KB) [v2] Thu, 19 Jun 2025 16:47:49 UTC (14 KB) [v3] Fri, 10 Apr 2026 10:14:13 UTC (14 KB) [v4] Fri, 12 Jun 2026 09:18:44 UTC (20 KB) Full-text links: Access Paper: View a PDF of the paper titled Instance complexity of Boolean functions, by Alison Hsiang-Hsuan Liu and Nikhil S. Mande View PDF HTML (experimental) TeX Source view license Current browse context: cs.CC < prev | next > new | recent | 2023-09 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• A General Composition Theorem for Approximate Degree#1078210
• UnionSparse: An Index-Efficient Sparsity Framework for Low-Bit Sparse LLM Inference on Edge#441749
• Efficient Randomized Communication Without Large Monochromatic Rectangles#1034557
• Measuring Mutual Information in Random Boolean Networks#639148
• Color Relationalism, Ordinary Illusion, and Color Incompatibility#763409