Paper Citation Record · LEDGER

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

As of 16 August 2026, this Paper Citation Record lists 48 of 48 outbound references and 13 inbound Pith citation observations for arXiv:2506.10748.

A citation records a reference. It does not transfer a finding from one paper to another.

pith.paper-citation-record.v1
2506.10748 v1

Coverage vector

measured 48 of 48 reference resolution

Typed states for the displayed outbound observations.

Source: paper_references, paper_reference_links, observed 2026-08-07T04:24:27.226304Z

measured 61 of 61 standing notices

One-hop event checks from named stored sources.

Source: scholarly_work_events, retraction_status_cache, observed 2026-08-16T06:30:59.297886+00:00

measured 13 of 13 inbound itemization

Pith citing papers itemized under the disclosed page cap.

Source: paper_references, paper_reference_links, observed 2026-08-01T12:53:33.766327Z

measured 0 of 1 external citation measurements

A source-named dated measurement, never combined with another source.

Source: pith, observed 2026-07-10T05:46:50.306961Z

Reference resolution

48 of 48 outbound references displayed

verified exact9
verified fuzzy7
unresolved31
parse uncertain0
malformed identifier0
metadata mismatch1

External citation measurements

No source-named external measurement is stored.

Outbound references

Observation 8127156f-ca78-4b20-9380-cd2448d410f7 · outbound

This paper cites Algorithmic universality, low-degree poly- nomials, and max-cut in sparse random graphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Algorithmic universality, low-degree poly- nomials, and max-cut in sparse random graphs

Reference 10

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.439592Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 87027f6b-6824-45e5-920c-0d7bf7dbfdd8 · outbound

This paper cites Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood

Reference 11

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.520500Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 45251f6b-cd6e-4451-aa14-281d5e9ddd67 · outbound

This paper cites Stochastic block models with many communities and the Kesten--Stigum bound.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Stochastic block models with many communities and the Kesten--Stigum bound

Reference 12

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.580870Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 975c7fce-92aa-4c05-bc50-3e84d9ffd1b9 · outbound

This paper cites An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds

Reference 13

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.671125Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 42cdbcd2-d77d-4cf7-922a-2f09f0aed989 · outbound

This paper cites On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule

Reference 14

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.717183Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation d80886c4-9e70-46f7-903c-edba91a67bb2 · outbound

This paper cites Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931 ,.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Low-degree hardness of detection for corre- lated Erd˝ os-R´ enyi graphs.arXiv preprint arXiv:2311.15931 ,

Reference 15

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.812597Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 336d24b9-53dc-44ae-b913-0f17cf72cad4 · outbound

This paper cites The low-degree hardness of finding large inde- pendent sets in sparse random hypergraphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials The low-degree hardness of finding large inde- pendent sets in sparse random hypergraphs

Reference 17

Resolution: verified exact; raw_fallback, observed 2026-08-07T04:24:28.535415Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 0d101b51-f463-41d5-bba9-bd2b3b855a3d · outbound

This paper cites Detecting Arbitrary Planted Subgraphs in Random Graphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Detecting Arbitrary Planted Subgraphs in Random Graphs

Reference 18

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.015488Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 69afa1e4-555f-4826-875a-b53b8ce71ad5 · outbound

This paper cites Optimal hardness of online algorithms for large independent sets.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Optimal hardness of online algorithms for large independent sets

Reference 20

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.121158Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e5a83bd1-31bf-4200-b970-e4e39251b971 · outbound

This paper cites Disordered systems in- sights on computational hardness.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Disordered systems in- sights on computational hardness

Reference 21

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.938388Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 61a46ba7-79c3-46a3-8597-3de179c0c6d5 · outbound

This paper cites Optimal low degree hardness for broadcasting on trees.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Optimal low degree hardness for broadcasting on trees

Reference 22

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.252990Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation aa3e6856-87d9-47de-98e7-572d8431d809 · outbound

This paper cites Strong low degree hardness for stable local optima in spin glasses.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Strong low degree hardness for stable local optima in spin glasses

Reference 23

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.295266Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 5a88e7a8-507f-4d96-b65a-a1e88e556003 · outbound

This paper cites Sum-of-squares lower bounds for independent set on ultra-sparse random graphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Sum-of-squares lower bounds for independent set on ultra-sparse random graphs

Reference 28

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.917318Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation d45f2266-ea15-45af-9c79-964c973d30b1 · outbound

This paper cites Statistical inference of a ranked community in a directed graph.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Statistical inference of a ranked community in a directed graph

Reference 29

Resolution: metadata mismatch; local_arxiv, observed 2026-08-07T04:24:28.201731Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 339288b1-f36d-4fa1-8c7f-929609163866 · outbound

This paper cites Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models

Reference 30

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.794793Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 691369a3-3c40-48f2-b98f-0ca3b90582f7 · outbound

This paper cites Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

Reference 31

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.870792Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation b9182341-c84a-4bb0-a072-a09df3339213 · outbound

This paper cites A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials

Reference 32

Resolution: verified exact; raw_fallback, observed 2026-08-07T04:24:28.106048Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 4c286b12-9ef2-4c83-9a0d-a26a217b6af0 · outbound

This paper cites Almost-Optimal Local-Search Methods for Sparse Tensor PCA.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Almost-Optimal Local-Search Methods for Sparse Tensor PCA

Reference 34

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.117470Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 2798fd47-74ef-47f2-855d-3503e3336b9c · outbound

This paper cites Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model

Reference 35

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:27.835686Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 4eeb56e9-3613-47d7-b9f5-d60c58565cfe · outbound

This paper cites On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials On The MCMC Performance In Bernoulli Group Testing And The Random Max Set-Cover Problem

Reference 36

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:27.644063Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 117d393f-9e8f-4741-a3f9-a44ec9e1d857 · outbound

This paper cites Phase transitions in spiked matrix estimation: information-theoretic analysis.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Phase transitions in spiked matrix estimation: information-theoretic analysis

Reference 37

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.328079Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation ed35b9c8-630c-4115-abc9-fcae816b3e19 · outbound

This paper cites Strong Low Degree Hardness for the Number Partitioning Problem.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Strong Low Degree Hardness for the Number Partitioning Problem

Reference 39

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.512685Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 3f45cc4b-f044-472b-bfe7-77f02b42c1f6 · outbound

This paper cites Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs

Reference 40

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.601170Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation e5868bf1-0bb2-4101-8ec6-1946a17f54bb · outbound

This paper cites Approximate message passing with spec- tral initialization for generalized linear models.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Approximate message passing with spec- tral initialization for generalized linear models

Reference 41

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.907373Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 0bc14466-8979-4a90-95c0-71bd3008e608 · outbound

This paper cites On optimal distinguishers for Planted Clique.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials On optimal distinguishers for Planted Clique

Reference 42

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:27.443334Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 9c4c5a25-2610-4bda-8713-5f773fbe39a3 · outbound

This paper cites Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems

Reference 43

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.847273Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 08029a3d-dbcf-44bf-b6d9-e2934bcdeebd · outbound

This paper cites Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses

Reference 44

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.913655Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation b268ebf9-8f6e-404e-ab4a-293f2ff3f0f1 · outbound

This paper cites Sum-of-Squares & Gaussian Processes I: Certification.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Sum-of-Squares & Gaussian Processes I: Certification

Reference 45

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.966629Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation cc41b965-41c4-4c69-b969-eaac0dab6bdf · outbound

This paper cites Sharp Phase Transitions in Estimation with Low-Degree Polynomials.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Reference 46

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:27.030768Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 8029d2bd-4266-4c6f-a8a6-06ee0dd08c31 · outbound

This paper cites A Concise Tutorial on Approximate Message Passing.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials A Concise Tutorial on Approximate Message Passing

Reference 48

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:27.226304Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 1e415d23-b62b-4957-813d-18677a3919d9 · outbound

This paper cites Computational lower bounds for multi-frequency group synchronization.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Computational lower bounds for multi-frequency group synchronization

Reference 1976

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:28.216755Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation e0354515-e6f9-4d70-9316-9389ca1a0e59 · outbound

This paper cites Some easy optimization problems have the overlap-gap property.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Some easy optimization problems have the overlap-gap property

Reference 1985

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.026517Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 92f86025-bb2b-45db-83e7-1c1f679b1569 · outbound

This paper cites Fourier Analysis of Iterative Algorithms.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Fourier Analysis of Iterative Algorithms

Reference 2000

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.529700Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation ac17c1da-afb1-4357-ae43-ec66bac437d3 · outbound

This paper cites Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

Reference 2005

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:28.896781Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation e481cb00-aaea-4ee1-8422-cbcc64d0ae84 · outbound

This paper cites Sum-of-squares proofs and the quest toward optimal algorithms.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Sum-of-squares proofs and the quest toward optimal algorithms

Reference 2006

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.119911Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 9b1e8f82-daa4-491b-a04a-86a075442119 · outbound

This paper cites Symmetric Perceptrons, Number Partitioning and Lattices.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Symmetric Perceptrons, Number Partitioning and Lattices

Reference 2008

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:27.096421Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 4b89cecb-d397-4a41-8b0b-e170f438341c · outbound

This paper cites A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials A computational transi- tion for detecting correlated stochastic block models by low-degree polynomials

Reference 2009

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.227968Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 5b99bf26-c404-41c1-a218-f01d781f3627 · outbound

This paper cites The LASSO risk for Gaussian matrices.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials The LASSO risk for Gaussian matrices

Reference 2011

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.949403Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation f3cf2947-dfaa-4047-8a84-154ff27cf229 · outbound

This paper cites A greedy anytime algorithm for sparse PCA.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials A greedy anytime algorithm for sparse PCA

Reference 2016

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.927655Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 2d7cb48d-1254-48c1-9c31-e67b3462ef69 · outbound

This paper cites Algorithmic thresholds for tensor PCA.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Algorithmic thresholds for tensor PCA

Reference 2017

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.969547Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 381bbbdd-1f88-4f9f-9f72-6c7e4b2fdef4 · outbound

This paper cites Fast, robust approximate message passing.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Fast, robust approximate message passing

Reference 2018

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:28.241069Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 291cdc5b-0798-4815-b338-af6d5b941e6b · outbound

This paper cites Approximate message-passing for convex optimization with non-separable penalties.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Approximate message-passing for convex optimization with non-separable penalties

Reference 2019

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:26.423484Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 282a4397-bb20-4021-bb01-549866163411 · outbound

This paper cites Low degree conjecture implies sharp computational thresholds in stochastic block model.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Low degree conjecture implies sharp computational thresholds in stochastic block model

Reference 2020

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.862524Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation de08cdf1-f584-4f44-972c-c8e72d96b3d7 · outbound

This paper cites Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes

Reference 2021

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:25.061900Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation bef3ace4-ea56-42ff-b4c2-92bfaf9522a9 · outbound

This paper cites Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation

Reference 2022

Resolution: verified exact; local_arxiv, observed 2026-08-07T04:24:28.883011Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 8081c65a-3982-44fe-bdd5-0a0f487ab13f · outbound

This paper cites Algorithms approaching the threshold for semi-random planted clique.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Algorithms approaching the threshold for semi-random planted clique

Reference 2023

Resolution: verified fuzzy; raw_fallback, observed 2026-08-07T04:24:28.959507Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation c38b180b-7d4f-43f4-867e-fad237eeb4e8 · outbound

This paper cites Detecting correlation efficiently in stochastic block models: breaking Otter’s threshold by counting decorated trees.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials Detecting correlation efficiently in stochastic block models: breaking Otter’s threshold by counting decorated trees

Reference 2024

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:24.345870Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 23876183-404a-484c-b1ee-8464e13ab8b4 · outbound

This paper cites The Quasi-Polynomial Low-Degree Conjecture is False.

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials The Quasi-Polynomial Low-Degree Conjecture is False

Reference 2025

Resolution: unresolved; no resolver link, observed 2026-08-07T04:24:23.810810Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Pith citing papers

Observation 12d01909-b568-46e7-a21b-239ee02b560d · inbound

Sharp Phase Transitions in Estimation with Low-Degree Polynomials cites this paper.

Sharp Phase Transitions in Estimation with Low-Degree Polynomials Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 30

Resolution: verified exact; arxiv_id, observed 2026-05-23T02:55:19.434944Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 51714b5c-4fb4-43dd-a353-e797b45e743f · inbound

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors cites this paper.

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 64

Resolution: verified exact; arxiv_id, observed 2026-05-14T23:33:16.402394Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation bd754b22-1415-4cdf-a037-7570f3447668 · inbound

Learning $\mathsf{AC}^0$ Under Graphical Models cites this paper.

Learning $\mathsf{AC}^0$ Under Graphical Models Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 26

Resolution: verified exact; arxiv_id, observed 2026-05-10T22:30:52.927246Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation abdf8e58-2511-43c7-bde6-acfffcfb9d75 · inbound

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps cites this paper.

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 12

Resolution: verified exact; arxiv_id, observed 2026-05-10T05:51:10.596891Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation baba80e9-3eb1-42e1-a50e-61c48859bf78 · inbound

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs cites this paper.

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 107

Resolution: verified exact; arxiv_id, observed 2026-05-11T21:11:20.535510Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation e9a072ee-be62-4ed1-aebe-75c7bd794237 · inbound

On efficient robust regression with subquadratic samples cites this paper.

On efficient robust regression with subquadratic samples Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 40

Resolution: metadata mismatch; arxiv_id, observed 2026-05-20T01:02:54.314746Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 189e5ef3-7307-4468-95a2-31d6c4dbfa14 · inbound

Linear Functional Testing with General Loadings in Sparse Regression: Separation Rates and Computational Barriers cites this paper.

Linear Functional Testing with General Loadings in Sparse Regression: Separation Rates and Computational Barriers Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 59

Resolution: verified exact; arxiv_id, observed 2026-05-21T03:13:56.136374Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 8dda36ca-6ebe-42d7-a026-577f2bc90a14 · inbound

Low-degree estimation thresholds in planted hypergraphs and tensor PCA cites this paper.

Low-degree estimation thresholds in planted hypergraphs and tensor PCA Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 19

Resolution: verified exact; arxiv_id, observed 2026-06-29T00:02:49.580380Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation b8b37e8f-976e-4912-9fb8-3c4334b4fa6f · inbound

Sharp Low-Degree Thresholds for Planted-vs-Planted Testing cites this paper.

Sharp Low-Degree Thresholds for Planted-vs-Planted Testing Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 14

Resolution: metadata mismatch; arxiv_id, observed 2026-07-02T06:16:43.969695Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation f3b555fd-06bf-4857-b899-1664514cd78d · inbound

Efficiently Learning Drifting Halfspaces with Massart Noise cites this paper.

Efficiently Learning Drifting Halfspaces with Massart Noise Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 42

Resolution: verified exact; arxiv_id, observed 2026-07-03T04:37:37.614296Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 6bb99042-fc29-4c64-bd5a-d8b233f10a98 · inbound

High-Dimensional Procrustes Matching via Tree Counts cites this paper.

High-Dimensional Procrustes Matching via Tree Counts Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 3

Resolution: metadata mismatch; local_arxiv, observed 2026-07-10T05:46:50.309079Z

Source-reported events for the cited work

No event found in the named queried sources as of 2026-08-16T06:30:59.297886+00:00.

Observation 5740d9d7-7c27-4706-85c4-066cbc407d5b · inbound

Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths cites this paper.

Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 143

Resolution: unresolved; no resolver link, observed 2026-08-01T12:53:33.766327Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.

Observation 51c7cf9c-caeb-44f5-a99d-19015f82bb89 · inbound

The Polynomial-Time Low-Degree Conjecture is False cites this paper.

The Polynomial-Time Low-Degree Conjecture is False Computational Complexity of Statistics: New Insights from Low-Degree Polynomials

Reference 7

Resolution: unresolved; no resolver link, observed 2026-08-01T10:21:09.312369Z

Source-reported events for the cited work

Unavailable: canonical work link unavailable.