Tushant Mittal

activity

20172026

collaborators

11 papers

cs.IT2026

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani +1

We show that for any $R, ε > 0$ and any prime $p \geq 2$ , there exists an infinite family of $p$ -ary quantum low-density parity-check (QLDPC) codes, rate $R$ , checks of weight $O_{ε} (1)$ …

cs.CC2026

Low Soundness Linearity Testing on the Half-Slice

Haakon Larsen, Tushant Mittal, Silas Richelson +1

Let $f : T \to {0, 1}$ be a Boolean function on the Boolean half-slice, $T$ , \ie elements of ${0, 1}^{n}$ with Hamming weight $n /2$ . We show that if $f (x) + f (y) = f (x + y)$ holds with p…

cs.CC2025

A General Framework for Low Soundness Homomorphism Testing

Tushant Mittal, Sourya Roy

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 giv…

cs.CC2025

Pseudorandomness of Expander Walks via Fourier Analysis on Groups

Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy

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 $Σ$ , and study the mean of…

cs.IT2025

Explicit Codes approaching Generalized Singleton Bound using Expanders

Fernando Granha Jeronimo, Tushant Mittal, Shashank Srivastava +1

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of $O (\frac{1}{ε})$ . In contrast to existing explicit constructions o…

cs.IT2024

List Decodable Quantum LDPC Codes

Thiago Bergamaschi, Fernando Granha Jeronimo, Tushant Mittal +2

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…

cs.CC2024

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime

Tushant Mittal, Sourya Roy

We give a randomness-efficient homomorphism test in the low soundness regime for functions, $f : G \to U_{t}$ , from an arbitrary finite group $G$ to $t \times t$ unitary matric…

cs.DS2022

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification

Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy +1

We give an efficient algorithm that transforms any bounded degree expander graph into another that achieves almost optimal (namely, near-quadratic, $d \leq 1/ λ^{2 + o (1)}$ ) trade-off…

cs.DS2021

Explicit Abelian Lifts and Quantum LDPC Codes

Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell +2

For an abelian group $H$ acting on the set $[ℓ]$ , an $(H, ℓ)$ -lift of a graph $G_{0}$ is a graph obtained by replacing each vertex by $ℓ$ copies, and each edge by a matching…

cs.CC2021

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

Gábor Ivanyos, Tushant Mittal, Youming Qiao

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 ra…

math.NT2017

The Mahler measure for arbitrary tori

Matilde Lalin, Tushant Mittal

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 t…