Day 40

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 December 13. Because of the limited time for grading there will be no extensions and a 1 point/hour late penalty. If you have any other uncompleted assignments they will also be due December 13 for partial credit.

We covered a Kolmogorov complexity version of Robin Moser's proof of the Lovász local lemma.

• A constructive proof of the Lovász local lemma by Robin Moser
• A Kolmogorov Complexity Proof of the Lovász Local Lemma (My blog post)

Hope you enjoyed the class and may all your lives be complete!

Day 39

Prefix-free complexity and the universal measure

• Sections 5 and 6 from my Kolmogorov Complexity survey
• Lecture notes with more details.

Day 38

Assignment 5 has been posted and due December 13.

Assignment 4 is still being graded but solutions have been posted on the T-Square resources page.

Introduction to Kolmogorov complexity with basic results, applications to primes and mathematical logic.

• Kolmogorov Complexity by Lance Fortnow

Day 37

Guest lecture by DeVon Ingram on the Sensitivity Conjecture and GKS games.

• A New Approach to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký and Michael Saks

Day 36

The following are polynomial related for any function f:{0,1}ⁿ→{0,1}.

• Decision Tree Complexity (deterministic query complexity)
• Certificate Complexity
• Block Sensitivity
• Degree of approximate polynomial
• Degree of exact polynomial
• Quantum query complexity

Links:

• Quantum lower bounds by polynomials by Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf
• On the degree of boolean functions as real polynomials by Noam Nisan and Mario Szegedy

Day 35

Shor's Algorithm - polynomial-time quantum algorithm for factoring

• Algorithms for quantum computation: discrete logarithms and factoring by Peter Shor

Day 34

More quantum: Deutsch-Jozsa, Grover and Simon

• Rapid solution of problems by quantum computation by David Deutsch and Richard Jozsa
• A fast quantum mechanical algorithm for database search by Lov Grover
• On the Power of Quantum Computation by Dan Simon