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...
557
Lance
fortnow
Nov 3, 2005 1:00 pm
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...
558
Lance
fortnow
Nov 4, 2005 11:32 am
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 ...
560
Lance Fortnow
fortnow
Nov 4, 2005 12:13 pm
Ignore the last message about podcasts. I was just testing and sent it out by mistake....
561
Lance
fortnow
Nov 5, 2005 12:52 pm
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...
562
Lance
fortnow
Nov 7, 2005 2:07 pm
This notice came into my inbox last week. ChicTech, an outreach program of the University of Illinois Department of Computer Science, extends an open...
563
Lance
fortnow
Nov 8, 2005 9:15 pm
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...
564
Lance
fortnow
Nov 10, 2005 1:37 pm
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 ...
565
Lance
fortnow
Nov 12, 2005 1:50 pm
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...
566
Lance
fortnow
Nov 14, 2005 11:01 pm
The acceptance rates at conferences for theoretical computer scientists tend to run higher than acceptance rates at conferences in other areas of computer...
567
Lance
fortnow
Nov 15, 2005 9:50 pm
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...
568
Lance
fortnow
Nov 17, 2005 12:02 am
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...
569
Lance
fortnow
Nov 18, 2005 2:00 am
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...
570
Lance
fortnow
Nov 19, 2005 12:44 pm
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...
571
Lance
fortnow
Nov 21, 2005 4:43 pm
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...
572
Lance
fortnow
Nov 22, 2005 4:57 pm
The December 4th paper submission deadline for the Computational Complexity Conference in Prague is fast approaching. Get your papers ready. Other deadlines:...
573
Lance
fortnow
Nov 23, 2005 6:28 pm
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...
574
Lance
fortnow
Nov 25, 2005 9:20 pm
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...
575
Lance
fortnow
Nov 28, 2005 2:37 am
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...
576
Lance
fortnow
Nov 29, 2005 10:18 pm
Dear Game Theorist/Computer Scientist: In keeping with our mission "to facilitate cross-fertilization between theories and applications of game theoretic...
577
Lance
fortnow
Nov 30, 2005 5:04 pm
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...
578
Lance
fortnow
Dec 1, 2005 9:12 pm
This Saturday comes the annual William Lowell Putnam Mathematical Competition . The contest is open to undergraduates at American universities. Any number can...
579
Lance
fortnow
Dec 2, 2005 10:09 pm
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...
580
Lance
fortnow
Dec 5, 2005 3:58 pm
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...
581
Lance
fortnow
Dec 6, 2005 3:33 pm
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...
582
Lance
fortnow
Dec 7, 2005 3:53 pm
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...
583
Lance
fortnow
Dec 8, 2005 1:08 pm
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...
584
Lance
fortnow
Dec 11, 2005 1:03 pm
We have seen many exciting papers based on the unique games conjecture for example that improving the Goemans-Williamson approximation algorithm for Max-Cut...
585
Lance
fortnow
Dec 13, 2005 1:12 pm
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...
586
Lance
fortnow
Dec 15, 2005 12:25 am
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)...
