Complexity Theory Markus Bläser, Balagopal Komarath

News

Circuit Lower Bounds

Written: 30.01.2020 10:31 Written By: Balagopal Komarath

First lower bound for parity (Random restrictions)

https://wiki.epfl.ch/edicpublic/documents/Candidacy%20exam/Furst%20Saxe%20Sipser%20-%201984%20-%20Parity%20circuits%20and%20the%20polynomial-time%20hierarchy.pdf

 

Razborov's lower bound for MAJORITY (polynomial method)

https://link.springer.com/article/10.1007%2FBF01137685

 

Natural proofs

http://www.mi.ras.ru/~razborov/int.ps



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators