This work is licensed under a
Creative Commons License.
|
Monday, January 05, 2009
Stephen Kleene: Not A Regular Guy
Posted by Lance
The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical computer science course more than Kleene. Kleene gave usand much more.
- Regular expressions and their equivalence to langugages accepted by finite automata. That's why we call them Regular Languages.
- Kleene Closure, the * operator in regular expressions. L* is the set of all finite concatenations of strings in L. Source of great homework problems, for example: Show P is closed under Kleene closure.
- A recursive definition of Turing's languages, the reason they are often called Recursive Languages (though not without controversy).
- The terminology Church's thesis that we now call the Church-Turing thesis (though more controversy).
- The arithmetic hierarchy, a forerunner of our polynomial-time hierarchy.
- The Smn theorem that one can uniformly hardwire part of the input into the code of a Turing machine.
- The recursion theorem (sometimes called the Kleene fixed point theorem) that informally says no matter how nasty the virus, some program remains unscathed.
Klenne passed away January 25, 1994 in Madison, Wisconsin where he spent most of his academic career.
8:22 AM
# 0 comments
Friday, January 02, 2009
Randomness in Voting
Posted by Lance
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, like the current senate race in Minnesota or the 2000 presidential race in Florida, every vote gets scrutinized very carefully and the process can drag out for months.This scrutinization ignores the randomness factor. Some people got stuck in traffic or maybe had some emergency that prevented them from voting. Some people went to the wrong voting area or their registration got lost. Some people just plain filled in the wrong oval, voting for the wrong candidate. These problems are rare and roughly cancel themselves out but in a very close election like Minnesota the randomness greatly outweighs the disputed ballots. Yet because of the hard cut-off the scrutinized ballots get the most attention.
I suggest we eliminate the hard-cut off by adding our own randomness. For simplicity suppose we had two candidates, Al and Norm, who received x and y votes respectively. We flip z=x+y uniform random coins. If the number of heads is at most x we declare Al the winner and Norm the winner otherwise. If x > z/2+ 10 z1/2 then this process would make Al the winner almost all the time. But as x and y get very close the probability that Al wins approaches 1/2. Since a change of a few disputed votes won't affect the probability dramatically, we won't have so many battles over so little.
9:03 AM
Wednesday, December 31, 2008
2008 Complexity Year in Review
Posted by Lance
Paper of the year goes to Optimal algorithms and inapproximability results for every CSP? by U. Washington grad student Prasad Raghavendra. The paper gives a semidefinite program approximating any constraint satisfaction problem, always the best possible approximation if the unique games conjecture holds.Some other notables: Aaronson-Wigderson's Algebrization, Raz's counterexample to the strong parallel repetition theorem and many others. Another good year for Complexity.
Despite the dozens of "proofs" that have come my way, the P vs. NP problem remains open. Maybe next year.
NSF funding for theoretical computer science are at the highest levels since I started this blog. Princeton hosts a new NSF sponsored Center for Computational Intractability and Microsoft opened a new research lab in Cambridge, Mass. The theoretical computer science landscape looks quite strong.
However the current economic crisis will pose great challenges to computer science and all of academics as university budgets tighten. Great research can happen in awful economies—computability theory got its start during the great depression for example. But we all suffer if we lose a generation of theorists to this economy.
We remember David Gale, Nick Reingold, Ingo Wegener and others who inspired our lives, George Carlin, Arthur C. Clarke, Michael Crichton, Bobby Fischer and Randy Pausch.
We thank guest posters Richard Beigel, Manuel Bodirsky, Rance Cleavland, Iftah Gamzu, Evan Golub, Nicole Immorlica, Kamal Jain, Joe Kruskal, James Lee, Richard Matthew McCutchen, Amir Michail, Ketan Mulmuley, Vahan Mkrtchyan, Kirk Pruhs, Ken Regan, Rahul Santhanam, Uzi Vishkin, Philipp Woelfel and Jens Zumbraegel for their contributions to our blog this year.
A personal thanks to Bill Gasarch, not only for allowing me to come back to the blog and staying on as co-blogger, but also for organizing a great Computational Complexity Conference at Maryland.
I will always have many great memories for 2008. I started a new job at Northwestern in January and it was a great first year. My eldest daughter became a teenager and had her Bat Mitzvah in May. And after an entertaining election season, our junior senator is just weeks away from becoming the first African-American president of these United States of America. An exciting year indeed.
7:23 AM
Wednesday, December 24, 2008
The Rooster
Posted by Lance
My daughters came up with the following joke.Two roosters sat on on a barn. The first rooster asked the second what time he was supposed to crow. The second rooster replied "in the morning".After coming up with the joke, my daughters wanted to change the Wikipedia entry for morning to make the joke funnier but I talked them out of it. I always have a hard time convincing them that Wikipedia is usually quite trustworthy when their teachers at school keep pounding on how unreliable Wikipedia can be.At 12:01 AM, the first rooster screamed "Cockle-Doodle-Do" waking up the farmer and his family. The second rooster said "Why are you doing that now?"
The first rooster said, "I looked up 'morning' in Wikipedia and it said morning starts at midnight."
The moral of the story: Don't trust Wikipedia.
Enjoy the holidays. We'll be back next week with the Complexity Year in Review.
7:52 AM
Tuesday, December 23, 2008
Springer Open Choice
Posted by Lance
First some administrative stuff. Posting will be light until the New Years. The comments feed is not working properly—Blogger is working on it. I deleted a spam comment from my spam post before I realized the comment was a joke. Sorry.We just finished up an article for the Springer journal Theory of Computing Systems. If you go to the article's web page you'll see the paper is open access, you can download it from anywhere. How did that happen?
In the final stages of production, Springer offered us the opportunity to have our paper in their new Open Choice plan. For a fee we could have our paper downloadable with a license similar to that used by Creative Commons for non-commercial use.
That fee would be $3000, far too much than I'm willing to pay to let you download the paper from Springer when you can download a version from my home page for free.
But Springer has deals with some institutions, mostly Dutch, to offer Open Choice for all their papers. And one of my co-authors is Dutch. So enjoy!
7:01 AM
Monday, December 22, 2008
No Good Deed Goes Unpunished
Posted by Lance
From the Ethicist in yesterday's New York Times Magazine.Another college professor and I wanted a student to work on a project of ours, but she is a Mac user and the project required a program written for the PC. My colleague's husband, a Ph.D. in computer science, suggested an alternative program the student could download. She did; her computer froze and would not restart. The husband refused to assist her further. As the spouse of a colleague and the person whose advice caused the problem, isn't he obligated to help?Randy Cohen, the Ethicist, gave a wishy-washy response that the husband doesn't have to help but he should.Ignoring the whole Mac/PC issues, why is "a Ph.D. in computer science" relevant to the story? We don't get the fields of the questioner or the colleague.
I certainly would stop giving advice if every time I recommended a program there was an implicit promise of additional support. Though my Ph.D. is in Applied Math so the situation above doesn't apply to me.
Reminds me of some good advice I got as an undergrad when I was working as a programmer for Cornell computer services. Some person called me by mistake asking for some technical support and I helped him out. But then this person kept calling. My officemate suggested I give him some wrong but harmless advice. The caller thought I was an idiot and never called again. Problem solved.
1:14 PM
Friday, December 19, 2008
Predicability in Movies: was there ever a case where...
Posted by GASARCH
This post was inspired by HALF of the movie FLIGHTPLAN.
I have watched HALF of the movie FLIGHTPLAN. In the movie Kyle Pratt (played by Jodie Foster- I didn't know that know that Kyle could be a girls name) takes her 6 years old kid on an airplane, the kid disapears, and the Flight Manifest said she was never there. So the captain and others think that Kyle is nuts.
Having not seen the rest of the movie yet I wonder which is true: (1) Kyle Foster IS nuts, or (2) there is some weird conspiracy going on. Gee, I wonder which one it will be!
In the real world I would of course assume (1). But since its a movie I absolutely know that (2) will be the case. The only point of suspense for me is will the final explanation make sense?.
SO, here is my question: Do you recall ever seeing a movie or TV show where it is clear that EITHER (1) the main character is nuts, or (2) there is a massive conspiracy. and it ends up being (1)? (I don't count if it ends up being a dream.)
YES, I know that if the main character was just nuts the story might not be as interesting. However, they should have the main character be nuts once in a while so that its not so predicable. That way when watching these things we would have a genuine question and genuine suspense. As for making it interesting- thats their job!6:52 AM
Thursday, December 18, 2008
Have We Solved Spam?
Posted by Lance
The amount of spam in my spam folder has dropped below fifty per day down from several hundred a few months ago. The amount of spam that gets through Gmail's filters to my inbox is well under one a day. I'm not sure why. Better spam filters, better enforcement, less economic incentives for spam, maybe even the bad economy is playing a role. While not completely solved, email spam is no longer a significant problem for me.This has happened without you having to pay me, solve a CAPTCHA or have your computer solve some hard problem to send me email. I have a mailto link on my home page (albeit generated by javascript code) and my various email addresses show up in plaintext on hundreds of pages scattered over the Internet.
For those of you who insist on making it painful to send you email (anything beyond a simple click or cut-and-paste without further editing), time to change your ways and not make your fear of spam make extra work for those of us who simply want to say hello, and maybe ask you to review a paper.
6:23 AM
Archives
