{"id":"b8eaca12-e768-41c3-b290-3cc7dbbb1ca7","arxiv_id":"2604.17061","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Tensor degeneracy is ∃ℝ-complete via exact algebraic reductions from quadratic feasibility, while hyperdeterminant vanishing's deterministic hardness reduces to a structured PIT instance.","lead":"The paper proves that deciding whether a multilinear map (tensor) is degenerate is complete for the existential theory of the reals using purely algebraic reductions. This separates the intrinsic geometric notion of tensor singularity from the hyperdeterminant polynomial and ties the latter's deterministic complexity to a polynomial identity testing problem.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.3","headline":"Exactness of quadratic-to-projective-bilinear reduction may not preserve real feasibility","rationale":"This matches the reader's weakest assumption on reduction exactness and degeneracy-hyperdeterminant coincidence. The proposed test is a direct, low-cost falsification of the load-bearing step using concrete instances; agreement on small cases would support the algebraic claim while disagreement would require rejecting the completeness result. The derandomization barrier discussion is downstream and does not affect the core hardness proof. No other internal inconsistencies appear in the stated structure.","tokens_in":1733,"tokens_out":381,"duration_ms":43262,"concrete_test":"Take two small homogeneous quadratic instances over ℝ (e.g., x² + y² = 0, infeasible nontrivially; x² - y² = 0, feasible). Manually follow the paper's reduction steps to produce the corresponding 3-tensor in the claimed format. Symbolically or numerically check whether the tensor is degenerate (existence of nonzero vectors satisfying the degeneracy condition) exactly when the original quadratic is feasible. Mismatch on either instance falsifies exact preservation.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The ∃ℝ-completeness rests on the chain being exact: homogeneous quadratic feasibility reduces to projective bilinear feasibility, then singular matrix-pencil feasibility, then tensor degeneracy, with no extraneous real solutions introduced or lost at any step. The quadratic-to-bilinear step is the weakest because projective embeddings and bilinear encodings over ℝ can alter the solution set (e.g., via scaling freedoms or sign patterns that satisfy the bilinear equations without satisfying the original quadratic). If this occurs, hardness fails to transfer even if later steps are faithful. The paper asserts the reductions are 'exact and entirely algebraic' with no gadgets, but this does not automatically guarantee real-solution preservation without explicit verification of the encoding maps.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that deciding degeneracy of 3-tensors is ∃ℝ-complete via an exact algebraic reduction chain with no combinatorial gadgets: homogeneous quadratic feasibility reduces to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally to tensor degeneracy. In boundary format, degeneracy coincides with hyperdeterminant vanishing. It further shows that deterministic hardness for hyperdeterminant vanishing reduces to a structured polynomial identity testing instance and formalizes the failure of several natural deterministic embedding strategies, establishing a sharp separation between the ∃ℝ-completeness of intrinsic tensor singularity and the derandomization barrier for its classical polynomial certificate.","tokens_in":1884,"tokens_out":629,"duration_ms":33190,"significance":"If the reductions hold exactly, the result is significant for algebraic complexity theory: it supplies a natural, gadget-free ∃ℝ-complete problem in multilinear algebra and cleanly isolates the gap between tensor degeneracy and the hyperdeterminant. The algebraic (rather than combinatorial) nature of the chain and the explicit reduction of deterministic hyperdeterminant hardness to PIT are notable strengths that would advance understanding of real algebraic decision problems and derandomization barriers.","major_comments":[{"comment":"The load-bearing step is the first reduction (homogeneous quadratic feasibility to projective bilinear feasibility). The manuscript asserts the reductions are 'exact and entirely algebraic' with no extraneous real solutions, but the skeptic correctly flags that projective embeddings and bilinear encodings can alter real solution sets via scaling freedoms or sign patterns. Explicit verification that the encoding maps are bijective on real feasible instances (including handling of homogeneous scalings and sign consistency) is required; without it, hardness transfer fails even if later steps are faithful. This should be addressed with a dedicated subsection or lemma detailing the real-solution correspondence.","section":"Abstract / Reduction Chain (presumably §3)"},{"comment":"The claim that 'degeneracy coincides with hyperdeterminant vanishing' in boundary format is used to isolate the exact gap, but the manuscript must confirm that this coincidence holds without additional conditions on the format or field characteristic, as the hyperdeterminant is defined only in boundary format and the degeneracy notion is intrinsic.","section":"Boundary Format Discussion (presumably §4)"}],"minor_comments":[{"comment":"The abstract and introduction would benefit from a short diagram or table summarizing the four-stage reduction chain and the precise feasibility-preserving maps at each step.","section":"Abstract"},{"comment":"Notation for the tensor formats and the 'completion polynomial' in the PIT reduction should be introduced with explicit definitions before use in the derandomization barrier argument.","section":"Derandomization Barrier Section"}],"recommendation":"major_revision","confidential_remarks":"The paper's fit for a complexity journal is good if the reduction details are supplied; the low-confidence verdict in the reader's report stems directly from the absence of the full proof text in the provided cache, so I recommend the editor request the complete manuscript for verification of the quadratic-to-bilinear step."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments on the reduction chain and boundary-format discussion. We address each major point below and will strengthen the manuscript accordingly.","responses":[{"response":"We agree that an explicit bijectivity argument would improve clarity. The reduction is constructed so that projectivization quotients out homogeneous scalings exactly and the bilinear map preserves the sign patterns of the original quadratic forms, introducing no extraneous real solutions. In the revision we will add a dedicated Lemma (new Lemma 3.2 in §3) that formally proves the maps are bijective on the real feasible sets, handling scalings via the projective space and sign consistency via the homogeneous quadratic structure. This will make the exactness fully transparent.","revision_made":"yes","referee_comment":"The load-bearing step is the first reduction (homogeneous quadratic feasibility to projective bilinear feasibility). The manuscript asserts the reductions are 'exact and entirely algebraic' with no extraneous real solutions, but the skeptic correctly flags that projective embeddings and bilinear encodings can alter real solution sets via scaling freedoms or sign patterns. Explicit verification that the encoding maps are bijective on real feasible instances (including handling of homogeneous scalings and sign consistency) is required; without it, hardness transfer fails even if later steps are faithful. This should be addressed with a dedicated subsection or lemma detailing the real-solution correspondence."},{"response":"The equivalence is a standard fact: over any field of characteristic zero (hence over the reals), a tensor in boundary format is degenerate if and only if its hyperdeterminant vanishes. Degeneracy is the intrinsic geometric notion (nontrivial kernel in the multilinear sense), while the hyperdeterminant supplies the polynomial certificate precisely when the format is boundary. We will insert a short clarifying paragraph in §4 stating that the equivalence requires only the boundary-format hypothesis and char 0, with no further restrictions.","revision_made":"yes","referee_comment":"The claim that 'degeneracy coincides with hyperdeterminant vanishing' in boundary format is used to isolate the exact gap, but the manuscript must confirm that this coincidence holds without additional conditions on the format or field characteristic, as the hyperdeterminant is defined only in boundary format and the degeneracy notion is intrinsic."}],"tokens_in":1462,"tokens_out":489,"duration_ms":29613,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core result is that deciding tensor degeneracy is ∃ℝ-complete. The paper reduces homogeneous quadratic feasibility to projective bilinear feasibility, then to singular matrix-pencil feasibility, and finally to tensor degeneracy, all without combinatorial gadgets. In boundary format this separates degeneracy from hyperdeterminant vanishing and frames the latter as a structured PIT instance over a completion polynomial. That is the new piece: an explicit algebraic barrier rather than another gadget-based hardness proof. The framing is useful because it shows why natural deterministic embeddings fail and isolates the exact gap between the geometric property and its polynomial certificate. The reductions are presented as exact and real-preserving, which is the right way to do this kind of work. If the maps really send feasible instances to feasible instances and vice versa without extra real solutions, the completeness claim holds. The paper also formalizes why several obvious derandomization strategies do not work, which is honest bookkeeping. The main soft spot is still the quadratic-to-bilinear step. Projective embeddings over the reals can change the solution set through scaling and sign patterns, and the abstract asserts exactness without showing the verification in the letter I have. If the full write-up checks that no extraneous real roots appear, the argument is fine; otherwise the hardness does not transfer. The rest of the chain looks more routine once that step is solid. This paper is for people who already work on ∃ℝ-completeness, tensor problems, or algebraic derandomization. A reader who knows the standard reductions for quadratic feasibility and PIT will follow the argument and see where the new barrier sits. It is worth sending to referees because the claims are precise, the approach is algebraic rather than ad-hoc, and the potential flaw is local and checkable rather than fatal to the whole idea.","headline":"Tensor degeneracy is ∃ℝ-complete via a clean algebraic reduction chain, but the hyperdeterminant-PIT link and reduction exactness both need verification.","tokens_in":2397,"tokens_out":427,"would_cite":false,"duration_ms":25112,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Tensor degeneracy is ∃ℝ-complete via an exact algebraic reduction chain that separates it from hyperdeterminant vanishing.","keywords":["tensor degeneracy","existential theory of the reals","hyperdeterminant","algebraic complexity","derandomization","polynomial identity testing","multilinear maps"],"falsifier":"An explicit 3-tensor constructed from a known ∃ℝ-hard quadratic instance for which one can verify by direct computation that degeneracy holds if and only if the original quadratic system is feasible.","tokens_in":2619,"feed_emoji":"","tokens_out":721,"duration_ms":40003,"temperature":0.7,"pith_summary":"The paper shows that deciding whether a multilinear map given by a tensor is degenerate is complete for the existential theory of the reals. It does so by composing three algebraic reductions that start from homogeneous quadratic feasibility, pass through projective bilinear feasibility and singular matrix-pencil feasibility, and end at tensor degeneracy, all without combinatorial gadgets. In boundary format the two notions coincide because degeneracy equals hyperdeterminant vanishing, but outside that format the hyperdeterminant is only a specific polynomial certificate whose zero set matches the degeneracy locus only after choosing a point outside a completion polynomial. This matters because it places the intrinsic singularity of tensors at the same decision complexity as other real-algebraic problems while showing that any deterministic algorithm for the hyperdeterminant must solve a structured instance of polynomial identity testing.","feed_headline":"Tensor degeneracy is ∃ℝ-complete via algebraic reductions","feed_subtitle":"Hyperdeterminant vanishing is separated by a structured PIT barrier that blocks deterministic hardness transfer.","key_machinery":"The exact algebraic reduction chain from homogeneous quadratic feasibility through bilinear forms and matrix pencils to tensor degeneracy, which preserves feasibility equivalence at each step.","core_discovery":"The central claim is that tensor degeneracy—the condition that the associated multilinear map has a nontrivial kernel in projective space—is ∃ℝ-complete. The proof is a chain of exact algebraic equivalences: homogeneous quadratic feasibility reduces to projective bilinear feasibility, which reduces to singular matrix-pencil feasibility, which is directly encoded as the degeneracy of a constructed tensor. In boundary format this degeneracy is identical to the vanishing of the hyperdeterminant. Therefore deterministic hardness for deciding hyperdeterminant vanishing reduces to the problem of finding a point outside the zero set of a certain completion polynomial, which is a structured PIT task","pith_inferences":["Similar exact algebraic reductions may establish ∃ℝ-completeness for other geometric properties of tensors such as rank or border rank.","The identified PIT barrier suggests that derandomization progress in algebraic complexity would directly yield deterministic algorithms for hyperdeterminant vanishing.","Tensor degeneracy problems arising in applications may remain hard even when the hyperdeterminant is unavailable as a certificate."],"forward_implications":["Deciding 3-tensor degeneracy is ∃ℝ-complete.","In boundary format, deciding hyperdeterminant vanishing is also ∃ℝ-complete up to selection of a point outside the completion polynomial zero set.","Any deterministic algorithm for hyperdeterminant vanishing must solve a structured polynomial identity testing instance.","Natural deterministic embedding strategies for transferring hardness to the hyperdeterminant fail."],"fun_headline_variants":["Tensor degeneracy ∃R-complete by quadratic to pencil reductions","Derandomization barrier for hyperdeterminant from tensor hardness","Tensor degeneracy separates from hyperdeterminant via PIT barrier","No combinatorial gadgets in ∃R proof for tensor degeneracy","Algebraic chain encodes tensor singularity as ∃R-complete"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The algebraic reductions preserve exact feasibility equivalence without introducing or losing solutions, and degeneracy coincides with hyperdeterminant vanishing precisely when the tensor is in boundary format.","fun_headline_variants_meta":{"raw":{"variants":["Tensor degeneracy ∃R-complete by quadratic to pencil reductions","Derandomization barrier for hyperdeterminant from tensor hardness","Tensor degeneracy separates from hyperdeterminant via PIT barrier","No combinatorial gadgets in ∃R proof for tensor degeneracy","Algebraic chain encodes tensor singularity as ∃R-complete"]},"model":"grok-4.3","cost_usd":0.006439,"raw_usage":{"total_tokens":2954,"prompt_tokens":703,"num_sources_used":0,"completion_tokens":78,"cost_in_usd_ticks":64390500,"prompt_tokens_details":{"text_tokens":703,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2173,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":703,"tokens_out":78,"duration_ms":28865,"temperature":1.0,"reasoning_tokens":2173,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-10T06:20:08.278616+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit 3-tensor constructed from a known ∃ℝ-hard quadratic instance for which one can verify by direct computation that degeneracy holds if and only if the original quadratic system is feasible.","supporting_citations":[],"review_version":1}