Pseudorandomness Reading Group

In our introductory meeting, we briefly went over the possible avenues to explore. We discussed list recovery in the pseudorandomness regime, epsilon-balanced codes near the GV bound, the use of codes in derandomization, in lower bounds, and various related pseudorandomness primitives such as subspace designs and subspace evasive sets.

Topic: List recoverable codes, condensers, and the GUV construction

We talked about the equivalence between list recovery (from errors) and seeded condensers. We also mentioned the lossless case, which corresponds to same-list list recovery.

In the series of our explicit constrictions, we went over the "folded Reed—Solomon"-based construction by Guruswami, Umans, and Vadhan (GUV), and established their list recoverability parameters in the pseudorandomness regime. To get lossless condensers, GUV use Parvaresh–Vardy codes, but the analysis is very similar. You can find it (and the rest as well) in João's notes. https://drive.google.com/file/d/1-8VuBOG0B4MyxqctWHdQBeIh7e5qFpgh/view?usp=sharing

Topic: The Ta-Shma—Umans Condenser

Today we talked about the Ta-Shma—Umans condenser, which has better entropy gap than the GUV condensers we saw in the last meeting (or, in the list recovery terminology, the dependence between the alphabet size and the input list size is better).

In terms of techniques, we talked about the use of “covering curves”, and the polynomial-method analysis that involved multiplicities. 

See Zeyu’s notes here: https://drive.google.com/file/d/1Y9ifuzlo1wuWJBNpL8iGOEIbIGTWXIV8/view?usp=sharing

Topic: Condensers from Multiplicity Codes

Speaker: Omar Alrabiah

Continuing our study of condensers from error correcting codes, we talked about

the paper "Unbalanced Expanders from Multiplicity Codes", by Kalev and Ta-Shma, which achieves 

the (lossless) GUV parameters with univariate multiplicity codes. In particular, we covered the new "root finding" step of their polynomial method invocation. 

See Omar's notes here: https://drive.google.com/file/d/14ORNeA-DtlErcrwxJ71UIdLfSbQuOTJW/view?usp=sharing

Speaker: Izzy Meckler

Topic: The Guruswami—Wang algorithm for list recovery of multiplicity codes

The meeting was postponed. We were supposed to talk about the GW algorithm, adapted to list recovery in the "coding" regime (https://arxiv.org/abs/1106.0436), following our discussion about list recovery of multiplicity codes in the pseudorandomness regime.

Speakers: S. Venkitesh and Prahladh Harsha

Topic: Improving list decoding and list recovery bounds by pruning

Today we discussed "output list pruning", which allows us to get better output list bounds for codes whose list decoding/recovery algorithms return linear subspaces (so basically, Folded RS and multiplicity codes, via the Guruswami—Wang algorithm). 

We discussed the pruning algorithm of Kopparty, Ron-Zewi, Saraf, and Wootters (https://arxiv.org/pdf/1805.01498.pdf), and the improvement by Tamo (https://arxiv.org/abs/2312.17097).

Topic: Avoiding Subspaces

Today we talked about the (pseudorandom) objects of subspace designs and subspace-evasive sets, and their uses in coding theory.

In terms of explicit constructions, we described the Dvir-Lovett constructions of subspace-evasive sets, and the Folded RS based construction of subspace designs.

You can see it all (and much more!) in Nic's notes: https://drive.google.com/file/d/1cu2mDEqK6kdNs5-CfITXU_9SH5OcW-kZ/view?usp=sharing 

Speaker: S. Venkitesh

Topic: Efficient Decoding of Ta-Shma Codes via Splittable Regularity 

After a brief reminder of Ta-Shma codes via the framework of parity samplers, we presented the notion of splittable regularity.
We then presented the “decoding via splittable regularity” framework of Jeronimo, Srivastava, and Tulsiani, and applied it on Ta-Shma codes, following this paper: https://granha.github.io/doc/regularity_decoding.pdf