arxiv: 2605.10701 · v1 · submitted 2026-05-11 · 🧮 math.OC · cs.DS

Recognition: 2 theorem links

· Lean Theorem

Handicap reduction for linear complementarity problems

L\'aszl\'o A. V\'egh, Marianna E.-Nagy

Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:05 UTC · model grok-4.3

classification 🧮 math.OC cs.DS

keywords linear complementarity problemssufficient matriceshandicap numberinterior point algorithmsdiagonal rescalingP*-matricesellipsoid methodbit complexity

0 comments

The pith

Sufficient matrices for linear complementarity problems admit an exponential upper bound on their handicap number based on input bit length.

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

The paper shows that the handicap number of a sufficient matrix, which governs the runtime of interior point algorithms for solving linear complementarity problems, grows at most exponentially with the bit length needed to describe the matrix entries. This follows from a new way to characterize which matrices are sufficient. The authors also give an algorithm that searches for the best diagonal rescaling of rows and columns to minimize the effective handicap, using the fact that good rescalings form a convex set that the ellipsoid method can optimize over. If the results hold, LCPs with sufficient matrices become solvable in time polynomial in the input size and this minimized handicap value. The same characterization yields a simpler proof that sufficient matrices coincide with P*-matrices.

Core claim

We give a new characterization of sufficient matrices that produces an exponential upper bound on the handicap number hat kappa(M) in the bit complexity of M. We also present an algorithm whose running time is polynomial in the input size and in the minimal handicap hat kappa star(M) achievable by positive diagonal rescalings of rows and columns; the algorithm runs the interior point method inside the ellipsoid method over the convex set of near-optimal rescalings, using failure of the interior point method as a separation oracle.

What carries the argument

A new characterization of sufficient matrices that directly supplies the exponential handicap bound, together with the convexity of the set of near-optimal row rescalings that lets the ellipsoid method locate a rescaling minimizing the effective handicap for the interior point algorithm.

If this is right

Interior point algorithms now solve LCPs with any sufficient matrix in time at most polynomial in the input size and exponential in the bit length of the entries.
Finding an optimal rescaling reduces the effective handicap and therefore the running time of the interior point algorithm on the equivalent problem.
The ellipsoid method can be used as an outer loop that improves the handicap whenever the interior point method fails to terminate quickly.
The new characterization supplies a simpler proof that a matrix is sufficient if and only if it is a P*-matrix.

Where Pith is reading between the lines

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

The exponential bound is the first finite upper limit known for the handicap and therefore answers whether the parameter can grow arbitrarily fast with input size.
The rescaling-plus-ellipsoid approach shows that diagonal equivalence can be exploited algorithmically to improve solver performance on the same LCP instance.
If future work tightens the bound from exponential to polynomial in the bit length, the long-standing open question of polynomial-time solvability for sufficient-matrix LCPs would be resolved.

Load-bearing premise

The proposed new characterization of sufficient matrices is correct and allows the exponential bound to be derived from the bit lengths of the matrix entries.

What would settle it

A concrete sufficient matrix whose handicap number exceeds every exponential function of the bit length of its entries would disprove the upper bound.

read the original abstract

Linear Complementarity Problems (LCPs) with sufficient matrices form an important subclass of LCPs, and it remains a significant open question whether problems in this class can be solved in polynomial time. Kojima, Megiddo, Noma, and Yoshise gave an Interior Point Algorithm (IPA) in 1991, that can solve LCPs with sufficient matrices in time bounded polynomially in the input size and the so-called handicap number $\hat\kappa(M)$ of the coefficient matrix $M$. However, this value can be exponentially large in the bit encoding length. In fact, no upper bounds were previously known on $\hat\kappa(M)$. Settling an open question raised in de Klerk and E.-Nagy (Math Programming, 2011), we give an exponential upper bound on $\hat\kappa(M)$ in the bit-complexity of $M$. This is based on a new characterization of sufficient matrices. The new characterization also leads to a simple new proof of V\"aliaho's theorem on the equivalence of sufficient and $\mathcal{P}^*$-matrices (Linear Algebra and its Applications, 1996). Noting that one can obtain an equivalent LCP by rescaling the rows and columns by a positive diagonal matrix, we define $\hat\kappa^\star(M)$ as the best possible handicap number achievable under such rescalings. Our second main result is an algorithm for LCPs with sufficient matrices, where the running time is polynomially bounded in the input size and in the optimized value $\hat\kappa^\star(M)$. This algorithm is based on the observation that the set of near-optimal row-rescalings forms a convex set. Our algorithm combines the Ellipsoid Method over the set of row rescalings, and an IPA with running time dependent on the handicap number of the matrix. If the IPA fails to solve the LCP in the desired running time, it provides a separation oracle to the Ellipsoid Method to find a better rescaling.

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.

Desk Editor's Note private letter to a colleague

This paper settles the 2011 open question with an exponential upper bound on the handicap number for sufficient matrices, derived from a new characterization, plus an ellipsoid algorithm to minimize it under rescaling.

read the letter

The main news is that they prove an exponential upper bound on hat kappa(M) for sufficient matrices, measured in the bit length of the input, and they give a practical way to find a row-and-column rescaling that makes the handicap as small as possible. Both results come from a new characterization of sufficient matrices that turns out to be equivalent to the standard definition. They also get a shorter proof of Välaho's equivalence theorem as a side benefit. The algorithm uses the ellipsoid method over the convex set of good rescalings, with the interior-point algorithm serving as the separation oracle when it times out. The stress-test confirms the convexity argument holds directly from the definition under positive diagonal scaling, with no circularity in the bound derivation. The bound itself follows from controlling the size of the relevant principal minors or determinants by the maximum bit size of the entries, which is a standard move once the characterization is available. The bound remains exponential, so this does not deliver a polynomial-time algorithm for sufficient LCPs, but the paper never claims it does. In practice the optimized hat kappa star(M) can be much smaller than the worst-case value, which is the point of the rescaling step. The work is aimed at people who already work on interior-point methods for linear complementarity problems and care about the complexity of the sufficient-matrix case. Anyone tracking the de Klerk–E.-Nagy question or the role of the handicap number will get direct value from the bound and the constructive rescaling procedure. The arguments are self-contained enough and the open-question resolution is concrete enough that the paper deserves a serious referee rather than a desk rejection.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces a new characterization of sufficient matrices for linear complementarity problems (LCPs). This is used to prove an exponential upper bound on the handicap number hat kappa(M) in the bit length of the entries of M, settling an open question of de Klerk and E.-Nagy. As a corollary it yields a new proof of Välaho's theorem on the equivalence of sufficient and P*-matrices. The paper further defines hat kappa star(M) as the minimal handicap achievable by positive diagonal row/column rescalings, shows that the set of near-optimal rescalings is convex, and gives an algorithm that solves the LCP in time polynomial in the input size and hat kappa star(M) by running the ellipsoid method over this set with an interior-point algorithm (IPA) serving as separation oracle.

Significance. If the central claims hold, the work is significant: it supplies the first known upper bound on hat kappa(M), removes a major obstacle to polynomial-time solvability of sufficient LCPs, and gives a practical rescaling procedure that can be combined with existing IPAs. The convexity argument and ellipsoid-method formulation are clean applications of convex optimization to LCP theory. The alternative proof of Välaho's theorem is a useful byproduct.

minor comments (3)

[§3] §3, Theorem 3.2: the equivalence proof between the new characterization and the standard definition of sufficient matrices is stated to proceed via principal-minor bounds; adding one explicit intermediate lemma that isolates the determinant bound used for the exponential estimate would improve readability.
[§5.2] §5.2, Algorithm 1: the separation-oracle step that invokes the IPA and returns a cutting plane when the running-time threshold is exceeded is described at a high level; a short pseudocode block or a one-sentence description of the returned hyperplane would make the implementation clearer.
[Abstract] The abstract claims the bound is 'exponential in the bit-complexity'; the precise dependence (e.g., O(2^{O(n tau)}) where tau is the max bit length) appears only later; a parenthetical remark in the abstract would help readers immediately gauge the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, the recognition of the significance of our results, and the recommendation for minor revision. We appreciate the acknowledgment that our exponential upper bound on the handicap number settles an open question and that the convexity and ellipsoid-method approach provides a clean algorithmic contribution. We will make the minor revisions in the next version of the manuscript.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper's central claims rest on a new characterization of sufficient matrices that is proven equivalent to the standard definition via direct algebraic arguments on principal minors and sign patterns, without any reduction to fitted parameters or prior self-referential results. The exponential upper bound on hat kappa(M) follows immediately by bounding the relevant determinants by the maximum bit length of the input entries, a standard number-theoretic estimate independent of the paper's other constructions. The convexity of the near-optimal rescaling set is established directly from the definition of hat kappa under diagonal scaling, and the ellipsoid-method algorithm invokes only the standard separation-oracle framework together with the existing IPA whose runtime dependence on handicap is taken as given from prior literature. No load-bearing self-citation, ansatz smuggling, or renaming of known results occurs in the derivation; the cited open question from de Klerk and E.-Nagy is merely motivational and not used in any proof step. The overall chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard facts from linear algebra and convex optimization together with the definition of sufficient matrices; no free parameters or new invented entities are introduced in the abstract.

axioms (2)

domain assumption Sufficient matrices admit the interior-point algorithm whose runtime is polynomial in the handicap number.
Invoked when the authors state that the IPA solves LCPs with sufficient matrices in time bounded by the handicap.
domain assumption The set of near-optimal row-rescalings forms a convex set.
Used to justify applying the ellipsoid method to search for a good rescaling.

pith-pipeline@v0.9.0 · 5671 in / 1471 out tokens · 24183 ms · 2026-05-12T04:05:33.164390+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
ˆκ(M) := min{κ≥0 | x⊤Mx + 4κ ∑_{i∈I+_M(x)} x_i(Mx)_i ≥0 ∀x∈R^n}
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and orbit embedding unclear
Theorem 1.4 equivalence of P*, sufficient, and condition (C) on Hadamard products u◦(Mv), v◦(Mu)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

S.-J. Chung. NP-completeness of the linear complementarity problem.Journal of Optimization Theory and Applications, 60:393–399, 1989

work page 1989
[2]

R. W. Cottle, J.-S. Pang, and R. E. Stone.The linear complementarity problem. SIAM, 2009

work page 2009
[3]

Dadush, S

D. Dadush, S. Huiberts, B. Natura, and L. A. V´ egh. A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix.Mathematical Programming, 204:135–206, 2024

work page 2024
[4]

de Klerk and M

E. de Klerk and M. E.-Nagy. On the complexity of computing the handicap of a sufficient matrix. Mathematical Programming, 129(2):383–402, 2011

work page 2011
[5]

E.-Nagy, T

M. E.-Nagy, T. Ill´ es, J. Povh, A. Varga, and J.ˇZerovnik. Sufficient matrices: properties, generating and testing.Journal of Optimization Theory and Applications, pages 1–33, 2023

work page 2023
[6]

Fukuda and T

K. Fukuda and T. Terlaky. Linear complementary and orientated matroids.Journal of the Operations Research Society of Japan, 35:45–61, 1992

work page 1992
[7]

Gr¨ otschel, L

M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver.Geometric algorithms and combinatorial optimization, vol- ume 2. Springer Science & Business Media, 2012

work page 2012
[8]

Guu and R

S.-M. Guu and R. W. Cottle. On a subclass ofP 0.Linear Algebra and Its Applications, 223:325–335, 1995

work page 1995
[9]

Ill´ es, M

T. Ill´ es, M. Nagy, and T. Terlaky. EP theorem for dual linear complementarity problems.Journal of Optimization Theory and Applications, 140:233–238, 2009. 21

work page 2009
[10]

Ill´ es, M

T. Ill´ es, M. Nagy, and T. Terlaky. A polynomial path-following interior point algorithm for general linear complementarity problems.Journal of Global Optimization, 47(3):329–342, 2010

work page 2010
[11]

Kojima, N

M. Kojima, N. Megiddo, T. Noma, and A. Yoshise.A unified approach to interior-point algorithms for linear complementarity-problems, volume 538. Springer Verlag, 1991

work page 1991
[12]

P. Tseng. Co-NP-completeness of some matrix classification problems.Mathematical Programming, 88(1):183–192, 2000

work page 2000
[13]

V¨ aliaho.P∗-matrices are just sufficient.Linear Algebra and Its Applications, 239:103–108, 1996

H. V¨ aliaho.P∗-matrices are just sufficient.Linear Algebra and Its Applications, 239:103–108, 1996

work page 1996
[14]

V¨ aliaho

H. V¨ aliaho. Determining the handicap of a sufficient matrices.Linear Algebra and Its Applications, 253:279–298, 1997

work page 1997
[15]

S. A. Vavasis and Y. Ye. A primal-dual interior point method whose running time depends only on the constraint matrix.Mathematical Programming, 74(1):79–120, 1996. 22

work page 1996