betaFeedback

WorksComputer Science

The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients

Abstract

Computing a Karush-Kuhn-Tucker (KKT) point of a quadratic polynomial over the unit hypercube is known to be CLSCLS-complete, when the coefficients of the polynomial are encoded in binary. We prove that the problem remains CLSCLS-complete even when the coefficients are encoded in unary. This is the first problem proven to remain CLSCLS-hard when the input is given in unary.

Introduction

Quadratic programming is possibly one of the most fundamental problems in continuous optimization, with applications ranging from game theory and machine learning, to engineering and computational chemistry [12]. One of the most basic forms of the problem is defined via “box constraints” [1, 4]. There, the problem is defined via an n×nn \times n symmetric coefficient-matrix QQ, and an nn-dimensional coefficient-vector c\mathbf{c}. The goal is to find a point in the nn-dimensional hypercube that minimizes the corresponding quadratic program, formally:

min⁡x∈[0,1]nP(x):=xTQx+cTx.(1)\min_{\mathbf{x} \in[0,1]^n} P(\mathbf{x}) := \mathbf{x}^{T}Q\mathbf{x} + \mathbf{c}^{T}\mathbf{x}. \tag*{(1)}

Since the complexity of the problem was proven to be NP-hard more than fifty years ago [17, 18], the relaxed solution of Karush-Kuhn-Tucker, a.k.a., KKT, points was considered. There, instead of a global optimum of P(x)P(\mathbf{x}), the solution can be any first-order stationary point, a.k.a. fixed point of gradient descent, of the polynomial. In a recent celebrated result, [11] showed that computing a KKT point of (1), even in the approximate sense, is CLS-complete. This serves as an indication that it is unlikely the problem to have a polynomial-time algorithm.

The complexity class CLS, standing for Continuous Local Search, was introduced by Daskalakis and Papadimitriou [9] to capture the complexity of search problems that belong to both PPAD [14] and PLS [13] yet no polynomial-time algorithm is known. In other words, the existence of the solution is guaranteed either via a fixed point argument or via a potential function argument. In their breakthrough result, [11] proved that CLS = PPAD ∩\cap PLS.

Since then, a series of works established CLS-hardness for congestion games [5] and equilibrium computation problems [10, 20], and very recently, in yet another breakthrough result, for KKT points in bilinear polynomials, i.e., polynomials without any square term [2]. However, in all of the above-mentioned results the input of the problem was given with binary encoding, hence the input could include coefficients of exponential precision. In fact, the correctness of the reduction of [11] heavily relies on the existence of exponential ratios between the coefficients and it explicitly asks as an open problem whether CLS-hardness still holds when the input is given in unary. Additionally, for the case of KKT points for bilinear polynomials, binary encoding is actually required in order to establish CLS-hardness [2]. If the input is given in unary the bilinear polynomials become polynomial-time solvable.

To see the latter, observe that a bilinear polynomial is affine in each coordinate separately. So it always has a global minimum, and hence a KKT point, at a Boolean vector, i.e., a solution where xi∈{0,1}x_i \in\{0,1\}. Moreover, a Boolean point is a KKT point precisely when no single bit flip decreases the objective. If the coefficients are integers, each improving flip decreases the objective by at least one. With polynomially bounded coefficients, the range of the objective on Boolean points is also polynomially bounded, and this elementary local search procedure terminates in polynomial time.

Hence, the open question from [11] becomes even more intriguing: is binary encoding required to establish CLS-hardness in general, or can we prove hardness even when the input is given in unary?

Our result and its implications. We answer the open question of [11] and prove that finding a KKT point of (1) remains CLS-hard even when all coefficients, of QQ and cc, are given in unary. This is the first problem where the input is given in unary and it is CLS-hard. As a consequence, our result rules out the existence of pseudopolynomial-time algorithm for KKT points. Our result provides an interesting dichotomy: allowing square terms produces a sharp change in complexity of KKT points. When the input is given in unary, bilinear KKT admits a polynomial time algorithm, whereas quadratic KKT remains CLS-complete; see Table 1. Thus, our result implies that the reduction of [2] is essentially “optimal”: the exponential blow-up in the coefficients of the produced bilinear polynomial is necessary. Finally, our result can be seen as a complement to the recent result of [2]. The equality CLS=PPAD∩PLS\mathrm{CLS} = \mathrm{PPAD} \cap\mathrm{PLS} gives two possible approaches to solving problems in CLS: one through fixed point computation and another through local search. A restriction that makes either approach efficient is enough to obtain a polynomial-time algorithm; for the latter, [19, 16] observed that many problems become tractable under unary encoding. Along with [2], we establish that hardness for KKT points persists when either square terms or large integer coefficients are excluded separately, but excluding both makes the problem tractable.

ObjectiveBinary-encoded coefficientsUnary-encoded coefficients
QuadraticCLS-complete [11]CLS-complete; this work
BilinearCLS-complete [2]Polynomial time; Boolean solution

Table 1. The complexity of computing exact KKT points over the unit cube.

Technical overview

Our starting point is the CLS-complete problem QUADRATIC-KKTproblem from [11], where we are given a quadratic polynomial PP with nn variables and binary-encoded coefficients, i.e., coefficients can have exponential precision. We construct a quadratic polynomial that preserves all stationary points of PP and has polynomially-bounded integer coefficients. The high-level idea is to simulate the exponentially-precise coefficients of PP with polynomially-many auxiliary variables: we “push” the precision of the coefficients to the values of the auxiliary variables at any KKT point of the constructed polynomial. In other words, at any KKT point of the constructed polynomial, the auxiliary variables need exponential precision and thus they can simulate the coefficients or the original instance.

More concretely now, our reduction consists of three main steps.

Step 1: Normalization. As first step, we normalize the coefficients of the input polynomial PP to take values in (−1,1)(-1,1), without changing its KKT points. This is done via a “standard” way. This step is crucial for our reduction in order to guarantee the solution space to be the unit hypercube; without normalization the next steps of the reduction would have required exponentially large numbers as solution for the auxiliary variables.

Step 2: Dyadic decomposition. The next step is to decompose the normalized polynomial as a sum of monomials with coefficients of the form 2−k2^{-k}, where kk is polynomially-bounded by the encoding length of the input. In fact, kk is bounded by the maximum number of bits required for any coefficient of PP. This decomposition of PP allows us to focus on each monomial independently and introduce independent auxiliary variables. Hence, every monomial is of the form g(x,y)=2−kxyg(x,y)=2^{-k}xy, where xx may also be equal to yy, and its partial derivatives are

∂g∂x=2−kyand∂g∂y=2−kx.\frac{\partial g}{\partial x}=2^{-k}y \quad\text{and}\quad\frac{\partial g}{\partial y}=2^{-k}x.

Observe, each variable contributes to the gradient of gg a value scaled by 2−k2^{-k}, i.e., a value obtained by halving the value kk times. Our goal then boils down to simulate this halving effect using integer coefficients by introducing a polynomial number of auxiliary variables.

Before we introduce the next step of the reduction, which simulates the halving effect, let us provide some high-level intuition for it. We can think of the variables xx and yy of a monomial as two gates that transmit signals to each other, using a chain of auxiliary variables as shown in Figure 1.

Figure 1. Two-way propagation of values through auxiliary variables.

A “blue” signal originates from xx and propagates towards yy, while getting halved each time it passes through an intermediate gate. Similarly, a “red” signal originates from yy and propagates towards xx, undergoing the same halving process. The goal is to create a gadget that: a) preserves the KKT points of PP and b) does not create any additional KKT points. The next step of the reduction formally achieves this.

Step 3: The quadratic chain gadget. For each monomial g(x,y)=s2−kxyg(x,y)=s2^{-k}xy, where s∈{−1,1}s\in\{-1,1\}, we introduce m=k+2m=k+2 auxiliary variables u1,…,umu_1,\ldots,u_m, denoted u\mathbf{u} for brevity, each constrained in [−1,1][-1,1], and construct the following quadratic chain gadget:

G(x,y,u)=3∑i=1m−1(2ui−ui+1)2+9um2−6xu1+6syum+x2+y2.G(x,y,\mathbf{u})=3\sum_{i=1}^{m-1}(2u_i-u_{i+1})^2+9u_m^2-6xu_1+6syu_m+x^2+y^2.

Each chain gadget satisfies the following property which is crucial for our purposes: for every fixed values of xx and yy the function GG is strictly convex with respect to u\mathbf{u}. This implies that, for fixed x,yx,y, GG admits a unique minimizer, denoted u∗(x,y)\mathbf{u}^*(x,y), which is the unique KKT point of GG as well. Crucially, the choice of the coefficients of GG ensure that u∗(x,y)\mathbf{u}^*(x,y) always resides inside [−1,1]m[-1,1]^m. In fact, we derive a closed form formula for the auxiliary variables where for i∈[m]i\in[m] we get that

ui=13(21−ix−s2i−my).u_i=\frac{1}{3}\left(2^{1-i}x-s2^{i-m}y\right).

Thus, at any KKT point of GG, the values of the auxiliary variables require exponential precision, which was our initial goal. The term 21−i2^{1-i} represents the “blue” signal from Figure 1, which halves as ii increases from 1 to mm, while the term 2i−m2^{i-m} represents the “red” signal. The detailed analysis is presented in Lemma 4.4.

As a side note, let us highlight that our chain gadget guarantees more than just equality of the derivatives: it establishes the stronger identity that 2−kxy2^{-k}xy is equal to G(x,y,u∗(x,y))G(x,y,\mathbf{u}^{*}(x,y)), which can be of independent interest (see Lemma 4.5).

Putting everything together. To complete our reduction, the final constructed polynomial is the summation of all chain gadgets of the dyadic monomials. The resulting polynomial has integer coefficients of polynomially bounded magnitude. To see this, observe the following: a) the coefficients in every chain gadget are constants; b) there are polynomially many chain gadgets; c) the length of each gadget is polynomial. Furthermore, since the auxiliary variables are disjoint across gadgets, the arguments from Step 3 for KKT points apply independently to them.

Preliminaries

For any positive integer nn, we denote [n]={1,…,n}[n]=\{1,\ldots,n\}. We consider quadratic polynomials over nn variables x=(xi)i∈[n]\mathbf{x}=(x_i)_{i\in[n]} that are given as a sum of monomials:

P(x)=∑i=1nqiixi2+∑1≤i<j≤nqijxixj+∑i=1ncixi(2)P(\mathbf{x})=\sum_{i=1}^{n}q_{ii}x_i^2+\sum_{1\leq i<j\leq n}q_{ij}x_ix_j+\sum_{i=1}^{n}c_ix_i \tag*{(2)}

where for all i,j∈[n]i,j\in[n] the coefficients qii,qij,ciq_{ii},q_{ij},c_i are assumed to be rational numbers.

We follow the definition of box-constrained KKT point of PP from [11].

Definition 3.1 (Box-constrained KKT points). For a quadratic polynomial PP, as expressed in (2), consider the constrained optimization problem min⁡x∈[0,1]nP(x)\min_{\mathbf{x}\in[0,1]^n}P(\mathbf{x}). A point x∗∈[0,1]n\mathbf{x}^{*}\in[0,1]^n is a Karush–Kuhn–Tucker (KKT) point of this optimization problem if for every coordinate i∈[n]i\in[n] the following conditions are satisfied:

∂P∂xi(x∗)≥0 if xi∗=0,∂P∂xi(x∗)=0 if xi∗∈(0,1),∂P∂xi(x∗)≤0 if xi∗=1.(3)\frac{\partial P}{\partial x_i}(\mathbf{x}^{*})\geq0\ \text{if }x_i^{*}=0,\qquad\frac{\partial P}{\partial x_i}(\mathbf{x}^{*})=0\ \text{if }x_i^{*}\in(0,1),\qquad\frac{\partial P}{\partial x_i}(\mathbf{x}^{*})\leq0\ \text{if }x_i^{*}=1. \tag*{(3)}

As it was formally explained in [11], under the above mentioned definition a KKT point always does exist.

Binary Vs Unary encoding. A quadratic polynomial is represented by an explicit list of its monomials and their corresponding rational coefficients. Hence, the input size is given by the number of variables, which is nn, plus the size of encoding the coefficients. When the coefficients are encoded in binary, i.e., as bitstrings, they can represent numbers of exponential precision, with respect of the input size. For example, the ratio between two coefficients can be 2Ω(n)2^{\Omega(n)}. On the other hand, when the coefficients are given in unary, they have only polynomially-bounded precision. In other words, P(x)P(\mathbf{x}) can be represented using integer-coefficients with absolute values bounded by the unary encoding length NN of the input polynomial. Hence, in this case the ratio between any two coefficients is bounded by poly⁡(N)\operatorname{poly}(N).

We proceed with the definition of Qᴜᴀᴅʀᴀᴛɪᴄ-KKT, the main computational problem of interest, and the current state of the art for its complexity.

Definition 3.2 (Qᴜᴀᴅʀᴀᴛɪᴄ-KKT). Given a quadratic polynomial PP over nn variables, compute a KKT point of the optimization problem min⁡x∈[0,1]nP(x)\min_{\mathbf{x}\in[0,1]^n}P(\mathbf{x}).

Theorem 3.3 ([11]). Qᴜᴀᴅʀᴀᴛɪᴄ-KKT is CLS-complete, when the input polynomial is given in binary.

The CLS-hardness reduction

In this section we establish the main theorem of our paper.

Theorem 4.1. Quadratic-KKT is CLS-complete even when the input is given in unary.

We present a polynomial-time reduction from Quadratic-KKT given with binary-encoded coefficients. Specifically, given an instance defined by a quadratic polynomial PP, we construct a quadratic polynomial H\mathcal{H} such that (i) the unary encoding length of H\mathcal{H} is polynomially bounded in the encoding length of PP, and (ii) every KKT point of H\mathcal{H} projects to a KKT point of PP.

We now outline the main steps of the reduction. In § 4.1, we construct a normalized quadratic polynomial P~\widetilde{P} whose coefficients admit a decomposition into signed dyadic terms of the form s2−ks2^{-k}, with s∈{−1,1}s \in\{-1,1\} and kk being polynomially bounded in the encoding length of PP. Lemma 4.2 establishes that P~\widetilde{P} and PP have exactly the same KKT points.

In § 4.2, we introduce the quadratic chain gadget, which is the main technical tool of our reduction. For any dyadic monomial 2−kxy2^{-k}xy, the gadget constructs a quadratic polynomial with constant-bounded integer coefficients and O(k)O(k) auxiliary variables. We prove that minimizing this polynomial over its auxiliary variables reproduces 2−kxy2^{-k}xy exactly, as established in Lemma 4.5.

In Section 4.3, we combine the quadratic chain gadgets corresponding to all dyadic monomials of P~\widetilde{P}. We show that every KKT point of the resulting quadratic polynomial projects onto a KKT point of P~\widetilde{P}, and hence of PP. Finally, in § 4.4, we transform the auxiliary domain to the unit hypercube and establish that the resulting polynomial H\mathcal{H} has integer coefficients with polynomially bounded unary encoding lengths.

Normalizing the Coefficients and Dyadic decomposition

Consider an instance of Quadratic-KKT and let P(x)P(\mathbf{x}) be the corresponding quadratic polynomial over [0,1]n[0,1]^n, as defined in Equation (2). Let KKT⁡(P)\operatorname{KKT}(P) denote the set of KKT points of PP. We construct a polynomial P~\widetilde{P} whose coefficients are polynomially bounded in the encoding length of PP, while preserving the set of KKT points, i.e., KKT⁡(P)=KKT⁡(P~)\operatorname{KKT}(P) = \operatorname{KKT}(\widetilde{P}).

Let AA be the least common multiple of the denominators of the coefficients appearing in P(x)P(\mathbf{x}). Compute the polynomial P′(x)=AP(x)P'(\mathbf{x}) = AP(\mathbf{x}). Notice that P′P' admits only integer coefficients. Let MM be the maximum value among 11 and the absolute values of the coefficients in P′P'. Set L=⌊log⁡2M⌋+1L = \lfloor\log_2 M \rfloor+ 1 and define S=2LS = 2^L. Finally compute the polynomial P~(x)=P′(x)/S\widetilde{P}(\mathbf{x}) = P'(\mathbf{x})/S. For this transformation the following holds.

Lemma 4.2. The polynomials PP and P~\widetilde{P} have exactly the same KKT points, namely KKT⁡(P)=KKT⁡(P~)\operatorname{KKT}(P) = \operatorname{KKT}(\widetilde{P}). Moreover every coefficient dd of P~\widetilde{P} admits a dyadic decomposition of the form

d=s∑k=1Lδk2−k,(4)d = s \sum_{k=1}^{L} \delta_k 2^{-k}, \tag*{(4)}

where s∈{−1,+1}s \in\{-1,+1\} and δk∈{0,1}\delta_k \in\{0,1\}.

Proof. For every x∈[0,1]n\mathbf{x} \in[0,1]^n and every i∈[n]i \in[n], we have ∂P~∂xi(x)=AS∂P∂xi(x)\frac{\partial\widetilde{P}}{\partial x_i}(\mathbf{x}) = \frac{A}{S}\frac{\partial P}{\partial x_i}(\mathbf{x}). Since A/S>0A/S > 0, the corresponding partial derivatives of PP and P~\widetilde{P} have the same sign and are equal to 00 at the same points. Consequently, for every i∈[n]i \in[n], the KKT condition associated with xix_i is satisfied by PP at x\mathbf{x} if and only if it is satisfied by P~\widetilde{P} at x\mathbf{x} and thus KKT⁡(P)=KKT⁡(P~)\operatorname{KKT}(P) = \operatorname{KKT}(\widetilde{P}).

Since P′P' has integer coefficients and P~(x)=P′(x)/2L\widetilde{P}(\mathbf{x}) = P'(\mathbf{x})/2^L, every coefficient dd of P~\widetilde{P} can be expressed as d=z/2Ld = z/2^L, for some integer z∈Zz \in\mathbb{Z} or which ∣z∣<2L|z| < 2^L. If z=0z = 0, the decomposition holds by

choosing s=1s=1 and δk=0\delta_k=0 for every k∈[L]k \in[L]. Otherwise, let s∈{−1,+1}s \in\{-1,+1\} denote the sign of zz. Since 0<∣z∣<2L0<|z|<2^L, the binary representation of ∣z∣|z| contains at most LL bits. Therefore, there exist δ1,…,δL∈{0,1}\delta_1,\ldots,\delta_L \in\{0,1\} such that ∣z∣=∑k=1Lδk2L−k|z|=\sum_{k=1}^{L}\delta_k2^{L-k}. Dividing both sides by 2L2^L and multiplying by ss, we get d=s∑k=1Lδk2−kd=s\sum_{k=1}^{L}\delta_k2^{-k}.

Using the above lemma, we can express P~\widetilde{P} as a sum of monomials with signed dyadic coefficients. Let RR denote the total number of nonzero terms obtained from expanding each coefficient in P~\widetilde{P} according to (4). For each r∈[R]r \in[R], let pr(x),qr(x)∈{1,x1,…,xn}p_r(\mathbf{x}),q_r(\mathbf{x}) \in\{1,x_1,\ldots,x_n\}. Their products represent all types of monomials appearing in P~\widetilde{P}, namely, quadratic, linear, and constant monomials. Consequently, we can express P~\widetilde{P} as the following dyadic expansion.

P~(x)=∑r=1Rsr2−krpr(x)qr(x),sr∈{−1,+1},1≤kr≤L.(5)\widetilde{P}(\mathbf{x})=\sum_{r=1}^{R}s_r2^{-k_r}p_r(\mathbf{x})q_r(\mathbf{x}),\qquad s_r\in\{-1,+1\},\qquad1\leq k_r\leq L. \tag*{(5)}

Since each coefficient contributes at most LL terms to the dyadic expansion and P~\widetilde{P} contains O(n2)O(n^2) monomials, we have R=O(n2L)R=O(n^2L). Moreover, because LL is polynomially bounded in the encoding length of PP, the dyadic expansion can be computed in polynomial time.

Quadratic chain gadget

Consider a dyadic monomial g(x,y)=s2−kxyg(x,y)=s2^{-k}xy, where s∈{−1,1}s\in\{-1,1\}, 1≤k≤L1\leq k\leq L and x,y∈[0,1]x,y\in[0,1]. Let m=k+2m=k+2 and introduce mm auxiliary variables u=(u1,…,um)∈[−1,1]m\mathbf{u}=(u_1,\ldots,u_m)\in[-1,1]^m. Consider the following quadratic polynomial which we refer to as quadratic chain gadget.

G(x,y,u)=3∑i=1m−1(2ui−ui+1)2+9um2−6xu1+6syum+x2+y2.(6)G(x,y,\mathbf{u})=3\sum_{i=1}^{m-1}(2u_i-u_{i+1})^2+9u_m^2-6xu_1+6syu_m+x^2+y^2. \tag*{(6)}

For fixed values of xx and yy in [0,1][0,1], let Gx,y:[−1,1]m→RG_{x,y}:[-1,1]^m\to\mathbb{R} denote the quadratic chain gadget, viewed as a function of u\mathbf{u}. Notice that the quadratic polynomial Gx,yG_{x,y} is continuous over the compact set [−1,1]m[-1,1]^m, and hence admits at least one global minimizer in this domain. Let u∗(x,y)\mathbf{u}^*(x,y) denote a global minimizer of Gx,yG_{x,y}, that is,

u∗(x,y)∈arg⁡min⁡u∈[−1,1]mGx,y(u).(7)\mathbf{u}^*(x,y)\in\mathop{\arg\min}_{\mathbf{u}\in[-1,1]^m}G_{x,y}(\mathbf{u}). \tag*{(7)}

The next lemma shows the relation between a global minimizer and a KKT point of Gx,yG_{x,y}.

Lemma 4.3. For every fixed x,y∈[0,1]x,y\in[0,1], the quadratic polynomial Gx,yG_{x,y} admits a unique global minimizer u∗(x,y)\mathbf{u}^*(x,y) over [−1,1]m[-1,1]^m, which is also the unique KKT point of Gx,y(u)G_{x,y}(\mathbf{u}) over $[-1,1]^m.

Proof. First we will show that Gx,yG_{x,y} is strictly convex in [−1,1]m[-1,1]^m. Fix the values for the variables x,yx,y and let Q(u)Q(\mathbf{u}) denote the quadratic part of Gx,yG_{x,y}, i.e.,

Q(u)=3∑i=1m−1(2ui−ui+1)2+9um2.Q(\mathbf{u})=3\sum_{i=1}^{m-1}(2u_i-u_{i+1})^2+9u_m^2.

Since Gx,yG_{x,y} differs from QQ only by linear terms in u\mathbf{u}, to establish that Gx,yG_{x,y} is strictly convex, it suffices to show that QQ is a positive-definite quadratic form, i.e., Q(u)>0Q(\mathbf{u})>0 for every u≠0\mathbf{u}\ne0.1 Now observe that Q(u)≥0Q(\mathbf{u})\geq0 as a sum of square terms while the equality holds if and only if u=0\mathbf{u}=0. Thus QQ is a positive definite form and hence Gx,yG_{x,y} is strictly convex. As a consequence of strict convexity, Gx,yG_{x,y} admits at most one global minimizer in [−1,1]m[-1,1]^m.2 Since Gx,yG_{x,y} admits at least one global minimizer in [−1,1]m[-1,1]^m, then u∗(x,y)\mathbf{u}^*(x,y) is the unique global minimizer of Gx,y(u)G_{x,y}(\mathbf{u}), namely

u∗(x,y)=arg⁡min⁡u∈[−1,1]m  Gx,y(u).\mathbf{u}^*(x,y)=\underset{\mathbf{u}\in[-1,1]^m}{\arg\min}\;G_{x,y}(\mathbf{u}).

Finally since Gx,yG_{x,y} is differentiable and strictly convex over [−1,1]m[-1,1]^m, a point satisfies the KKT conditions for Gx,yG_{x,y} if and only if it is a global minimizer.3 As u∗(x,y)\mathbf{u}^*(x,y) is the unique global minimizer of Gx,yG_{x,y}, it follows that it is also the unique KKT point of Gx,yG_{x,y}.

However, uniqueness on its own does not suffice to establish the correctness of the gadget. Since the auxiliary variables are box-constrained a KKT point of GG, with xx and yy not fixed, does not necessarily satisfy the stationarity equations of the original polynomial. We must therefore ensure that the auxiliary variables satisfy the unconstrained stationarity conditions, at every KKT of GG. This is satisfied if we prove that the unique minimizer u∗\mathbf{u}^* for every fixed x,yx,y lies in the interior of the feasible domain.

Lemma 4.4. For every x,y∈[0,1]x,y\in[0,1] it holds that u∗(x,y)∈(−1,1)m\mathbf{u}^*(x,y)\in(-1,1)^m.

Proof. Fix x,y∈[0,1]x,y\in[0,1] and consider the unconstrained stationarity equations of Gx,yG_{x,y} as follows

4u1−2u2=x,(8)4u_1-2u_2=x, \tag*{(8)}
5ui−2ui−1−2ui+1=0,2≤i≤m−1,(9)5u_i-2u_{i-1}-2u_{i+1}=0,\qquad2\le i\le m-1, \tag*{(9)}
4um−2um−1=−sy.(10)4u_m-2u_{m-1}=-sy. \tag*{(10)}

Since Gx,yG_{x,y} is strictly convex, as established in Lemma 4.3, its unconstrained stationarity system LS admits at most one solution. As a consequence if LS admits a solution, then this is unique.

We express the solution of LS as a linear combination of two auxiliary solutions. Specifically let LS1 denote the linear system obtained from LS by setting x=1x=1 and y=0y=0 and let LS2 denote the linear system obtained from LS by setting x=0x=0 and sy=−1sy=-1. Observe that all three linear systems share the same coefficient matrix, which is equal to the Hessian of QQ multiplied by 1/61/6. Since QQ is a strictly convex quadratic form, its Hessian, and as a consequence the coefficient matrix of the linear systems, is positive definite and hence invertible. Consequently, each system admits a unique solution.

Consider v\mathbf{v} and w\mathbf{w} to be the solutions of LS1 and LS2, respectively. By linearity we get that

u=xv−syw.(11)\mathbf{u}=x\mathbf{v}-sy\mathbf{w}. \tag*{(11)}

We now obtain the explicit solutions of LS1 and LS2. Observe that both systems share the following linear homogeneous recurrence relation

5zi−2zi−1−2zi+1=0,2≤i<m.5z_i-2z_{i-1}-2z_{i+1}=0,\qquad2\le i<m.

where we use ziz_i to denote either viv_i or wiw_i. We solve this recurrence relation using the roots of its characteristic polynomial. Assume that zi=riz_i=r^i for ri≠0r^i\ne0. Substituting ziz_i with rir^i in the recurrence relations and dividing by ri−1r^{i-1} we get the characteristic quadratic polynomial

2r2−5r+2=0.2r^2-5r+2=0.

Solving this polynomial we get the characteristic roots r=1/2r = 1/2 and r=2r = 2. Finally a solution to the homogeneous recurrence relation is given by the formula

zi=a2i+b2−i,a,b∈Q,i∈[m].(12)z_i = a2^i + b2^{-i}, \qquad a,b \in\mathbb{Q}, \qquad i \in[m]. \tag*{(12)}

We proceed to determine the parameters aa and bb using the boundary conditions in LS1 and LS2. Consider LS1 whose boundary conditions are 4v1−2v2=14v_1 - 2v_2 = 1 and 4vm−2vm−1=04v_m - 2v_{m-1} = 0 and let ui=a12i+b12−iu_i = a_1 2^i + b_1 2^{-i} for i∈[m]i \in[m] be a solution. Setting ziz_i as viv_i and substituting (12) in the first boundary condition we get b1=2/3b_1 = 2/3. Similarly substituting (12) in the second boundary condition we get a1=0a_1 = 0 and thus

vi=21−i3,i∈[m].(13)v_i = \frac{2^{1-i}}{3}, \qquad i \in[m]. \tag*{(13)}

Next, consider LS2, whose boundary conditions are 4w1−2w2=04w_1 - 2w_2 = 0 and 4wm−2wm−1=14w_m - 2w_{m-1} = 1 and let wi=a22i+b22−iw_i = a_2 2^i + b_2 2^{-i} for i∈[m]i \in[m] be a solution. Setting ziz_i as wiw_i and substituting (12) in the first boundary condition we get b2=0b_2 = 0. Similarly substituting (12) in the second boundary condition we get a2=1/(32m)a_2 = 1/(32^m) and therefore

wi=2i−m3,i∈[m].(14)w_i = \frac{2^{i-m}}{3}, \qquad i \in[m]. \tag*{(14)}

Substituting (13) and (14) in (11) we get that the unique solution of LS is

ui=13(21−ix−s2i−my),i∈[m].(15)u_i = \frac{1}{3}\left(2^{1-i}x - s2^{i-m}y\right), \qquad i \in[m]. \tag*{(15)}

Finally since x,y∈[0,1]x,y \in[0,1], applying the triangle inequality for every i∈[m]i \in[m],

∣ui∣≤13(21−i+2i−m)≤23,|u_i| \le\frac{1}{3}\left(2^{1-i} + 2^{i-m}\right) \le\frac{2}{3},

which proves that u∗(x,y)∈(−1,1)m\mathbf{u}^*(x,y) \in(-1,1)^m.

Having established the interiority of the unique minimizer u∗(x,y)\mathbf{u}^*(x,y), we proceed to show that substituting u∗(x,y)\mathbf{u}^*(x,y) into the quadratic chain gadget G(x,y,u)G(x,y,\mathbf{u}) yields exactly the original dyadic monomial g(x,y)g(x,y).

Lemma 4.5. For every xx and yy in [0,1][0,1], it holds that G(x,y,u∗(x,y))=g(x,y)G(x,y,\mathbf{u}^*(x,y)) = g(x,y). Proof. We substitute the explicit form of u∗(x,y)\mathbf{u}^*(x,y) as given in (15), in the quadratic chain gadget expression (6). For 1≤i<m1 \le i < m it holds that

2ui∗−ui+1∗=13(22−ix−s2i−m+1y)−13(2−ix−s2i−m+1y)=2−ix.2u_i^* - u_{i+1}^* = \frac{1}{3}\left(2^{2-i}x - s2^{i-m+1}y\right) - \frac{1}{3}\left(2^{-i}x - s2^{i-m+1}y\right) = 2^{-i}x.

Therefore,

3∑i=1m−1(2ui∗−ui+1∗)2=3x2∑i=1m−14−i=x2(1−41−m).3\sum_{i=1}^{m-1}(2u_i^* - u_{i+1}^*)^2 = 3x^2\sum_{i=1}^{m-1}4^{-i} = x^2(1 - 4^{1-m}).

Adding the explicit expression um∗=13(21−mx−sy)u_m^* = \frac{1}{3}(2^{1-m}x - sy) and u1∗=13(x−s21−my)u_1^* = \frac{1}{3}(x - s2^{1-m}y) we get that

G(x,y,u∗)=x2(1−41−m)+(21−mx−sy)2−2x(x−s21−my)+2sy(21−mx−sy)+x2+y2,G(x,y,\mathbf{u}^*) = x^2(1 - 4^{1-m}) + (2^{1-m}x - sy)^2 - 2x(x - s2^{1-m}y) + 2sy(2^{1-m}x - sy) + x^2 + y^2,

since m=k+2m = k + 2 after calculations we get that G(x,y,u∗(x,y))=s2−kxyG(x,y,\mathbf{u}^*(x,y)) = s2^{-k}xy.

Computing a KKT point of P~\widetilde{P}

Recall that the dyadic decomposition of P~(x)\widetilde{P}(\mathbf{x}), given in (5), consists of RR monomials of the form gr(pr(x),qr(x))=sr2−krpr(x)qr(x)g_r(p_r(\mathbf{x}),q_r(\mathbf{x}))=s_r2^{-k_r}p_r(\mathbf{x})q_r(\mathbf{x}), with r∈[R]r\in[R] and 1≤kr≤L1\le k_r\le L. For each monomial grg_r consider a set of mr=kr+2m_r=k_r+2 disjoint auxiliary variables ur=(ur,1,…,ur,mr)∈[−1,1]mr\mathbf{u}_r=(u_{r,1},\ldots,u_{r,m_r})\in[-1,1]^{m_r} and construct the quadratic chain gadget Gr(pr(x),qr(x),ur)G_r(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r) as given in (6). Letting u=(u1,…,uR)\mathbf{u}=(\mathbf{u}_1,\ldots,\mathbf{u}_R) and U=∏r=1R[−1,1]mr\mathcal{U}=\prod_{r=1}^{R}[-1,1]^{m_r}, we add the quadratic chain gadgets and get the induced combined quadratic chain polynomial

G(x,u)=∑r=1RGr(pr(x),qr(x),ur),where(x,u)∈[0,1]n×U(16)\mathcal{G}(\mathbf{x},\mathbf{u})=\sum_{r=1}^{R}G_r(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r),\qquad\text{where}\quad(\mathbf{x},\mathbf{u})\in[0,1]^n\times\mathcal{U} \tag*{(16)}

Notice that because each quadratic chain gadget admits a disjoint set of auxiliary variables, then for fixed x\mathbf{x}, minimizing G(x,u)\mathcal{G}(\mathbf{x},\mathbf{u}) over u\mathbf{u} is equivalent to minimizing each GrG_r over ur\mathbf{u}_r. Since for fixed x∈[0,1]n\mathbf{x}\in[0,1]^n by the notation we defined earlier

min⁡ur∈[−1,1]mrGr(pr(x),qr(x),ur)=Gr(pr(x),qr(x),ur∗(pr(x),qr(x))),\min_{\mathbf{u}_r\in[-1,1]^{m_r}}G_r(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r)=G_r\left(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r^*(p_r(\mathbf{x}),q_r(\mathbf{x}))\right),

then combining the above expression with Lemma 4.5 we get that

∑r=1Rmin⁡ur∈[−1,1]mrGr(pr(x),qr(x),ur)=∑r=1Rgr(pr(x),qr(x)).(17)\sum_{r=1}^{R}\min_{\mathbf{u}_r\in[-1,1]^{m_r}}G_r(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r)=\sum_{r=1}^{R}g_r(p_r(\mathbf{x}),q_r(\mathbf{x})). \tag*{(17)}

For any x∈[0,1]n\mathbf{x}\in[0,1]^n, let u∗(x)=(u1∗(x),…,uR∗(x))\mathbf{u}^*(\mathbf{x})=(\mathbf{u}_1^*(\mathbf{x}),\ldots,\mathbf{u}_R^*(\mathbf{x})), where ur∗(x)\mathbf{u}_r^*(\mathbf{x}) denotes the unique auxiliary minimizer of the rr-th quadratic chain gadget. Then for a fixed vector x∈[0,1]n\mathbf{x}\in[0,1]^n,

G(x,u∗(x))=min⁡u∈UG(x,u)=∑r=1Rmin⁡ur∈[−1,1]mrGr(pr(x),qr(x),ur),\mathcal{G}(\mathbf{x},\mathbf{u}^*(\mathbf{x}))=\min_{\mathbf{u}\in\mathcal{U}}\mathcal{G}(\mathbf{x},\mathbf{u})=\sum_{r=1}^{R}\min_{\mathbf{u}_r\in[-1,1]^{m_r}}G_r(p_r(\mathbf{x}),q_r(\mathbf{x}),\mathbf{u}_r),

where from equations (17) and (5) we get that G(x,u∗(x))=P~(x)\mathcal{G}(\mathbf{x},\mathbf{u}^*(\mathbf{x}))=\widetilde{P}(\mathbf{x}). Finally we establish that every KKT point of G\mathcal{G} maps back to an exact KKT point of P~\widetilde{P}.

Proposition 4.6. If (x′,u′)(\mathbf{x}',\mathbf{u}') is a KKT point of G\mathcal{G} then x′\mathbf{x}' is a KKT point of P~\widetilde{P}.

Proof. Let (x′,u′)(\mathbf{x}',\mathbf{u}') be a KKT point of G\mathcal{G}. Since the auxiliary variables of the quadratic chain gadgets are disjoint, for every r∈[R]r\in[R], the vector ur′\mathbf{u}'_r satisfies the KKT conditions of Gr(pr(x′),qr(x′),ur)G_r(p_r(\mathbf{x}'),q_r(\mathbf{x}'),\mathbf{u}_r) with respect to ur\mathbf{u}_r. From Lemma 4.3, each quadratic chain gadget admits a unique KKT point with respect to its auxiliary variables which coincides with its unique interior minimizer. Consequently, ur′=ur∗(x′)\mathbf{u}'_r=\mathbf{u}_r^*(\mathbf{x}') for every r∈[R]r\in[R], and hence u′=u∗(x′)\mathbf{u}'=\mathbf{u}^*(\mathbf{x}'). From the previous discussion it holds that for every x∈[0,1]n\mathbf{x}\in[0,1]^n, P~(x)=G(x,u∗(x))\widetilde{P}(\mathbf{x})=\mathcal{G}(\mathbf{x},\mathbf{u}^*(\mathbf{x})). Differentiating with respect to xix_i, for i∈[n]i\in[n], we get that

∂P~∂xi(x′)=∂G∂xi(x′,u∗(x′))+∑r=1R∑j=1mr∂G∂ur,j(x′,u∗(x′))∂ur,j∗∂xi(x′).\frac{\partial\widetilde{P}}{\partial x_i}(\mathbf{x}')=\frac{\partial\mathcal{G}}{\partial x_i}(\mathbf{x}',\mathbf{u}^*(\mathbf{x}'))+\sum_{r=1}^{R}\sum_{j=1}^{m_r}\frac{\partial\mathcal{G}}{\partial u_{r,j}}(\mathbf{x}',\mathbf{u}^*(\mathbf{x}'))\frac{\partial u_{r,j}^*}{\partial x_i}(\mathbf{x}').

Because in Lemma 4.4, we showed that the auxiliary minimizers are interior therefore ∂G∂ur,j(x′,u∗(x′))=0\frac{\partial\mathcal{G}}{\partial u_{r,j}}(\mathbf{x}',\mathbf{u}^*(\mathbf{x}'))=0 for every r∈[R]r\in[R] and j∈[mr]j\in[m_r]. Hence for every i∈[n]i\in[n] it follows that

∂P~∂xi(x′)=∂G∂xi(x′,u′).(18)\frac{\partial\widetilde{P}}{\partial x_i}(\mathbf{x}')=\frac{\partial\mathcal{G}}{\partial x_i}(\mathbf{x}',\mathbf{u}'). \tag*{(18)}

Since (x′,u′)(\mathbf{x}',\mathbf{u}') is a KKT point of G\mathcal{G}, it follows from Equation (18) that x′\mathbf{x}' satisfies the KKT conditions of P~\widetilde{P} over [0,1]n[0,1]^n.

Transforming the auxiliary domain

To finalize the reduction we transform the domain of the auxiliary variables from [−1,1]m[-1,1]^m to [0,1]m[0,1]^m. Let M=∑r=1RmrM=\sum_{r=1}^{R}m_r denote the total number of auxiliary variables in G(x,u)\mathcal{G}(\mathbf{x},\mathbf{u}). For each auxiliary variable ur,j∈[−1,1]u_{r,j}\in[-1,1], we introduce a new variable vr,j∈[0,1]v_{r,j}\in[0,1] such that ur,j=2vr,j−1u_{r,j}=2v_{r,j}-1. Let v\mathbf{v} denote the vector of all new auxiliary variables and let H(x,v)=G(x,2v−1)\mathcal{H}(\mathbf{x},\mathbf{v})=\mathcal{G}(\mathbf{x},2\mathbf{v}-1) be the resulting quadratic polynomial defined over [0,1]n+M[0,1]^{n+M}. For every i∈[n]i\in[n] and every auxiliary coordinate (r,j)(r,j),

∂H∂xi(x,v)=∂G∂xi(x,2v−1)and∂H∂vr,j(x,v)=2∂G∂ur,j(x,2v−1).\frac{\partial\mathcal{H}}{\partial x_i}(\mathbf{x},\mathbf{v})=\frac{\partial\mathcal{G}}{\partial x_i}(\mathbf{x},2\mathbf{v}-1) \quad\text{and}\quad \frac{\partial\mathcal{H}}{\partial v_{r,j}}(\mathbf{x},\mathbf{v})=2\frac{\partial\mathcal{G}}{\partial u_{r,j}}(\mathbf{x},2\mathbf{v}-1).

Also the substitution maps the boundary points of the two intervals as follows: vr,j=0v_{r,j}=0 if and only if ur,j=−1u_{r,j}=-1 and vr,j=1v_{r,j}=1 if and only if ur,j=1u_{r,j}=1, while every interior point is mapped again to an interior point. Consequently, the KKT conditions for the original variables remain unchanged, while the KKT conditions for the auxiliary variables are preserved because their partial derivatives are multiplied by 2. Hence,

(x,v)∈KKT⁡(H)⟺(x,2v−1)∈KKT⁡(G).(19)(\mathbf{x},\mathbf{v})\in\operatorname{KKT}(\mathcal{H})\Longleftrightarrow(\mathbf{x},2\mathbf{v}-1)\in\operatorname{KKT}(\mathcal{G}). \tag*{(19)}

Proof of Theorem 4.1

Consider an arbitrary instance of Quadratic-KKT defined by a quadratic polynomial PP over [0,1]n[0,1]^n, and let NN denote its binary encoding length. By Lemma 4.2, the polynomial P~\widetilde{P} constructed in § 4.1 has exactly the same KKT points as PP and admits a dyadic decomposition consisting of R=O(n2L)R=O(n^2L) monomials.

We first show that L=O(N)L=O(N). Recall from § 4.1 that A=lcm⁡(b1,…,bt)A=\operatorname{lcm}(b_1,\ldots,b_t), where let’s assume that b1,…,btb_1,\ldots,b_t are the denominators of the coefficients of PP, and that MM is the maximum of 1 and the absolute values of the coefficients of P′=APP'=AP, while L=⌊log⁡2M⌋+1L=\lfloor\log_2 M\rfloor+1. Since A≤∏j=1tbjA\le\prod_{j=1}^{t}b_j, we have log⁡2A≤∑j=1tlog⁡2bj≤N\log_2 A\le\sum_{j=1}^{t}\log_2 b_j\le N. As the numerators of PP also have binary encoding lengths at most NN, every coefficient of P′=APP'=AP has absolute value at most 2O(N)2^{O(N)}. Consequently, log⁡2M=O(N)\log_2 M=O(N), and hence L=O(N)L=O(N).

Next, we construct the combined quadratic chain polynomial G\mathcal{G} as defined in Equation (16), that is summing over all quadratic chain gadgets (see Equation (6)) that correspond to the dyadic monomials of P~\widetilde{P}. Let MauxM_{\mathrm{aux}} denote the total number of auxiliary variables that emerge from the construction of G\mathcal{G}. By Proposition 4.6, every KKT point of G\mathcal{G} projects onto a KKT point of P~\widetilde{P}, and hence, by Lemma 4.2, to a KKT of PP. Applying the affine transformation of § 4.4, we obtain the quadratic polynomial H(x,v)=G(x,2v−1)\mathcal{H}(\mathbf{x},\mathbf{v})=\mathcal{G}(\mathbf{x},2\mathbf{v}-1) over the domain [0,1]n+Maux[0,1]^{n+M_{\mathrm{aux}}}. By Equation (19), every KKT point of H\mathcal{H} corresponds to a KKT point of G\mathcal{G}, and therefore yields a KKT point of PP.

It remains to bound the encoding length of the constructed instance H\mathcal{H}. Since each gadget introduces mr=kr+2≤L+2m_r=k_r+2\le L+2 auxiliary variables, their total number satisfies

Maux=∑r=1Rmr≤R(L+2)=O(n2L2).M_{\mathrm{aux}}=\sum_{r=1}^{R}m_r\le R(L+2)=O(n^2L^2).

Moreover, each gadget contains O(mr)O(m_r) terms with constant-bounded integer coefficients (see Equation (6)), which also holds after the affine transformation. Thus, every coefficient of the resulting polynomial H\mathcal{H} is an integer of absolute value at most

O(∑r=1Rmr)=O(n2L2).O\left(\sum_{r=1}^{R}m_r\right)=O(n^2L^2).

Since we established that L=O(N)L = O(N), both the number of variables and the unary encoding lengths of the coefficients of H\mathcal{H} are polynomially bounded in NN, i.e, the encoding length of PP. Since H\mathcal{H} is quadratic and has polynomially many variables, then it contains at most quadratically many monomials in the number of variables. Furthermore, its construction can be performed in polynomial time, which concludes our proof.

Discussion

One obvious and important question that remains open is whether Quadratic-KKT remains hard, either for CLS, or for a different complexity class/under a different assumption, when the coefficients are constant. Such a result would not contradict anything of our current understanding of CLS, or TFNP in general. As a side note, let us highlight two things. Firstly, quadratic optimization is NP-hard even when all coefficients are constants (think of Max-Cut in unweighted graphs). Second, there exist several problems that are PPAD-hard even when all coefficients are small constants [7] or even binary [15, 8, 3].

One approach to attack the above mentioned problem would be to use our technique when the starting point is a quadratic polynomial with polynomially-bounded coefficients and hope that after a number of iterations we can end up with a polynomial with constant coefficients. Unfortunately, this cannot work under the current construction of the chain gadget. The reason is that after the dyadic decomposition, for every occurrence of a variable xx it creates one copy of x2x^2 in every chain. One way to bypass this obstacle could be by proving that Quadratic-KKT remains hard even on “sparse” instances, i.e., instances where each variable appears only a constant number of times. Another direction could be to create a different chain gadget that does not preserve a one-to-one correspondence of stationary points, but works only the approximate sense.

Acknowledgements

We sincerely thank Ioannis Panageas for the insightful discussions on CLS and for his substantial contribution to the development of the final form of the paper. Argyrios Deligkas and Stavros D. Ioannidis were supported by the EPSRC grant EP/X039862/1. We used various versions of GPT Pro to explore proof strategies during the development of this work.

References

  1. [1]Amar Andjouh and Mohand Ouamer Bibi. Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems. Journal of Optimization Theory and Applications, 192(1):360–378, 2022.
  2. [2]Ioannis Anagnostides, Ioannis Panageas, and Jingming Yan. The complexity of Nash equilibrium in network congestion and coordination games. arXiv preprint arXiv:2609.33225, 2026.arxiv.org/abs/2609.33225
  3. [3]Eleni Batziou, John Fearnley, Abheek Ghosh, and Rahul Savani. The complexity of sparse win-lose bimatrix games. arXiv preprint arXiv:2602.18380, 2026.arxiv.org/abs/2602.18380
  4. [4]Samuel Burer and Adam N Letchford. On nonconvex quadratic programming with box constraints. SIAM Journal on Optimization, 20(2):1073–1089, 2009.DOI
  5. [5]Yakov Babichenko and Aviad Rubinstein. Settling the complexity of Nash equilibrium in congestion games. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pages 1426–1437, 2021.arxiv.org/abs/2012.04327
  6. [6]Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  7. [7]Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. Pure-circuit: Tight inapproximability for PPAD. Journal of the ACM, 71(5):1–48, 2024.DOI
  8. [8]Jérémi Do Dinh and Alexandros Hollender. Tight inapproximability of Nash equilibria in public goods games. Inf. Process. Lett., 186:106486, 2024.DOI
  9. [9]Constantinos Daskalakis and Christos Papadimitriou. Continuous local search. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 790–804. SIAM, 2011.
  10. [10]Edith Elkind, Abheek Ghosh, and Paul W. Goldberg. Simultaneous contests with equal sharing allocation of prizes: Computational complexity and price of anarchy. In International Symposium on Algorithmic Game Theory, pages 133–150. Springer, 2022.
  11. [11]John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of computing KKT solutions of quadratic programs. J. ACM, 72(5):31:1–31:48, 2025.
  12. [12]Vladimir V. Gusev, Duncan Adamson, Argyrios Deligkas, Dmytro Antypov, Christopher M. Collins, Piotr Krysta, Igor Potapov, George R. Darling, Matthew S. Dyer, Paul G. Spirakis, and Matthew J. Rosseinsky. Optimality guarantees for crystal structure prediction. Nat., 619(7968):68–72, 2023.DOI
  13. [13]David S Johnson, Christos H Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of computer and system sciences, 37(1):79–100, 1988.DOI
  14. [14]Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498–532, 1994.
  15. [15]Christos Papadimitriou and Binghui Peng. Public goods games in directed networks. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 745–762, 2021.arxiv.org/abs/2106.00718
  16. [16]C. H. Papadimitriou, A. A. Schäffer, and M. Yannakakis. On the complexity of local search. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC ’90, page 438–445, New York, NY, USA, 1990. Association for Computing Machinery.
  17. [17]Sartaj Sahni. Some related problems from network flows, game theory and integer programming. In 13th Annual Symposium on Switching and Automata Theory (SWAT 1972), pages 130–138. IEEE, 1972.
  18. [18]Sartaj Sahni. Computationally related problems. SIAM Journal on computing, 3(4):262–279, 1974.DOI
  19. [19]Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56–87, 1991.DOI
  20. [20]Emanuel Tewolde, Caspar Oesterheld, Vincent Conitzer, and Paul W Goldberg. The computational complexity of single-player imperfect-recall games. arXiv preprint arXiv:2305.17805, 2023.arxiv.org/abs/2305.17805

Paper details

vlnc:W_6anze6zn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents