Computing Theory

• NP-hard does not mean hard
  December 29, 2017
• Boolean Logic in Polynomials
  July 24, 2017
• The Blum-Blum-Shub Pseudorandom Generator
  July 11, 2016
• Zero Knowledge Proofs — A Primer
  July 5, 2016
• The Boosting Margin, or Why Boosting Doesn't Overfit
  September 21, 2015
• What does it mean for an algorithm to be fair?
  July 13, 2015
• Methods of Proof — Diagonalization
  June 8, 2015
• Hamming's Code
  March 2, 2015
• A Proofless Introduction to Information Theory
  February 16, 2015
• The Quantum Bit
  December 15, 2014
• A Motivation for Quantum Computing
  December 8, 2014
• Linear Programming and the Simplex Algorithm
  December 1, 2014
• The Complexity of Communication
  November 10, 2014
• On the Computational Complexity of MapReduce
  October 5, 2014
• Occam's Razor and PAC-learning
  September 19, 2014
• Parameterizing the Vertex Cover Problem
  August 25, 2014
• An Update on "Coloring Resilient Graphs"
  July 14, 2014
• A problem that is not (properly) PAC-learnable
  April 21, 2014
• Stable Marriages and Designing Markets
  April 2, 2014
• Want to make a great puzzle game? Get inspired by theoretical computer science.
  March 17, 2014
• On Coloring Resilient Graphs
  February 21, 2014
• Simulating a Biased Coin with a Fair Coin
  February 12, 2014
• How to Conquer Tensorphobia
  January 17, 2014
• Probably Approximately Correct — a Formal Theory of Learning
  January 2, 2014
• Anti-Coordination Games and Stable Graph Colorings
  September 9, 2013
• Guest Post: Torus-Knotted Baklava
  June 28, 2013
• Conferences, Summer Work, and an Advisor
  June 3, 2013
• A Sample of Standard ML, the TreeSort Algorithm, and Monoids
  April 7, 2013
• Information Distance — A Primer
  December 4, 2012