{"id":"89728f1a-0856-4bee-9f2b-b235a2893406","arxiv_id":"2508.21327","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The thesis derives new approximation algorithms and conditional/unconditional lower bounds for CSPs, polynomial optimization over the sphere, and matrix p-to-q norms.","lead":"A computer science thesis proves new limits and algorithms for LP and SDP relaxation hierarchies across three optimization problems. Its headline results include a Sherali-Adams lifting theorem, SoS-level trade-offs for sphere polynomial optimization, and the first quasi-polynomial-time hardness for hypercontractive matrix norms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.1.1's completeness relies on nested ℓ2-embeddings for all subsets, a property Theorem 2.3.5 does not state; Lemma 2.5.3's 'rigidity' claim is not justified.","rationale":"The reader's weakest_assumption flags the local ℓ2-embeddability theorem (Theorem 2.3.5) as load-bearing, and that is where the real risk lies. However, the reader does not identify the specific failure mode: Theorem 2.3.5 guarantees an embedding for each subset separately, but the construction of consistent distributions for the Sherali–Adams hierarchy requires a coherent family of embeddings, with the embedding of T being the restriction of the embedding of S up to a unitary. The proof of Lemma 2.5.3 asserts this by an appeal to 'rigidity of ℓ2' that is not valid in general. Because this step is needed to make the partitioning schemes consistent (Claim 2.5.5), the completeness half of Theorem 2.1.1 is not fully proved in the text as written. This does not mean the theorem is false; the gap may be repairable, for instance by explicitly constructing embeddings through a common skeleton of paths, or by showing that the [CMM09] embedding is already coherent. But as a standalone submission, the proof is incomplete at a load-bearing point. The verdict remains CONDITIONAL, matching the reader's assessment, because the issue is a missing argument rather than a demonstrated contradiction, and the full version [BGG+17] may supply the needed details.","tokens_in":80219,"tokens_out":16452,"duration_ms":168336,"concrete_test":"Check whether the family of embeddings produced by the constructive proof of Theorem 2.4.10 is coherent: for a small random hypergraph that satisfies the conditions of Theorem 2.3.5, compute the embeddings for a set S and a subset T⊆S and test if a unitary φ exists with φ(W_T)⊆W_S. Alternatively, exhibit a simple Euclidean metric on S (e.g., a square) and a subset T with two embeddings into the unit sphere that are not related by any unitary extending to S; such an example would directly falsify the rigidity assertion in Lemma 2.5.3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proof of Theorem 2.1.1 hinges on Lemma 2.5.3, which converts local ℓ2-embeddability into a consistent partitioning scheme. Lemma 2.5.3 requires that for every T⊆S, the chosen isometric embeddings W_S, W_T of the metric ρ_μ satisfy φ(W_T)⊆W_S for some unitary φ. The proof asserts this “by the rigidity of ℓ2”. This is not a consequence of Theorem 2.3.5, which only gives, for each set S of size ≤t, existence of some embedding into the unit sphere. Finite Euclidean metrics are not rigid in the required sense: for example, take S to be a square and T its three vertices; T has two mirror-image embeddings, only one of which is a restriction of a given embedding of S, and the other is not related by a unitary that extends to S. The local structure here is a forest, and the metric ρ_μ inherits this flexibility. Claim 2.5.5 uses nestedness essentially to prove 𝒫_S|T=𝒫_T; without a coherent family of embeddings, the distributions constructed in Lemma 2.6.4 may be inconsistent, invalidating the Sherali–Adams solution at level Ω(log n/log log n). The dichotomy and its extended-formulation corollary therefore rely on an unproven geometric coherence condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The thesis studies convex optimization hierarchies for three problems. Chapter 2 proves that a (c,s) integrality gap for the basic LP relaxation of any MAX k-CSP(f) can be lifted to a (c-ε,s+ε) integrality gap for Ω(log N / log log N) levels of the Sherali-Adams hierarchy, and via [KMR17] yields super-polynomial lower bounds for LP extended formulations. The proof constructs a random blown-up instance from the basic LP gap and uses local ℓ2-embeddable metrics to build consistent partitioning schemes. Chapter 3 studies approximating the maximum absolute value of a homogeneous polynomial over the unit sphere, proving level-q SoS tradeoffs for arbitrary, non-negative-coefficient, and sparse polynomials, as well as lower bounds for non-negative coefficients. Chapter 4 studies p→q matrix norms, giving hardness results for hypercontractive norms under a quasi-polynomial derandomization assumption and approximation algorithms for p ≥ q ≥ 2 cases. The thesis is generally detailed and mostly self-contained, though a few load-bearing steps are compressed.","tokens_in":80637,"tokens_out":38860,"duration_ms":380077,"significance":"If the results hold as stated, the CSP lifting theorem is a strong and elegant dichotomy: it says that a basic LP gap already captures the worst-case approximation behavior of super-constant-level Sherali-Adams relaxations for every predicate, with consequences for extended formulation lower bounds. The polynomial optimization results provide explicit level-vs-approximation tradeoffs and, notably, algorithms that do not solve the SDP; the non-negative-coefficient lower bound gives a polynomial integrality gap. The matrix norm results contribute the first hardness evidence for hypercontractive norms under a standard derandomization assumption and near-tight algorithms in the p ≥ q regime. The proofs are mostly constructive and detailed, and the use of geometry (ℓ2 embeddings, convex body diameter estimation, Banach space factorization) is coherent and well motivated.","major_comments":[{"comment":"The proof of Lemma 2.5.3 asserts, in one sentence, that for T ⊆ S the chosen ℓ2 embeddings W_S and W_T are nested up to a unitary transformation 'by the rigidity of ℓ2'. This is the only step that turns the per-set embeddings guaranteed by Theorem 2.3.5 into a coherent family of embeddings, and the consistency of the entire partitioning scheme (and hence of the Sherali-Adams solution in Lemma 2.6.4) depends on it. The assertion is not immediate from Theorem 2.3.5, which only says that each small set has some isometric embedding. The statement is nevertheless true for finite subsets of a Hilbert space: the isometry between the two copies of T extends to an orthogonal map of the ambient space, so adding a short proof (or a precise reference) is sufficient. As written, the manuscript leaves a load-bearing step unjustified and should be revised to include that argument.","section":"§2.5, Lemma 2.5.3 and Claim 2.5.5"}],"minor_comments":[{"comment":"The objective in the level-t Sherali-Adams LP is printed as f(α·b_C); it should presumably be f(α+b_C), consistent with the surrounding text and Fig. 2.2.","section":"§2.2.2, Fig. 2.1"},{"comment":"The sentence 'for any S⊆T' appears to have the inclusion backwards; the subsequent use requires T⊆S. Please fix.","section":"§2.5, Lemma 2.5.3 proof"},{"comment":"The overview says that the strengthening of Ineq. (3.5) to Ineq. (3.6) is shown in [BGG+17], but a proof appears later in §3.4.1 as Lemma 3.4.2. Please add a cross-reference to the in-manuscript proof to avoid the impression that a central step is deferred to an external full version.","section":"§3.2.1, Ineq. (3.6)"},{"comment":"The consistency step uses D_{𝒞(U_i)}|𝒞(V_i) = D_{𝒞(V_i)} by Lemma 2.6.3. This requires noting that 𝒞(V_i) is indeed a subtree of 𝒞(U_i) when V_i ⊆ U_i; the monotonicity of the closure operator makes this true, but it should be stated explicitly.","section":"§2.6.4, Lemma 2.6.4"},{"comment":"There are several typographical and wording issues: 'for infinitely may N' in Theorem 2.6.7, 'we refer this difference as' in the introduction, and 'no random polynomial can approximate' in §3.6. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"This is a PhD thesis combining three substantial research threads, and it reads as an archival thesis rather than a focused journal article. The editor may wish to consider whether the venue normally accepts such multi-topic manuscripts. The technical content appears largely sound; the main requested change is local (a proof of the nested-embedding assertion in Lemma 2.5.3). The references to [BGG+17] are to the author's own full version and are mostly backed by proofs in the thesis, but the cross-referencing should be cleaned up."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a real thesis with three substantial threads. The headline claim is the Sherali-Adams lifting theorem: any basic LP integrality gap for a CSP becomes a super-constant-level Sherali-Adams gap and, via KMR17, an LP extended formulation lower bound. If correct, this is a major structural result, and it is genuinely new relative to KTW14 and CMM09. The polynomial optimization chapter also delivers real value: explicit trade-offs between approximation ratio and n^{O(q)} running time, algorithmically constructible, with guarantees stated against the level-q SoS optimum. The matrix norm chapter gives the first hardness for hypercontractive p-to-q norms under quasi-polynomial derandomization, plus almost tight algorithms for p >= q with 2 in [q,p]. The writing is straightforward, the proofs are detailed, and the paper does not hide fitted constants behind the central statements. Credit is earned there.\n\nThe soft spots are not evenly distributed. The matrix norm hardness depends on NP not being in BPTIME(2^{(log n)^{O(1)}}), which is stated properly but weakens the headline. Several load-bearing proofs, including the strengthening of Ineq. (3.5) to (3.6) and parts of the folded decoupling, are deferred to the companion full version. That is acceptable in a thesis but makes independent verification harder.\n\nThe real problem is in Chapter 2. Lemma 2.5.3 claims that local l2 embeddability yields a consistent partitioning scheme by asserting nested embeddings via \"the rigidity of l2.\" That assertion is not justified. The local embedding theorem gives, for each set S, existence of some embedding into the sphere; it says nothing about choosing embeddings coherently so that W_T embeds into W_S for every T subset S. Finite Euclidean metrics are not rigid in that sense, as the square/three-vertices example shows. The consistency of the partitions and hence the distributions D_S depends on this nesting, so Theorem 2.1.1 is currently resting on an unproven geometric coherence condition. This is not a minor gap; it is the load-bearing step of the CSP chapter.\n\nWho gets value? Anyone working on LP/SDP hierarchies, CSP approximability, or extended formulations should read this, especially to see the attack surface. The polynomial and matrix norm chapters are solid and worth citing on their own. The CSP result, as written, is not independently verified enough to build on without checking the coherence question.\n\nRecommendation: send it to peer review. A serious referee should focus on Lemma 2.5.3 and the nested embedding construction. The paper may be fixable, but only if that step can be proven or replaced.","headline":"Real results, but the CSP lifting theorem has an unproven geometric coherence step; the polynomial and matrix norm chapters stand on much firmer ground.","tokens_in":81085,"tokens_out":1925,"would_cite":true,"duration_ms":24083,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every constraint satisfaction problem, a basic LP relaxation is as powerful, for approximation, as super-constant levels of the Sherali-Adams hierarchy.","keywords":["Sherali-Adams hierarchy","integrality gaps","constraint satisfaction problems","sum-of-squares hierarchy","polynomial optimization","matrix norms","hypercontractive norms","LP extended formulations"],"falsifier":"For the CSP thread: exhibit a predicate f and a (c,s) basic-LP gap instance such that the Omega(log N/log log N)-level Sherali-Adams relaxation of the constructed random instance has value below c-epsilon; this would refute Theorem 2.1.1 directly. For the matrix thread: give a randomized polynomial-time algorithm approximating any hypercontractive ||A||_{p->q} (1<p<q<infinity, 2 not in [p,q]) within 2^{(log n)^{1-epsilon}} for some epsilon>0; this would contradict the claimed hardness (or show the derandomization assumption false).","tokens_in":80151,"feed_emoji":"🧮","tokens_out":10297,"duration_ms":96591,"temperature":0.7,"pith_summary":"This thesis studies what convex relaxation hierarchies can and cannot do for three optimization problems. The central CSP result is a dichotomy: for every predicate f and every (c,s) integrality-gap instance of the basic LP relaxation of MAX k-CSP(f), the same gap (up to epsilon) reappears at Omega(log N / log log N) levels of the Sherali-Adams hierarchy. Consequently, no polynomial-size LP extended formulation can beat the basic LP on such instances. For polynomial optimization over the sphere, the thesis gives a tradeoff between the level q of the sum-of-squares SDP and the approximation ratio, with better ratios for polynomials that are non-negative or sparse. For matrix p->q norms, it proves the first NP-hardness of approximation in the hypercontractive regime 1<p<q<infinity, under the quasi-polynomial derandomization assumption, and near-matching algorithms when p>=q and 2 lies in [q,p].","feed_headline":"Basic LP matches Sherali-Adams at super-constant levels","feed_subtitle":"For every CSP, the cheapest LP relaxation already caps what the hierarchy can approximate; gaps lift automatically.","key_machinery":"Three objects carry the arguments. (1) For CSPs: the (c,s)-integrality-gap instance of the basic LP used as a template, together with the locally l2-embeddable metric rho_mu on random hypergraphs and consistent partitioning schemes (built from separating decompositions of finite subsets of l2) that produce the local distributions satisfying Sherali-Adams consistency; the theorem that does the work is Theorem 2.1.1. (2) For polynomial optimization: the spectral relaxation value Lambda(h) = inf over matrix representations of the largest eigenvalue, which equals the SoS level-q optimum; the weak decoupling lemma relating Lambda(g)/||g||_inf to the multilinear components of g, and its folded-pol","core_discovery":"The load-bearing theorem of the CSP thread is Theorem 2.1.1: a (c,s) integrality gap for the basic LP of MAX k-CSP(f) implies, for every epsilon>0, (c-epsilon, s+epsilon) integrality gaps for c_epsilon * log N / log log N levels of the Sherali-Adams relaxation on instances of size N. Combined with the extended-formulation connection of [CLRS13, KMR17], this yields near-optimal lower bounds for every polynomial-size LP extended formulation of the problem. The theorem is proved by taking the basic-LP gap instance as a template and generating a random multipartite instance; the geometry of local l2-embeddable metrics on random hypergraphs is used to build consistent local distributions that foo","pith_inferences":["The CSP dichotomy suggests a practical proof strategy for LP lower bounds: construct only a basic-LP gap, which is often much easier than constructing a hierarchy-aware gap, and the hierarchy limitation follows automatically; this may be applicable to other hierarchy-based lower-bound programs beyond CSPs.","The weak decoupling lemma, which decouples without increasing variable count beyond 2n, might be useful in constrained polynomial optimization settings (e.g., the simplex or hypercube) and in sub-exponential algorithm design, as the thesis itself hints.","For matrix norms, the reliance on the quasi-polynomial derandomization assumption means the cleanest open target is to remove that assumption, or to show the reduction can be derandomized, which would upgrade the hardness to unconditional NP-hardness under P != NP.","The 'folding' technique suggests a testable prediction: for polynomials that decompose into low-degree easy parts, SoS at level q should converge roughly as (n/q)^{(d - d_easy)/2}, and one could verify this on structured instances such as 2->4 norms of tall matrices."],"forward_implications":["For every predicate f, the entire approximability curve of the basic LP relaxation—not just its worst-case ratio—is inherited by the Omega(log N/log log N)-level Sherali-Adams relaxation, so improving the hierarchy beyond the basic LP is impossible in the worst case.","The dichotomy yields, via [KMR17], lower bounds of the form N^{c' log N/log log N} for any LP extended formulation that attempts to (c-epsilon, s+epsilon)-approximate a CSP with a basic-LP (c,s) gap; proving a basic-LP gap is thus sufficient to rule out all polynomial-size LPs.","For polynomial optimization over the sphere, level-q SoS, run in n^{O(q)} time, interpolates between the known n^{d/2-1} polynomial-time approximation (q=O(1)) and exactness for q=Omega(n); the paper's bounds are worst-case, instance-independent guarantees.","The tilde-Omega(n^{1/6}) gap for degree-4 non-negative polynomials shows that the SoS hierarchy, even at constant levels, cannot achieve a sub-polynomial worst-case approximation for a natural class of non-negative polynomials.","For p->q norms, any future algorithm beating 2^{(log n)^{1-epsilon}} in the hypercontractive case would either refute the derandomization assumption or settle a long-standing gap; in the regime p>=q with 2 in [q,p], the approximation ratio is pinned down up to numerical factors involving Grothendieck constants."],"supporting_citations":[{"why":"Supplies the local l2-embeddable metric and the Sherali-Adams gap construction for MAX-CUT that the CSP lifting extends.","marker":"[CMM09]"},{"why":"Proves local l2-embeddability of the metric rho on sparse hypergraphs, the geometric guarantee the Sherali-Adams construction depends on.","marker":"[ABLT06]"},{"why":"Defines the metric rho_mu and proves its local l2-embedding; used for consistent partitioning schemes.","marker":"[CMM07a]"},{"why":"Provides separating decompositions of finite subsets of l2, used to build the consistent partitioning schemes.","marker":"[CCG+98]"},{"why":"Establishes the connection between Sherali-Adams integrality gaps and lower bounds on LP extended formulation size.","marker":"[CLRS13]"},{"why":"Improves that connection; combined with Theorem 2.1.1 gives the N^{c' log N/log log N} extended-formulation lower bounds.","marker":"[KMR17]"},{"why":"Gives the vanishing-measure construction and the O(log log n)-level SA gaps for approximation-resistant predicates that the thesis strengthens to log n/log log n.","marker":"[KTW14]"},{"why":"Gives the baseline n^{d/2-1} polynomial-time approximation for arbitrary degree-d polynomials over the sphere, which the SoS tradeoff interpolates.","marker":"[HLZ10]"},{"why":"Provides the SoS analysis framework for non-negative coefficient polynomials and the 2->4 norm, which the polynomial optimization chapter builds on.","marker":"[BKS14]"},{"why":"Proves ETH-based hardness for the 2->q norm, the starting point for the p->q hardness results.","marker":"[BBH+12]"}],"fun_headline_variants":["Basic LP matches super-constant Sherali-Adams for CSPs","Super-constant Sherali-Adams gives no edge over basic LP","For every CSP, basic LP already caps the hierarchy","Basic LP relaxation suffices against Sherali-Adams for CSPs","High Sherali-Adams levels redundant for CSPs"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The load-bearing premise is the quasi-polynomial derandomization assumption NP not subset BPTIME(2^{(log n)^{O(1)}}) for the matrix-norm NP-hardness, and, in the CSP thread, the local l2-embeddability guarantee for the metric rho on random hypergraphs; if either fails, the corresponding claimed lower bounds do not go through.","fun_headline_variants_meta":{"raw":{"variants":["Basic LP matches super-constant Sherali-Adams for CSPs","Super-constant Sherali-Adams gives no edge over basic LP","For every CSP, basic LP already caps the hierarchy","Basic LP relaxation suffices against Sherali-Adams for CSPs","High Sherali-Adams levels redundant for CSPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001034,"raw_usage":{"total_tokens":4258,"prompt_tokens":881,"completion_tokens":3377,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":625,"completion_tokens_details":{"reasoning_tokens":3292}},"tokens_in":625,"tokens_out":3377,"duration_ms":24994,"temperature":1.0,"reasoning_tokens":3292,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T14:22:44.442288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the CSP thread: exhibit a predicate f and a (c,s) basic-LP gap instance such that the Omega(log N/log log N)-level Sherali-Adams relaxation of the constructed random instance has value below c-epsilon; this would refute Theorem 2.1.1 directly. For the matrix thread: give a randomized polynomial-time algorithm approximating any hypercontractive ||A||_{p->q} (1<p<q<infinity, 2 not in [p,q]) within 2^{(log n)^{1-epsilon}} for some epsilon>0; this would contradict the claimed hardness (or show the derandomization assumption false).","supporting_citations":[],"review_version":1}