Computational Complexity

An assistant professor asks How do I get on program committees and editorial boards? PC chairs and editors-in-chief usually have several e...

The recent FOCS conference had two best paper award winners, the Khot-Vishnoi paper I had mentioned in my post on unique games and Correct...

Yesterday my fifth-grade daughter, doing her math homework, asked Is there a faster way to find greatest common factors other than with fa...

Thanks to Rocco for bringing us the news from FOCS, particularly a comprehensive summary of the business meeting. I am glad to have watched...

Final guest post from FOCS attendee Rocco Servedio. Well, another FOCS has come and gone. In 50 years -- 100, tops -- we will know which p...

The 2005 Knuth Prize was awarded to Mihalis Yannakakis of Columbia University. Mihalis's Knuth prize lecture was on "Probability a...

Notes from the FOCS 2005 business meeting, reported by Rocco Servedio. Yuengling, Sam Adams, Aspen Edge (low-carb). Local arrangemen...

A guest post from FOCS attendee Rocco Servedio. Thanks to Lance for giving me this opportunity to fill in. I'm in Pittsburgh for FOCS,...

Another guest post by Bill Gasarch Combinatorics is a branch of Computer Science First episode, Second Season of NUMB3RS I could have a...

I am spending most of this week at the University of Nebraska for a talk and a workshop . What does Nebraska have to do with Notre Dame, whe...

In a new paper , Daskalakis, Goldberg and Papadimitriou show that finding Nash Equilibrium in matrix games with four or more players is comp...

How do you measure your impact as a computer scientist? You can try measures like the Citeseer rank or the h-index , but the only scientifi...

The University of Chicago denying tenure to an assistant professor is rarely a breaking news story. Yet political scientist Daniel Drezner...

Fonts are the last thing I want to worry about when I write a research paper. Unfortunately fonts have often become the last thing I need to...

As you can see from the timestamp of this post, I came into work quite early this morning. I had to drive and needed an early start (about 6...

September Edition Usually we think of the class NP as either languages accepted in polynomial-time by a nondeterministic Turing machine or...

Piotr Indyk, himself a 2003 Packard Fellow, writes On the recent blog topic of awards : you might be interested to know that Venkat Gurusw...

A colleague is refereeing a paper in a non-computer science area that shows a certain computational problem is NP-complete. The proof uses a...

My first computer was a TRS-80, my second an Apple IIe. In college I mostly programmed in IBM 370 assembly code. But in graduate school (fir...