Every voting scheme has the property that in some scenario a change of a single vote can change the outcome. When a major election has a very close result,...
The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical...
I just got back from SODA 2009 in New York (Symposium on Discrete Algorithms). In later posts I will describe some of the interesting papers that I saw, Today...
There have been 23 IEEE Conferences on Computational Complexity and I have been to all of them. There have been 20 ACM-SIAM Symposiums on Discrete Algorithms...
I liked the SODA2009 paper Sorting and Selection in Posets since it makes you look at ordinary sorting in a new way. What does it mean to sort a list? We...
Samir Khuller guest posts about having conferences in exotic locations. During the SODA Business Meeting I was a bit alarmed at some of the suggestions made...
When you first make a conjecture you don't know if it will be important or interesting or both or neither. In the case below it was solved quickly, the answer...
Nicole Immorlica pointed me to a Wall Street Journal article about a ranking of 200 jobs by CareerCast. Number one: Mathematician. So what is a mathematician?...
- You are wrong. Figure it out. Sometimes you can still salvage something interesting out of your flawed proof. - You believe the proof is correct. Your belief...
Amitabh Varshney (Graphics Faculty at UMCP) emailing me the following: Someone told me a while ago that there are some theory conferences in which members of...
It was a common joke to point out how people really overestimate low or zero probability events. Why in the pre-flight briefing do the flight attendants teach...
Less than two week after I was born, Martin Luther King, Jr. gave his "I Have a Dream" speech. Watch the speech if you haven't seen it yet. I consider it the...
The state of our economy calls for action: bold and swift. And we will act not only to create new jobs but to lay a new foundation for growth. We will build...
Below is a Presidential Trivia Quiz. Some of the questions are obscure, so it might be more fun to just wait until Monday when I post the answers and then read...
Apparently Mark Braverman has settled a major open question about circuits due to Linial and Nisan. He shows that any poly-logarithmically independent...
The ANSWERS to my Presidential Quiz are linked to here First I'll answer the questions raised in the comments of the presidential quiz post. - Who served the...
RANDOM THOUGHTS on the inaugural. (After this post I will post on politics far less often.) - My colleague Evan Golub went into DC on Tuesday morning of the ...
Why do we think solving P vs NP is hard? There are some matematical reasons (oracles, Natural Proofs, Algebraization) but there is also this notion that many...
The James Bond Movie Goldeneye had the following scene which is typical of movies and some TV shows. Scenario: A (good) female Russian computer programmer has...
Just got back from vacationing in Obama's other home state and found a new govenor in Illinois when I got back. About time. TTI-Chicago has moved into their...
The stimulus package being shopped to congress by the Obama administration includes a considerable amount of science funding. The House passed a version that...
There is a new BLOG on our blogroll. It is Blown to Bits and it is associated to the book Blown to Bits: Your Life, Liberty, and Happiness after the digital...
Alice: Does Carol's proof solve your big open problem? Bob: Yes, but it's an ugly proof so it doesn't count. A beautiful proof—a proof from "The Book"—is a...
Josh Burdick had my course on concrete complexity a long time ago. He still dabbles in the area and recently sent me two manuscripts here and here He seems to...
Jason Hartline comments on a report by CNN about the size of the government bailout. "To put a trillion dollars in context, if you spend a million dollars ...
Many articles of interest in the New York Times. Chris Maase pointed me to the article Scientists Disappointed by Direction of Financing. Scientists, who were...
(This article had help from Clyde Kruskal, Joe Kruskal, Bill Kahn, Hans Courant, and Lucy Moser.) Bill James, the baseball statistician, once had an article on...
Last reminder: Complexity submission deadline tonight midnight Eastern. In a nice move, Mitzenmacher posted both the titles and abstracts of STOC papers on the...
Suppose you had no specific reason to be on campus. No classes, no talks, no scheduled meetings with students/advisors, no meetings scheduled. Would you go to...
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.
