{"id":"25b2e7e3-7a37-4b79-a5a2-43c311f6dfa8","arxiv_id":"2607.29386","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An algorithm finds epsilon-approximate solutions to mixed integer quadratic programs in polynomial time on a Turing machine when the number of integer variables and negative Hessian eigenvalues are fixed.","lead":"This paper gives a fast approximation algorithm for mixed integer quadratic programs, a class of optimization problems used in logistics, finance, and engineering. It works for non-convex objectives whenever the number of integer variables and the number of negative-curvature directions are fixed, completing a long-standing complexity classification.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 4 omits the branch where the second Lemma 18 application returns a flat direction; the repair is immediate, so the central claim is not endangered, but the proof needs a patch.","rationale":"I read the paper as a serious complexity-theoretic contribution whose central claim is the polynomial-time approximation algorithm for MIQP with fixed p and k_-. The proof is long but the architecture is coherent: rational Jacobi rotations give a rational near-diagonalization that preserves inertia; Theorem 5 provides simultaneous diagonalization and spherical form; Proposition 3 solves spherical-form MIQP via mesh partitioning; Propositions 4 and 5 give the theorem of the alternative that either produces an approximate solution or partitions the instance into subinstances with fewer integer variables; the recursion then terminates in polynomial time. The weakest point is Proposition 4, exactly as the Reader identifies: the proof omits the case where the second application of Lemma 18 returns a flat direction rather than a lattice point. This is a genuine omission, but it is immediately repairable by scaling the flat direction by 2, and the width bound follows from the same scaling argument already used in the first flat-direction case. I therefore do not see a reason to move the verdict: the paper should remain conditionally acceptable pending a proof patch. I also considered whether the heavy reliance on the author's prior results, especially Lemma 18, is problematic; since these results are published externally and are used as black boxes, this is not circularity. The main algorithm is parameter-free, and no numerical experiments are claimed, which is normal for this kind of paper. Overall, the central claim appears sound, with the noted proof gap being the only substantive issue.","tokens_in":37286,"tokens_out":28388,"duration_ms":304213,"concrete_test":"Explicitly patch Proposition 4 by inserting the missing case: if the second invocation of Lemma 18 returns flat direction u, set v=2u and verify (a) v^T b_i ∈ Z for i≤p and v^T b_i=0 for i>p; (b) width_v(B(0,n^{3/2})) ≤ 8p 2^{p(p-1)/4} n^{3/2}. The calculation in (b) is a one-line scaling check; if it passes, the proposition is correct as stated. An additional sanity check is to test Lemma 18 on a small skewed mixed-integer lattice with B(-3e_1/4,1/4) to confirm that the flat-direction case is genuinely reachable and that the bound holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Proposition 4, after the first application of Lemma 18 to B(3e_1/4,1/4) returns a lattice point y+, the proof applies Lemma 18 a second time to B(-3e_1/4,1/4) and then says: 'Symmetrically, we can assume that Lemma 18 finds a vector y-'. This is not justified: the second application may instead return a nonzero flat direction u. The three possible outcomes are: (i) first call returns a flat direction; (ii) first call returns y+ and second returns y-; (iii) first call returns y+ and second returns a flat direction u. Case (iii) is missing. The repair is immediate and was noted by the Reader: set v=2u. Since u^T(2b_i) ∈ Z for i≤p and u^T(2b_i)=0 for i>p, we have v^T b_i ∈ Z for i≤p and v^T b_i=0 for i>p. Moreover, because both B(0,1/4) and B(-3e_1/4,1/4) have radius 1/4, width_v(B(0,n^{3/2})) = 8n^{3/2} width_u(B(-3e_1/4,1/4)) ≤ 8p 2^{p(p-1)/4} n^{3/2}. Thus the missing branch is harmless to the statement of Proposition 4, but it is a real gap in the written proof. No more serious flaw emerged: the reliance on Lemma 18 is on a published result, the recursion depth and branching are polynomial for fixed p, and the diagonalization arguments are internally coherent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a polynomial-time Turing-machine approximation algorithm for mixed integer quadratic programming (MIQP) when the number p of integer variables and the number k_- of negative eigenvalues of the Hessian are fixed. The algorithm either detects infeasibility or returns an epsilon-approximate solution for any rational epsilon in (0,1], in time polynomial in the instance size, size(epsilon), and 1/epsilon. The main technical engine is a rational version of Jacobi rotations that nearly diagonalizes a symmetric matrix while exactly preserving inertia, leading to a simultaneous diagonalization/rounding procedure for ellipsoids and polytopes. This is combined with mesh partitioning and linear underestimators for spherical-form MIQP, plus a recursion driven by a flatness theorem for mixed integer lattices. The paper also argues that both restrictions are necessary unless P=NP, and that the result is new already in the purely continuous case in the Turing model.","tokens_in":37634,"tokens_out":7474,"duration_ms":78498,"significance":"If correct, this completes the complexity characterization for approximating MIQP in terms of p and k_-, subsuming earlier results for concave and fixed-rank cases, and giving the first Turing-machine polynomial-time approximation algorithm for continuous quadratic programming with fixed k_-. The rational Jacobi rotations and the inertia-preserving near-diagonalization theorems are potentially useful independent tools. The proofs are generally careful and quantitative, with explicit size bounds and running-time analyses; the reliance on the author's own prior lemmas is substantial but not circular. However, one proof branch is missing in Proposition 4, as detailed below; the gap is local and has an immediate repair, but it must be fixed before the proof is complete.","major_comments":[{"comment":"After the first application of Lemma 18 returns y+, the proof says 'Symmetrically, we can assume that Lemma 18 finds a vector y-' when Lemma 18 is applied to B(-3e_1/4,1/4). This ignores the branch where the second application returns a nonzero flat direction u instead of a lattice point. The repair is immediate: set v=2u. Then u^T(2b_i) ∈ Z for i≤p and u^T(2b_i)=0 for i>p imply v^T b_i ∈ Z for i≤p and v^T b_i=0 for i>p, and width_v(B(0,n^{3/2})) = 8n^{3/2} width_u(B(-3e_1/4,1/4)) ≤ 8p 2^{p(p-1)/4} n^{3/2}. Thus the proposition's conclusion remains true, but the proof as written is incomplete. Since Proposition 4 is used in Proposition 5 and then in Theorem 1, this is a load-bearing gap, though a readily fixable one.","section":"§4.4, Proposition 4"}],"minor_comments":[{"comment":"The running-time expression 'O(n^4(log(1/δ)+logn+log(max(1,∥A∥_F)))^2)' is easy to misread as O(n^4) times a squared parenthesis; clarify the exponent placement.","section":"Theorem 2, statement"},{"comment":"Reference [11] says '4rd edition'; should be '4th edition'.","section":"References"},{"comment":"The funding statement starts with 'F unding:' rather than 'Funding:'; fix the typo.","section":"Funding line"},{"comment":"The necessity of fixing p and k_- is argued in the introduction via reductions to previously known NP-hard problems. This is convincing, but since these are central to the 'complete characterization' claim, a formal statement of the reductions (or precise pointers to the exact theorems used) would strengthen the paper.","section":"§1, lower-bound discussion"}],"recommendation":"major_revision","confidential_remarks":"The self-citations are extensive, and several key auxiliary results (Lemma 18, Lemma 22, Lemma 23) come from the author's own prior papers. This is not circular, as the target theorem is proved here, but the heavy overlap means the report should verify that each borrowed lemma is indeed established in the cited sources. The missing branch in Proposition 4 is the only substantive proof gap I found; the repair is exactly as described in my major comment and should be easy for the author to incorporate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe headline: this is a real result, and the main theorem looks right to me. If the proof is correct, Del Pia completes the complexity characterization for approximating MIQP, and the new rational Jacobi rotation machinery is a genuine contribution, not a repackaging. The continuous case (p=0) being new on a Turing machine is significant.\n\nWhat's actually new: Theorem 1 gives a Turing-machine algorithm for epsilon-approximation with p and k_- fixed — this subsumes Vavasis's real-RAM work and Del Pia's earlier fixed-rank results. The rational simultaneous diagonalization (Theorem 4) and the rational Jacobi rotations are new technical tools, with careful size and running-time bounds. The eigenvalue-gap argument (Lemmas 9–13) is clean, and the rounding to zero without changing inertia is well executed. The reliance on Lenstra's rounding and flatness theorem is appropriate; those are external published results, not contrived for this paper.\n\nSoft spots: the proof of Proposition 4 has a genuine gap. After the first call to Lemma 18 returns a lattice point y+, the second call to the same lemma is said, 'symmetrically,' to return a lattice point y-. But that call could return a flat direction u. The missing branch is harmless: setting v=2u gives the required integer direction with the same width bound, and the paper's conclusion still holds. But as written, the case is omitted, and the proof needs a patch. This is minor — the repair is immediate and the central argument doesn't depend on it. Also, several load-bearing subroutines come from Del Pia's own earlier papers. That's a citation-pattern smell only if the results are questionable; these are published, and the target theorem is new, so I don't see a circularity problem. The paper has no experiments, which is fine for a complexity result.\n\nWho it's for: anyone working on algorithms for nonconvex QP or MIQP, and complexity theorists interested in rational orthogonal transformations. The paper deserves a serious referee. If I were the editor, I'd send it out with a request that the referee check the Prop 4 repair and the recursion depth carefully.\n\nRecommendation: engage with it — referee it, and expect a small revision, not a rejection.","headline":"Strong, publishable complexity paper with new rational Jacobi machinery and one easily patched gap in Proposition 4; worth refereeing.","tokens_in":38140,"tokens_out":1548,"would_cite":true,"duration_ms":18181,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","90C10","68Q25","65F15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that MIQP with fixed numbers of integer variables and negative Hessian eigenvalues admits polynomial-time epsilon-approximation on a Turing machine, and that both restrictions are necessary unless P=NP.","keywords":["mixed integer quadratic programming","approximation algorithm","rational Jacobi rotations","simultaneous diagonalization","inertia of Hessian","computational complexity","Turing machine","fixed parameter"],"falsifier":"Take a small instance with p=2 and one negative Hessian eigenvalue, run the recursive algorithm, and compare its returned feasible solution against a brute-force optimum; returning a solution whose objective gap exceeds epsilon(f_sup - f_inf) would refute Theorem 1. More directly, search for a rational lattice and a radius-1/4 ball with no lattice point such that every admissible dual direction has width larger than p 2^{p(p-1)/4}; such a ball would falsify the flatness lemma on which the recursion depends.","tokens_in":37131,"feed_emoji":"🧮","tokens_out":12468,"duration_ms":112159,"temperature":0.7,"pith_summary":"The paper establishes a sharp complexity boundary for approximating mixed integer quadratic programming (MIQP). Its main theorem gives an algorithm that, whenever the number p of integer variables and the number k_- of negative eigenvalues of the objective's Hessian are fixed, either detects infeasibility or returns an epsilon-approximate solution, running in polynomial time on a Turing machine. The same theorem shows that neither restriction can be removed without collapsing to NP-hardness, assuming P is not NP. The result matters because it converts a class of nonconvex, integer-constrained problems that previously had no provable Turing-machine approximation into one with a concrete worst-case guarantee; it is new even in the continuous case, where earlier polynomial-time approximations relied on a real-RAM model.","feed_headline":"Fix two counts and mixed-integer quadratic programs become polynomial","feed_subtitle":"Finds epsilon-approximate MIQP solutions in polynomial time when p and k- are fixed; both restrictions are necessary.","key_machinery":"The engine is the rational Jacobi rotation: an exactly orthogonal rational matrix, built via the Weierstrass parametrization c=(1-u^2)/(1+u^2), s=2u/(1+u^2), that approximately annihilates a chosen off-diagonal entry of a symmetric matrix. Iterating these rotations drives the off-diagonal Frobenius norm below any prescribed tolerance; a classical lower bound on the size of nonzero eigenvalues of integer symmetric matrices then guarantees that zeroing tiny entries cannot change inertia. Composing this with a standard ellipsoid rounding algorithm yields a simultaneous diagonalization that maps the feasible polytope to spherical form while making the objective separable up to an arbitrarily sma","core_discovery":"The central claim is Theorem 1: for any instance of MIQP whose objective is bounded below on the feasible region and any rational epsilon in (0,1], there is a Turing-machine algorithm that either proves infeasibility or finds an epsilon-approximate solution in time polynomial in the instance size, size(epsilon), and 1/epsilon, provided p and k_- are fixed. The paper also proves that, unless P=NP, fixing both p and k_- is necessary: allowing p to grow would decide integer feasibility in polynomial time, and allowing k_- to grow would solve 3SAT in polynomial time already with p=0. The algorithmic novelty is a rational simultaneous diagonalization: a rational nonsingular change of basis that m","pith_inferences":["Extension: the rational Jacobi rotations give a polynomial-time approximate spectral decomposition over the rationals, so they may transfer to other settings where exact diagonalization blocks Turing-machine algorithms, such as generalized eigenvalue problems or trust-region subproblems.","Extension: the inertia-preserving rounding recipe—drive the off-diagonal norm below an eigenvalue gap, then round small entries to zero—could be adapted to yield rational approximation guarantees for other structured nonconvex optimization problems.","Extension: a natural testable next step is an implementation study, since the paper is algorithmic and contains no computational experiments; measuring practical runtimes and approximation quality on small MIQP instances would reveal how the polynomial bounds behave in practice.","Manuscript note: the proof of Proposition 4 omits the branch in which the second application of the flatness lemma returns a flat direction instead of a lattice point; the text states the repair is immediate using the same width argument, but that case is not written out."],"forward_implications":["For fixed p and k_-, epsilon-approximate solutions to MIQP can be found in polynomial time on a Turing machine, including detection of infeasibility.","The result is new already for purely continuous quadratic programming (p=0); earlier polynomial-time approximations of that case required a real-RAM computation model.","Both fixed-parameter assumptions are necessary: dropping either one makes the approximation problem NP-hard, assuming P is not NP.","The dependence on 1/epsilon cannot be reduced to a purely logarithmic dependence without solving an NP-hard problem.","The recursion tree has depth at most p and polynomially many leaves for fixed p, so the algorithm terminates with the promised running time."],"fun_headline_variants":["MIQP approximation made polynomial by fixing p and k-","Rational Jacobi rotations tame mixed-integer quadratic programming","Fix two counts to approximate MIQP in polynomial time","New algorithm: polynomial-time epsilon-approx for MIQP"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The recursion relies on a flatness lemma for mixed-integer lattices that bounds the width of any radius-1/4 ball with no lattice point by p 2^{p(p-1)/4}, independent of the lattice basis; if that bound fails, the partition into subproblems with fewer integer variables—and with it the polynomial-time guarantee—collapses.","fun_headline_variants_meta":{"raw":{"variants":["MIQP approximation made polynomial by fixing p and k-","Rational Jacobi rotations tame mixed-integer quadratic programming","Fix two counts to approximate MIQP in polynomial time","New algorithm: polynomial-time epsilon-approx for MIQP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000169,"raw_usage":{"total_tokens":1102,"prompt_tokens":746,"completion_tokens":356,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":291}},"tokens_in":490,"tokens_out":356,"duration_ms":3664,"temperature":1.0,"reasoning_tokens":291,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T08:09:22.718094+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small instance with p=2 and one negative Hessian eigenvalue, run the recursive algorithm, and compare its returned feasible solution against a brute-force optimum; returning a solution whose objective gap exceeds epsilon(f_sup - f_inf) would refute Theorem 1. More directly, search for a rational lattice and a radius-1/4 ball with no lattice point such that every admissible dual direction has width larger than p 2^{p(p-1)/4}; such a ball would falsify the flatness lemma on which the recursion depends.","supporting_citations":[],"review_version":1}