Language has never been my strong suit. I didn't speak full sentences until I was five. I had a 220 point spread between my verbal and math SAT scores. I...
Two great open questions from the early 70's: Is PNP? Who was Deep Throat? Now that we know the answer to the latter, can a resolution of P versus NP be far ...
Toda's famous theorem states that the polynomial-time hierarchy reduces to counting problems (in complexity terms PH P #P ). His proof uses two lemmas: PHBPP P...
An old math joke: Three friends from college went on to become a doctor, lawyer and a mathematicians. They met back at reunion and the discussion went to ...
Should you have jokes in talks? Too much humor can detract from your real work but a little laughter can lighten up an otherwise dry presentation. You must use...
Jeff Erickson makes an important point in his post on the SoCG (Computational Geometry) business meeting. Links and emphasis are his. Finally, and most...
The University of Chicago has four graduation convocations in the spring quarter spread throughout today and tomorrow. The first session (mostly law students)...
Howdy from the 20 th IEEE Conference on Computational Complexity in San Jose, California. Last night we had a short business meeting with beer and wine but...
Yesterday Manuel Blum gave the invited talk on Understanding "Understanding:" Steps towards a Mathematical Scientific Theory of Consciousness . He started with...
As the long computer science recruiting season has pretty much finished we go around conference like STOC and Complexity asking "Where will you be next year?"...
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...
May Edition The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space by Albert Meyer and Larry Stockmeyer, FOCS (then called...
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...
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...
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...
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...
Theory Matters points to a definition of Theoretical Computer Science given on the SIGACT Home Page . The field of theoretical computer science is interpreted...
The list of accepted papers for the upcoming FOCS Conference has been posted (via Suresh via Bacon ). Given recent comments the Internet really raises...
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...
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...
The great game theorist Robert Aumann writes about consciousness . Sometimes, people express perplexity as to the nature of the problem. They do not see...
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...
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.
