Chris Barwick (aka optionsScalper ) is a fan of Euler and tracked down my academic legacy back to Euler and Gauss through many other great mathematicians. Of...
477
Lance
fortnow
Jun 21, 2005 12:07 am
May Edition The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space by Albert Meyer and Larry Stockmeyer, FOCS (then called...
478
Lance
fortnow
Jun 22, 2005 12:23 pm
A famous complexity theorist once said "The hardest part of being an advisor is not working on your student's problems." Good open problems are quite rare and...
479
Lance
fortnow
Jun 23, 2005 11:34 am
Rarely do people notice the true technological breakthroughs in science fiction and fantasy movies. Roger Ebert gets it in his review of the rather silly...
480
Lance
fortnow
Jun 24, 2005 12:23 pm
On May 13 in the US, the Star Trek franchise (temporarily?) ends 18 straight years of first-run episodes. Bill Gasarch comments. About a month ago was the...
481
Lance
fortnow
Jun 27, 2005 10:47 am
A unique game consists of an undirected connected graph G=(V,E), a color set C, and for each edge {i,j} with i<j a permutation i,j :CC. A coloring of the graph...
482
Lance
fortnow
Jun 28, 2005 11:17 am
Theory Matters points to a definition of Theoretical Computer Science given on the SIGACT Home Page . The field of theoretical computer science is interpreted...
483
Lance
fortnow
Jun 30, 2005 12:15 am
The list of accepted papers for the upcoming FOCS Conference has been posted (via Suresh via Bacon ). Given recent comments the Internet really raises...
484
Lance
fortnow
Jun 30, 2005 9:15 pm
Sanjeev Arora asked the "theory blogs" to take up the issue of finding a few new challenges of theory that one can sell to nonspecialists and congressional...
485
Lance
fortnow
Jul 4, 2005 2:53 am
Old Joke: Is there a fourth of July in Canada? Sure there is, right between the third of July and the fifth of July. Outside of the US the Fourth has no...
486
Lance
fortnow
Jul 5, 2005 1:00 pm
The great game theorist Robert Aumann writes about consciousness . Sometimes, people express perplexity as to the nature of the problem. They do not see...
487
Lance
fortnow
Jul 6, 2005 2:16 pm
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...
488
Lance
fortnow
Jul 8, 2005 12:21 am
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...
489
Lance
fortnow
Jul 11, 2005 2:00 am
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...
490
Lance
fortnow
Jul 12, 2005 10:56 am
June Edition In 1970 Walter Savitch proved one of the truly classic results in complexity showing that one can simulate nondeterministic space in deterministic...
491
Lance
fortnow
Jul 14, 2005 12:59 pm
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...
492
Lance
fortnow
Jul 15, 2005 3:52 pm
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...
493
Lance
fortnow
Jul 18, 2005 4:46 pm
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...
494
Lance
fortnow
Jul 19, 2005 10:11 pm
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 ...
495
Lance
fortnow
Jul 21, 2005 1:16 pm
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...
496
Lance
fortnow
Jul 22, 2005 2:15 pm
To paraphrase George Bernard Shaw, Computability Theory and Computational Complexity Theory are two fields separated by a common terminology. Computability...
497
Lance
fortnow
Jul 25, 2005 4:54 pm
In 1981, Juris Hartmanis wrote some observations on the early days of computational complexity. The article also contains some interesting discussions on...
498
Lance
fortnow
Jul 26, 2005 6:37 pm
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...
499
Lance
fortnow
Jul 27, 2005 9:36 pm
Consider the following two voting schemes to elect a single candidate. Majority Vote. A Majority of Majorities (think an electoral college system with states...
500
Lance
fortnow
Jul 29, 2005 2:29 pm
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...
501
Lance
fortnow
Jul 31, 2005 5:31 pm
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....
502
Lance
fortnow
Aug 2, 2005 1:34 am
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...
503
Lance
fortnow
Aug 2, 2005 2:16 pm
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...
504
Lance
fortnow
Aug 3, 2005 8:50 pm
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....
505
Lance
fortnow
Aug 4, 2005 4:13 pm
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...
