Space proof complexity for random 3-CNFs

The main technical innovation is a variant of Hall's Lemma. We show that in bipartite graphs with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of (2−ϵ), for ϵ<15.