DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2026.103

A General Framework for Low Soundness Homomorphism Testing

Authors: Tushant Mittal and Sourya Roy

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

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 ℤ_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 GL_n(F_q), and finite-dimensional Lie algebras over F_q. We also recover the result of Kiwi [TCS'03] for testing homomorphisms between F_qⁿ and F_q. Prior to this work, such tests were only known for abelian groups with a constant maximal order (such as F_qⁿ). 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(ε^{-2}) (for agreement parameter ε). This improves upon the currently best-known bound of O(ε^{-105}) due to Dinur, Grigorescu, Kopparty, and Sudan [STOC'08], and Guo and Sudan [RANDOM'14].

Cite as

Tushant Mittal and Sourya Roy. A General Framework for Low Soundness Homomorphism Testing. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 103:1-103:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mittal_et_al:LIPIcs.ITCS.2026.103,
  author =	{Mittal, Tushant and Roy, Sourya},
  title =	{{A General Framework for Low Soundness Homomorphism Testing}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{103:1--103:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.103},
  URN =		{urn:nbn:de:0030-drops-253901},
  doi =		{10.4230/LIPIcs.ITCS.2026.103},
  annote =	{Keywords: Property Testing, Coding Theory}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.49

Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Authors: Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

A long line of work has studied the pseudorandomness properties of walks on expander graphs. A central goal is to measure how closely the distribution over n-length walks on an expander approximates the uniform distribution of n-independent elements. One approach to do so is to label the vertices of an expander with elements from an alphabet Σ, and study closeness of the mean of functions over Σⁿ, under these two distributions. We say expander walks ε-fool a function if the expander walk mean is ε-close to the true mean. There has been a sequence of works studying this question for various functions, such as the XOR function, the AND function, etc. We show that: - The class of symmetric functions is O(|Σ|λ)-fooled by expander walks over any generic λ-expander, and any alphabet Σ . This generalizes the result of Cohen, Peri, Ta-Shma [STOC'21] which analyzes it for |Σ| = 2, and exponentially improves the previous bound of O(|Σ|^O(|Σ|) λ), by Golowich and Vadhan [CCC'22]. Moreover, if the expander is a Cayley graph over ℤ_|Σ|, we get a further improved bound of O(√{|Σ|} λ). Morever, when Σ is a finite group G, we show the following for functions over Gⁿ: - The class of symmetric class functions is O({√|G|}/D λ}-fooled by expander walks over "structured" λ-expanders, if G is D-quasirandom. - We show a lower bound of Ω(λ) for symmetric functions for any finite group G (even for "structured" λ-expanders). - We study the Fourier spectrum of a class of non-symmetric functions arising from word maps, and show that they are exponentially fooled by expander walks. Our proof employs Fourier analysis over general groups, which contrasts with earlier works that have studied either the case of ℤ₂ or ℤ. This enables us to get quantitatively better bounds even for unstructured sets.

Cite as

Fernando Granha Jeronimo, Tushant Mittal, and Sourya Roy. Pseudorandomness of Expander Walks via Fourier Analysis on Groups. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jeronimo_et_al:LIPIcs.APPROX/RANDOM.2025.49,
  author =	{Jeronimo, Fernando Granha and Mittal, Tushant and Roy, Sourya},
  title =	{{Pseudorandomness of Expander Walks via Fourier Analysis on Groups}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.49},
  URN =		{urn:nbn:de:0030-drops-244157},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.49},
  annote =	{Keywords: Expander graphs, pseudorandomness}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2022.20

Mixing of 3-Term Progressions in Quasirandom Groups

Authors: Amey Bhangale, Prahladh Harsha, and Sourya Roy

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

In this paper, we show the mixing of three-term progressions (x, xg, xg²) in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any D-quasirandom group G and any three sets A₁, A₂, A₃ ⊂ G, we have |Pr_{x,y∼ G}[x ∈ A₁, xy ∈ A₂, xy² ∈ A₃] - ∏_{i = 1}³ Pr_{x∼ G}[x ∈ A_i]| ≤ (2/(√{D)})^{1/4}. Prior to this, Tao answered this question when the underlying quasirandom group is SL_{d}(𝔽_q). Subsequently, Peluse extended the result to all non-abelian finite simple groups. In this work, we show that a slight modification of Peluse’s argument is sufficient to fully resolve Gowers' quasirandom conjecture for 3-term progressions. Surprisingly, unlike the proofs of Tao and Peluse, our proof is elementary and only uses basic facts from non-abelian Fourier analysis.

Cite as

Amey Bhangale, Prahladh Harsha, and Sourya Roy. Mixing of 3-Term Progressions in Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 20:1-20:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.20,
  author =	{Bhangale, Amey and Harsha, Prahladh and Roy, Sourya},
  title =	{{Mixing of 3-Term Progressions in Quasirandom Groups}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{20:1--20:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.20},
  URN =		{urn:nbn:de:0030-drops-156163},
  doi =		{10.4230/LIPIcs.ITCS.2022.20},
  annote =	{Keywords: Quasirandom groups, 3-term arithmetic progressions}
}

Search Results

Documents authored by Roy, Sourya

A General Framework for Low Soundness Homomorphism Testing

Abstract

Cite as

Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Abstract

Cite as

Mixing of 3-Term Progressions in Quasirandom Groups

Abstract

Cite as

Thanks for your feedback!

Could not send message