# computational complexity

- Zero Knowledge Proofs for NP

August 1, 2016 - The Complexity of Communication

November 10, 2014 - On the Computational Complexity of MapReduce

October 5, 2014 - Parameterizing the Vertex Cover Problem

August 25, 2014 - A problem that is not (properly) PAC-learnable

April 21, 2014 - On Coloring Resilient Graphs

February 21, 2014 - Miller-Rabin Primality Test

June 16, 2013 - Ramsey Number Lower Bound

December 2, 2012 - Kolmogorov Complexity—A Primer

April 21, 2012 - Classic Nintendo Games are NP-Hard

March 22, 2012 - Other Complexity Classes

February 29, 2012 - P vs. NP, A Primer (And a Proof Written in Racket)

February 23, 2012 - Turing Machines and Conway's Dreams

June 30, 2011 - Google's Page Rank—The Final Product

June 20, 2011 - Big-O Notation—A Primer

June 14, 2011