Computational Complexity

Someone took me to task because in November I posted that the CRA News had 50 pages of job ads but didn't note that very few of those a...

A while back I had a paper in an intermediary stage. The version posted to my Ramsey Theory Course Website was not final. Is the paper publ...

I was 11 forty years ago when Dungeons and Dragons first appeared and by high school many of my friends spent far too many hours embarkin...

My chairman, Samir Khuller, asked me to post our job posting for a lecturer to my blog, so I and doing it right now . I think he overestimat...

Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future ...

(Stephen Colbert tells me that NFL guards their copyright of the name of the game they played on Sunday, which is why stores say they have a...

We start the favorite theorems with a result that might surprise many is still less than ten years old. Undirected Connectivity in Log-Sp...

Dana Richards emailed us about a place to write how Martin Gardner influenced you. You can leave such comments here .  I left a comment ther...

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...