PaperlayerView exact revision on arXiv

Source-linked AI summary

Unconditional Lower Bounds for the Fredman--Khachiyan Algorithms for Monotone Boolean Duality Testing

Khaled Elbassioni

arXiv:2610.34474v1cs.CCcs.DS

TL;DR

Monotone Boolean duality testing has an open exact-complexity question, including for the quasi-polynomial Fredman–Khachiyan algorithms. The paper analyzes their recursive procedures on constructed dual pairs and proves unconditional superpolynomial call lower bounds, with distinct bounds for Algorithms A and B.

  • Problem

    The exact complexity of monotone Boolean duality testing remains open, including the complexity of Fredman–Khachiyan’s quasi-polynomial algorithms.

    Source: §1 · p. 2

  • Method

    The paper analyzes recursive calls on constructed dual pairs, using a read-once-family polynomial argument for Algorithm A and a symmetric padded family for Algorithm B.

    Source: §4.4 · p. 14

  • Results

    N^Ω(log N) calls for Algorithm A and N^Ω(√(log N/log log N)) for Algorithm B are established as unconditional lower bounds.

    Source: §1 · p. 2, §5 · p. 15

  • Takeaways & Limitations

    On the read-once family, Algorithm A’s call count is N^Θ(log N), and the lower bound holds for every permitted branching-variable choice.

    Source: §5 · p. 15

    The bounds concern the original recursion-tree model and do not cover procedures that merge isomorphic calls, add positive stopping tests, or use different decompositions without further proof.

    Source: §5 · p. 15

Abstract

from arXiv · show

We prove unconditional lower bounds on the number of recursive calls made by the two algorithms of Fredman and Khachiyan (1996) for monotone Boolean duality testing, as a function of the explicit input size $N$. For Algorithm A we show a lower bound of $N^{\Omega(\log N)}$ on the dual pairs $(\HH_k,\LL_k)$ obtained from the read-once family of Gurvich and Khachiyan. The proof lower-bounds the number of leaves of every binary decision tree computing the function by the modulus of its multilinear polynomial evaluated at a complex point of the unit circle. It therefore applies to every choice of branching variables and, more generally, to the class of two-child variable-restriction procedures whose terminal calls have polynomially bounded decision-tree complexity. On this family the number of calls is exactly $N^{\Theta(\log N)}$. For Algorithm B, a symmetric specialization of the polynomial padding construction of Kobayashi, Kurita, and Wasa, with full polynomial blocks, yields at least $q^{(t-1)k-t(t-1)/2}$ calls, where $k=4t^2$ and $q=\Theta(t^2)$; as a function of $N$ this is $N^{\Omega(\sqrt{\log N/\log\log N})}$ along an infinite family. In an appendix we show that applying the padding construction directly to Algorithm A gives $\Omega(2^n)$ calls on a dual pair obtained from an unsatisfiable $n$-variable formula, which is only $N^{\Omega(\sqrt{\log N/\log\log N})}$ in terms of the input size. No complexity-theoretic assumption is used. The proofs allow every branching-variable choice permitted by the respective algorithm. They concern the original recursive procedures, counting every invocation separately, without sharing calls or adding positive stopping tests.

1 Introduction

Monotone Boolean duality testing has an open exact-complexity question, and practical implementations of Fredman–Khachiyan’s quasi-polynomial algorithms perform better than their theoretical bounds. This paper gives the first superpolynomial lower bounds on recursive calls for both algorithms.

1 Introduction

  • The exact complexity of monotone Boolean duality testing remains open, despite quasi-polynomial algorithms and polynomial-time algorithms for some special cases.The input consists of irredundant monotone CNF representations whose functions are tested for duality.Source: §1 · pp. 1–2
  • Practical implementations of both algorithms, especially the simpler Algorithm A, perform much better than their proven upper bounds, while non-trivial lower bounds for either algorithm were previously unknown.The cited passage says this gap suggested their running-time analyses might be improved.Source: §1 · p. 2
  • The paper establishes the first superpolynomial recursive-call lower bounds for both Fredman–Khachiyan algorithms: N^Ω(log N) for A and N^Ω(√(log N/log log N)) for B.The bounds count calls of the original recursion-tree procedures.Source: §1 · p. 2
  • The Algorithm B lower bound builds on the polynomial padding technique of Kobayashi, Kurita, and Wasa, while applying that technique directly to A yields only the weaker exponent scale.The cited prior reduction is ETH-based; the paper’s Algorithm B lower bound is unconditional.Source: §1 · p. 2
  • For Algorithm A, the proof analyzes the Gurvich–Khachiyan read-once family using complex multilinear polynomials, extending the lower bound to every binary decision tree computing the function.The approach also motivates a broader class of two-child variable-restriction procedures.Source: §1 · p. 2
  • Superpolynomial lower bounds were already known for simpler algorithms, including Berge multiplication, rather than for the two Fredman–Khachiyan procedures.Source: §1 · p. 2

2 Preliminaries

The paper develops an unconditional lower bound for Algorithm A by converting recursive restrictions into decision trees and evaluating the target function’s multilinear polynomial at a complex point. On the explicit read-once family, this yields N^{Ω(log N)} calls for Algorithm A and extends to two-child restriction procedures with polynomially bounded terminal decision-tree complexity.

2 Preliminaries

  • The call-count lower bounds count every recursive invocation separately and apply to the original recursion-tree model, not to all algorithms for duality testing.The procedures use their original stopping rules, with no memoization, merged calls, or additional positive stopping tests.Source: §2 · p. 3

3.1 Variable-restriction algorithms

  • A procedure with two-child variable restrictions and terminal decision-tree complexity at most α(N) yields a decision tree with at most α(N)L leaves when it has L terminal calls.Algorithm A is included because its terminal functions have decision trees with at most two leaves.Source: §3.1 · p. 4

3.3 A polynomial evaluation lower bound for decision trees

  • Every decision tree computing F has at least |P_F(z, …, z)| leaves when |z| and |1−z| are at most one.The read-once family’s polynomial evaluation grows exponentially at the chosen complex point.Source: §3.3 · p. 6

3.4 Transferring the bound to variable-restriction algorithms

  • N^{Ω(log N)} calls are required on the read-once family for Algorithm A, and the same bound holds for procedures with α(N) = 2^{o((log N)^2)}.The family also has an upper bound of 2^{O(v_k)} calls, giving N^{Θ(log N)} calls for Algorithm A.Source: §3.4 · p. 7
  • The complex evaluation point is essential to the growth argument: real choices in the permitted interval leave the initial polynomial magnitude at most one.The selected complex point has |z| = |1−z| = 1 and gives an initial magnitude greater than one.Source: §3.4 · p. 7

4 An NΩ(√

This section constructs a symmetric polynomial-padding family that forces Algorithm B’s decomposition at every tracked node, yielding an N^{Ω(√(log N/log log N))} lower bound on calls along an infinite family. The bound holds for every permitted branching-vertex choice and counts invocations separately.

4.1 Polynomial padding and its elementary properties

  • Polynomial padding labels vertices by degree-less-than-t polynomials, making each padded family hittable exactly when a base edge is hit or two same-block vertices have distinct evaluations.A full selector is a minimal transversal, while any minimal transversal containing multiple vertices in a block has size at most 2t.Source: §4.1 · p. 8

4.2 A symmetric padding family

  • Adding a fixed polynomial permutes the symmetric family’s minimal transversals, and every vertex has positive transversal frequency at most 4/q².The symmetric construction sets k = 4t² and takes q as the smallest power of two at least k + 1.Source: §4.2 · pp. 9, 12

4.3 The exact secondary restriction in FK-B

  • For each of the q^(m-1) edges in the selected block’s padding family, the secondary child is isomorphic to (H_(m-1,r-1), L_(m-1,r-1)).The restriction removes that block and its evaluation point while reducing the polynomial degree bound by one.Source: §4.3 · pp. 12–13

4.4 Forcing the decomposition at every tracked node

  • For all sufficiently large t, every tracked state passes the necessary-condition test and executes the secondary decomposition for every permitted variable choice.The states remain dual, avoid the small-family stopping rule, and satisfy the frequency conditions that trigger the decomposition.Source: §4.4 · pp. 13–14
  • N^{Ω(√(log N/log log N))} calls occur along an infinite family, with k = 4t^2 and q = Θ(t^2).The input-size estimates translate the call-count lower bound into the stated bound; binary vertex labels add only an O(log(v + 2)) encoding factor.Source: §4.4 · p. 14
  • At each tracked state with r ≥ 2, every selected vertex forces the required rule, and each of the qm−1 surviving distinct block-edge terms creates a copy of the next state.All subproblems are dual, so the first branch cannot return a nonduality witness that avoids these secondary calls.Source: §4.4 · p. 14
  • The recursive count retains at least qk−h−1 children per retained node at level h, uniformly across the selected block and remaining evaluation points.The procedure counts invocations separately, even when calls are isomorphic; ignoring first branches and other secondary calls only lowers the count.Source: §4.4 · p. 14

5 Scope, explicitness, and concluding remarks

The paper establishes superpolynomial recursive-call lower bounds for both Fredman–Khachiyan algorithms, with a stronger bound for Algorithm A on the read-once family. The bounds hold in the stated recursion-tree model, and the paper identifies limits on extending them to other procedures or inputs.

5 Scope, explicitness, and concluding remarks

  • Algorithm A makes N^Ω(log N) calls on the read-once pairs, with an exact N^Θ(log N) count on that family.The lower bound follows from decision-tree leaf bounds using multilinear-polynomial evaluation and applies to every branching-variable choice and the stated class of two-child restriction procedures.Source: §5 · p. 15
  • Algorithm B makes N^Ω(√(log N/log log N)) calls on the symmetric padded pairs, while applying padding directly to Algorithm A yields only the same exponent scale.Known upper bounds are N^O(log^2 N) for Algorithm A and N^O(log N/log log N) for Algorithm B, leaving gaps in both cases.Source: §5 · p. 15
  • Both input families are explicit; the padded family can be enumerated and its transversal family computed by testing candidate subsets and removing redundancies.The B-family construction requires padding the empty original edge before reduction.Source: §5 · p. 15
  • The lower bounds concern explicit input families and the original recursion-tree procedures, counting calls separately without sharing isomorphic subproblems or adding positive stopping tests.The proofs require neither ETH nor SETH and do not establish lower bounds for all duality-testing algorithms; the read-once bound does not transfer to Algorithm B.Source: §5 · p. 15

A.1 A selector-tree lower bound

The selector-tree argument lower-bounds the leaves needed to shrink independent coordinate domains using point-equality queries. Applied to duality testing, it converts that leaf bound into a lower bound on terminal invocations and calls, without restricting variable selection.

A.1 A selector-tree lower bound

  • The product weight is conserved when a queried domain exceeds its threshold and increases when its size is at most that threshold.For an equality query, the yes domain is a singleton and the no domain removes the queried value; other coordinate domains are unchanged.Source: §A.1 · pp. 16–17
  • The local child-weight inequality implies that the root weight is no greater than the sum of terminal-leaf weights.At the root the weight is the product of (d_i - s_i + 1); at each nonempty terminal leaf it is 1.Source: §A.1 · p. 17
  • The selector lower bound assumes no full selector is a transversal and that every edge leaves at most s_i vertices outside it in each block.Under these conditions, the proposition lower-bounds terminal invocations, hence calls, for procedures in R_α.Source: §A.1 · p. 17
  • Restricting a decision tree to full selectors yields equality queries on independent block domains, so the leaf bound applies regardless of variable-selection frequency.For Algorithm A, the recursion tree can be completed to a decision tree with at most twice as many leaves as recursion-tree leaves.Source: §A.1 · pp. 17–18

A.2 A balanced labeling

The balanced labeling assigns distinct low-degree polynomials to assignment indices so that evaluation fibers stay small at every field point. Full groups of q indices contribute exactly one index to each target-value fiber.

A.2 A balanced labeling

  • The labeling injects the first d nonnegative integers into polynomials of degree less than t, with every evaluation fiber at every field point of size at most ceil(d/q).The construction assumes q is prime and d ≤ qt.Source: §A.2 · p. 18
  • Writing each index in base q and using its digits as polynomial coefficients gives distinct polynomials for distinct indices.The coefficient vector uniquely determines the integer.Source: §A.2 · p. 18
  • Each complete group of q consecutive indices has fixed higher digits and a constant digit that ranges over the whole field.At any fixed evaluation point, the resulting values sweep the field once, so each group contributes exactly one index to any target fiber.Source: §A.2 · pp. 18–19
  • An incomplete final group contributes at most one index to any target-value fiber because its constant digits are distinct but do not cover the field.Summing the complete- and incomplete-group contributions bounds the total fiber size.Source: §A.2 · p. 19

A.3 Application to the SAT construction

The SAT construction encodes assignments as block vertices and pads the resulting hypergraph using polynomial labels. For unsatisfiable formulas, it gives a lower bound on calls that is exponential in the number of variables for procedures with polynomial terminal decision-tree complexity.

A.3 Application to the SAT construction

  • Each block vertex represents an assignment to that variable block, and a clause edge contains assignments making at least one literal in the clause true.A full selector meets every clause edge exactly when its assembled assignment satisfies the formula; unsatisfiability therefore rules out a transversal full selector.Source: §A.3 · p. 19
  • The construction chooses a balanced partition and a prime q above the number of original edges, then labels assignment vertices and pads the hypergraph.The resulting family of small minimal transversals is the entire transversal family supplied to the algorithm.Source: §A.3 · p. 19
  • The leaf lower bound follows by applying the selector proposition with d_i = 2|B_i| and s_i = ceil(d_i/q).The product of the block sizes is 2^n.Source: §A.3 · p. 20
  • For fixed procedures with polynomial terminal decision-tree complexity, the explicit unsatisfiable-formula family yields exponentially many calls in n.The proof obtains a leaf-count logarithm of Ω(n) because log N is o(n) on this family.Source: §A.3 · p. 20

Related papers

Loading 2610.34474v1…