{"id":"11820df5-7570-4af1-a427-55e508071f9c","arxiv_id":"2502.08210","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Using resultants to build a defining polynomial and Thom's lemma to isolate the correct root, a single new variable per algebraic expression replaces several radical variables in polynomial reformulations.","lead":"This paper introduces a method to rewrite optimization problems with algebraic functions (built from radicals) into polynomial optimization problems while using fewer auxiliary variables than the standard approach. On two benchmark examples modified with radicals, the new formulation speeds up sum-of-squares solving by up to 50x.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The density condition (Aall ∩ D dense in D) is the load-bearing limitation: for equality-constrained or lower-dimensional D it can fail, and the reformulation then excludes the true optimum (e.g., min √x s.t. x=0 becomes infeasible).","rationale":"The reader's weakest_assumption identifies precisely the condition that must hold for the reformulation to preserve the optimum: Aall ∩ D must be dense in D. This is the most load-bearing concern because the central claim is that the polynomial reformulation is equivalent to the original algebraic program; if the density condition fails, the reformulation can be infeasible even when the original has a well-defined optimum. The paper states the condition but does not provide an automatic check, and the sufficient condition it offers (D contained in the closure of its interior) is restrictive. The worked examples all satisfy this condition, so they do not test the boundary of the claim. The concern is concrete and demonstrated by the simple equality-constrained example. Other potential weaknesses—such as the incorrect equality in Lemma 2 (the degree bound is still valid as an upper bound), the reliance on external results in Theorem 3, and the computational cost of enumerating connected components—are real but less central: they affect complexity and presentation rather than the correctness of the reduction under the stated hypothesis. Because the paper explicitly limits its applicability to settings where the density condition holds, the reader's CONDITIONAL verdict remains appropriate; my read does not change that verdict.","tokens_in":15123,"tokens_out":29821,"duration_ms":284524,"concrete_test":"Run the proposed reformulation on the algebraic program: minimize √x subject to x = 0, with defining polynomial z^2 − x = 0 and isolating inequality z > 0. If the polynomial program is infeasible while the original has optimal value 0 at x=0, the density condition's failure is confirmed. For a control, run the same reformulation on min (x−1)^2 + √x subject to x ≥ 0, where Aall ∩ D is dense in D; the optimal values should match, showing the method works exactly when the condition holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 justifies the reformulation only when Aall ∩ D is dense in D. The paper's sufficient condition—D contained in the closure of its interior—excludes equality constraints and other lower-dimensional feasible sets, and no automatic check of the underlying density condition is provided. This is not a minor technicality: for min √x subject to x=0, the reformulation adds z^2 − x = 0, z > 0, and x = 0; the only candidate z=0 violates z > 0, so the polynomial program is infeasible while the original has optimum 0 at x=0. Thus, for feasible sets not contained in the closure of their interiors, the method can fail to represent the true optimum. The paper acknowledges this limitation in the Discussion, but it directly restricts the central claim that algebraic programs can be reduced to polynomial programs. Other issues (the erroneous equality in Lemma 2's degree statement, the potential combinatorial blow-up of connected components) are secondary because they affect complexity bounds rather than the correctness of the reduction on the domain where the density condition holds.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for converting algebraic programs (optimization/feasibility problems whose objectives and constraints are radical expressions) into polynomial programs. For each radical expression it introduces a single new variable z, computes a defining polynomial via iterated resultants (Algorithm 1), and derives polynomial inequalities that isolate the intended branch of the algebraic function using Thom's lemma and a sign-of-derivatives encoding (Algorithm 2). Section 4 then reformulates the original program by adding these polynomial equalities and inequalities, and claims equivalence when a density condition holds. The method is demonstrated on modified Goldstein-Price and Rosenbrock problems, where the new formulation uses substantially fewer variables in the sum-of-squares relaxation and reports speedups of up to about 50x.","tokens_in":15340,"tokens_out":10520,"duration_ms":121269,"significance":"If the reduction is valid on its intended domain, this is a useful contribution: it connects algebraic programs to the mature toolkit for polynomial programs (CAD, Positivstellensatz certificates, sum-of-squares relaxations) and it can reduce the number of auxiliary variables compared with the standard one-variable-per-radical reformulation. The algorithms are concrete and the benchmark examples are checkable by hand; the reported speedups, while on toy instances, are plausible and clearly reported. The paper is also honest about several limitations, including the density condition and the possible combinatorial explosion of connected components. No code or data artifacts are included, so the experimental section is the main evidence for the performance claims.","major_comments":[{"comment":"The central equivalence claim is conditional on the density of Aall ∩ D in D, but this condition is not checked and it can fail for very simple algebraic programs. For example, min √x subject to x = 0 has feasible set D = {0} and optimum 0, but the proposed reformulation introduces z^2 - x = 0, z > 0, x = 0, which is infeasible because z = 0 violates z > 0. Thus the reformulation does not merely lose a certificate of optimality; it can turn a feasible program into an infeasible one. The paper acknowledges this in the Discussion, but the abstract and the opening of Section 4 state the reduction without this qualification. I ask the authors to restate the main theorem with the density hypothesis explicitly, to state that the method is intended for feasible sets contained in the closure of their interiors (or, more generally, for cases where the density condition is verified), and to provide an automatic or algorithmic check of the density condition rather than only saying that CAD can in principle decide it.","section":"Section 4, first paragraph"},{"comment":"The claimed equality dRes,x' = dp,x' dq,x + dp,x dq,x' is false in general; the correct statement is an upper bound, since cancellations in the determinant of the Sylvester matrix can lower the degree. For instance, with p = (y+1)x + 1 and q = (y+1)x + 2, one has Res_x(p,q) = y+1, whose degree in y is 1, while the formula gives 1·1 + 1·1 = 2. The proof's 'there exists a permutation' argument shows only that a term of that degree can occur, not that cancellations cannot occur. This does not invalidate Theorem 2, whose statement already uses 'at most', but the lemma and its proof should be corrected to an inequality, and Theorem 2's proof should be adjusted accordingly.","section":"Lemma 2"},{"comment":"Theorem 3 is the theoretical basis for the isolating inequalities, but its proof delegates the key existence and continuity of the roots r1,...,rk to Lemma 3.6 of [Strzeboński, 2000] without stating that lemma or verifying its hypotheses in detail. Given that Algorithm 2's correctness depends on the assertion that the derivative sign pattern identifies a single continuous root on each connected component of A, the authors should either state and prove the needed lemma in the paper or give a fully self-contained argument, including a precise statement of how the real-valuedness of the radical expression is used.","section":"Theorem 3 and Algorithm 2"}],"minor_comments":[{"comment":"The component descriptions contain the algebraic number √5 (e.g., y > (7 + 3√5)x/2). Since the goal is a polynomial program over the reals, these constants should be encoded with an auxiliary variable and polynomial equations (e.g., w^2 = 5, w > 0) or the paper should state that algebraic constants are allowed.","section":"Example 6"},{"comment":"The sentence 'the second constraint can be eliminated as we cancel the z from the first constraint' is misleading at z = 0, where division by z is not valid. The subsequent inequality z^2 + 2 - x - y ≥ 0 is valid, but the derivation should be explained without dividing by z or with an explicit case discussion.","section":"Section 4.2"},{"comment":"It would be helpful to specify whether the reported total times include the preprocessing overhead (0.135 s and 0.52 s stated in the text) or only the solver time, so that the speedup comparison is unambiguous.","section":"Tables 1 and 2"},{"comment":"There are several typos and notational slips: 'Sylvster' in Definition 1, 'straightforwrad' in Section 4.3, 'This are the cases' in Section 4, and inconsistent use of x1/2 versus √x. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The bound on the number of connected components is quoted from [Basu et al., 1996] without specifying which parameter corresponds to the number of polynomials or the degree bound e; please make the application of that result explicit so the reader can verify the (d choose n)(O(e))^n expression.","section":"Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the underlying idea is sound for the restricted class of problems where the density condition holds. My main concern is that the title and abstract promise a general reduction of algebraic programs to polynomial programs, while the method can provably fail on equality-constrained instances; this is fixable by a carefully qualified theorem and an explicit verification procedure. The incorrect degree equality in Lemma 2 is also fixable without changing the main algorithmic conclusions. I do not see grounds for rejection, but the revision should address these load-bearing points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution to the optimization reformulation toolbox, and the limitation that matters most is the one the authors themselves flag—the density condition on the feasible set. The central idea—one new variable per algebraic function rather than per radical, with branch isolation by derivative sign conditions—is new relative to the cited work, and the worked examples show the payoff. The benchmarks are tiny and the code is not shipped, so the speedup claims should be read as illustrative, not definitive.\n\nWhat is genuinely good: Algorithm 1 (recursive resultant construction of a defining polynomial) is a clean application of Zippel's framework, and the presentation is careful about square-free parts and non-minimality. Algorithm 2's use of Thom encodings for functions—derivative sign conditions over connected components of the set A—is the real novelty, and Example 6 shows it is non-obvious. The degree bounds in Theorem 2 are useful, though Lemma 2's degree equality is suspicious; the proof argues via 'there exists a permutation' that achieves the bound, which only gives an upper bound in general. That is a minor flaw in the write-up, not in the method, since Theorem 2 states 'at most'—but Lemma 2 as stated overclaims.\n\nThe soft spot that matters: the reformulation is only equivalent if Aall ∩ D is dense in D. The paper states this and gives sufficient conditions (D contained in closure of its interior), but that excludes equality constraints and lower-dimensional feasible sets. The stress-test example is exactly right: min sqrt(x) s.t. x=0 becomes infeasible after the reformulation because the isolating inequality z>0 kills the only candidate. So the 'reduction of algebraic programs to polynomial programs' is not general; it is a reduction for programs with full-dimensional feasible sets or where density can be verified. That is a genuine limitation, and it should be front and center in the intro, not just the Discussion. The paper does mention it, which is to its credit.\n\nAlso: no code or data supplied, and the two benchmarks are small. The claim that the relaxation is 'not weaker' from the lower bounds is okay for those runs but not a general statement.\n\nVerdict: worth a serious referee. The idea is sound, the presentation is mostly honest, and the limitations are stated rather than hidden. A referee should push on Lemma 2, on the density condition (ask for an automatic check or a sharper sufficient condition), and on reproducibility. I would not cite it yet for the speedup numbers, but I would cite it for the single-variable-per-function reformulation and the Thom-encoding isolation idea.","headline":"A useful, honest paper with a real algorithmic idea and a clearly stated but load-bearing density condition; worth refereeing carefully, not desk-rejecting.","tokens_in":15815,"tokens_out":1650,"would_cite":true,"duration_ms":16169,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C22","14P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimization problems with radical expressions can be rewritten as polynomial programs using one new variable per algebraic function plus isolating inequalities, and the tested benchmarks solve up to 50x faster.","keywords":["algebraic programs","polynomial programs","radical expressions","defining polynomial","resultant","Thom encoding","sum-of-squares relaxation","cylindrical algebraic decomposition"],"falsifier":"Take a one-dimensional algebraic program with feasible set D = {0}, such as minimizing x subject to x = 0 and \\sqrt{x} \\geq 0, and apply the two algorithms literally: the resultant defining A is nonzero only for x \\neq 0, so Algorithm 2 returns no isolating component at x = 0, and the reformulated polynomial program becomes infeasible even though the original has the feasible point x = 0. Checking whether the reformulation's optimal value equals the original value on such a lower-dimensional feasible set would directly test the claimed equivalence.","tokens_in":14951,"feed_emoji":"🧮","tokens_out":10738,"duration_ms":98090,"temperature":0.7,"pith_summary":"The paper aims to make algebraic programs—optimization or feasibility problems whose objective and constraints are algebraic functions built from radicals—tractable with the machinery of polynomial optimization. Its central proposal is a reformulation that introduces one new variable for each algebraic function appearing in the program, rather than one new variable for each distinct radical. The transformation has two algorithmic steps: construct a defining polynomial for the radical expression, then generate polynomial inequalities that single out the intended branch of that polynomial using derivative signs. The paper proves the construction correct and reports that, on two benchmark problems with added algebraic terms, the reformulation yields values equivalent to the standard one-variable-per-radical approach while solving up to 50 times faster. The catch is a density condition: the reformulation is equivalent only when the feasible set is contained in the closure of its interior, so the method is not directly applicable to equality-constrained or lower-dimensional feasible sets.","feed_headline":"Rewriting algebraic programs as polynomials cuts solve time up to 50x","feed_subtitle":"One variable plus polynomial inequalities per algebraic function shrinks relaxations and preserves lower bounds.","key_machinery":"The argument is carried by a two-stage symbolic construction. First, a defining polynomial p(z,x) for a radical expression is built recursively by resultants: each arithmetic operation or integer radical on subexpressions is translated into a resultant of the corresponding defining polynomials, eliminating the auxiliary variables of the subexpressions. Second, the intended root is isolated by a Thom encoding: on each connected component of the set where p and its derivatives share no root, the signs of the derivatives of p at the algebraic function are constant, and those signs, together with p = 0, form polynomial inequalities that select exactly that branch. The reformulation replaces each radical expression by one new variable z plus these constraints, and the paper proves the equivalence of the original and reformulated programs under the condition that the feasible set is contained in the closure of its interior.","core_discovery":"On its own terms, the paper's discovery is that any algebraic program written with radical expressions can be rewritten as a polynomial program with exactly one auxiliary variable per algebraic function, provided the feasible set is dense in its interior. The key is to replace each radical expression f(x) by a variable z together with a defining polynomial p(z,x) = 0 and a collection of polynomial inequalities that isolate the branch corresponding to f. The defining polynomial is assembled recursively from resultants of the defining polynomials of the expression's subterms, and the isolating inequalities come from sign conditions on the derivatives of p, which are constant on each connected component of the set where the relevant resultants do not vanish. Over such components, the sign pattern of the derivatives uniquely characterizes the root, so the polynomial constraints together describe exactly the graph of f. The paper shows on a modified Goldstein-Price and a modified Rosenbrock problem that this reformulation produces semidefinite relaxations with far fewer variables and, in the reported experiments, up to roughly 50 times faster total solution times than the standard reformulation, without weakening the lower bounds.","pith_inferences":["For algebraic programs whose feasible set is full-dimensional but has equality constraints, the density condition could be restored by a preliminary dimension-reduction step or by solving a perturbed problem and taking limits; the paper does not explore this.","The derivative-sign isolation method could double as a symbolic real-valuedness test: if no connected component of A yields a real value for the radical expression over a given domain, the expression is non-real there.","A natural stress test would be to feed the two algorithms a nested radical expression with several variables, such as \\sqrt{x^2 + \\sqrt{y^2+1}}, and measure the degree of the defining polynomial and the number of isolating components; the paper's examples give no data on how these scale with expression depth.","In multi-constraint programs where the same algebraic function recurs, the single-variable reformulation may also reduce the number of blocks in the semidefinite program, a separate effect from the reduction in scalar variables that the reported timings do not isolate."],"forward_implications":["Polynomial-programming tools—cylindrical algebraic decomposition, Positivstellensatz infeasibility certificates, and sum-of-squares relaxations—become available for algebraic programs, with the number of auxiliary variables governed by the number of algebraic functions rather than the number of radicals.","On the modified Goldstein-Price benchmark the new reformulation uses 6-8 times fewer semidefinite variables and runs up to about 40 times faster in total time, and on the modified Rosenbrock benchmark the speedup reaches about 50 times.","The reformulation returns the same lower bounds as the straightforward one-variable-per-radical version at matching sum-of-squares degrees, indicating the relaxation is not weakened.","The isolating-inequality construction gives an algorithmic way to generate branch cuts for algebraic functions, since each branch is described by polynomial equalities and inequalities.","The equivalence is conditional on the feasible set being contained in the closure of its interior; for equality-constrained or lower-dimensional feasible sets the paper states the reformulation may exclude the true optimum."],"supporting_citations":[{"why":"Supplies the resultant identities that build a defining polynomial for sums, products, quotients, and radicals of algebraic functions, the core of Algorithm 1.","marker":"[Zippel, 1993, Section 9.4]"},{"why":"Provides the Sylvester matrix and resultant definitions, Thom's Lemma, and the cylindrical algebraic decomposition background used by Algorithm 2.","marker":"[Basu et al., 2006]"},{"why":"Its Lemma 3.6 is used in Theorem 3 to show the roots of the defining polynomial vary continuously on each connected component of A.","marker":"[Strzeboński, 2000]"},{"why":"Introduces Thom encodings for real algebraic numbers, which Algorithm 2 extends to algebraic functions by using derivative signs as isolating inequalities.","marker":"[Coste and Roy, 1988]"},{"why":"Introduces cylindrical algebraic decomposition, the algorithm the paper cites for computing the connected components of A in Algorithm 2.","marker":"[Collins, 1974]"},{"why":"Establishes sum-of-squares relaxations to semidefinite programs, the polynomial-optimization method used in the numerical comparisons.","marker":"[Parrilo, 2003]"},{"why":"Supplies the Goldstein-Price and Rosenbrock test functions that the paper modifies with added algebraic terms for the benchmarks.","marker":"[Surjanovic and Bingham, 2013]"},{"why":"Gives the cell-count bound that Theorem 4 uses to limit the number of connected components over which an algebraic function can exist.","marker":"[Basu et al., 1996]"}],"fun_headline_variants":["One variable per algebraic function cuts solve time up to 50x","Algebraic programs to polynomials: one variable each, 50x speedup","Single-var trick turns algebraic programs into polynomial ones, 50x faster","Algebraic programs simplified: one variable per function, 50x speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole equivalence rests on the feasible set being contained in the closure of its interior, so that the points where the isolating polynomials are well-behaved are dense in the feasible set; equality-constrained or lower-dimensional feasible sets can break the reduction.","fun_headline_variants_meta":{"raw":{"variants":["One variable per algebraic function cuts solve time up to 50x","Algebraic programs to polynomials: one variable each, 50x speedup","Single-var trick turns algebraic programs into polynomial ones, 50x faster","Algebraic programs simplified: one variable per function, 50x speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001606,"raw_usage":{"total_tokens":6434,"prompt_tokens":1023,"completion_tokens":5411,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":639,"completion_tokens_details":{"reasoning_tokens":5330}},"tokens_in":639,"tokens_out":5411,"duration_ms":40187,"temperature":1.0,"reasoning_tokens":5330,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T06:00:17.997239+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a one-dimensional algebraic program with feasible set D = {0}, such as minimizing x subject to x = 0 and \\sqrt{x} \\geq 0, and apply the two algorithms literally: the resultant defining A is nonzero only for x \\neq 0, so Algorithm 2 returns no isolating component at x = 0, and the reformulated polynomial program becomes infeasible even though the original has the feasible point x = 0. Checking whether the reformulation's optimal value equals the original value on such a lower-dimensional feasible set would directly test the claimed equivalence.","supporting_citations":[{"cited_title":"Effective Polynomial Computation","cited_arxiv_id":null,"evidence_quote":"Supplies the resultant identities that build a defining polynomial for sums, products, quotients, and radicals of algebraic functions, the core of Algorithm 1."},{"cited_title":"Algorithms in Real Algebraic Geometry","cited_arxiv_id":null,"evidence_quote":"Provides the Sylvester matrix and resultant definitions, Thom's Lemma, and the cylindrical algebraic decomposition background used by Algorithm 2."},{"cited_title":"Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets","cited_arxiv_id":null,"evidence_quote":"Introduces Thom encodings for real algebraic numbers, which Algorithm 2 extends to algebraic functions by using derivative signs as isolating inequalities."},{"cited_title":"Quantifier elimination for real closed fields by cylindrical algebraic decomposition--preliminary report","cited_arxiv_id":null,"evidence_quote":"Introduces cylindrical algebraic decomposition, the algorithm the paper cites for computing the connected components of A in Algorithm 2."},{"cited_title":"Semidefinite programming relaxations for semialgebraic problems","cited_arxiv_id":null,"evidence_quote":"Establishes sum-of-squares relaxations to semidefinite programs, the polynomial-optimization method used in the numerical comparisons."},{"cited_title":"On the number of cells defined by a family of polynomials on a variety","cited_arxiv_id":null,"evidence_quote":"Gives the cell-count bound that Theorem 4 uses to limit the number of connected components over which an algebraic function can exist."}],"review_version":1}