Day 19

Finished proof of Razborov-Smolensky. Links in Day 18 post.

Kannan's non-constructive proof that Σ^p₂ does not have n^k-size circuit for any constant k.

Links:

• Circuit-size lower bounds and non-reducibility to sparse sets by Ravi Kannan
• Blog post on Kannan's result