pith. sign in

arxiv: 2309.15026 · v3 · submitted 2023-09-26 · 💻 cs.CC

Instance complexity of Boolean functions

Alison Hsiang-Hsuan Liu , Nikhil S. Mande This is my paper

Pith reviewed 2026-05-24 07:22 UTC · model grok-4.3

classification 💻 cs.CC
keywords instance complexitysymmetric Boolean functionsquery complexitydecision treesParity functionGreater-Than functioncertificate complexitycompetitive ratio
0
0 comments X

The pith

Symmetric Boolean functions have instance complexity fully characterized, with only Parity and its complement achieving value 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines instance complexity for query algorithms on Boolean functions, where this measure is the worst-case ratio of an algorithm's query cost to the lowest possible cost achievable by an algorithm that already knows the input. It provides a complete characterization of this measure specifically for all symmetric Boolean functions. This leads directly to the conclusion that Parity and its complement are the sole symmetric functions attaining the lowest possible instance complexity of 1. The work further analyzes several graph properties and identifies two functions, Greater-Than and Odd-Max-Bit, where instance complexity stays constant even though the ratio of standard query complexity to minimum certificate complexity grows linearly with input size.

Core claim

Instance complexity of symmetric Boolean functions is completely characterized. As a direct consequence, Parity and its complement are the only symmetric functions with instance complexity 1. For Greater-Than and Odd-Max-Bit the ratio of query complexity to minimum certificate complexity is linear in the input size, yet explicit algorithms achieve constant instance complexity.

What carries the argument

Instance complexity, defined as the maximum over all inputs of (query cost of the algorithm on that input) divided by (minimum cost of any algorithm knowing the input in advance), evaluated in the decision-tree query model for Boolean functions.

If this is right

  • Only Parity and its complement among symmetric Boolean functions have instance complexity 1.
  • Instance complexity equals the ratio of query complexity to minimum certificate complexity for all functions studied except Greater-Than and Odd-Max-Bit.
  • Algorithms exist for Greater-Than and Odd-Max-Bit that achieve constant instance complexity.
  • Instance complexity of graph properties such as Connectivity and k-clique containment can be determined from their query and certificate structures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The gap between instance complexity and the query-to-certificate ratio for certain functions indicates that competitive analysis can separate algorithm performance more finely than worst-case query measures alone.
  • The characterization technique for symmetric functions may apply to other restricted classes such as read-once or monotone functions beyond those already examined.
  • Instance complexity values for additional graph properties could expose competitive bottlenecks not visible in standard query complexity.

Load-bearing premise

Instance complexity is measured as the worst-case ratio of an algorithm's query cost to the optimal cost when the input is known in advance, within the standard decision-tree model.

What would settle it

An explicit symmetric Boolean function other than Parity or its complement for which every algorithm has instance complexity exactly 1, or a symmetric function whose instance complexity value falls outside the claimed characterization.

Figures

Figures reproduced from arXiv: 2309.15026 by Alison Hsiang-Hsuan Liu, Nikhil S. Mande.

Figure 1
Figure 1. Figure 1: Visual representation of the predicate Df of a symmetric Boolean function f. The interval [ℓ0(f), ℓ1(f)] is the largest interval on which f is constant. Remark 2.5. Given that certificate complexity is a more well-studied measure than minimum certificate complexity, one might ask about the relationship between InstC(f) and DT(f)/C(f). For AND, OR, the former quantity is n (by Lemma 2.4) and the latter quan… view at source ↗
Figure 2
Figure 2. Figure 2: A decision tree Tn for Greater-Than on 2n input bits We now argue that this algorithm A witnesses InstC(GTn) ≤ 2. We analyze the instance complexity of each input with respect to A. – Consider an input of the form (x, y) with x = y. By definition, this is a 0-input for GTn. In order to certify that x ≯ y, it suffices to query all of the 0-variables of x and all of the 1-variables of y. It is also necessary… view at source ↗
Figure 3
Figure 3. Figure 3: A decision tree Tn for Odd-Max-Bit on n input bits with n odd this algorithm B witnesses InstC(OMBn) < 2. We analyze the instance complexity of each input with respect to B. – Let x be a 0-input to OMBn. First, consider the input x = 0n. Any certificate for this input must query all variables xi with i odd, since if unqueried, we could set xi = 1, forcing OMBn = 1. Moreover, the set of all variables xi wit… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies instance complexity (IC) of Boolean functions, defined as the worst-case ratio of an algorithm's query cost on an input to the cost of an optimal algorithm that knows the input in advance. It complements Grossman et al. by giving a complete characterization of IC for all symmetric Boolean functions and concludes that only Parity and its complement achieve IC=1. The paper also computes IC for graph properties including Connectivity and k-Clique containment, and exhibits a strong separation: for Greater-Than and Odd-Max-Bit, the QC/min-certificate ratio is linear while explicit algorithms achieve constant IC.

Significance. If the characterizations and separation hold, the work is significant because it supplies an exhaustive classification for an important natural class (symmetric functions) and demonstrates that IC is not always equal to the QC/min-certificate ratio, thereby refining the relationship between the new measure and classical query-complexity quantities. The explicit algorithm constructions and the corollary isolating Parity provide concrete, falsifiable content.

minor comments (3)
  1. [§1] §1: the formal definition of instance complexity (max_x cost(A,x)/cost(OPT_x)) should be restated verbatim before the symmetric-function results are stated, to make the subsequent claims self-contained.
  2. [§3] The proof of the symmetric characterization (presumably in §3 or §4) relies on case analysis over the possible sensitivity patterns; a short table summarizing the IC value for each type of symmetric function (e.g., threshold, exact-k, parity) would improve readability.
  3. [§5] For the Greater-Than and Odd-Max-Bit separation, the constant upper bound on IC is obtained by a specific algorithm; the manuscript should explicitly state the constant achieved (e.g., 2 or 3) rather than only asserting “constant.”

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the assessment of significance, and the recommendation of minor revision. No specific major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper applies the externally defined measure of instance complexity from Grossman et al. (distinct authors) to symmetric Boolean functions and other examples via standard decision-tree arguments and explicit algorithm constructions. No step reduces a claimed result to a fitted parameter, self-referential equation, or load-bearing self-citation chain; the characterizations and separations follow from direct analysis of the given definition without internal circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on established definitions in query complexity without introducing new free parameters or postulated entities.

axioms (2)
  • domain assumption Instance complexity is defined as the maximum, over all inputs x, of (cost of the algorithm on x) / (cost of an optimal algorithm that knows x in advance).
    This is the measure introduced by Grossman et al. and used as the central object of study.
  • standard math Boolean functions are evaluated in the standard decision-tree query model.
    Background assumption of the field invoked throughout the abstract.

pith-pipeline@v0.9.0 · 5835 in / 1447 out tokens · 72613 ms · 2026-05-24T07:22:37.974305+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · 1 internal anchor

  1. [1]

    Tur \'a n's graph theorem

    Martin Aigner. Tur \'a n's graph theorem. The American Mathematical Monthly , 102(9):808--816, 1995

    work page 1995

  2. [2]

    Complexity measures and decision tree complexity: a survey

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. , 288(1):21--43, 2002

    work page 2002

  3. [3]

    On the instance optimality of detecting collisions and subgraphs

    Omri Ben-Eliezer, Tomer Grossman, and Moni Naor. On the instance optimality of detecting collisions and subgraphs. arXiv preprint arXiv:2312.10196 , 2023

    work page arXiv 2023

  4. [4]

    Complete subgraphs are elusive

    B \'e la Bollob \'a s. Complete subgraphs are elusive. Journal of Combinatorial Theory, Series B , 21(1):1--7, 1976

    work page 1976

  5. [5]

    Extremal graph theory

    B \'e la Bollob \'a s. Extremal graph theory . Courier Corporation, 2004

    work page 2004

  6. [6]

    Competitive information design for pandora's box

    Bolin Ding, Yiding Feng, Chien - Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's box. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 , pages 353--381. SIAM , 2023

    work page 2023

  7. [7]

    Query-competitive algorithms for cheapest set problems under uncertainty

    Thomas Erlebach, Michael Hoffmann, and Frank Kammer. Query-competitive algorithms for cheapest set problems under uncertainty. Theor. Comput. Sci. , 613:51--64, 2016

    work page 2016

  8. [8]

    Computing shortest paths with uncertainty

    Tom \' a s Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, and Rina Panigrahy. Computing shortest paths with uncertainty. J. Algorithms , 62(1):1--18, 2007

    work page 2007

  9. [9]

    Computing the median with uncertainty

    Tom \' a s Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, and Jennifer Widom. Computing the median with uncertainty. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing , pages 602--607. ACM , 2000

    work page 2000

  10. [10]

    Instance complexity and unlabeled certificates in the decision tree model

    Tomer Grossman, Ilan Komargodski, and Moni Naor. Instance complexity and unlabeled certificates in the decision tree model. In 11th Innovations in Theoretical Computer Science Conference, ITCS , volume 151 of LIPIcs , pages 56:1--56:38. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    work page 2020

  11. [11]

    Halld \' o rsson and Murilo Santos de Lima

    Magn \' u s M. Halld \' o rsson and Murilo Santos de Lima. Query-competitive sorting with uncertainty. Theor. Comput. Sci. , 867:50--67, 2021

    work page 2021

  12. [12]

    Computing minimum spanning trees with uncertainty

    Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Mat \' u s Mihal \' a k, and Rajeev Raman. Computing minimum spanning trees with uncertainty. In STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science , volume 1 of LIPIcs , pages 277--288. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, Germany, 2008

    work page 2008

  13. [13]

    Lecture Notes on Evasiveness of Graph Properties

    L \'a szl \'o Lov \'a sz and Neal E Young. Lecture notes on evasiveness of graph properties. arXiv preprint cs/0205031 , 2002

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  14. [14]

    On an external problem in graph theory

    Paul Tur \'a n. On an external problem in graph theory. Mat. Fiz. Lapok , 48:436--452, 1941

    work page 1941