A General Framework for Low Soundness Homomorphism Testing

Sourya Roy; Tushant Mittal

REVIEW 2 major objections 3 minor 15 references

A General Framework for Low Soundness Homomorphism Testing

T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read A single kernel-weighted test gives constant-query homomorphism tests for arbitrary cyclic groups and several non-abelian families.

desk verdict The kernel-weighted framework is a genuinely useful idea, but the headline arbitrary-cyclic theorem is false as stated and the cyclic section needs major revision before the paper can be trusted. read the letter →

arxiv 2509.05871 v2 pith:SFBRTER4 submitted 2025-09-07 cs.CC cs.DSmath.CO

Tushant Mittal , Sourya Roy This is my paper · ORCID

classification cs.CCcs.DSmath.CO MSC 68Q1720D6094B35

keywords homomorphismtestinglowsoundnessregimelistdecodingcyclicgroupsinnerautomorphismscharacterkernel-weightedevaluationmapfinite

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 tries to establish that low-soundness homomorphism testing—where a function passes the test with probability $\delta$ that may be far below the random passing rate—is governed by one general $k$-query test. For arbitrary cyclic groups $G,H$, it claims that if $f$ passes $\mathrm{Test}_{\ker k}$ with probability $\delta_k$, then some homomorphism agrees with $f$ on at least $(\zeta(2)^2\delta_k)^{1/(k-3)}$ of the inputs, and the list of homomorphisms with agreement at least $\varepsilon$ has size $O(\varepsilon^{-3})$. The same machinery yields the first constant-query low-soundness tests for non-abelian groups: automorphisms of dihedral and symmetric groups, inner automorphisms of finite simple and extraspecial groups, and characters of $\mathrm{GL}_n(\mathbb{F}_q)$ and of Lie algebras over $\mathbb{F}_q$, and it recovers the known 3-query vector-space test. A sympathetic reader would care because these are the first such tests beyond abelian groups of bounded exponent, and because the proof reduces testing to bounding a group-theoretic constant rather than doing Fourier analysis.

What carries the argument

The machinery is the evaluation map $\Gamma_x:\operatorname{Hom}(G,H)\to H^k$, $\Gamma_x(\varphi)=(\varphi(x_1),\dots,\varphi(x_k))$, which is $N$-to-one on its image with $N=|\ker\Gamma_x|$. The test $\mathrm{Test}_{\ker k}$ samples $x=(x_1,\dots,x_k)\in G^k$ with probability proportional to $|\ker\Gamma_x|$ and accepts exactly when $(f(x_1),\dots,f(x_k))$ lies in the image of $\Gamma_x$. Lemma 2.1 rewrites the agreement moment as $\delta_k\gamma_k/|G|^k$ plus a small error term, where $\gamma_k=\sum_\varphi|\ker\varphi|^k$; once $\gamma_k$ is bounded, the test's soundness and list size follow by telescoping ratios. For automorphisms the same construction replaces kernels by pointwise stabilizers and $\gamma_k$ by $\rho_k=\sum_\varphi|\operatorname{Fix}(\varphi)|^k$, whose inner-automorphism version is the conjugacy-class zeta function $\sum_C|C|^{1-k}$.

What would settle it

Compute $\gamma_4$ and $\gamma_3$ exactly for $G=H=\mathbb{Z}_6$ (or $\mathbb{Z}_p$ for a small prime $p$). If $\gamma_4/\gamma_3<|G|\zeta(2)^2$, then the claimed $k=4$ guarantee fails as stated, because it would require agreement at least $\zeta(2)^2\delta_4$, which exceeds 1 for large $\delta_4$. This is a finite calculation and can be checked by brute force.

Watch

Extended reading notes

Core claim

The paper's central claim is that the $k$-th power moment of agreement, $\sum_{\varphi\in\operatorname{Hom}(G,H)}\operatorname{agr}(f,\varphi)^k$, can be rewritten exactly as the kernel-weighted expectation of the number of homomorphisms consistent with $f$ on a random $k$-tuple. This identity converts soundness analysis into a calculation of $\gamma_k=\sum_\varphi|\ker\varphi|^k$. For cyclic groups the paper claims $\gamma_k\le |G|^k\zeta(k-1)^2$ and uses the telescoped ratios to obtain the soundness bound $(\zeta(2)^2\delta_k)^{1/(k-3)}$; for prime-power cyclic groups and $p$-rank $t$ abelian targets it obtains agreement roughly $\delta^{1/(k-t-1)}$ and list size $O(\varepsilon^{-(t+1)})$. The same moment identity, with pointwise stabilizers replacing kernels, gives inner-automorphism tests, and a lifting lemma extends the tests from a base group to any group projecting onto it, which is how the $\mathrm{GL}_n(q)$ and Lie-algebra character tests are derived.

Load-bearing premise

The load-bearing premise for the arbitrary-cyclic-group theorem is that the telescoped ratio of kernel counts, $\gamma_k/\gamma_3$, is at least $|G|^{k-3}\zeta(2)^2$, but the paper's stated bound on that ratio goes in the opposite direction and the proof invokes a prime-power estimate for general cyclic groups.

Editorial extensions

If this is right

For arbitrary cyclic groups, $k$-query tests with soundness scaling like $\delta^{1/(k-3)}$ become available for every $k\ge 4$, giving a smooth query-versus-soundness tradeoff.
Combinatorial list decoding for cyclic-group homomorphisms improves to $O(\varepsilon^{-2})$ in the prime-power case and $O(\varepsilon^{-3})$ in the general case, replacing the previous $O(\varepsilon^{-105})$ bound.
Low-soundness tests now exist for non-abelian groups: automorphisms of dihedral and symmetric groups, and inner automorphisms of finite simple and extraspecial groups, none of which had constant-query tests before.
The lifting theorem yields the first Hamming-metric character tests for $\mathrm{GL}_n(\mathbb{F}_q)$ and for finite-dimensional Lie algebras over $\mathbb{F}_q$, with the same query count and guarantee as the base test.
Because the analysis is moment-based rather than Fourier-based, it applies whenever a bound on $\gamma_k$ (or $\rho_k$) is available, including groups where $H$ does not embed into $\mathbb{C}$.

Reading between the lines

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

If the cyclic theorem's constant is corrected (the stated proof needs $\gamma_k/\gamma_3\ge |G|^{k-3}\zeta(2)^2$, while Proposition 3.8 only upper-bounds that ratio), the $k\ge 4$ tradeoff would still survive with a different constant, and the list-size improvement would likely survive unchanged.
The kernel-weighted distribution explains why the uniform 3-query product test from the literature fails on cyclic groups: uniform triples with product 1 rarely lie inside the small kernels that dominate the agreement moment, whereas kernel weighting concentrates samples exactly where the evaluation map is many-to-one.
The method should extend to any group family with a controllable bound on the conjugacy-class zeta function $\sum_C |C|^{1-k}$, such as alternating groups, direct products, or additional Lie-type groups, since the test's logic depends only on that ratio.
A concrete next test: check whether the telescoping argument works for $k=3$ on cyclic groups once the ratio constant is fixed; a successful version would yield a 3-query test matching the known vector-space test's query count.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Colleague,

The paper is worth engaging, but the headline result does not hold as stated. The framework—the kernel-weighted evaluation-map moment identity—is genuinely useful, and the prime-power cyclic results (Theorem 3.4) look plausible. The non-abelian automorphism sections may contain real new tests, though I did not audit them line by line.

The soft spot is Theorem 3.10, and it is not minor. For G,H arbitrary cyclic, it claims agreement at least (ζ(2)^2·δ_k)^(1/(k-3)). Take f a homomorphism: δ_k=1, and for k=4 the bound exceeds 1. Impossible. The proof misapplies Corollary 3.3, which is only for prime-power G, to general cyclic groups, and the zeta constant enters inverted: Proposition 3.8 gives γ_k/γ_3 ≥ |G|^(k-3)/ζ(2)^2, not |G|^(k-3)·ζ(2)^2. So the first claimed constant-query low-soundness test for arbitrary cyclic groups is unsupported. The list-decoding bound of O(ε^-3) for general cyclic groups is tied to the same flawed argument, so it is also in question, though it could be salvaged with a correct constant.

Section 4 also has moment formulas that look off by a factor of |Hom(G,H)|; taken literally the dimensions do not match. That affects the recovery of Kiwi's result. These are fixable in principle, but they are load-bearing, not typos.

What is actually new: the kernel-weighted distribution and the rewriting of Σ_φ agr(f,φ)^k as a test-passing probability is a clean idea, and the prime-power and non-abelian applications demonstrate it has range. If the cyclic section is repaired, this could be a solid paper. As it stands, the advertised first constant-query tests for arbitrary cyclic groups is the part that fails.

Who should read it: property testers and coding theorists. The framework section is worth a look; the cyclic guarantees should not be relied upon until fixed.

My recommendation: it deserves a serious referee, but the current version should not be accepted. The referee should be pointed at Theorem 3.10 and the Section 4 normalization. If those are fixed, it can be a good paper.

Referee Report

2 major / 3 minor

Summary. The paper introduces a general k-query framework for low-soundness homomorphism testing, based on rewriting the kth agreement moment as an expectation over tuples weighted by the kernel of the evaluation map. It claims constant-query tests for homomorphisms between arbitrary cyclic groups, between vector spaces and fields, for automorphisms and inner automorphisms of several non-abelian families, and for lifted character tests, together with improved list-decoding bounds for cyclic groups. The framework is novel in scope and the constants are derived from explicit group-theoretic quantities rather than fitted parameters.

Significance. If the results were correct, this would be a substantial advance: it would give the first low-soundness constant-query tests for non-abelian groups, unify several known tests such as Kiwi's, and improve the cyclic list-decoding bound from O(eps^-105) to O(eps^-2) or O(eps^-3). The moment identity in Lemma 2.1 is elegant and likely reusable, and the framework is self-contained. However, the headline cyclic-group theorem is false as stated, and the vector-space moment computations are internally inconsistent as written; both issues are load-bearing for the paper's central claims.

major comments (2)

[§3.2, Theorem 3.10 and Table 1] Theorem 3.10 is false as stated. For k=4, take f to be a homomorphism: the test passes with probability delta_4=1 and agr(f,varphi)=1, but the claimed lower bound is (zeta(2)^2 * 1)^(1/(4-3)) = zeta(2)^2 ≈ 2.705 > 1, which is impossible. The proof is not a valid derivation for arbitrary cyclic groups: it repeats the proof of Theorem 3.4 with an undefined parameter t and an undefined prime p, and it invokes Corollary 3.3, a prime-power statement, after Lemma 3.6 without the per-prime telescoping that would be needed. The available bounds point in the opposite direction: Proposition 3.8 gives gamma_k >= |G|^k and gamma_3 <= |G|^3 zeta(2)^2, hence gamma_k/gamma_3 >= |G|^(k-3)/zeta(2)^2, so the telescoping product can only yield M >= (delta_k / zeta(2)^2)^(1/(k-3)), the reciprocal of the displayed constant. Since Theorem 3.10 is the headline cyclic-group result and is cited by Table 1, Theorem 1.2, and Theorem 6.6, the affected statements must be corrected.
[§4.1, Claims 4.2 and 4.4] The moment computations for the vector-space test are internally inconsistent as written. Claim 4.2 states Pr[rank(x)=k] ≈ q^(-2n)(1 - q^(k-1)/(q^n(q-1))), which tends to 0, while the proof of the same claim expands the product to 1 - O(q^(k-n)) ≈ 1. Claim 4.4 then writes the leading term of sum_phi agr(f,phi)^k as q^(-n) Pr[rank=k] * q^(n-k), which with Pr[rank=k] approximately 1 is q^(-k), whereas the definition of beta in the proof and Lemma 2.1 give q^(n-k) for a random f. The sums in Claim 4.4 and Corollary 4.7 also involve delta_1, and the binomial identity involves a delta_0 term, although R_1 is empty for k>1 and delta_0 is never defined. Because Corollary 4.7 and Theorem 4.8 depend directly on Claim 4.4, the soundness proof for Hom(F_q^n, F_q) is not verifiable in the submitted form.

minor comments (3)

[§3.1, proof of Theorem 3.4] In the telescoping product, the exponent (1/|G|)^(k-t) should be (1/|G|)^(k-t-1) when multiplying from i=t+2 to k; the subsequent line silently restores the correct exponent.
[Notation and typos] The manuscript has extensive typesetting corruption, with the tuple variable rendered as a sequence of unusual symbols, and many typos such as 'exstraspecial', 'inverible', 'unitrianguar', and 'Riemmann'; a careful copyedit is needed.
[§4.1, Definition 4.1] The level-j sets R_j are defined for tuples in G^k, but Claim 4.4 evaluates delta_j on G^j and the case j=1 is not handled; the relationship between these R_j should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the tests are derived from exact moment identities and explicit group-theoretic bounds, with no fitted inputs or load-bearing self-citations.

full rationale

The derivation chain is self-contained. The core identity (Lemma 2.1) rewrites Σ_φ agr(f,φ)^k exactly as an expectation of the test indicator weighted by |ker Γ_x|; Corollary 2.2 defines δ_k as that normalized expectation, and Eq. (3) is the generic inequality max agr ≥ (Σ agr^i)/(Σ agr^{i-1}). The cyclic-group results then reduce to the group-theoretic constants γ_k computed from Claim 2.3 and Lemmas 3.2/3.6; no parameter is fitted to data, and no 'prediction' is a renamed input. The only self-citation, [MR24], appears in a related-work list for character testing and is not used to justify any theorem. The ζ(2) constant in Theorem 3.10 is suspect: Proposition 3.8 supplies γ_k/γ_3 ≥ |G|^{k-3}/ζ(2)^2, which would place ζ(2)^2 in the denominator rather than the numerator, but this is a calculation/direction error, not a circular reduction, since the claimed guarantee is not obtained by substituting the conclusion into an assumption. I find no significant circularity.

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

No fitted parameters are introduced; all constants are group-theoretic or imported from cited theorems. The main unstated convention is that some moment sums in Section 4 appear to be normalized by |Hom(G,H)| without being labeled. The derivation otherwise rests on standard finite-group facts and several deep prior results on conjugacy classes and quasirandomness.

assumptions (8)

standard math Finite abelian groups decompose into p-components and Hom respects this decomposition (Fact 1.7).
Used in Lemma 3.6 and Theorem 3.10 to reduce cyclic groups to prime powers.
domain assumption Aut(S_n) equals Inn(S_n) for n != 6 (Segal).
Used to test automorphisms of symmetric groups as inner automorphisms in Section 5.2.1.
domain assumption Conjugacy-class zeta function bounds for finite simple groups from [LS05, Cor. 5.1], excluding PSL2(q), PSL3(q), PSU3(q).
Used for the non-abelian finite simple group inner-automorphism test; imported from deep prior literature.
domain assumption Landazuri-Seitz quasirandomness degrees for bounded-rank simple groups of Lie type ([LS74]).
Gives the c(r) constant used in Claim 5.17 for quasirandom groups.
domain assumption Extraspecial p-groups have p conjugacy classes of size 1 and p^(r-1)-1 classes of size p ([Pan04, Prop. 7.1]).
Gives the exact rho_tilde_k bound in Corollary 5.21.
standard math Homomorphisms from a group G to an abelian group H factor through G/[G,G] (Fact 6.4).
Basis of the lifting tests and all character-testing results.
standard math Binomial identity Fact 4.6.
Used to collapse the binomial expansion in Corollary 4.7.
domain assumption Checking membership in Im(Gamma_x) and sampling from the kernel-weighted distribution is assumed feasible for the studied families.
The paper explicitly defers efficient implementation details in Remark 5.9, so the tests are analyzed only at the level of query complexity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A General Framework for Low Soundness Homomorphism Testing." pith.science (2026). https://pith.science/paper/SFBRTER4

@misc{pith2026250905871,
  author       = {Pith},
  title        = {Pith review of: A General Framework for Low Soundness Homomorphism Testing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SFBRTER4}},
  note         = {Machine review of arXiv:2509.05871}
}

abstract

We introduce a general framework to design and analyze algorithms for the problem of testing homomorphisms between finite groups in the low-soundness regime. In this regime, we give the first constant-query tests for various families of groups. These include tests for: (i) homomorphisms between arbitrary cyclic groups, (ii) homomorphisms between any finite group and $\mathbb{Z}_p$, (iii) automorphisms of dihedral and symmetric groups, (iv) inner automorphisms of non-abelian finite simple groups and extraspecial groups, and (v) testing linear characters of $\mathrm{GL}_n(\mathbb{F}_q)$, and finite-dimensional Lie algebras over $\mathbb{F}_q$. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between $\mathbb{F}_q^n$ and $\mathbb{F}_q$. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as $\mathbb{F}_q^n$). No tests were known for non-abelian groups. As an additional corollary, our framework gives combinatorial list decoding bounds for cyclic groups with list size dependence of $O(\varepsilon^{-2})$ (for agreement parameter $\varepsilon$). This improves upon the currently best-known bound of $O(\varepsilon^{-105})$ due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14].

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 8 canonical work pages

[7]

Quasirandom groups

arXiv:0710.3877, doi:10.1017/ S0963548307008826. 29 [GS14] Alan Guo and Madhu Sudan. List Decoding Group Homomorphisms Between Supersolvable Groups. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM),

work page Pith review arXiv
[9]

28 [ISS07] Gábor Ivanyos, Luc Sanselme, and Miklos Santha

URL:https://mathoverflow.net/q/162275 (version: 2014-04-03). 28 [ISS07] Gábor Ivanyos, Luc Sanselme, and Miklos Santha. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. InPro- ceedings of the 24th Annual Conference on Theoretical Aspects of Computer Sci- ence, STACS’07, page 586–597, Berlin, Heidelberg,

work page 2014
[10]

An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups

Springer-Verlag. arXiv:quant-ph/0701235. 30 [JNV+21] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE.Commun. ACM, 64(11):131–138,

work page Pith review arXiv
[12]

1, 2, 3, 4, 19 [LS74] Vicente Landazuri and Gary M Seitz

doi:10.1016/S0304-3975(02) 00816-2. 1, 2, 3, 4, 19 [LS74] Vicente Landazuri and Gary M Seitz. On the minimal degrees of projective representations of the finite chevalley groups.Journal of Algebra, 32(2):418–443, 1974.doi:10.1016/0021-8693(74)90150-1. 30 [LS05] Martin W. Liebeck and Aner Shalev. Character degrees and random walks in finite groups of Lie t...

doi:10.1016/s0304-3975(02 1974
[2003]

5 [BK21] Amey Bhangale and Subhash Khot

Manuscript. 5 [BK21] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. InProceedings of the 53rd ACM Symposium on Theory of Computing, 2021.doi:10.1145/3406325.3451003. 1 [BLR90] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. InProceedings of the 22...

arXiv 2021
[2006]

2 [Gop13] Parikshit Gopalan

doi: 10.1007/11830924\_35. 2 [Gop13] Parikshit Gopalan. A Fourier-Analytic Approach to Reed-Muller Decoding. IEEE Trans. Inf. Theory, 59(11):7747–7760,

doi:10.1007/11830924
[2007]

1, 2 [BSVW03] Eli Ben-Sasson, Madhu Sudan, Salil P

doi:10.1002/rsa.20182. 1, 2 [BSVW03] Eli Ben-Sasson, Madhu Sudan, Salil P . Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via ε-biased sets. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 612–621, 2003.doi:10.1145/780542.780631. 1 [Cha10] Robin Chapman. Image of a fixed element under a random endom...

arXiv
[2008]

3 [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson

doi:10.1145/1374376.1374418. 3 [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. InApproximation, Randomization, and Combinatorial Op- timization. Algorithms and Techniques, pages 304–315. Springer Berlin Heidelberg, 2006.doi:10.1007/11830924_29. 6 [GGMT23] W. T. Gowers, Ben Green, Freddie Manne...

arXiv

Show all 15 references

[2010]

7 [DGKS08] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan

URL:https://mathoverflow.net/q/30378 (version: 2010-07-04). 7 [DGKS08] Irit Dinur, Elena Grigorescu, Swastik Kopparty, and Madhu Sudan. Decod- ability of group homomorphisms beyond the Johnson bound. InProceed- ings of the 40th ACM Symposium on Theory of Computing, pages 275–284,

2010
[2012]

1 [Seg40] Irving E

arXiv:1011.0107,doi:10.2140/apde.2012.5.627. 1 [Seg40] Irving E. Segal. The automorphisms of the symmetric group.Bull. Am. Math. Soc., 46:565, 1940.doi:10.1090/S0002-9904-1940-07261-1. 4 39

2012 arXiv
[2013]

doi:10.1109/TIT.2013. 2274007. 2 [Gow08] W. T. Gowers. Quasirandom Groups.Combinatorics, Probability and Com- puting, 17(3):363–387, May

2013 doi
[2014]

4230/LIPIcs.APPROX-RANDOM.2014.737

doi:10. 4230/LIPIcs.APPROX-RANDOM.2014.737. 3 [HW03] Johan Håstad and Avi Wigderson. Simple analysis of graph tests for linearity and PCP.Random Structures & Algorithms, 22(2):139–160,

2014
[2015]

5 [MR24] Tushant Mittal and Sourya Roy

arXiv:1009.6230, doi:10.1137/140958578. 5 [MR24] Tushant Mittal and Sourya Roy. Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime, 2024.arXiv:2405.18998. 5 [NV17] Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglemen...

2024 arXiv
[2016]

5 [Pan04] Casian Alexandru Pantea

arXiv: 1509.00930,doi:10.1002/rsa.20639. 5 [Pan04] Casian Alexandru Pantea. On the number of conjugacy classes of finite p- groups.Mathematica (Cluj), 46 (69)(2):193–203,

arXiv
[2021]

1 [Kiw03] M

doi:10.1145/3485628. 1 [Kiw03] M. Kiwi. Algebraic testing and weight distributions of codes.Theoreti- cal Computer Science, 299(1):81–106,

doi

Pith tools

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

[1] [7]

Quasirandom groups

arXiv:0710.3877, doi:10.1017/ S0963548307008826. 29 [GS14] Alan Guo and Madhu Sudan. List Decoding Group Homomorphisms Between Supersolvable Groups. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM),

work page Pith review arXiv

[2] [9]

28 [ISS07] Gábor Ivanyos, Luc Sanselme, and Miklos Santha

URL:https://mathoverflow.net/q/162275 (version: 2014-04-03). 28 [ISS07] Gábor Ivanyos, Luc Sanselme, and Miklos Santha. An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups. InPro- ceedings of the 24th Annual Conference on Theoretical Aspects of Computer Sci- ence, STACS’07, page 586–597, Berlin, Heidelberg,

work page 2014

[3] [10]

An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups

Springer-Verlag. arXiv:quant-ph/0701235. 30 [JNV+21] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE.Commun. ACM, 64(11):131–138,

work page Pith review arXiv

[4] [12]

1, 2, 3, 4, 19 [LS74] Vicente Landazuri and Gary M Seitz

doi:10.1016/S0304-3975(02) 00816-2. 1, 2, 3, 4, 19 [LS74] Vicente Landazuri and Gary M Seitz. On the minimal degrees of projective representations of the finite chevalley groups.Journal of Algebra, 32(2):418–443, 1974.doi:10.1016/0021-8693(74)90150-1. 30 [LS05] Martin W. Liebeck and Aner Shalev. Character degrees and random walks in finite groups of Lie t...

doi:10.1016/s0304-3975(02 1974

[5] [2003]

5 [BK21] Amey Bhangale and Subhash Khot

Manuscript. 5 [BK21] Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. InProceedings of the 53rd ACM Symposium on Theory of Computing, 2021.doi:10.1145/3406325.3451003. 1 [BLR90] M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. InProceedings of the 22...

arXiv 2021

[6] [2006]

2 [Gop13] Parikshit Gopalan

doi: 10.1007/11830924\_35. 2 [Gop13] Parikshit Gopalan. A Fourier-Analytic Approach to Reed-Muller Decoding. IEEE Trans. Inf. Theory, 59(11):7747–7760,

doi:10.1007/11830924

[7] [2007]

1, 2 [BSVW03] Eli Ben-Sasson, Madhu Sudan, Salil P

doi:10.1002/rsa.20182. 1, 2 [BSVW03] Eli Ben-Sasson, Madhu Sudan, Salil P . Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCPs via ε-biased sets. In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 612–621, 2003.doi:10.1145/780542.780631. 1 [Cha10] Robin Chapman. Image of a fixed element under a random endom...

arXiv

[8] [2008]

3 [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson

doi:10.1145/1374376.1374418. 3 [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson. Robust local testability of tensor products of LDPC codes. InApproximation, Randomization, and Combinatorial Op- timization. Algorithms and Techniques, pages 304–315. Springer Berlin Heidelberg, 2006.doi:10.1007/11830924_29. 6 [GGMT23] W. T. Gowers, Ben Green, Freddie Manne...

arXiv