Computational Complexity

An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many othe...

A brilliant math ugrad at UMCP, Doug, is also a creative writer who wants to work on large cardinals. His creative writing may help him th...

When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apart...

YOU got into your undergrad school because not only were you good at Math but you were on the Fencing Team and in the Latin Club (so you co...

I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I reali...

I taught a 3-week summer course to High School Students called Computer Science: A Hands Off Approach which did some theory. One thing ...

[Nina Balcan asked me to mention that the  COLT submission deadline is February 7] Jean Francois Puget writes a controversial post  No, T...

A while back my parents were in town on a weekend when I was scheduled to give a talk to HS students who had done well on the Maryland math ...

As I am sure readers of this blog know Alan Turing was prosecuted for homosexuality in 1952, forced into hormone treatment, and committed s...

The complexity result of the year goes to  The Matching Polytope has Exponential Extension Complexity  by Thomas Rothvoss. Last year's p...

Guest post by Vijay Vazirani Our field has been blessed with some great books: classics such as Knuth's volumes and Garey & Johnso...

Sometimes we are asked to evaluate how good a journal or conference  formally(Excellent, Very Good, Good, Fair, Better-than-being-poked-by-a...

A couple of policy changes recently, one that supposedly enhances privacy and another that could reduce it. Google has been implementing p...

(Jon Katz wanted me to mention this:  A wise man once noted that there are fewer quantum algorithms than thereare quantum-algorithms textboo...

Hadi Esmaeilzadeh is the newest professor in the School of Computer Science at Georgia Tech. Hadi works in computer architecture and did s...

(Tal Rabin, Shubhangi Saraf and Lisa Zhang asked me to remind you to publicize this: the bi-annual Women in theory (WIT workshop), NYC, May ...

Two years ago I gave a lecture and  posted about bitcoin. Of course what I didn't do was buy a bitcoin whose value back then was about ...

Who was the first scientist to warn of Global Warning? These questions are complicated, but I would say it was Bing Crosby in a paper called...

(This post was inspired by Adam Winklers awesome book Gunfight: The Battle over the Right to Bear Arms in America . Disclaimers one: Adam...

A few centuries ago if you wanted to do science and not independently wealthy you needed help . Most of the important astronomers and natu...