Computational Complexity

Perhaps the very first example one sees of the probabilistic method: Show there exists a graph on n vertices with no clique or independent s...

Who would have thought the next theoretical computer science powerhouse would have come from Atlanta? Georgia Tech this year has hired Santo...

A few publishers showed their wares at STOC. This is a good opportunity to talk them about book ideas or about publisher's policies and ...

A commenter asked about the Fly America Act that requires, with few exceptions, that when traveling abroad on US money, such as an NSF gran...

I don't go to many talks at STOC, I prefer hanging out in the hallways and talking with other attendees. But the best talk I saw so far ...

Howdy from Seattle. Here's some highlights from the STOC business meeting. 78 papers accepted out of a record 288 submissions. There...

April Edition For many years the standard example of a probabilistic algorithm checked whether a number was prime. Riemann's Hypoth...

Via CRA Bulletin the 2004-2005 Taulbee Survey has been posted. A wealth of statistics about computer science in the US and Canada. The cha...

How could I not blog about Jonathan Farley's op-ed piece The NSA's Math Problem ? Farley looks at the NSA's use of phone data as...

Suppose we could create a system where all automobile traffic in the US would be controlled by a central computer system. Traffic would flow...

This Monday May 15th is the early registration deadline for this year's Conference on Computational Complexity in Prague. The early reg...

Ehud Kalai proposes renaming the Game Theory Society to the Game Science Society and welcomes your comments. The goal of changing the name...

Razborov and Rudich's paper Natural Proofs gives a combinatorial framework for proofs to show that circuits in a given class cannot ach...

A computer science paper goes through many phases: manuscript, technical report, conference submission and proceedings and journal submissio...

Luca and Oded talk about rejection. Here are some thoughts. Rejection hurts. Academics thrive on earning the respect of their peers and i...

A panel at the National Academy of Sciences suggests that the US should support Fermilab's bid to land the International Linear Collide...

For a talk I wanted to show a map of the United States using four colors with the usual constraint that every pair of states that share a co...

Bob Soare, who wrote one of the great textbooks on recursion theory and then almost single-handedly changed the name of the field to compu...

If you have an academic job offer, what next? Don't forget to negotiate. I wrote a post on negotiating last fall and in particular you ...

Kurt Gödel came into our world one hundred years ago today. Gödel's incompleteness theorems changed the way we think about mathematics...