This work is licensed under a
Creative Commons License.
|
Monday, October 06, 2008
The Unexpected Hanging Paradox-any seriosu math their?
Posted by GASARCH
(20th Maryland TCS Day Tue, Oct 14, 2008 9:30am - 4pm)
The liar paradox is very similar to the serious math of Godel's Incompleteness theorem. Berry's Paradox is very simlar to the serious math of the Kolmogorov function (map x to the length of the shortest description of x) being noncomputable.
Is their any serious math that is similar to the Unexpected Hanging Paradox? Here is the paradox:
A judge tells a condemned man that he will hang on either M, Tu, W, Th, or Friday at 1:00PM And that he will be surprised when it happens. His lawyer tells him not to worry: The hanging can't happen on Friday, since if he is alive by Thursday at 1:01PM then he knows it will be on Friday and hence won't be surprised. However, he also knows he can't be hung on Thursday since Friday is out, so if by Wedensday at 1:01PM he alive he will KNOW that it is Thursday. Hence he won't be surprised. Hence it can't be Thursday. Proceeding like this he reasons that he can't be hung. On Thursday the judge comes with the noose- and the prisoner is surprised.
I'm not asking for a resolution-- it seems to be a significant problem for philosophy-- however, I am asking: Is there some serious math that is similar to this paradox?10:06 AM #
Friday, October 03, 2008
A minor but perhaps indicative failure of technology
Posted by GASARCH
In Feburary of 2007 needed to look up on Hallmark Channel Website if they had some program changes. They did not have any program changes on the website but they did have a number to call. The subwebsite had the number 1-888-390-7474. I called it and it said:You have reached viewer services at the Hallmark Channel. In order for us to better serve our viewers, this mailbox is specialized designed to answer most of your questions. If you are having trouble viewing the Hallmark Channel, press 1. For a list of program changes, press 2.I thought GREAT!. I pressed 2.The following changes have been made to our program scheduled as of Wedensday June 29, 2005. Jane Doe-The Harder they Fall, originally scheduled to air Friday July 1, 2005 9:00 Eastern and Pacific, 8:00PM Central, and 7:00PM Mountain time, has been replaced by Matlock-The Power Brokers.They had not updated their phone message in two years. I left a message (If you would like to leave a comment, press 4) telling them of their error. I have since called on April 1, May 1, and June 1 of 2007 to see if they have corrected it. They had not. I've also emailed them, to no effect. (Its been fixed since then.)
How could a phone line be this out of date? How could the website maintainers not know this?For this particular issue, the breakdown of technology is not important. But it troubles me that in other domains it might be.
- They got careless and are not suffering for it so they don't know they got careless. I'm not going to stop watching their shows because their website gives a phone number that is two years out of date.
- Lack of coordination- the right hand does not that the left hand stopped working two years ago.
9:37 AM #
Thursday, October 02, 2008
Go Sox
Posted by Lance
After beating three different teams in three days to make the playoffs, my White Sox join the Cubs in an historic time in Chicago: The first time both Chicago baseball teams are in the postseason since that great 1906 World Series. The Sox open the playoffs today against the surprising AL East winner Tampa Bay.With the Boston Red Sox that makes all three teams that I have once held season tickets (I lived walking distance from Wrigley for a year and I organized season tickets for the theory group at MIT as a student there). And add on Milwaukee a team I have grown to like as they play in new stadium that I can get to easier than either of the Chicago ball fields and you can't beat the sausage race. And four more teams that hopefully will all be eliminated in the first round. This is just the ultimate playoff year to keep me distracted from various fiscal crises and political activities. I might not get much research done in October.
The eyes of America look at the Cubs who last won a World Series in 1908, one hundred years ago. But although I now teach north of the city, my heart remains with the Southsiders. The best outcome: The White Sox win the world series in five games. Why five and not the full seven? Because it is so much more fun to see the Cubs choke at home.
6:53 AM #
Wednesday, October 01, 2008
When does Alice deserve to be a co-author?
Posted by GASARCH
When has someone done enough work to deserve a co-authorship? Here are a few scenarios I have seen. I will say what did happen, not what should have happened.
- Alice comes up with the problem and makes some obvious observations about it, she shows it to others, who solve it. She writes it all up. (Alice got the co-authorship.)
- Alice comes up with the problem and makes some obvious observations about it, she shows it to others, who solve it. She does not write it up but does some proofreading. (I've seen this twice- once she got the co-author, once not.)
- Bob shows Alice a problem, Alice makes one observation that is the key. She has put only 2 minutes of work into the paper. (Alice got the co-authorship.)
- Bob has already written up the 50 page paper and it has covered all of the cases except for one. Alice solves the one case left. It was not a hard case at all. (Alice did not get the co-authorship.)
- Bob and Carol solve the problem together. Alice is in the room and does not contribute anything, but her tenure case is coming up soon and she is a bit short on papers. (Alice got the co-authorship. This is a rare scenario.)
- Alice proofreads a paper and finds a serious flaw in it, but fixes tht flaw. It was a rather subtle flaw and needed very clever argument to fix it. (Alice got the co-authorship.)
- Alice reads Bob's paper and comes up with a generalization that Bob does not care about, but wouldn't really be worth a paper on its own. (The paper did not have the generalization and Alice did not get the co-authorship.)
- Alice makes a key observation that makes all of the proofs shorter. The Conference version has her as a co-author. However, while writing up the journal version it is noticed that Alice's contribution was not correct. It is removed and the journal version is pretty much what it would have been had Alice not been involved at all. (Alice asked to be taken off of the journal version The other authors were surprised by this and did not mind keeping her as an author. They pointed out that there were other people on the paper that were even less involved. But they agreed to take her off on her insistence.)
10:48 AM #
Tuesday, September 30, 2008
Making People Fly
Posted by Lance
The advertising tagline for the 1978 movie SupermanYou'll believe a man can fly!I grew up at a magical time for movies when special effects started to look almost realistic. The 15-year me was truly amazed that Superman actually did look like he flew, special effects done by careful camera work and very thin wires. Today actors where larger cables and harnesses digitally removed in post-production, unless the entire flying sequence is entirely computer generated.Back then we still had limits to special effects which made movies like Star Wars all the more impressive. Back then hidden supports were needed to make the hovercraft float. George Lucas has since gone back and added digital creatures to the original films, blasphemous to us fans who grew up with the movie.
We have reached the point where special effect can achieve pretty much anything the director can imagine. This gives some advantages, forcing movies like Dark Knight, Iron Man and Spiderman to rely on strong stories, characters and actors since special effects alone no longer sells movies (see Speed Racer). But no longer can we amaze teen-age kids with new technologies that make the seemingly impossible that come to life. Kids who, amazed by some of this work, done by computers, made them a hobby and then a career.
Biomedical engineering seems to be the new expanding major, at least at Northwestern. Computer Science needs to regain that coolness factor to attract the CS majors we and society continue to need.
7:57 AM #
Monday, September 29, 2008
comp Geom/MD Theory day/New Blog/Bond, James Bond
Posted by GASARCH
- The call for papers for the 25th Annual Symposium on Computational Geometry is here. submissions are due December 1.
- 20th Maryland Theoretical Computer Science Day! Tuesday, Oct 14, 2008! 9:30am -- 4pm (see online schedule for details)! AVW 2460 A.V.Williams Building! schedule
- A new Theory Blog! It will emphasize applications to Global Health Metrics! Author is Abraham Flaxman! The website is linked to by our site.
- A new James Bond Movie will be out soon Quantum of Solace. The Plot: Bad guys build a quantum computer and begin factoring numbers and breaking codes, but then Lance Fortnow and Scott Aaronson write a paper that shows their approach is flawed!
10:35 AM #
Friday, September 26, 2008
An Accidental Theorem
Posted by Lance
First a reminder that the FOCS early registration/hotel registration deadline is a week from today, October 3.At the Dagstuhl open problem session last week I gave the following conjecture that I had worked on with Harry Buhrman and Rahul Santhanam the week before in Amsterdam.
(*) NEXP is not contained in NP/nc for any constant c.NEXP is the class of languages computable in nondeterministic time 2poly(n), NP is nondeterministic polynomial time and nc represents advice, non-uniform information of up to nc bits that depend only on the input length. No one would think (*) is false, the question was to prove it without using any assumptions.I described the failed approach using derandomization via IKW. I also mentioned the best known separation, that NEXP is provably not in NP/no(1).
Later someone asked me how to prove that known result. I tried to reconstruct the proof on the fly. I ended up with a proof that also showed (*) and didn't use any derandomization.
What's the lesson? Sometimes a proof shows up in the strangest places, like when accidentally proving something stronger when you meant to prove something weaker.
Proof of (*): Assume (*) false. NE (the class of problems computable in nondeterministic time 2O(n)) would be in NTIME(nk)/nc for some k since NE has linear-time complete sets. We now have EXP is in NEXP is in NP/nc is in NE/nc is in NTIME(nck)/nc2 (by translation) in DTIME(2nck)/nc2. From this you can use standard diagonalization to get a contradiction.
Later Harry, Rahul and I strengthened the result to show
NEXP is not contained in PNP[nc]/nc for any constant c. (That's polynomial time with nc queries to some NP-complete set and nc bits of advice.)The proofs relativize and you can't do better with the size of the advice or number of queries with a relativizable proof.6:05 AM #
Thursday, September 25, 2008
Markets and Polls
Posted by Lance
A couple of weeks ago a strange thing happened on our electoral markets map. California turned red for a couple of hours. A few days later Michigan turned red as well. Neither of these states are about to vote republican, rather there were odd trades of Obama at a very low price in California and McCain at a high price in Michigan. Since we used the closing price the states were colored wrong until another trade occured.So we adjusted our algorithm so that if the closing price is lower than the bid price (the price someone is willing to pay) we use the bid price instead. Also if the closing price is higher than the ask price (the price someone is willing to sell) we use the ask price. That seems to avoid the problems of rouge trades.
Which brings me to a controversial post at fivethirtyeight.com, a site that makes predictions based on poll numbers. Nate Silver notes that the prediction of Obama of the markets to win the presidency (about 58%) is much lower than his site's prediction (about 72%). Silver suggests the disparity is because of a rouge trader or traders that seem to be driving the price down and even buying Hillary stock.
I don't buy it. There is quite a bit of volume on these securities and the prices on Obama should bounce back quickly and in fact it does. The rouge trader cannot explain a difference of 14 points. The Hillary factor can be explained by the long-shot bias (people overweigh low probability events). The markets suggest that the probability that Hillary is president is about the same as McCain winning Illinois which sounds about right (even if they are both too high at around 4%).
I have a different theory: The race is tighter than the Silver analysis suggests. The polls can give you numbers about each state but not the correlation between them. Silver gives an explanation of how he handles the correlations in his simulations:
Our simulation accounts for this tendency by applying a similarity matrix, which evaluates the demographic relationships between different states by of a nearest-neighbor analysis as described here. Our process recognizes, for instance, that as the polling in Ohio moves, the polling in a similar state like Michigan is liable to move in the same direction. On the other hand, there may be little relationship between the polling movement in Ohio and that in a dissimilar state like New Mexico.Silver admits he has little data to back up this claim. I believe the correlations are much tighter—that most of the states might move in the same direction depending on some future event or ad or gaffe or performance on the yet-to-be-held debates, that there is high future correlation even between Ohio and New Mexico.The swing states are typically highly correlated and if the four states running about 50% (Nevada, Ohio, Virginia and New Hampshire) all go to McCain then the Electoral college ties and it would just take one other state (like New Mexico) to push it over.
The analysis of each state can be done well with polls and historical data and the market prices and polls for the individual states do not differ that much. But understanding the correlations between states is more guesswork and I trust the wisdom of the crowds over the wisdom of the one.
6:42 AM #
Archives
