Computational Complexity

Theorem of the year goes to Omer Reingold who shows Undirected Connectivity in Logarithmic Space , settling the long-standing open problem...

A guest post from Alan Selman It is a common and acceptable practice to present a preliminary version of a paper at a conference and th...

Fred Roberts, Rakesh Vohra and myself are co-charing the DIMACS Special Focus on Computation and the Socio-Economic Sciences , a series of...

Chennai, the location of the recent FSTTCS conference reviewed in the last post , was one of the areas hit hard by today's earthquake ...

By Prahladh Harsha and Jaikumar Radhakrishnan It was nice to be back in Madras after a long time and even nicer to meet friends from ...

In 1994, I listed My Favorite Ten Complexity Theorems of the Past Decade in conjunction with an invited talk at that year's FST&TCS...

Coming in January to the American television network CBS, a series about a FBI agent who recruits his brother, a math genius, to help sol...

One of my Indian graduate students mentioned the university yookla and gets confused when I talk about Texas (not UTA) or Illinois (as ...

A commenter yesterday asked about a Crooked Timber post arguing that many strong departments place an emphasis on hiring students from ot...

Consider the following paragraphs from Tom Clancy's 1998 novel Rainbow Six . The phone they spoke over was the Russian version of the ...

November Edition We started this list of favorite theorems with derandomization of time classes. Now we end the list by looking at der...

Academic bloggers (like Jeff and Suresh ) are up in arms about a column by Ailee Slater in the University of Oregon student paper. We...

Iowa State graduate student Chad Brewbaker created a graphical map of the complexity classes in the zoo . Who says you can't have fun ...

Volunteer to organize a conference and I guarantee you will get an email like the following I am a computer scientist from Nigeria. I am...

The National Science Foundation rarely gets mentioned in the popular press. After the recent budget cut , the NSF now gets some mention, in...

Birthday Boy Rocco Servedio gave a talk at TTI on Friday on learning random functions over random inputs. John Langford asked about distr...

Texas student Vladimir Trifonov gives An O(log n log log n) Space Algorithm for Undirected Connectivity . If it came out a few months earl...

In the month of November 44.3% of the hits on this website came from windows machines. If you are in this minority and don't mind a sma...

A program committee member who asked me to review a paper pointed me to Oded Goldreich's Suggestions to Program Committees , one of hi...

While we have seen a increase in computer science funding over the past few decades, it has not kept up with the great increase in the numbe...