In this paper, we present a new construction of simplicial complexes of subpolynomial degree with arbitrarily good local spectral expansion. Previously, the only known high-dimensional expanders (HDXs) with arbitrarily good expansion and less than polynomial degree were based on one of two constructions, namely Ramanujan complexes and coset complexes. ... more >>>

We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error ... more >>>

The width complexity measure plays a central role in Resolution and other propositional proof systems like Polynomial Calculus (under the name of degree). The study of width lower bounds is the most extended method for proving size lower bounds, and it is known that for these systems, proofs with small ... more >>>