The Quasi-Polynomial Low-Degree Conjecture is False

Aayush Jain; Jun-Ting Hsieh; Pravesh K. Kothari; Rares-Darius Buhai

REVIEW 3 major objections 4 minor 5 cited by

The Quasi-Polynomial Low-Degree Conjecture is False

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper constructs a permutation-invariant planted tensor distribution whose low-degree advantage against the uniform tensor distribution is exactly zero at degree $n^{1-6\epsilon}$, while a quasi-polynomial-time algorithm…

desk verdict Refutes Hopkins' low-degree conjecture with a genuinely new permutation-resilient Reed-Solomon construction; the proof has fixable parameter gaps but the counterexample is real. read the letter →

arxiv 2505.17360 v1 pith:VYLTUDIV submitted 2025-05-23 cs.CC cs.DS

Rares-Darius Buhai , Jun-Ting Hsieh , Aayush Jain , Pravesh K. Kothari This is my paper

classification cs.CCcs.DS MSC 68Q1768Q2594B35

keywords low-degreeconjectureadvantageplanteddistributionpermutationinvarianceReed-Solomoncodeslistdecodingaverage-casecomplexityinformation-computationgap

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that a vanishing low-degree advantage is not enough to certify noise-tolerant computational hardness, even under the symmetry and product-null hypotheses that the low-degree conjecture imposes. It builds, for every integer $k\ge 2$ and small enough $\epsilon>0$, an $S_n$-symmetric planted distribution on symmetric $k$-tensors in $\{0,1\}^{n^{\otimes k}}$ whose degree-$n^{1-6\epsilon}$ low-degree advantage against the uniform null distribution is exactly zero, yet an $n^{O(\log^{1/(k-1)} n)}$-time algorithm tells the $\epsilon$-noised planted tensor apart from a uniform one with probability $1-o(1)$. The construction hides Reed-Solomon evaluations of a random degree-$(m-1)$ polynomial inside a random symmetric tensor; the code's $(m-1)$-wise independence erases all low-degree moments, while list-decoding in the high-error regime recovers the polynomial. A second, rotationally invariant matrix construction shows that the largest eigenvalue can distinguish two distributions that polynomials of degree about $n^{1/3}/\operatorname{polylog}(n)$ cannot tell apart. The result means the low-degree heuristic needs additional structural conditions before it can be used as a hardness criterion.

What carries the argument

The main engine is Reed-Solomon list-decoding used as a permutation-resilient code. A random degree-$(m-1)$ polynomial over a finite field $\mathbb{F}_q$ is evaluated at random points $\alpha_j$, the pairs $(\alpha_j,\beta_j)$ are written in binary and embedded in a small block of a symmetric $k$-tensor, and the rest of the tensor is filled with uniform bits; a final random $S_n$ permutation hides the block. The Reed-Solomon code's $(m-1)$-wise independence makes any $m-1$ embedded entries jointly uniform, which forces the degree-$(m-1)$ low-degree advantage to be exactly zero. On the distinguishing side, a high-error list-decoding algorithm for Reed-Solomon codes recovers a short list containing the true polynomial from the uncorrupted, non-repeated evaluations that survive the noise operator, and the algorithm accepts if any listed polynomial matches enough surviving pairs. For the matrix example, the machinery is rotational invariance: a low-degree polynomial's expectation over random Gaussian columns reduces to a symmetric polynomial of the eigenvalues, and in the relevant parameter regime any such polynomial has small advantage, while the top eigenvalue of the noised planted matrix stays positive by a Gaussian quadratic-form concentration argument.

What would settle it

Fix $k=2$, small $\epsilon>0$, and $m=n^{1-6\epsilon}$, and compare the algorithm's final check of $n'=O(n^{1-6\epsilon})$ matching evaluations with the list-decoding requirement $t>\sqrt{nm}=n^{1-3\epsilon}$; since $n^{1-6\epsilon}$ is asymptotically smaller than $n^{1-3\epsilon}$, one must either set $t$ much larger than the stated check or prove that many more surviving pairs exist. A concrete calculation, for chosen $n$ and $\epsilon$, of how many uncorrupted non-repeated evaluations survive and whether any admissible $t$ satisfies both the theorem's condition and the algorithm's acceptance rule would settle whether the claimed success probability holds; the rectangular variant is also stated without a detailed proof, so its guarantees are less directly checkable.

Watch

Extended reading notes

Core claim

The central discovery is a counterexample to the low-degree conjecture in its own parameter range. Theorem 2.1 asserts that for every integer $k\ge 2$ and small enough $\epsilon>0$, with $Q_n$ uniform over symmetric $k$-tensors in $\{0,1\}^{n^{\otimes k}}$, there is an $S_n$-symmetric $P_n$ with $\operatorname{Adv}_{\le D}(P_n,Q_n)=0$ for $D=n^{1-6\epsilon}$, while a distinguisher running in time $n^{O(\log^{1/(k-1)} n)}$ separates $T_\epsilon P_n$ from $Q_n$ with probability $1-o(1)$. Because the null is a product distribution and the planted distribution is permutation invariant, this satisfies the hypotheses of the conjecture, so the conjecture is false. The same construction, with rectangular tensor shapes, yields a polynomial-time distinguisher and refutes the broader heuristic that polylogarithmic-degree indistinguishability rules out polynomial-time noise-tolerant algorithms. A separate theorem over $\mathbb{R}^{n\times n}$ gives rotationally invariant null and planted distributions with vanishing degree-$n^{\Omega(1)}$ advantage while the largest eigenvalue is a successful polynomial-time distinguisher.

Load-bearing premise

The construction stands on the parameter trade-off in the list-decoding step: enough uncorrupted, non-repeated Reed-Solomon evaluations must survive the noise for the true polynomial to reappear on the list, which forces the polynomial degree to be at most about $n^{1-6\epsilon}$ with the right constants; the proof also never fixes the threshold count $t$ used in the algorithm's final check, leaving a gap in the stated guarantee.

Editorial extensions

If this is right

A vanishing low-degree advantage at degree $n^{1-6\epsilon}$ is compatible with a quasi-polynomial-time noise-tolerant distinguisher, so the low-degree conjecture as stated is false.
In the rectangular setting the same construction yields a polynomial-time distinguisher, refuting the broader heuristic that polylogarithmic-degree indistinguishability rules out polynomial-time algorithms for rectangular inputs.
For tensor order $k=1$ the conjecture is reported to hold in concurrent work, so the dividing line is not symmetry alone but the order of the tensor; hardness conclusions for $k\ge 2$ cannot rest on vanishing low-degree advantage alone.
The Boolean counterexample transfers to a Gaussian null distribution on symmetric tensors via sign thresholds, so the counterexample is not an artifact of the Boolean alphabet.
Spectral methods can escape low-degree indistinguishability: a rotationally invariant pair with vanishing degree-$n^{1/3}/\operatorname{polylog}(n)$ advantage is separated by the top eigenvalue in polynomial time.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The construction suggests that the real bottleneck in the conjecture is not whether the null is a product distribution, but whether the planted signal is spread across all coordinates in a way that survives relabeling; any efficiently list-decodable code with large dual distance would be a systematic source of similar counterexamples.
The trace-moment intuition that spectral methods are captured by $O(\log n)$-degree polynomials fails at polynomial scale; testing smaller planted eigenvalues could map precisely where low-degree and spectral thresholds diverge.
A natural testable extension is whether the counterexample persists for noise rates approaching $1$ or for degrees closer to $n^{1-o(1)}$; if it does, even very strong low-degree indistinguishability carries no hardness signal.
The paper leaves the rectangular-polynomial-time variant and the final list-decoding threshold $t$ as the least explicit steps; a reader who wants to rely on the theorem should first fill in an explicit threshold that satisfies the list-decoding guarantee.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: this paper gives the first counterexample to the Boolean low-degree conjecture, and the core construction is both new and correct. The proof has some unfinished parameter details, but they are gaps in presentation, not load-bearing errors.

The main result (Theorem 2.1) constructs an S_n-symmetric planted distribution over symmetric k-tensors in {0,1}^{n^{⊗k}} that has zero LDA for D = n^{1-6ε}, yet a quasi-polynomial-time algorithm distinguishes T_ε P_n from uniform after noise. The key idea is to hide a degree-m Reed-Solomon codeword in a random submatrix of the tensor and then apply a random permutation. The m-wise independence of RS codewords gives exactly zero LDA; Guruswami-Sudan list-decoding gives the distinguisher. That's a clean, non-reductive counterexample, and it kills the conjecture as stated. The matrix counterexample (Theorem 3.1) is also nice: rotationally invariant null and planted distributions with vanishing n^{1/3}-degree LDA but top-eigenvalue distinguisher; the reduction to symmetric univariate polynomials via Lemma 3.9 is elegant.

Now the soft spots, in proportion. The stress-test note is on target. Step 3 of the algorithm in Lemma 2.11 never specifies the agreement threshold t for Guruswami-Sudan. The check n' = O(n^{1-6ε}) is far below sqrt(n|S'|), so the algorithm as written isn't runnable. That's a concrete gap, easily fixed by setting t = Θ(sqrt(nm)) and checking that many agreements. Second, the planted-case analysis needs Ω(n(1-ε)^{2 log_2 q}) > sqrt(nm); with q=Θ(n), the exponent margin is only about 0.12 ε, so the proof relies on hidden constants and on ε being small enough. The theorem says "small enough ε", which is fine, but the paper should spell out the constants or give a cleaner bound. Third, the abstract says "any fixed ε>0" while Theorem 2.1 requires small enough ε; that's an overclaim. Fourth, the zero-LDA degree D and the bound m ≤ n^{1-6ε} in Lemma 2.11 are off by an additive 1 (you need m-1 ≥ D). Minor, absorbed by O notation, but should be stated. Fifth, Lemma 2.14 has a typo: the success probability in the planted case is written as ≥ exp(-n^{1-O(ε)}), which decays; clearly meant 1 - exp(-...).

None of these undermine the counterexample. The main theorem is true as far as I can tell, and the fixes are routine. The paper is honest about limitations (e.g., quasi-polynomial rather than polynomial distinguisher in the symmetric case) and the discussion of what vanishing LDA should mean is sensible.

Who should read it: anyone working on average-case complexity, low-degree methods, or statistical-to-computational gaps. It's a major result in that area. A serious editor should send this to peer review; with the parameter details cleaned up, it's a strong paper. Recommendation: engage with it, with a referee who knows list-decoding.

Referee Report

3 major / 4 minor

Summary. The paper claims to refute Hopkins' low-degree conjecture by constructing, for every fixed k≥2 and sufficiently small ε>0, an S_n-invariant planted distribution P_n on {0,1}^{binom(n,k)} such that Adv_{\le D}(P_n,Q_n)=0 for D=n^{1-6ε} while an n^{O(log^{1/(k-1)} n)}-time algorithm distinguishes T_ε P_n from the uniform distribution Q_n with probability 1-o(1). The construction hides a Reed-Solomon codeword in a random block of a symmetric k-tensor; the (m-1)-wise independence of the codeword gives zero LDA, and Guruswami-Sudan list-decoding recovers the hidden polynomial after noise and a random permutation. The paper also presents a second example over rotation-invariant matrix distributions in which a degree-n^{Ω(1)} LDA vanishes but the top eigenvalue gives an efficient noise-tolerant distinguisher.

Significance. If the parameter gaps identified below are closed, the main result is a significant refutation of a conjecture that has been used as evidence of hardness in many average-case problems. The construction is elegant: it shows that permutation-resilient list-decodable codes yield counterexamples, and it isolates the role of the noise model and symmetry. The second example is also valuable as a cautionary counterexample for non-product nulls. The proof is structured and uses standard tools (Reed-Solomon list-decoding, Hanson-Wright, orthogonal polynomials), and the paper gives precise theorem statements, which makes the remaining gaps local rather than conceptual. That said, the current text does not fully specify the list-decoding threshold or the constants needed for the central planted-case argument.

major comments (3)

[§2.2, Lemma 2.11, Step 3] The algorithm invokes the Guruswami-Sudan list-decoder on {(α_j,β_j)}_{j∈S'} without specifying the agreement threshold t required by Fact 2.7. Fact 2.7 requires t > sqrt(|S'| m), which for q=Θ(n) and m ≤ n^{1-6ε} is on the order of n^{1-3ε}; the subsequent check of n'=O(n^{1-6ε}) agreements is far below this quantity, so the algorithm as written cannot be executed with the stated check. The planted-case argument also needs the number of uncorrupted non-repeated pairs to exceed t, not merely sqrt(nm), for the true polynomial to appear in the output list. Please specify t explicitly (e.g., t = ceil(sqrt(|S'|m))+1), make the post-list check consistent with t, and re-verify the null-case union bound and the planted-case lower bound under that threshold.
[§2.2, Lemma 2.11, planted case] The separation Ω(n(1−ε)^{2 log₂ q}) > sqrt(n m) is asserted only through asymptotic exponents. With q=Θ(n), the left side has exponent 1 − 2 log₂(1/(1−ε)) ≈ 1 − 2.885ε, while the right side has exponent at most 1 − 3ε under m ≤ n^{1−6ε}; the margin is about 0.115ε. Because both sides carry unspecified multiplicative constants, the inequality holds only if ε is sufficiently small relative to those constants, and Theorem 2.1 and Lemma 2.11 do not state such a condition. Please give explicit constants or a concrete condition on ε (and n) under which the planted-case guarantee follows.
[Theorem 2.1 and Lemma 2.10] The theorem states Adv_{\le D}(P_n,Q_n)=0 for D=n^{1−6ε}, but Lemma 2.10 gives only (m−1)-wise uniformity and Lemma 2.11 assumes m ≤ n^{1−6ε}. These statements are compatible only up to an additive one: one needs m−1 ≥ D, i.e., m ≥ n^{1−6ε}+1, which contradicts m ≤ n^{1−6ε} as written. Please set m = n^{1−6ε}+1 (or state D = m−1) and carry the resulting +1 through the list-decoding condition; alternatively, restate the theorem with D = n^{1−6ε}−1.

minor comments (4)

[§2.2, Lemma 2.10] The proof refers to 'Theorem 2.9' and 'Theorem 2.6' where it means Definition 2.9 and Fact 2.6; similar cross-reference slips occur in Observation 1.5 ('Theorem 1.4') and in Lemma 3.7 ('Theorem 3.2').
[§2.3, Lemma 2.14] The planted-case success probability is written as ≥ exp(−n^{1−O(ε)}), which tends to zero and is thus meaningless; it should be ≥ 1−exp(−n^{1−O(ε)}) to match Theorem 2.1 and the proof.
[§3.3, proof of Theorem 3.1] The planted case is described as 'For M∼P_n' but the distinguisher is applied to the noisy matrix M'=(1−ε)M_1+εM_0; the notation should be corrected to M' to match Lemma 3.7 and the theorem statement.
[§1, Conjecture 1.2] The text repeatedly refers to 'Theorem 1.2' when discussing the conjecture (e.g., 'The conditions of S_n-invariance...' and 'Theorem 1.2, if true'); this should be 'Conjecture 1.2'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof constructs distributions and proves both vanishing LDA and an efficient distinguisher from standard external list-decoding theorems.

full rationale

No step in the derivation reduces to its own inputs. The planted distribution in Definition 2.9 is constructed from random Reed–Solomon evaluations; its zero LDA is proved in Lemma 2.10 using Fact 2.6 (m−1-wise independence of Reed–Solomon codewords), a standard external fact, and the distinguisher in Lemma 2.11 relies on the Guruswami–Sudan list-decoding theorem (Fact 2.7), also standard and external. The matrix counterexample in Section 3 uses only elementary properties of Gaussian matrices, the Hanson–Wright inequality, and an internal Gram–Schmidt/Legendre argument (Lemmas 3.8–3.10). No parameter is fitted to the target claim and then renamed a prediction; no load-bearing assumption is justified by a self-citation. The authors' own prior works appear only in survey-style contextual citations, and the concurrent personal-communication citation [HKK+25] is used to contrast the k=1 case, not to support either theorem. The skeptic's concerns about the unspecified Guruswami–Sudan threshold t and the narrow O(ε) parameter margin in the planted-case analysis are genuine technical/correctness risks, but they concern whether the proof is fully specified or the constants close, not whether a claimed prediction is equivalent by definition to an input. Hence the circularity score is 0.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

All parameters are construction choices, not fitted to data. The paper introduces no new physical or mathematical entities; its contributions are new distributions and a new application of known coding theory.

free parameters (5)

m (Reed-Solomon degree) = m <= n^{1-6eps}
Sets the vanishing-LDA degree D = m-1 and ensures enough correct evaluations survive noise for list-decoding.
q (field size) = q = Theta(n), power of two
Controls the number of rows in the planted block (2 log q) and the list-decoding runtime.
gamma (null eigenvalue probability) = C log^2 n / n
Sets the rank and negative-eigenvalue magnitude of the matrix null distribution; chosen to balance concentration and low-degree indistinguishability.
lambda_* (planted positive eigenvalue) = gamma log n
The positive eigenvalue that the top-eigenvalue distinguisher detects; must satisfy lambda_* <= 1/(2d(d+1)) for the low-degree bound.
m_eig (number of eigenvalues in matrix model) = Theta(n)
Parameter m in Definitions 3.3-3.4; chosen so the spectral and low-degree calculations line up.

assumptions (5)

standard math Guruswami-Sudan list-decoding algorithm exists and runs in O(n^15) time, outputting all polynomials with at least t > sqrt(nm) agreements (Fact 2.7).
Used in Lemma 2.11 and Lemma 2.14 to recover the planted Reed-Solomon polynomial from noisy evaluations.
standard math Reed-Solomon code with random coefficients is (m-1)-wise independent (Fact 2.6).
Used in Lemma 2.10 to show the planted distribution has uniform marginals on any m-1 tensor entries, yielding zero low-degree advantage.
standard math Hanson-Wright inequality for Gaussian quadratic forms (Fact 3.6).
Used in Lemma 3.7 to show the planted positive eigenvalue survives noise.
standard math Sheppard's lemma transfers Gaussian noise to Boolean sign noise (Remark 2.2).
Used to extend the Boolean counterexample to Gaussian tensors, but not load-bearing for the main theorem.
domain assumption Conjecture 1.2 is the intended all-degree formalization of Hopkins' low-degree conjecture.
The paper refutes this statement; if the original conjecture only covers D = polylog n, the target is broader than the original formal version, though the paper argues the all-degree version is the one used in the literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Quasi-Polynomial Low-Degree Conjecture is False." pith.science (2026). https://pith.science/paper/VYLTUDIV

@misc{pith2026250517360,
  author       = {Pith},
  title        = {Pith review of: The Quasi-Polynomial Low-Degree Conjecture is False},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VYLTUDIV}},
  note         = {Machine review of arXiv:2505.17360}
}

abstract

There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closeness of low-degree moments - between a null distribution and a related planted distribution. Such hardness results are now ubiquitous not only for foundational average-case problems but also central questions in statistics and cryptography. This line of work is supported by the low-degree conjecture of Hopkins, which postulates that a vanishing degree-$D$ LDA implies the absence of any noise-tolerant distinguishing algorithm with runtime $n^{\widetilde{O}(D)}$ whenever 1) the null distribution is product on $\{0,1\}^{\binom{n}{k}}$, and 2) the planted distribution is permutation invariant, that is, invariant under any relabeling $[n] \rightarrow [n]$. In this paper, we disprove this conjecture. Specifically, we show that for any fixed $\varepsilon>0$ and $k\geq 2$, there is a permutation-invariant planted distribution on $\{0,1\}^{\binom{n}{k}}$ that has a vanishing degree-$n^{1-O(\varepsilon)}$ LDA with respect to the uniform distribution on $\{0,1\}^{\binom{n}{k}}$, yet the corresponding $\varepsilon$-noisy distinguishing problem can be solved in $n^{O(\log^{1/(k-1)}(n))}$ time. Our construction relies on algorithms for list-decoding for noisy polynomial interpolation in the high-error regime. We also give another construction of a pair of planted and (non-product) null distributions on $\mathbb{R}^{n \times n}$ with a vanishing $n^{\Omega(1)}$-degree LDA while the largest eigenvalue serves as an efficient noise-tolerant distinguisher. Our results suggest that while a vanishing LDA may still be interpreted as evidence of hardness, developing a theory of average-case complexity based on such heuristics requires a more careful approach.

Discussion (0). Sign in to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Kikuchi Hierarchy is Sharp for $k$XOR
cs.DS 2026-07 conditional novelty 8.0 of 10

Normalized Kikuchi matrices achieve the sharp m ~ rho^{-2} n^{k/2} / ell^{k/2-1} trade-off with no logarithmic loss for detection, recovery, and two-sided refutation in kXOR, with matching low-degree lower bounds.
Improved Strongly Polynomial Work-Span Tradeoffs for Directed Single Source Shortest Paths
cs.DS 2026-07 conditional novelty 8.0 of 10

For any t, directed shortest paths can be computed with near-linear work plus n^{1+o(1)}t^2 work and roughly n/t parallel depth, matching the undirected tradeoff.
Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
quant-ph 2025-05 conditional novelty 8.0 of 10

A quantum extension of the low-degree method shows that state designs imply computational hardness for many single-copy quantum measurement strategies, yielding new information-computation gaps.
Strong Refutation of Random Ordering CSPs
cs.DS 2026-07 accept novelty 7.0 of 10

Random ordering CSPs with coordinate-degree-d predicates admit poly-time ε-strong refutation above ~n^{d/2}/ε² clauses, with a smooth time-density-ε tradeoff via Kikuchi matrices that is near-optimal under the low-coo...
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
math.ST 2025-06 accept novelty 2.0 of 10

A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

98 extracted references · 67 canonical work pages · cited by 5 Pith papers

[1]

Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Varun Narayanan. Cryptography from Planted Graphs: Security with Logarithmic-Size Messages . In Guy N. Rothblum and Hoeteck Wee, editors, Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part I , volume 14369 of Lect...

2023
[2]

Public-key cryptography from different assumptions

Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 171--180, 2010

2010
[3]

http://admin.aimath.org/resources/lowdegreecomplexity/participantlist/ , 2024

Workshop on low degree polynomial methods in average case complexity. http://admin.aimath.org/resources/lowdegreecomplexity/participantlist/ , 2024

2024
[4]

Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification

Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification . In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference...

2019
[5]

Graph-codes

Noga Alon. Graph-codes. European Journal of Combinatorics , 116:103880, 2024

2024
[6]

Statistical-computational tradeoffs in mixed sparse linear regression

Gabriel Arpino and Ramji Venkataramanan. Statistical-computational tradeoffs in mixed sparse linear regression. In The Thirty Sixth Annual Conference on Learning Theory , pages 921--986. PMLR, 2023

2023
[7]

Bandeira, Ahmed El Alaoui, Samuel B

Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik. The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics . In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference ...

2022
[8]

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

Matthew Brennan and Guy Bresler. Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness . In Conference on Learning Theory , pages 469--470. PMLR, 2019

2019

Show all 98 references

[9]

Random algebraic graphs and their convergence to erdos-renyi

Kiril Bangachev and Guy Bresler. Random algebraic graphs and their convergence to erdos-renyi. CoRR , abs/2305.04802, 2023

2023 arXiv
[10]

On the fourier coefficients of high-dimensional random geometric graphs

Kiril Bangachev and Guy Bresler. On the fourier coefficients of high-dimensional random geometric graphs. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-2...

2024
[11]

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure . In Conference On Learning Theory , pages 48--166. PMLR, 2018

2018
[12]

Brennan, Guy Bresler, Samuel B

Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, and Tselil Schramm. Statistical query algorithms and low degree tests are almost equivalent. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Color...

2021
[13]

Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S

Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 202...

2021
[14]

Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh K. Kothari. Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) . In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology - EUROCRYPT 2018 - 37th Annual Intern...

2018
[15]

Computational-statistical gaps for improper learning in sparse linear regression

Rares - Darius Buhai, Jingqiu Ding, and Stefan Tiegel. Computational-statistical gaps for improper learning in sparse linear regression. CoRR , abs/2402.14103, 2024

2024 arXiv
[16]

The algorithmic phase transition of random k-sat for low degree polynomials

Guy Bresler and Brice Huang. The algorithmic phase transition of random k-sat for low degree polynomials. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 298--309. IEEE , 2021

2021
[17]

The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

Guy Bresler and Brice Huang. The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials . In 2021 IEEE 62nd annual symposium on foundations of computer science (FOCS) , pages 298--309. IEEE, 2022

2021
[18]

Hopkins, Jonathan A

Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11...

2016
[19]

Permuted Puzzles and Cryptographic Hardness

Elette Boyle, Justin Holmgren, and Mor Weiss. Permuted Puzzles and Cryptographic Hardness . In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part II , volume 11892...

2019
[20]

Low-degree security of the planted random subgraph problem

Andrej Bogdanov, Chris Jones, Alon Rosen, and Ilias Zadik. Low-degree security of the planted random subgraph problem. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography - 22nd International Conference, TCC 2024, Milan, Italy, December 2-6, 2024, Proceeding...

2024
[21]

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Andrej Bogdanov, Pravesh K Kothari, and Alon Rosen. Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method . In Theory of Cryptography Conference , pages 268--285. Springer, 2023

2023
[22]

Kothari, and David Steurer

Rares-Darius Buhai, Pravesh K. Kothari, and David Steurer. Algorithms approaching the threshold for semi-random planted clique. In S TOC '23--- P roceedings of the 55th A nnual ACM S ymposium on T heory of C omputing , pages 1918--1926. ACM, New York, [2023] 2023

1918
[23]

Bandeira, Dmitriy Kunisky, and Alexander S

Afonso S. Bandeira, Dmitriy Kunisky, and Alexander S. Wein. Computational hardness of certifying bounds on constrained PCA problems. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA ...

2020
[24]

Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

Quentin Berthet and Philippe Rigollet. Complexity Theoretic Lower Bounds for Sparse Principal Component Detection . In Conference on learning theory , pages 1046--1066. PMLR, 2013

2013
[25]

The complexity of sparse tensor PCA

Davin Choo and Tommaso d'Orsi. The complexity of sparse tensor PCA . In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information P...

2021
[26]

A computational transition for detecting correlated stochastic block models by low-degree polynomials

Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials. CoRR , abs/2409.00966, 2024

2024
[27]

Wein, and Ilias Zadik

Amin Coja - Oghlan, Oliver Gebhard, Max Hahn - Klimroth, Alexander S. Wein, and Ilias Zadik. Statistical and computational phase transitions in group testing. CoRR , abs/2206.07640, 2022

2022 arXiv
[28]

On the Security of Subspace Subcodes of Reed-Solomon Codes for Public Key Encryption

Alain Couvreur and Matthieu Lequesne. On the Security of Subspace Subcodes of Reed-Solomon Codes for Public Key Encryption . IEEE Trans. Inf. Theory , 68(1):632--648, 2022

2022
[29]

Almost-Linear Planted Cliques Elude the Metropolis Process

Zongchen Chen, Elchanan Mossel, and Ilias Zadik. Almost-Linear Planted Cliques Elude the Metropolis Process . Random Structures & Algorithms , 66(2):e21274, 2025

2025
[30]

Low-degree hardness of detection for correlated erd o s-r \' e nyi graphs

Jian Ding, Hang Du, and Zhangsong Li. Low-degree hardness of detection for correlated erd o s-r \' e nyi graphs. CoRR , abs/2311.15931, 2023

2023
[31]

Detection and recovery of hidden submatrices

Marom Dadon, Wasim Huleihel, and Tamir Bendory. Detection and recovery of hidden submatrices. CoRR , abs/2306.06643, 2023

2023 arXiv
[32]

Low degree conjecture implies sharp computational thresholds in stochastic block model

Jingqiu Ding, Yiding Hua, Lucas Slot, and David Steurer. Low degree conjecture implies sharp computational thresholds in stochastic block model. arXiv preprint arXiv:2502.15024 , 2025

2025 arXiv
[33]

Lossy Cryptography from Code-Based Assumptions

Quang Dao and Aayush Jain. Lossy Cryptography from Code-Based Assumptions . In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part III ...

2024
[34]

Non-Gaussian Component Analysis via Lattice Basis Reduction

Ilias Diakonikolas and Daniel Kane. Non-Gaussian Component Analysis via Lattice Basis Reduction . In Conference on Learning Theory , pages 4535--4547. PMLR, 2022

2022
[35]

Kothari, Gleb Novikov, and David Steurer

Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, and David Steurer. Sparse PCA: algorithms, adversarial perturbations and certificates. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 , pa...

2020
[36]

Kane, Thanasis Pittas, and Nikos Zarifis

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. Statistical query lower bounds for learning truncated gaussians. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada...

2023
[37]

Wein, and Afonso S

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. The average-case time complexity of certifying the restricted isometry property. IEEE Trans. Inform. Theory , 67(11):7355--7361, 2021

2021
[38]

Wein, and Afonso S

Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, and Afonso S. Bandeira. Subexponential-time algorithms for sparse PCA . Found. Comput. Math. , 24(3):865--914, 2024

2024
[39]

Abhishek Dhawan, Cheng Mao, and Alexander S. Wein. Detection of dense subhypergraphs by low-degree polynomials. CoRR , abs/2304.08135, 2023

2023 arXiv
[40]

Detection of Dense Subhypergraphs by Low-Degree Polynomials

Abhishek Dhawan, Cheng Mao, and Alexander S Wein. Detection of Dense Subhypergraphs by Low-Degree Polynomials . Random Structures & Algorithms , 66(1):e21279, 2025

2025
[41]

The low-degree hardness of finding large independent sets in sparse random hypergraphs

Abhishek Dhawan and Yuzhou Wang. The low-degree hardness of finding large independent sets in sparse random hypergraphs. CoRR , abs/2404.03842, 2024

2024
[42]

Vempala, and Ying Xiao

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto...

2013
[43]

Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes

Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran. Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes . In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 954--965. I...

2020
[44]

Low-degree hardness of random optimization problems

David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Low-degree hardness of random optimization problems. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 131--140. IEEE, 2020

2020
[45]

Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics

David Gamarnik, Aukosh Jagannath, and Alexander S Wein. Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics . SIAM Journal on Computing , 53(1):1--46, 2024

2024
[46]

Kizildag, Will Perkins, and Changji Xu

David Gamarnik, Eren C. Kizildag, Will Perkins, and Changji Xu. Algorithms and barriers in the symmetric binary perceptron model. CoRR , abs/2203.15667, 2022

2022 arXiv
[47]

Guruswami and M

V. Guruswami and M. Sudan. Improved decoding of reed-solomon and algebraic-geometric codes. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) , pages 28--37, 1998

1998
[48]

The landscape of the planted clique problem: Dense subgraphs and the overlap gap property

David Gamarnik and Ilias Zadik. The landscape of the planted clique problem: Dense subgraphs and the overlap gap property. CoRR , abs/1904.07174, 2019

1904 arXiv
[49]

Algorithmic Thresholds for Refuting Random Polynomial Systems

Jun-Ting Hsieh and Pravesh K Kothari. Algorithmic Thresholds for Refuting Random Polynomial Systems . In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1154--1203. SIAM, 2022

2022
[50]

Rigorous Implications of the Low-Degree Heuristic

Jun-Ting Hsieh, Daniel Kane, Pravesh K Kothari, Jerry Li, Sidhanth Mohanty, and Stefan Tiegel. Rigorous Implications of the Low-Degree Heuristic . In Personal communication , 2025

2025
[51]

The power of sum-of-squares for detecting hidden structures

Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures . In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 720--731. IEEE, 2017

2017
[52]

Optimal Low degree hardness for Broadcasting on Trees

Han Huang and Elchanan Mossel. Optimal Low degree hardness for Broadcasting on Trees . arXiv preprint arXiv:2502.04861 , 2025

2025
[53]

Statistical inference and the sum of squares method

Samuel Hopkins. Statistical inference and the sum of squares method . PhD thesis, Cornell University, 2018

2018
[54]

Efficient bayesian estimation from few samples: community detection and related problems

Samuel B Hopkins and David Steurer. Efficient bayesian estimation from few samples: community detection and related problems . In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) , pages 379--390. IEEE, 2017

2017
[55]

Strong low degree hardness for stable local optima in spin glasses

Brice Huang and Mark Sellke. Strong low degree hardness for stable local optima in spin glasses. CoRR , abs/2501.06427, 2025

2025
[56]

D. L. Hanson and F. T. Wright. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist. , 42:1079--1083, 1971

1971
[57]

Counterexamples to the Low-Degree Conjecture

Justin Holmgren and Alexander S Wein. Counterexamples to the Low-Degree Conjecture . In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2021

2021
[58]

Computational lower bounds for community detection on random graphs

Bruce Hajek, Yihong Wu, and Jiaming Xu. Computational lower bounds for community detection on random graphs . In Conference on Learning Theory , pages 899--928. PMLR, 2015

2015
[59]

Large cliques elude the Metropolis process

Mark Jerrum. Large cliques elude the Metropolis process . Random Structures & Algorithms , 3(4):347--359, 1992

1992
[60]

Phase transition for detecting a small community in a large network

Jiashun Jin, Zheng Tracy Ke, Paxton Turner, and Anru Zhang. Phase transition for detecting a small community in a large network. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023 . OpenReview.net, 2023

2023
[61]

How to Leverage Hardness of Constant-Degree Expanding Polynomials over R to build iO

Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. How to Leverage Hardness of Constant-Degree Expanding Polynomials over R to build iO . In Advances in Cryptology--EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techn...

2019
[62]

Sum-of-squares lower bounds for sparse independent set

Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, and Jeff Xu. Sum-of-squares lower bounds for sparse independent set. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 406--416. IEEE , 2021

2021
[63]

Sum-of-squares lower bounds for densest k-subgraph

Chris Jones, Aaron Potechin, Goutham Rajendran, and Jeff Xu. Sum-of-squares lower bounds for densest k-subgraph. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 , p...

2023
[64]

Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA , pages 392--401. A...

1993
[65]

Dmitriy Kunisky, Cristopher Moore, and Alexander S. Wein. Tensor cumulants for statistical inference on invariant distributions. In 2024 IEEE 65th A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2024 , pages 1007--1026. IEEE Computer Soc., Los Alamitos, CA, [2...

2024
[66]

Kothari, Aaron Potechin, and Jeff Xu

Pravesh K. Kothari, Aaron Potechin, and Jeff Xu. Sum-of-squares lower bounds for independent set on ultra-sparse random graphs. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver,...

2024
[67]

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing

Dmitriy Kunisky. Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing . arXiv preprint arXiv:2403.07862 , 2024

2024 arXiv
[68]

Is planted coloring easier than planted clique? In The Thirty Sixth Annual Conference on Learning Theory , pages 5343--5372

Pravesh Kothari, Santosh S Vempala, Alexander S Wein, and Jeff Xu. Is planted coloring easier than planted clique? In The Thirty Sixth Annual Conference on Learning Theory , pages 5343--5372. PMLR, 2023

2023
[69]

Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio

Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio . In ISAAC Congress (International Society for Analysis, its Applications and Computation) , pages 1--50. Springer, 2019

2019
[70]

Computational lower bounds for graphon estimation via low-degree polynomials

Yuetian Luo and Chao Gao. Computational lower bounds for graphon estimation via low-degree polynomials. Ann. Statist. , 52(5):2318--2348, 2024

2024
[71]

Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs

Zhangsong Li. Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs. arXiv preprint arXiv:2502.09832 , 2025

2025
[72]

Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation

Alex Lombardi and Vinod Vaikuntanathan. Limits on the locality of pseudorandom generators and applications to indistinguishability obfuscation. In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, Novem...

2017
[73]

Wein, and Afonso S

Matthias L \" o ffler, Alexander S. Wein, and Afonso S. Bandeira. Computationally efficient sparse clustering. CoRR , abs/2005.10817, 2020

2005 arXiv
[74]

Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model

Zhongyuan Lyu and Dong Xia. Optimal Clustering by Lloyd Algorithm for Low-Rank Mixture Model . CoRR , abs/2207.04600, 2022

2022 arXiv
[75]

Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures , 2022

Zhongyuan Lyu and Dong Xia. Optimal Estimation and Computational Limit of Low-rank Gaussian Mixtures , 2022

2022
[76]

Computational and statistical thresholds in multi-layer stochastic block models

Jing Lei, Anru R Zhang, and Zihan Zhu. Computational and statistical thresholds in multi-layer stochastic block models. The Annals of Statistics , 52(5):2431--2455, 2024

2024
[77]

McEliece

Robert J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report 42--44 , pages 114--116, 1978

1978
[78]

Lifting sum-of-squares lower bounds: degree-2 to degree-4

Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu. Lifting sum-of-squares lower bounds: degree-2 to degree-4. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 840--853, 2020

2020
[79]

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Andrea Montanari, Daniel Reichman, and Ofer Zeitouni. On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors . IEEE Transactions on Information Theory , 63(3):1572--1579, 2016

2016
[80]

On -Biased Generators in NC^0

Elchanan Mossel, Amir Shpilka, and Luca Trevisan. On -Biased Generators in NC^0 . In Annual Symposium on Foundations of Computer Science , volume 44, pages 136--145. Citeseer, 2003

2003
[81]

Precise error rates for computationally efficient testing

Ankur Moitra and Alexander S Wein. Precise error rates for computationally efficient testing. arXiv preprint arXiv:2311.00289 , 2023

2023 arXiv
[82]

Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation

Andrea Montanari and Alexander S Wein. Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation. Probability Theory and Related Fields , pages 1--53, 2024

2024
[83]

Optimal spectral recovery of a planted vector in a subspace

Cheng Mao and Alexander S Wein. Optimal spectral recovery of a planted vector in a subspace. Bernoulli , 31(2):1114--1139, 2025

2025
[84]

Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Testing network correlation efficiently via counting trees. Ann. Statist. , 52(6):2483--2505, 2024

2024
[85]

Detection-Recovery Gap for Planted Dense Cycles

Cheng Mao, Alexander S Wein, and Shenduo Zhang. Detection-Recovery Gap for Planted Dense Cycles . In The Thirty Sixth Annual Conference on Learning Theory , pages 2440--2481. PMLR, 2023

2023
[86]

Polynomial codes over certain finite fields

Irving S Reed and Gustave Solomon. Polynomial codes over certain finite fields . Journal of the society for industrial and applied mathematics , 8(2):300--304, 1960

1960
[87]

Is It Easier to Count Communities Than Find Them? In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Cynthia Rush, Fiona Skerman, Alexander S Wein, and Dana Yang. Is It Easier to Count Communities Than Find Them? In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2023

2023
[88]

Hanson- W right inequality and sub- G aussian concentration

Mark Rudelson and Roman Vershynin. Hanson- W right inequality and sub- G aussian concentration. Electron. Commun. Probab. , 18:no. 82, 9, 2013

2013
[89]

A public-key cryptosystem based on binary Reed-Muller codes

Vladimir Michilovich Sidelnikov. A public-key cryptosystem based on binary Reed-Muller codes . Discrete Mathematics and Applications , 1994

1994
[90]

V. M. SIDELNIKOV and S. O. SHESTAKOV. On insecurity of cryptosystems based on generalized reed-solomon codes. Discrete Mathematics and Applications , 2(4):439--444, 1992

1992
[91]

Decoding of reed solomon codes beyond the error-correction bound

Madhu Sudan. Decoding of reed solomon codes beyond the error-correction bound. J. Complex. , 13(1):180--193, 1997

1997
[92]

Computational barriers to estimation from low-degree polynomials

Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials . The Annals of Statistics , 50(3):1833--1858, 2022

2022
[93]

Youngtak Sohn and Alexander S. Wein. Sharp phase transitions in estimation with low-degree polynomials. CoRR , abs/2502.14407, 2025

2025 arXiv
[94]

Optimal low-degree hardness of maximum independent set

Alexander S Wein. Optimal low-degree hardness of maximum independent set. Mathematical Statistics and Learning , 4(3):221--251, 2022

2022
[95]

Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials

Alexander S Wein. Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials . In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1685--1698, 2023

2023
[96]

On some fine-grained questions in algorithms and complexity

Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018 , pages 3447--3487. World Scientific, 2018

2018
[97]

F. T. Wright. A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric. Ann. Probability , 1(6):1068--1070, 1973

1973
[98]

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

Ilias Zadik, Min Jae Song, Alexander S Wein, and Joan Bruna. Lattice-Based Methods Surpass Sum-of-Squares in Clustering . In Conference on Learning Theory , pages 1247--1248. PMLR, 2022

2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Cryptography from Planted Graphs: Security with Logarithmic-Size Messages

Damiano Abram, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and Varun Narayanan. Cryptography from Planted Graphs: Security with Logarithmic-Size Messages . In Guy N. Rothblum and Hoeteck Wee, editors, Theory of Cryptography - 21st International Conference, TCC 2023, Taipei, Taiwan, November 29 - December 2, 2023, Proceedings, Part I , volume 14369 of Lect...

2023

[2] [2]

Public-key cryptography from different assumptions

Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 171--180, 2010

2010

[3] [3]

http://admin.aimath.org/resources/lowdegreecomplexity/participantlist/ , 2024

Workshop on low degree polynomial methods in average case complexity. http://admin.aimath.org/resources/lowdegreecomplexity/participantlist/ , 2024

2024

[4] [4]

Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification

Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai. Indistinguishability Obfuscation Without Multilinear Maps: New Paradigms via Low Degree Weak Pseudorandomness and Security Amplification . In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology - CRYPTO 2019 - 39th Annual International Cryptology Conference...

2019

[5] [5]

Graph-codes

Noga Alon. Graph-codes. European Journal of Combinatorics , 116:103880, 2024

2024

[6] [6]

Statistical-computational tradeoffs in mixed sparse linear regression

Gabriel Arpino and Ramji Venkataramanan. Statistical-computational tradeoffs in mixed sparse linear regression. In The Thirty Sixth Annual Conference on Learning Theory , pages 921--986. PMLR, 2023

2023

[7] [7]

Bandeira, Ahmed El Alaoui, Samuel B

Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, and Ilias Zadik. The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics . In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference ...

2022

[8] [8]

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

Matthew Brennan and Guy Bresler. Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness . In Conference on Learning Theory , pages 469--470. PMLR, 2019

2019