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.

  @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},
  url =		{https://drops.dagstuhl.de/opus/volltexte/2022/15684},
  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.

  @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).

  @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)\).