Tushant Mittal

About

A theory CS postdoc (Motwani Fellow) at Stanford University hosted by Mary Wootters and Tselil Schramm. I obtained my Ph.D. at the University of Chicago, where I was extremely fortunate to be advised by Madhur Tulsiani and Janos Simon. My interest in algebra took root at IIT Kanpur where I did my undergrad.

Research interests include pseudorandomness, (high-dimensional) expansion, quantum error correction, and anything sufficiently seasoned with algebra!
CV
Preprints
Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime

Joint work with Sourya Roy.
arXiv Abstract BibTeX
```
@misc{MR24,
      title={{Derandomized Non-Abelian Homomorphism Testing 
        in Low Soundness Regime}}, 
      author={Tushant Mittal and Sourya Roy},
      year={2024},
      eprint={2405.18998}
    }
    
```
We give a randomness-efficient homomorphism test in the low soundness regime for functions, $f:G\to \mathbb{U}_t$, from an arbitrary finite group $G$ to $t \times t$ unitary matrices. We show that if such a function passes a derandomized Blum–Luby–Rubinfeld (BLR) test (using small-bias sets), then (i) it correlates with a function arising from a genuine homomorphism, and (ii) it has a non-trivial Fourier mass on a low-dimensional irreducible representation.

In the full randomness regime, such a test for matrix-valued functions on finite groups implicitly appears in the works of Gowers and Hatami [Sbornik: Mathematics '17], and Moore and Russell [SIAM Journal on Discrete Mathematics '15]. Thus, our work can be seen as a near-optimal derandomization of their results. Our key technical contribution is a "degree-2 expander mixing lemma'' that shows that Gowers' $U^2$ norm can be efficiently estimated by restricting it to a small-bias subset. Another corollary is a "derandomized'' version of a useful lemma due to Babai, Nikolov, and Pyber [SODA'08] and Gowers [Comb. Probab. Comput.'08].
Research Publications
A General Framework for Low Soundess Homomorphism Testing

ITCS'26.

Joint work with Sourya Roy.
arXiv Video Abstract BibTeX
```
@misc{MR25,
      title={{A General Framework for Low Soundness Homomorphism Testing}}, 
      author={Tushant Mittal and Sourya Roy},
      year={2025},
      eprint={2509.05871}
    }
    
```
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 $ \mathsf{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].
Pseudorandomness of Expander Walks via Fourier Analysis on Groups

RANDOM'25.

Joint work with Fernando G. Jeronimo and Sourya Roy.
arXiv Abstract BibTeX
```
@InProceedings{JMR25,
  author =	{Jeronimo, Fernando Granha and 
    Mittal, Tushant  and Roy, Sourya},
  title =	{{Pseudorandomness of Expander Walks via
     Fourier Analysis on Groups}},
  booktitle =	{29th International Conference on
     Randomization and Computation (RANDOM)},
  year =	{2025},
  eprint = {2507.14445},
	doi = {10.4230/LIPIcs.APPROX/RANDOM.2025.49}
}
    
```
One approach to study the pseudorandomness properties of walks on expander graphs is to label the vertices of an expander with elements from an alphabet $\Sigma$, and study the mean of functions over $\Sigma^n$. We say expander walks $\varepsilon$-fool a function if, for any unbiased labeling of the vertices, the expander walk mean is $\varepsilon$-close to the true mean. We show that:
- The class of symmetric functions is $O(|\Sigma|\cdot\lambda)$-fooled by expander walks over any generic $\lambda$-expander, and any alphabet $\Sigma$ . This generalizes the result of Cohen, Peri, Ta-Shma [STOC'21] which analyzes it for $ |\Sigma| = 2$, and exponentially improves the previous bound of $ O(|\Sigma|^{O(|\Sigma|)}\cdot \lambda ) $, by Golowich and Vadhan [CCC'22]. Additionally, if the expander is a Cayley graph over $\mathbb{Z}_{|\Sigma|}$, we get a further improved bound of $O(\sqrt{|\Sigma|}\cdot\lambda)$.
Explicit Codes approaching Generalized Singleton Bound using Expanders

STOC'25 (Invited to Special Issue).

Joint work with Fernando G. Jeronimo, Shashank Srivastava, and Madhur Tulsiani.
arXiv Video (Madhur) Abstract BibTeX
```
@inproceedings{JMST25,
author = {Jeronimo, Fernando Granha and Mittal, Tushant 
  and Srivastava, Shashank and Tulsiani, Madhur},
title = {{Explicit Codes Approaching Generalized Singleton Bound 
  using Expanders}},
year = {2025},
doi = {10.1145/3717823.3718302},
booktitle = {Proceedings of the 57th Annual ACM 
  Symposium on Theory of Computing (STOC)},
eprint = {2502.07308}
}
    
```
We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of $O(\frac{1}{\varepsilon})$. In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs.
Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS'95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a "local-to-global" phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every $R, \varepsilon \in (0,1)$ and $k \in \mathbb{N}^+$, we obtain an explicit family of codes $ C \subseteq \Sigma^n $, with rate $R$ such that,
- They achieve the $\varepsilon$-relaxed generalized Singleton bound: for any $g \in \Sigma^n $ and any list $H$ of at most $k$ codewords, we have, $ \mathbb{E}_{h \in H}[\Delta(g,h)] ~\geq~ \frac{|H|-1}{|H|} \cdot (1-R-\varepsilon) $.
- The alphabet size is a constant depending only on $\varepsilon$ and $k$.
- They can be list decoded up to radius $\frac{k-1}{k}(1-R-\varepsilon)$, in time $n^{O_{k,\varepsilon}(1)}$.
As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.
List Decodable Quantum LDPC Codes

QIP'25 (Poster).

Joint work with Thiago Bergamaschi, Fernando G. Jeronimo, Shashank Srivastava, and Madhur Tulsiani.
arXiv Poster Abstract BibTeX
```
@misc{BJMST25,
  title = {{List Decodable Quantum LDPC Codes}},
  author = {Bergamaschi, Thiago and Jeronimo, Fernando Granha and 
    Mittal, Tushant and Srivastava, Shashank and Tulsiani, Madhur },
  year = {2025},
  note = {Quantum Information Processing (QIP) 2025 (Poster).},
  eprint = {2411.04306}
}
    
```
We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property.

Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes.
Expanders with Symmetry: Constructions and Applications

Ph.D. Dissertation, 2024
UChicago Repository Dissertation
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

FOCS'22, SICOMP'24 (Special Issue)

Joint work with Fernando G. Jeronimo, Sourya Roy, Avi Wigderson.
arXiv Conference Video Abstract BibTeX
```
  @inproceedings {JMRW22,
    author = {Jeronimo, Fernando Granha and
        Mittal, Tushant  and Roy, Sourya and Wigderson, Avi},
    booktitle = 
    {Proceedings of the 63rd IEEE 
      Symposium on Foundations of Computer Science},
    title = {Almost {R}amanujan {E}xpanders from
      {A}rbitrary {E}xpanders via {O}perator {A}mplification},
    year = {2022},
    doi = {10.1109/FOCS54457.2022.00043},
    eprint    = {2209.07024},
    }
    
```
We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/\lambda^{2+o(1)}$ ) trade-off between (any desired) spectral expansion $\lambda$ and degree $d$. Furthermore, the algorithm is local: every vertex can compute its new neighbors as a subset of its original neighborhood of radius $O(\log(1/\lambda))$. The optimal quadratic trade-off is known as the Ramanujan bound, so our construction gives almost Ramanujan expanders from arbitrary expanders.

The locality of the transformation preserves structural properties of the original graph, and thus has many consequences. Applied to Cayley graphs, our transformation shows that any expanding finite group has almost Ramanujan expanding generators. Similarly, one can obtain almost optimal explicit constructions of quantum expanders, dimension expanders, monotone expanders, etc., from existing (suboptimal) constructions of such objects. Another consequence is a "derandomized" random walk on the original (suboptimal) expander with almost optimal convergence rate. Our transformation also applies when the degree is not bounded or the expansion is not constant.

We obtain our results by a generalization of Ta-Shma's technique in his breakthrough paper [STOC 2017], used to obtain explicit almost optimal binary codes. Specifically, our spectral amplification extends Ta-Shma's analysis of bias amplification from scalars to matrices of arbitrary dimension in a very natural way. Curiously, while Ta-Shma's explicit bias amplification derandomizes a well-known probabilistic argument (underlying the Gilbert-Varshamov bound), there seems to be no known probabilistic (or other existential) way of achieving our explicit (``high-dimensional") spectral amplification.
Explicit Abelian Lifts and Quantum LDPC Codes

ITCS'22

Joint work with Fernando G. Jeronimo, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani.
arXiv Video Abstract BibTeX
```
  @InProceedings{JMOPT22,
  author =	{Jeronimo, Fernando Granha and 
    Mittal, Tushant  and
              O'Donnell, Ryan and Paredes, Pedro and 
              Tulsiani, Madhur},
  title =	{{Explicit Abelian Lifts and 
    Quantum LDPC Codes}},
  booktitle =	{13th Innovations in Theoretical 
    Computer Science
                Conference (ITCS 2022)},
  year =	{2022},
  volume =	{215},
  publisher =	{Schloss Dagstuhl -- 
    Leibniz-Zentrum f{\"u}r Informatik},
  doi =		{10.4230/LIPIcs.ITCS.2022.88},
  eprint =      {2112.01647}
  }
            
```
For an abelian group $H$ acting on the set $[\ell]$, an $ (H,\ell) $-lift of a graph $G_0 $ is a graph obtained by replacing each vertex by $\ell$ copies, and each edge by a matching corresponding to the action of an element of $H$.

Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance $\widetilde{\Omega}(N^{3/5})$, and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance $\Omega(N/\log(N))$.

However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019].

In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group $H \leqslant \mathrm{Sym}(\ell)$, constant degree $d \ge 3$ and $\epsilon > 0$, we construct explicit $d$-regular expander graphs $G$ obtained from an $(H,\ell)$-lift of a (suitable) base $n$-vertex expander $G_0$ with the following parameters:
- (i) $\lambda(G) \le 2\sqrt{d-1} + \epsilon$, for any lift size $\ell \le 2^{n^{\delta}}$ where $\delta=\delta(d,\epsilon)$,
- (ii) $\lambda(G) \le \epsilon \cdot d$, for any lift size $\ell \le 2^{n^{\delta_0}}$ for a fixed $\delta_0 > 0$, when $d \ge d_0(\epsilon)$, or
- (iii) $\lambda(G) \le \widetilde{O}(\sqrt{d})$, for lift size ``exactly'' $\ell = 2^{\Theta(n)}$.
As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes.

Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for $2$-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result $(iii)$ is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.
Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras

ITCS'22

Joint work with Gábor Ivanyos and Youming Qiao.
arXiv Video Abstract BibTeX
```
  @InProceedings{IMQ22,
    author =	{Ivanyos, G\'{a}bor and Mittal, Tushant and Qiao,
                Youming},
    title =	{{Symbolic Determinant Identity Testing and
                Non-Commutative Ranks of Matrix Lie Algebras}},
    booktitle =	{13th Innovations in Theoretical Computer Science
                  Conference (ITCS 2022)},
    year =	{2022},
    volume =	{215},
    publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    url =	{https://drops.dagstuhl.de/opus/volltexte/2022/15683},
    doi =	{10.4230/LIPIcs.ITCS.2022.87},
    eprint =    {2109.06403}
}
            
```
One approach to make progress on the symbolic determinant identity testing (SDIT) problem is to study the structure of singular matrix spaces. After settling the non-commutative rank problem (Garg--Gurvits--Oliveira--Wigderson, Found. Comput. Math. 2020; Ivanyos--Qiao--Subrahmanyam, Comput. Complex. 2018), a natural next step is to understand singular matrix spaces whose non-commutative rank is full. At present, examples of such matrix spaces are mostly sporadic, so it is desirable to discover them in a more systematic way.

In this paper, we make a step towards this direction, by studying the family of matrix spaces that are closed under the commutator operation, that is, matrix Lie algebras. On the one hand, we demonstrate that matrix Lie algebras over the complex number field give rise to singular matrix spaces with full non-commutative ranks. On the other hand, we show that SDIT of such spaces can be decided in deterministic polynomial time. Moreover, we give a characterization for the matrix Lie algebras to yield a matrix space possessing singularity certificates as studied by Lovász(B. Braz. Math. Soc., 1989) and Raz and Wigderson (Building Bridges II, 2019).

The Mahler measure for arbitrary tori

Research in Number Theory '18.
Joint work with Matilde Lalín .

arXiv

Abstract

BibTeX

      @article{LM18,
        doi = {10.1007/s40993-018-0112-3},
        url = {https://doi.org/10.1007/s40993-018-0112-3},
        year = {2018},
        month = Mar,
        publisher = {Springer Science and Business Media {LLC}},
        volume = {4},
        number = {2},
        author = {Matilde Lal{\'{\i}}n and Tushant Mittal},
        title = {The Mahler measure for arbitrary tori},
        journal = {Research in Number Theory},
        eprint = {1708.02466}
    }

We consider a variation of the Mahler measure where the defining integral is performed over a more general torus. We focus our investigation on two particular polynomials related to certain elliptic curve $E$ and we establish new formulas for this variation of the Mahler measure in terms of $L'(E,0)$.

Expository articles

Recent surveys and expositions. For a complete list, click here.
Quantum LDPC Codes: An exposition of recent results

My Master's Thesis!
Note - This is a working draft and an update with newer results is coming soon.
HDX — Notes on Trickle-Down and Random Walks

Notes on a pair of lectures by Tali Kaufman at the 2022 Summer School on New tools for optimal mixing of Markov chains: Spectral independence and entropy decay.
Thanks - To Eric and Daniel for proofreading and improving the presentation.
Random Matrix Theory — Matrix (Expander) Chernoff Bound

Notes based on the talks given at the TTIC/UChicago reading group on random matrix theory.
Talks

Slides of the talks given.
Undergrad Projects

Reports and files of the projects undertaken during undergrad.
Credits

This site design is "inspired" (read, completely ripped off) from the blog of Yefim Vedernikoff. The animated 't' was created using the Animated Letters plugin created by Luis Manuel.

About

CV

Preprints

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime

Research Publications

A General Framework for Low Soundess Homomorphism Testing

Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Explicit Codes approaching Generalized Singleton Bound using Expanders

List Decodable Quantum LDPC Codes

Expanders with Symmetry: Constructions and Applications

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

Explicit Abelian Lifts and Quantum LDPC Codes

Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras

The Mahler measure for arbitrary tori

Expository articles

Quantum LDPC Codes: An exposition of recent results

HDX — Notes on Trickle-Down and Random Walks

Random Matrix Theory — Matrix (Expander) Chernoff Bound

Talks

Undergrad Projects

Credits