When you cannot achieve the optimum solution of a problem, how do you measure the performance of an algorithm? If you knew the distribution of instances, you...
About a month ago I had the phone in my office removed. The number was one digit off from both maternity and a nurse's station at the U of C hospitals and if...
A guest post by Rakesh Vohra. Fortnow's post on competitive ratio's has prompted a number to speculate on the `right' number of people who should engage in ...
Welcome to ComplexityCast, the first of a very occasional podcast, an audio version of this weblog. First up, Bill Gasarch and I talk about the P versus NP...
This notice came into my inbox last week. ChicTech, an outreach program of the University of Illinois Department of Computer Science, extends an open...
An excellent Chronicle article on negotiating your job offer. I fully agree with the article that you lose out considerably by not negotiating and that you...
October Edition We end the list of favorite theorems from 1965-74 with two seminal papers by Cook and Reckhow. Stephen Cook and Robert Reckhow, Time-bounded ...
Alice (not the real name) has a STOC submission with Bob and wanted to put the paper on a public archive. Bob insists that the paper not go public until the...
The acceptance rates at conferences for theoretical computer scientists tend to run higher than acceptance rates at conferences in other areas of computer...
Janos Simon gives a history of RAMs expanding on my recent Favorite Theorems post . A single paper is like a snapshot of the state of research at one point in...
As a Cornell University alum I get the occasional email from the president talking about the great things going on on the Ithaca campus. Today's email I...
When we teach relativization, we often ask the class for a set A such that P A =NP A . The usual answers we get are an NP-complete A (which doesn't work unless...
You attend the University of Chicago for three years, take a few years off and come back to finish your Bachelor's degree in Chemistry. You worked really hard...
When a scientist visits another university to give a seminar, someone gets assigned as host who during the talk introduces the speaker, makes sure the talk...
The December 4th paper submission deadline for the Computational Complexity Conference in Prague is fast approaching. Get your papers ready. Other deadlines:...
Two years ago for the first time, I gave the proof of the PCP (Probabilistically Checkable Proof) theorem in my graduate complexity course. The result, first...
Chris Leonard, Elsevier editor of the CS theory journals is leaving Elsevier to be head of communities of the digital music service Digimpro . Theory loses a...
Two very different articles in today's New York Times about battling the decline of interest in Chess. In the Op-Ed section, Jennifer Shahade, a recent US...
Dear Game Theorist/Computer Scientist: In keeping with our mission "to facilitate cross-fertilization between theories and applications of game theoretic...
After my post on teaching PCPs, a reader questioned the wisdom of spending 6-8 lectures on PCP and asked what topics should be taught in an introductory...
This Saturday comes the annual William Lowell Putnam Mathematical Competition . The contest is open to undergraduates at American universities. Any number can...
Luca asked about the topics in the complexity courses I took in 1985 and 1986. I dug up my old course notes and wrote down what was covered. Some more in the...
Many of you submitted papers to the Complexity conference by yesterday's deadline, now you should let the world see them. Submit your papers to an archive...
Someone asked me recently how I became a complexity theorist? After all most high school students don't say they want to be a theoretical computer scientist...
Guest Post by Bill Gasarch with help from Harry Lewis and Richard Ladner. What are the surprising results in theory? By surprising we DO NOT mean surprising...
This week I am visiting the University of Texas in Austin. Yes, another football school , but they also have a boffo complexity group with Anna Gl, Adam...
We have seen many exciting papers based on the unique games conjecture for example that improving the Goemans-Williamson approximation algorithm for Max-Cut...
Nicholas Kristof writes in a New York Times op-ed column The Hubris of the Humanities (paid subscription required) that the lack of appreciation for science...
In my second Complexitycast , Scott Aaronson and I try to answer the question "What should physicists know about computational complexity?" MP3 (21:52, 3.8MB)...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
