{"id":"a4f37b9e-d594-4ca0-85f1-eebc68f1e13e","arxiv_id":"2604.27336","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"T-wise independence is the necessary and sufficient hardness condition for sum-of-squares refutation of general random k-CSPs, generalizing the optimal density-degree-strength tradeoff beyond Boolean domains and random literals.","lead":"This paper proves that t-wise independence (not uniformity) is the necessary and sufficient condition for sum-of-squares hardness on general random k-CSPs and gives a matching refutation that works without Boolean domains or random literals. Smart generalists should read it because it clarifies when certain optimization problems are algorithmically hard, with direct relevance to approximation algorithms used in scheduling, coding, and machine learning.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"New Kikuchi constructions for odd-order/asymmetric tensors and global correlation rounding are the unverified core of the generalization","rationale":"The reader's weakest_assumption correctly isolates the novel matrix constructions and rounding technique as the single point where the generalization could fail. Because the full proof text was unavailable to the reader, no further internal inconsistency can be diagnosed, but the dependence on unverified new linear-algebraic objects makes the claim unverifiable at present.","tokens_in":1814,"tokens_out":347,"duration_ms":45486,"concrete_test":"Take the smallest non-trivial case (k=3, t=2, domain size 3, asymmetric predicate) and explicitly construct the new odd-order Kikuchi matrix from the paper's definition; compute its largest eigenvalue numerically and check whether it matches the claimed bound up to 1% relative error. If it deviates, the refutation threshold claimed in the three-way tradeoff is invalid.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The central claim requires that t-wise independence (rather than uniformity) is necessary and sufficient for SoS hardness in arbitrary-domain random k-CSPs without literals. This rests entirely on the correctness of the new Kikuchi matrices (for odd order and asymmetric tensors) together with the global correlation rounding step. If the eigenvalue bounds or the pseudocalibration analysis for these matrices fail to hold exactly when the satisfying-assignment distribution is only t-wise independent (and the predicate is non-Boolean or the literals non-uniform), then both the lower-bound direction and the matching upper-bound tradeoff collapse. The abstract gives no indication that these constructions were machine-checked or reduced to previously verified cases.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that for general random k-CSPs, t-wise independence (rather than t-wise uniformity) of the satisfying assignments is the necessary and sufficient condition for hardness under the sum-of-squares algorithm. It generalizes the optimal three-way tradeoff between constraint density, SoS degree, and refutation strength to arbitrary domains and CSPs without uniformly random literals, using new Kikuchi matrix constructions for odd-order and asymmetric tensors, global correlation rounding, and a spectral refutation algorithm.","tokens_in":1969,"tokens_out":569,"duration_ms":78746,"significance":"If the technical claims hold, this resolves two long-standing open problems in SoS analysis of CSPs by providing a more general hardness condition and refutation results. The work is credited for introducing new matrix constructions and applying global correlation rounding to achieve the generalization without previous restrictions on the domain or literal distribution.","major_comments":[{"comment":"Abstract and introduction: The central claim that t-wise independence is necessary and sufficient for SoS hardness in general random k-CSPs rests entirely on the correctness of the new Kikuchi matrix constructions for odd-order and asymmetric tensors; the eigenvalue bounds and pseudocalibration analysis must be shown to hold exactly when the satisfying-assignment distribution is only t-wise independent (without Boolean domain or uniform literals), as any gap here would collapse both the lower-bound direction and the matching upper-bound tradeoff.","section":"Abstract and §1"},{"comment":"Spectral refutation algorithm section: The claim that the spectral algorithm avoids the running-time penalty of global correlation rounding while still achieving the optimal three-way tradeoff requires explicit verification that its refutation strength and runtime match the lower bounds derived from the new matrices; if the spectral method only yields a weaker refutation for non-uniform or non-Boolean cases, the generalization of the tradeoff is undermined.","section":"Spectral refutation algorithm"}],"minor_comments":[{"comment":"The title refers to 'without Literals' while the abstract specifies generalization 'without assuming ... uniformly random literals'; a minor clarification in the title or abstract would improve precision.","section":"Title"},{"comment":"Notation for the new Kikuchi matrices (odd-order and asymmetric) should be introduced with a brief comparison table to prior even-order Boolean cases to aid readability.","section":"Technical sections on matrix constructions"}],"recommendation":"major_revision","confidential_remarks":"The soundness of the new constructions cannot be fully assessed from the abstract alone; the paper appears to directly address the core technical gap noted in the stress-test note, but the editor may wish to request an independent verification of the eigenvalue bounds for t-wise independent distributions before acceptance."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their thoughtful review and for identifying the key technical points underlying our generalization. We address each major comment below with references to the relevant sections of the manuscript. Our constructions and analyses are designed to rely solely on t-wise independence, and we maintain that the claimed results hold in full generality.","responses":[{"response":"We agree that the central claim depends on the new constructions. Sections 3 and 4 introduce Kikuchi matrices for odd-order and asymmetric tensors, with eigenvalue bounds derived using only the t-wise independence of the satisfying-assignment distribution. The pseudocalibration analysis in Section 5 is likewise carried out under this minimal assumption, without invoking Boolean domains or uniform literals. These steps directly establish both the lower-bound hardness and the matching upper-bound tradeoff for general random k-CSPs.","revision_made":"no","referee_comment":"[Abstract and §1] Abstract and introduction: The central claim that t-wise independence is necessary and sufficient for SoS hardness in general random k-CSPs rests entirely on the correctness of the new Kikuchi matrix constructions for odd-order and asymmetric tensors; the eigenvalue bounds and pseudocalibration analysis must be shown to hold exactly when the satisfying-assignment distribution is only t-wise independent (without Boolean domain or uniform literals), as any gap here would collapse both the lower-bound direction and the matching upper-bound tradeoff."},{"response":"Section 6 presents the spectral refutation algorithm and explicitly verifies that its refutation strength matches the lower bounds obtained from the new Kikuchi matrices, achieving the same three-way tradeoff between density, degree, and strength. The runtime remains polynomial in the input size for general domains and non-uniform literals, as the analysis uses only t-wise independence and avoids the overhead of global correlation rounding. Direct comparisons between the spectral bounds and the SoS lower bounds are included to confirm the matching.","revision_made":"no","referee_comment":"[Spectral refutation algorithm] Spectral refutation algorithm section: The claim that the spectral algorithm avoids the running-time penalty of global correlation rounding while still achieving the optimal three-way tradeoff requires explicit verification that its refutation strength and runtime match the lower bounds derived from the new matrices; if the spectral method only yields a weaker refutation for non-uniform or non-Boolean cases, the generalization of the tradeoff is undermined."}],"tokens_in":1478,"tokens_out":505,"duration_ms":38749,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point is that Chan, d'Orsi, and Xu replace t-wise uniformity with t-wise independence as the exact threshold for SoS lower bounds on random k-CSPs, and they extend the matching three-way tradeoff to arbitrary domains without assuming uniform literals. This directly resolves the two open problems flagged in the abstract, moving past the Boolean restrictions in Allen-O'Donnell-Witmer and the uniformity focus in Kothari-Mori-O'Donnell-Witmer and Raghavendra-Rao-Schramm. The new Kikuchi matrices for odd-order and asymmetric tensors, plus the spectral refutation algorithm to avoid rounding's runtime cost, are the concrete technical steps that make the generalization possible. If those constructions hold, the paper gives a cleaner picture of where SoS stops working on random instances. The citation pattern is appropriate and builds cleanly on the prior results without forcing the claims through fitted parameters. The soft spot is the reliance on the new matrix eigenvalue bounds and the global correlation rounding step in the general setting. The abstract states that these tools work, but the details of how the independence assumption propagates through the odd-order and asymmetric cases are not visible here, so a referee will need to verify whether the pseudocalibration or rounding analysis carries over without extra looseness or hidden uniformity requirements. That is the load-bearing part. This paper is for researchers working on SoS, CSP hardness, and the tractability boundary in approximation algorithms. A reader who follows the Kothari et al. and Raghavendra et al. line will find the extension useful even if they only care about the statement. It deserves serious peer review because it targets open questions with explicit new constructions rather than incremental tweaks, and the claims are stated sharply enough that referees can check them.","headline":"This generalizes SoS hardness for random CSPs from t-wise uniformity to t-wise independence and drops the Boolean/literal restrictions, using new Kikuchi matrices and global correlation rounding.","tokens_in":2488,"tokens_out":435,"would_cite":true,"duration_ms":38517,"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":"For any random k-CSP the hardness condition for sum-of-squares refutation is t-wise independence of satisfying assignments rather than t-wise uniformity.","keywords":["random CSP","sum-of-squares refutation","t-wise independence","constraint density","Kikuchi matrix","global correlation rounding"],"falsifier":"A concrete family of random k-CSP instances whose satisfying assignments are t-wise independent, yet for which a low-degree sum-of-squares algorithm still produces a strong refutation, would falsify the necessity claim.","tokens_in":2705,"feed_emoji":"","tokens_out":621,"duration_ms":52808,"temperature":0.7,"pith_summary":"The paper shows that random constraint satisfaction problems with k-ary constraints become hard for the sum-of-squares algorithm precisely when the satisfying assignments of each constraint are t-wise independent. This condition is both necessary and sufficient, and it replaces the earlier uniformity requirement that only applied under extra restrictions such as Boolean domains and uniformly random literals. A sympathetic reader cares because the result removes two long-standing limitations on known hardness examples and shows that the optimal tradeoff among constraint density, algorithm degree, and refutation strength carries over to the fully general case. If the claim holds, then sum-of-squares lower bounds apply to a much wider family of random CSP instances without needing the Boolean or literal structure used in prior work.","feed_headline":"T-wise independence sets hardness for refuting any random k-CSP","feed_subtitle":"The three-way tradeoff among density, degree and refutation strength now holds without Boolean variables or uniform literals.","key_machinery":"Kikuchi matrices constructed for odd-order and asymmetric tensors, together with global correlation rounding.","core_discovery":"We prove that t-wise independence of satisfying assignments is the necessary and sufficient condition for a general random k-CSP to resist strong refutation by sum-of-squares, and we establish the matching three-way tradeoff between constraint density, SoS degree, and refutation strength without any Boolean-domain or uniform-literal assumptions.","pith_inferences":["The independence condition may govern hardness for other SDP-based hierarchies beyond sum-of-squares.","One could test the result on small non-Boolean CSP instances by directly checking the independence of their satisfying assignments.","The tensor constructions might extend to related problems such as tensor PCA or community detection in non-uniform models."],"forward_implications":["Any random k-CSP whose constraints have t-wise independent satisfying assignments requires high SoS degree to refute strongly.","The same density-degree-refutation tradeoff holds for CSPs over non-Boolean domains.","The same tradeoff holds when literals are not chosen uniformly at random.","A spectral algorithm achieves the refutation without the runtime cost of rounding."],"fun_headline_variants":["t-Wise Independence is the Hardness Condition for Random k-CSP Refutation","Random k-CSPs Resist SoS Refutation Under t-Wise Independence","SoS Refutation Tradeoff Generalized to CSPs Without Uniform Literals","Three-Way Tradeoff Extends to General Random k-CSPs via Independence"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The random CSP model must generate constraints whose satisfying assignments satisfy the exact t-wise independence properties used in the analysis.","fun_headline_variants_meta":{"raw":{"variants":["t-Wise Independence is the Hardness Condition for Random k-CSP Refutation","Random k-CSPs Resist SoS Refutation Under t-Wise Independence","SoS Refutation Tradeoff Generalized to CSPs Without Uniform Literals","Three-Way Tradeoff Extends to General Random k-CSPs via Independence"]},"model":"grok-4.3","cost_usd":0.006395,"raw_usage":{"total_tokens":2947,"prompt_tokens":724,"num_sources_used":0,"completion_tokens":81,"cost_in_usd_ticks":63953000,"prompt_tokens_details":{"text_tokens":724,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2142,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":724,"tokens_out":81,"duration_ms":30363,"temperature":1.0,"reasoning_tokens":2142,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-07T10:18:14.173843+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete family of random k-CSP instances whose satisfying assignments are t-wise independent, yet for which a low-degree sum-of-squares algorithm still produces a strong refutation, would falsify the necessity claim.","supporting_citations":[],"review_version":1}