In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Isomorphism: namely, we show that every family of depth-$2$ Boolean circuits deciding Group Isomorphism requires quasipolynomial-size. We complement this with upper bounds of ... more >>>

We provide a deterministic polynomial-time list decoding algorithm for Reed-Solomon codes over prime fields that approaches list decoding capacity on every evaluation set in the low (constant) rate regime.

more >>>

This work studies super-Ramanujan graphs: \(d\)-regular graphs whose spectral expansion lies strictly below the Ramanujan threshold \(2\sqrt{d-1}\). Although this threshold is asymptotically optimal for fixed \(d\) as \(n\) tends to infinity, it leaves open the finer question of how small the spectral expansion can be as a joint function of ... more >>>