CS 6520 - Computational Complexity Fall 2017

Final Day of Class. It's been a good ride. Assignment 4 has been graded and solutions on the resource page. Assignment 5 is due Decemb...

Prefix-free complexity and the universal measure Sections 5 and 6 from my Kolmogorov Complexity survey Lecture notes with more details....

Assignment 5 has been posted and due December 13. Assignment 4 is still being graded but solutions have been posted on the T-Square resour...

Guest lecture by DeVon Ingram on the Sensitivity Conjecture and GKS games. A New Approach to the Sensitivity Conjecture by Justin Gilmer...

The following are polynomial related for any function f:{0,1} n →{0,1}. Decision Tree Complexity (deterministic query complexity) Certif...

Shor's Algorithm  - polynomial-time quantum algorithm for factoring Algorithms for quantum computation: discrete logarithms and facto...

More quantum: Deutsch-Jozsa , Grover and Simon Rapid solution of problems by quantum computation by David Deutsch and Richard Jozsa A ...