Computational Complexity

The paper of the year goes to Settling the Complexity of 2-Player Nash-Equilibrium by Xi Chen and Xiaotie Deng which finished characterizin...

As we start thinking about our Theoretical Foundations proposals, a few related items from the theory community. Joan Feigenbaum and Mich...

From about early December to late January the academic world takes a little breather as many universities end their fall quarters and start ...

December 22, 2006 Dear Recruiting Committee: George Henry is among the top fifty computational complexity theorists on the market this yea...

Last month the University of Chicago faculty received an email from new president Robert Zimmer and soon-to-be-provost Thomas Rosenbaum abou...

Can a CS degree propel you to a major acting role on a popular new TV series? Worked for this person . I heard a complaint that in the mov...

Now that most of the FCRC Deadlines have passed, I would again suggest that you post your papers on a public archive like the Electronic C...

Chicago will be invaded by economists in early January, coming to the American Economic Association's Annual Meeting . At the same tim...

You can tell a lot about a field by how researchers motivate their results in papers and talks. Pure mathematics often gives little or no mo...

The NSF has a new Theoretical Foundations solicitation. Due date is February 19. Theory of Computing has its own component within this clus...

In the ninth Complexitycast , Bill Gasarch and I answer reader's questions . MP3 (25 minutes, 4.3MB) In the podcast we mentioned posts...

This past year I listed my favorite computational complexity theorems from 1975-1984. Alternation (Chandra-Kozen-Stockmeyer) Relativizati...

Standa Zivny asks I'd like to ask you about CLIQUE→SAT reduction. The reduction 3-SAT→CLIQUE is a standard one from undergrad course. S...

An Off-Broadway tale of beauty and the geeks . Vickie Martin is über-popular. She's also wicked smart. Victoria Martin: Math Team Queen...

The Church-Turing thesis roughly states that everything computable is computable by a Turing machine. I strongly believe the Church-Turing t...

At a community concert last Sunday the host said he was pleased with the attendance given the competition with the Bears game. He also said ...

How do you take a twenty page research paper and condense its essence into a few words? A couple of title don'ts with some (made up) exa...

Friday morning I IM'd a co-author in India, in the evening I Skyped to Hong Kong. A Dutch professor emailed me about a paper we have wit...

Last month Yisroel Brumer wrote a Newsweek My Turn column Let's Not Crowd Me, I'm Only a Scientist . Brumer talks about how he has b...

Marilyn vos Savant writes a weekly column for Parade Magazine instered into many US papers. She's best known in the math community for ...