< Home

Seminar: Circuit Lower Bounds

Schedule

Friday 1:30 pm --- 4:30 pm, every two weeks
Offline meetings preferred, along with Zoom
Locations for offline meetings will be notified in the future.
  • Feb 2, Xinyu: [MW19]
  • Feb 16, Guangxu: [JS10]
  • Mar 1, Miryam
  • Mar 22, Guangxu
  • Apr 5, Chandra
  • Apr 19, Devansh

    • Materials

  • [GRSS23] Top-Down Lower Bounds for Depth-Four Circuits
  • [MW19] Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds
  • [HJP93] Top-Down Lower Bounds for Depth-Three Circuits
  • [Williams11] Non-Uniform ACC Circuit Lower Bounds
  • [JS10] Circuits with Arbitrary Gates for Random Operators
  • [Dru12] Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators
  • [Rosenthal21] Bounds on the QAC0 Complexity of Approximating Parity
  • [NPVY23, preprint] On the Pauli Spectrum of QAC0
    •