Computational Complexity

What is a one-way function , intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal def...

UCLA Professor Andrew Kahng gave this wonderful speech to the incoming computer science graduate students. While designed for UCLA, with mi...

We just got email that Proof , a movie adapted from the play , will be filmed in and around the University of Chicago campus over the next f...

Christos Papadimitriou has been exercising his creative talents. He has a new book Turing (A Novel about Computation) building a love story...

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima...

In a conversation I had last week, a professor planned to use slides from lecture notes he found on the web in his own slides. He planned ...

Last week I posed the following question: (1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly hal...

As promised back in March, the October 2003 BEATCS Complexity Column is on whether we can truly settle the P versus NP question. Scott Aar...

I have received some requests for the call for papers for STOC 2004 which will be held in Chicago. Maybe it is because I gave the presentati...

The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impa...

A colleague of mine, who shall remain nameless, likes to schedule time for research, a certain set block of time during the day where he pu...

The call for papers for the 2004 ACM Conference on Electronic Commerce is now available. I'm posting this note as my duty as a program...

Here I am, my first day back on the campus of the University of Chicago. It's quiet here, Chicago is on the quarter system and classes d...

My office is all packed up and ready to be shipped. On Friday we move out of our house. I've moved my web pages to Chicago. Burned my fi...

I have a gap in my knowledge of work in theory done between 1979 (the publication of Hopcroft and Ullman ) and 1985 (when I started gradua...

Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schöning answers this question in the affirmat...

Cleaning out my office I came across some old SIGACT News that Bill Gear had given me when he cleaned out his office after his retirement....

When I move back to Chicago, I will go back to my old email address . I got to thinking about how my career can be described by my em...

A few months ago I had a post describing information markets, a system of buying and selling securities that pay off if a given future eve...

I know this is not a sports weblog and I don't even like bicycling but anytime an American named Lance wins a major championship I can...