Lower-Bounds

• Circuit Complexity: AC0, NC, P/poly, and the PARITY ∉ AC0 Proof · 2019-09-29

  A rigorous journey through circuit complexity classes—AC0, NC, P/poly—and the landmark result that PARITY cannot be computed by constant-depth polynomial-size circuits.

• Communication Complexity: Yao's Two-Party Model, the Rectangle Method, and Lower Bounds Galore · 2019-08-18

  A deep investigation of communication complexity—the mathematics of information exchange between parties—and its far-reaching implications for circuits, data structures, and streaming.