#Lower-Bounds

2 posts in tag “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.