Nanda Raghunathan points me to a new paper by Gatis Midrijanis giving a simple proof of the best known rigidity lower bounds for the Sylvester matrices. The...
When I went to high school (1978-81) we had a computer room with three teletype machines that connected at 10 characters/second and we saved programs on paper...
Some professors consider it a badge of honor to keep huge stacks of papers covering their desk and often most of their floor. But in reality once you bury a...
June Edition In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic...
Guest post from theory music expert Bill Gasarch. There is some (not a lot) of novelty songs about computer science, and less about theory . There is a new CD...
My technical posts rarely draw many comments but Tuesday's post on Savitch's Theorem brought a long discussion on hard versus easy proofs that started with...
Ever notice how computer science departments in the US are like baseball teams. They try to hire the best players so they can be better than other departments...
Today's Science Times has an article on Danica McKellar an mathematically-talented actress, best known for her role as Winnie on Wonder Years. She has a Bacon ...
I just finished the latest Harry Potter book. Amazing how much you can read when stuck at an airport. It seemed like half the people at the Seattle airport on...
To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability...
In 1981, Juris Hartmanis wrote some observations on the early days of computational complexity. The article also contains some interesting discussions on...
When do you understand a proof? Such understanding has many levels. Knowing the rough techniques used. Following the proof line by line. Can recreate the...
Consider the following two voting schemes to elect a single candidate. Majority Vote. A Majority of Majorities (think an electoral college system with states...
The Americans develop a powerful computer to run its nuclear weapons. The Soviets develop a similar machine. The two are connected and take over the world with...
What does it take to be a successful in our profession? Intelligence. You need an innate talent in different forms to succeed as a scientist. Problem Solving....
We normally define relativization to an oracle A with a special Turing machine that has an extra tape where the machine can write down a string x and move to a...
Chris Leonard who edits the Elsevier journals in theoretical computer science has started a weblog Computing Chris . He plans to address some of the concerns...
When I was in grade school we learned that Jupiter had twelve moons. We had a test. "How many moons does Jupiter have?" I wrote "12" and it was marked correct....
An email from Rocco Servedio. Did you see this New York Times article ? Thought you might be interested in pointing this out on the weblog, maybe a CS theory...
I am just finishing the last of three west coast trips this summer. I went to the Complexity conference, two universities (U. Wash and Caltech), three...
July Edition As a graduate student, Manuel Blum wanted to study computational complexity freed from any specific machine model. His paper set the tone for much...
Sanjeev Arora and Bernard Chazelle write the Viewpoint Column Is the Thrill Gone? in this months Communications of the ACM . One wonders if the failure of...
Robin Houston writes Although I'm not a complexity theorist, I very much enjoy reading your weblog. I also enjoy solving the Sudoku puzzles published in the...
Elsevier is opening up I&C for the rest of the year. The Publisher and Editorial Board of Information and Computation are pleased to announce that for one...
Let's look at some relativized worlds which really push the limits of what we don't know how to prove. Once again I refer you to the zoo for definitions of...
The US has reached its limit for H1-B visas not just for this fiscal year but for the next. A foreign technical worker wanting to work in the US wouldn't be...
Simulated Annealing is a heuristic technique for optimization problems. Think of an optimization problem as hills and valleys where you want to find the lowest...
In a popular summer movie Wedding Crashers , two friends go to weddings and receptions uninvited for food, drink, entertainment and to pick up single women. We...
I am back from our family vacation to the Black Hills of South Dakota. Thanks to Ryan O'Donnell for guest blogging. I have donated $26 to hurricane relief in...
Ronald Fagin writes in response to my post The New Research Labs . Lance has invited us to give an update on the state of theory at the IBM Almaden Research...
