expositions

A Way to Visualize the Sumcheck Protocol and Some of its Extensions

The point of this text is to share a simple visualization that helps me imagine the celebrated sumcheck protocol of Lund, Fortnow, Karloff, and Nisan (1992). The visualization also facilitates understanding two extensions of the protocol: A stronger property called batchability that the protocol can support, and the more general interactive proof of Goldwasser, Kalai and Rothblum (2015).

Cook’s Proof of the Non-deterministic Time Hierarchy Theorem

The first proof of a non-deterministic time hierarchy theorem, by Cook (1973), is not typically taught in textbooks and courses, since subsequent proofs are simpler and yield better results. Nevertheless, the proof is interesting and based on a very natural idea. In this text I describe it.

On implications of better sub-exponential lower bounds for AC0

Lower bounds for AC0 circuits of sub-exponential size have been known since the ‘80s. The point of this text is to highlight the (known) fact that lower bounds for AC0 circuits of significantly larger sub-exponential size imply lower bounds for polynomial-sized circuits from circuit classes such as AC0[Sym], linear threshold circuits of constant depth, and NC1.

Karp-Lipton theorems: Translating non-uniform "collapses" into uniform "collapses"

Assume that there exists an infinite sequence of small circuits, one for each input length, that solves some “hard” problem. Can we use this fact to construct a single efficient algorithm that solves some (possibly different) “hard” problem on all input lengths? This is the technical question that underlies many results that are typically referred to as “Karp-Lipton theorems”, following the classic result in this spirit by Karp and Lipton (1980). My goal in this text is to describe the various ideas that were introduced over the years to try and answer the question.

Non-trivial derandomization implies weak lower bounds: An (almost) elementary proof

Ryan Williams' fundamental result asserts that any non-trivial derandomization of a circuit class C implies weak lower bounds for C. This text presents an alternative (known) argument, in which C is separated from the class E^{NP} (rather than from the class NEXP, as in the original result). The proof is short, almost completely self-contained, and applies to more classes C than the original result. 

The Bazzi-Razborov-Braverman Theorems: Polylogarithmic Independence Fools AC0

A step-by-step review of the proof that polylog-wise independent distributions fool AC0. The text starts from Bazzi's proof framework, and tries to articulate exactly what we need (and are trying to do) in each step, while abstracting some general parts of the proof. The presentation of Braverman's proof is somewhat non-standard, relying on the notion of randomized tests.

Overview of the lower bound of Li, Razborov, and Rossman for subgraph isomorphism in AC0

An interesting line of research in low-level complexity in the last decade deals with polynomial lower bounds for circuits of small depth solving subgraph isomorphism. Since the problem is NP-complete, the hope is that these lower bounds can be extended to large classes (e.g., to NC1). The text is an overview of a key result in this context, and is intended to be as simple and self-contained as possible.

Linear interpolation of polynomials on lines

Multilinear and low-degree extensions 

Instance checkers 

Consistent normalizations when working with Fourier 

Manifolds and varieties 

Every function F_{q^n} -> F_q is a sum of monomial traces