Computational Complexity

Friday, February 29, 2008

 
ToCT is a Go

Posted by Lance

The ACM Transactions on Computation Theory, with yours truly as Editor-in-Chief, is now accepting submissions.

ACM Transactions on Computation Theory will cover theoretical computer science complementing the scope of the ACM Transactions on Algorithms and the ACM Transactions on Computational Logic including, but not limited to, computational complexity, foundations of cryptography, randomness in computing, coding theory, models of computation including parallel, distributed and quantum and other emerging models, computational learning theory, theoretical computer science aspects of areas such as databases, information retrieval, economic models and networks.

The journal will be available online on the ACM Digital Library and to those who are SIGACT Members ($18/year which also gives you access to STOC proceedings, ACM Transactions on Algorithms and SIGACT News).

We have an excellent editorial board awaiting your papers. So either go to the ToCT web page or directly to the submission server, submit your papers, and come in on the ground floor of what will be one of the great theory journals.

7:21 AM #

Thursday, February 28, 2008

 
Ineffective Spam- or is it?

Posted by GASARCH

I recently got the following spam which I will paraphrase.

I hate to me the one to tell you this but everyone is talking about how fat you are. Its disgusting. As a friend, I recommend going to THIS WEBSITE to buy a product that will help you shed those unsighly pounds.

Since I am thin and computer-savy (at least in this regard) I knew it was spam. However, even if I was fat and naive I would still know it was spam since I got 25 copies of this email from different addresses. Wording was identical.

1. Could someone really fall for this after getting 25 copies?
2. Are there still people out there who fall for these things at all? (I assume yes since I still get plenty of spam.)
3. Did they send out that many hoping that only one would get through? So they were counting on good spam filters. This makes their target people who are fat, naive, and have good spam filters. A thin demographic.
4. More generally, I wonder if spam-scams are less effective then they used to be becuase people are getting wise to them. Or are they more effective as more people begin working on the web every day.

11:11 AM #

Wednesday, February 27, 2008

 
When good recommender systems go bad!

Posted by GASARCH

Lance brought up the question of amazon giving bad or odd here. The oddest pointer to an item I might want is as follows.

I bought a novelty CD by a group called Throwing Toasters (it was very good). I then was asked by amazone Do you want to buy a toaster? and got a pointer to home applicances.

Why did it make that association? Asking various computer people I got three answers. The only thing they had in common was that everyone was sure they were right.

1. When many people buy an item the amazon software can do a reasonable data mining and make intelligent guesses about what groups of items go together. However, since this item was probably not bought by many people, it does a random word search algorithm instead.
2. Of the few few people who bought this item before, some of them did buy toasters as well! So if only 4 other people bought this item, but 1 of them also bought a toaster, then WOW- 1/4 of all people who bought this item bought toasters, so its worth inquiring if the current purchaser wants one.
3. Its a programming bug.

I don't know which one it is, but I'd like to know.

1:33 PM #

Tuesday, February 26, 2008

 
FOCS 2008 Call For Papers is available

Posted by GASARCH

FOCS call for papers is out: here and here. (These look the same but the websites I was emailed look different.)

1. I have never been able to differentiate FOCS from STOC and most people say STOC-FOCS as though it is one word. If someone else knows of a difference they had in the past, please enlighten.
2. The content of both of them have changed over time. In Complexity its gone from more logic-based to more combinatorics-based. In Algorithms I expect that its changed but don't know the paradigm shift. If somone else does, please enlighten.
3. When I have knowledge of a paper (e.g., I'm a co-author or proofread it carefully for the author) that is rejected from COMPLEXITY and go to the conference, I have one of the following opinions afterwards:
   1. There is NO paper here that is so obviously worse than mine that it should have been turned down and mine should have gotten in. (This is quite common.)
   2. There ARE papers that are obviously worse than mine and should have been turned down, and mine should have gotten in. (This is very rare.)
4. By contrast, for STOC-FOCS, I usually have a hard time telling how a paper compare with ones that make it. It can be hard to compare a paper in (say) Complexity with one in (say) Algorithms.

9:37 AM #

Monday, February 25, 2008

 
Outed by Amazon

Posted by Lance

Either the worst or the best example of a recommendation system in action.

Via parterre box

6:19 AM #

Friday, February 22, 2008

 
Compulsory Voting with Careful Consideration of Choices

Posted by Lance

Guest Post by Amir Michail

It's hard to understand why people vote. If we put aside social pressure (e.g., what your friends and family think) and sense of duty, a rational person should be embarrassed at having wasted any time at all on voting—in the same way that a rational person would be embarrassed at having bought a lottery ticket.

To address this problem, one might consider a compulsory voting system where it takes the same effort to vote as to cast a "no vote". It's compulsory in the sense that if you do nothing, then you will be subject to a significant fine.

But even such a system is not enough as people could simply vote randomly. In fact, a rational person should vote randomly since admitting to having voted otherwise would be embarrassing given the insignificant probability of making a difference.

So how do we require people not only to vote (possibly casting a "no vote") but also think carefully about their choice?

Two ideas:

1. Compulsory Voting in Blocks

   To vote for X you would need to write the names of at least k other people whom you know are voting for X (this applies also for a "no vote"). This would encourage more people to have discussions with their friends/family and think more carefully about their choice. However, one could argue that rational people would select a candidate randomly in blocks (since again for small k, the probability of making a difference is insignificant).

2. Compulsory Voting with Consequences

   Voters would be personally responsible for their choice. In particular, an objective measure would be used several years later to see whether their choice was a good one and they would be penalized/awarded financially correspondingly. This is sort of like a prediction market for politics with real money.

While (2) might seem more promising than (1), at least with respect to rational people, there's the issue of the choice of objective measure.

Do you have better ideas to require people not only to vote but to also take their vote seriously?

8:21 AM #

Thursday, February 21, 2008

 
Why is Lance Lance and GASARCH GASARCH?

Posted by GASARCH

A while back a comment asked Why is Lance Lance and Gasarch Gasarch? It meant why are posts by Lance labelled Posted by Lance where as posts by Gasarch and labelled Posted by GASARCH. Why use Lance's first name and Gasarch's last name? (It didn't ask why is GASARCH in caps. They likely knew its my trademark.)

Lance is not a rare name, but its rare enough that if you say Lance in the context of Complexity Theory, people know who you mean. Bill (or William) is a common name. There are two in my department: Bill Arbaugh who does security and Bill Pugh who does PL (he is known to the theory community for inventing skip lists). They don't do theory, but Bill Rounds, Bill Steiger, , Bill Roscoe, Bill Hesse, Bill Harrison all do. I don't know who Bill Marion is, but he wrote an article about why Discrete Math is good for computer scientists to know (the topic of another blog perhaps). (Some of these Bill's call themselves William.)

Which famous people are only known by one name? This depends on what you mean by famous and known. I could not find a list on the web, but by poking around I made up my own. Additions are welcome. I list them with comments on if I count them or not and why.

1. Bono- Paul Hewson. YES- Never knew his first name. Or his last name. Music.
2. Charo- Maria Rosaria Pilar Martinez Molina Baeza. YES. I can see why she went to one name. Actress?
3. Cher- Cherilyn Sarkisian LaPierre. YES. One name is better than her real name. Music and Movies.
4. Edge- David Evans. NO- never heard of this guy. Music.
5. Elvira- Cassandra Peterson. YES- A C-list celeb or lower. Could have used her real first name. Actress?
6. Elvis- Elvis Prestly. YES, though his last name is well known. Music.
7. Elvis- Elvis Costello. NO. He should have used Costello. Music.
8. Halston- Roy Halston Frowick. NO- never heard of this one. Fashion Designer.
9. Hammer- Stanley Kirk Hacker Burell. YES- though I thought he went by M.C. Hammer. Music.
10. Kreskin- George Joseph Kresge. Jr. YES- he was a famous mindreader.
11. Liberace- Wladziu Valention Liberace. YES. Didn't now Liberace was really his last name.
12. Madonna- Madonna Louise Veronica Ciccone. YES. Didn't know Madonna her really her first name. Music.
13. Prince- Prince Roger Nelson. YES. Didn't know Prince was really his first name. Also used this as a name. Music.
14. Sting- Gordon Matthew Sumner. YES. Could have used Gordon or Sumner as his one name. Well... maybe not. Music.
15. Mr. T- Lawrence Tureaud. YES- Is this one name? I say YES. Actor?
16. Topol- Chaim Topol. YES. Actor.
17. Twiggy- Leslie Horby. YES- Was more famous in an earlier era, but still a celeb. Dancer.
18. ***SORELLE***- a grad student in my department. She will be famous one day. She already has the name for it.

10:03 AM #

Wednesday, February 20, 2008

 
Campus Tragedy

Posted by Lance

The shooting at Northern Illinois University hits close to home. NIU is located in DeKalb, about 60 miles west of Chicago and it draws many students from the Chicago area. Our hearts go out to the victims and their families.

Since the Virgina Tech tragedy last spring, universities have beefed up security both in numbers and how they operate. The University of Chicago, Northwestern and my daughter's school district all recently implemented instant alert systems that emails and texts me, and call my home, mobile and office (which forwards to my mobile). But none of these preparations can stop a single incident like at Northern Illinois or the shooting death of University of Chicago graduate student Amadou Cisse last November during a robbery attempt, or an outright terrorist attack.

Nothing short of a fenced in perimeter with airport-style security can really keep a campus safe. So must we have an unsafe academic environment? If fact we don't. The number of campus shootings is quite low, considerably less than deaths due to suicide or alcohol abuse. Campus shootings just get more press because they are rare and often have multiple victims. These press reports never seem to mention that the vast majority of college student somehow manage to graduate without permanent injuries of any kind.

11:05 AM #

Tuesday, February 19, 2008

 
More funny answers on math olympiad

Posted by GASARCH

(I had a prior post on FUNNY ANSWERS TO MATH OLYMPIAD QUESTIONS: here. This one is a different problem.)

In 2000 I made up and graded the following problem from the Maryland Math Olympiad from 2007 (for High School Students)

There are 2000 cans of paint. Show that at least one of the following two statements is true:

1. There are at least 45 cans of the same color.
2. There are at least 45 cans of all different colors.

It was problem 1 so it was supposed to be easy 95% of the students got it right and I suspect everyone reading this blog can do it. Note that the students taking this exam, Part II of a math olympiad, did well on part I, so they are good students. (Part I is 25 TOUGH multiple choice questions, point off if you are wrong, and Part II is 5 problems that require proofs.)

I got two funny answers:

ANSWER ONE: Paint cans are grey. Hence there are all the same color. Therefore there are 2000 cans that are the same color.

ANSWER TWO: If you look at a paint color really really carefully there will be differences. Hence, even if two cans seem to both be (say) RED, they are really different. Therefore there are 2000 cans of different colors.

Were they serious?

The first one points to a problem with the phrasing of the question- I clearly did not mean the cans themselves, and all of the other students knew that, but looking at the problem it could be interepreted that way. This person might have been serious.

The second one I can't imagine was serious.

1:00 PM #

Monday, February 18, 2008

 
Engineering Challenges

Posted by Lance

The National Academy of Engineering released their Grand Challenges for Engineering on Friday:

• Make solar energy economical
• Provide energy from fusion
• Develop carbon sequestration methods
• Manage the nitrogen cycle
• Provide access to clean water
• Restore and improve urban infrastructure
• Advance health informatics
• Engineer better medicines
• Reverse-engineer the brain
• Prevent nuclear terror
• Secure cyberspace
• Enhance virtual reality
• Advance personalized learning
• Engineer the tools of scientific discovery

Many of these challenges have direct or indirect connections to computer science but I wish they had made more reference to the deep algorithmic issues that would play such an important role in these challenges and in society in general.

5:55 AM #

Friday, February 15, 2008

 
Valiant wins EATCS award

Posted by GASARCH

Valiant won the EATCS award. This was already reported on Luca Aceto's blog To goto Valiants website go here To goto the EATCS annoucement of why they are giving it to Valiant go here

So what has Valiant done? Here is an incomplete high level list which may be exaggerated.

1. Defined #P and showed Perm was NP-complete and also that most NPC problems have #P analogs.
2. Was co-author on Valiant-Vazarani paper (duh). Main result: if given a formula that you KNOW has either 0 or 1 SAT assignments, telling which one is hard (unless NP=R). Was also a first step towards Toda's theorem.
3. Defined PAC learning.
4. Defined Superconcentrators- a kind of expander graph.
5. Started Algebraic analogs of Boolean Complexity.
6. Had some stuff on parallelism.
7. Started the recent Matchgate algorithm paradigm.
8. Put up with me being his TA for Combinatorics.

I'm surprised he hasn't won the Turing Award yet, but I'm sure he will.

10:33 AM #

Thursday, February 14, 2008

 
There is no such thing as a sure thing

Posted by GASARCH

Flashback to 1973: The Miami Dolphins were 16-0 before the superbowl. Yet they were underdogs! As a naive kid I did not understand this. My dad explained to me that the Washington Redskins (the other team) had a harder schedule. Even so, if you win every game you must be doing something right. I thought it was a sure thing!!- They WON so I was right! Unfortunately I did not bet my dad on the game.

Flashforward to 2008: The New England Patriots were 18-0 before the superbowl. They were favorites! As a naive adult I just assumed they would win. My father-in-law explained to me that the New England Patriots won some games they should have lost. Even so, if you win every game you must be doing something right. I thought it was a sure thing!!- They LOST so I was wrong! Fortunately I did not bet my father-in-law on the game.

Flashback a little bit to just before Superbowl 2008. Past history indicates that superbowls almost never have an exciting finish. As naive adults, my father, my father-in-law, and I just assumed there would not be an exciting finish. We thought it was a sure thing!!- The game HAD an exciting finish- so we were wrong! Fortunately, we did not bet on this.

Flashback a little bit to just before Superbowl 2008. Past history indicates that superbowls almost never have an exciting finish. As naive adults, my father, my father-in-law, and I just assumed there would not be an exciting finish. We thought it was a sure thing!!- The game HAD an exciting finish- so we were wrong! Fortunately, we did not bet on this.

Actually you can't bet on there will not be an exciting finish since its not that well defined. By contrast, you can bet on (I am not making this up) the first touchdown will be scored by a player from one of the top 100 schools via US News and World Reports rankings.

10:42 AM #

Wednesday, February 13, 2008

 
Average Case versus Worst Case

Posted by Lance

A young theorist said something like this in a recent talk.

Complexity theorists studied worst-case complexity until the mid-80's and then have focused on average-case complexity since.

I asked him why he though that and he said that he had given an earlier talk and said complexity theorists focused only on worst-case complexity and was told this wasn't true since the mid-80's.

What did happen in the mid-80's? Levin came up with his definition of average-case complexity classes. Modern cryptography started to really grow around then with their emphasis on hard on average assumptions. Results like Nisan-Wigderson connected average-case hardness with derandomization.

But most of the great work in complexity continued to focus on worst-case complexity: Circuit lower bounds, nondeterministic space closed under complement, Toda's theorem, interactive proofs, PCPs, hardness of approximation results, Primes in P, SL=L and much more. Even derandomization results are now based on worst-case hardness.

Why the focus on worst instead of average case? We can't know the underlying distributions for sure and worst case complexity handles any distribution.

In crypto they know the underlying distribution since their protocols create it. But now even in that community you now see a slight move to base protocols on worst-case assumptions, using average-to-worst case reductions for lattice-based problems. I worry though that these average-to-worst case reductions imply less that the average case complexity of these problems are harder than we expected and more that the worst case is easier than we thought.

5:32 AM #

Tuesday, February 12, 2008

 
The Moment of Truth

Posted by Lance

The list of accepted papers for the 2008 IEEE Conference on Computational Complexity has been posted. Since I was on the PC I won't talk about specific papers, though I am very happy with the decisions we made. A special thanks to Paul Beame, the PC chair, who did an excellent job running the electronic PC meeting.

The conference itself will be held June 23-26 on the University of Maryland–College Park Campus, locally organized by Richard Chang, Marius Zimand and our very own Bill Gasarch.

5:49 AM #

Monday, February 11, 2008

 
The Candidates on Science Funding

Posted by Lance

Neither of the Democratic candidates have pushed science funding as a major theme in their campaigns, but I pulled out the sections about non-medical funding from their websites below. Upshot: Clinton has a far more detailed plan, but offers only half as much additional funding as Obama.

Read Obama's first sentence. Bush gets his "anti-science" label because he often ignores scientific arguments in policy decisions. But Bush has tried to fund science, proposing budgets to double the NSF just as Obama claims he himself would do. But science has become one of the casualties of a weak incumbent.

Given the large domestic agendas of Clinton and Obama, we cannot know now how hard they would push for science funding if elected. Bush has proposed a 14% increase in the NSF for 2009 and we should push Congress to appropriate these funds. It might be the last chance for a while to get a much needed funding increase for science.

Barack Obama:

Invest in the Sciences: Barack Obama supports doubling federal funding for basic research, changing the posture of our federal government from being one of the most anti-science administrations in American history to one that embraces science and technology. This will foster home-grown innovation, help ensure the competitiveness of US technology-based businesses, and ensure that 21st century jobs can and will grow in America. As a share of the Gross Domestic Product, American federal investment in the physical sciences and engineering research has dropped by half since 1970. Yet, it often has been federally-supported basic research that has generated the innovation to create markets and drive economic growth. For example, one recent report demonstrated how federally supported research in fiber optics and lasers helped spur the telecommunications revolution.

Hillary Clinton:

Increase the basic research budgets 50% over 10 years at the National Science Foundation (NSF), the Department of Energy's Office of Science, and the Defense Department. The increased investment can be accomplished through a combination of new and reallocated funds. At present, federal expenditures on basic research total $28 billion, $13 billion of which is spent outside of the National Institutes of Health (NIH).

• Increase research focus on the physical sciences and engineering. Funding for research in the physical sciences and engineering have remained relatively flat for over a decade, while other nations have stepped up spending. Hillary Clinton proposes to direct the federal agencies to commit a large portion of their budget increases to research in these areas.
• Require that federal research agencies set aside at least 8% of their research budgets for discretionary funding of high-risk research. It is critical to support unconventional research that has the potential of producing break-through results. Under the Bush administration, agencies like the Defense Advance Research Projects Agency (DARPA) have reduced support for truly revolutionary research. This is a problem because DARPA has played a major role in maintaining America’s economic and military leadership. DARPA backed such projects as the Internet, stealth technology, and the Global Positioning System.
• Ensure that e-science initiatives are adequately funded. E-science has transformative potential, and we must accelerate the pace of discovery and investment to ensure that America leads the emerging field. E-science is research that links Internet-based tools, global collaboration, supercomputers, high-speed networks, and software for simulation and visualization. The potential of e-science is great. For example, researchers could one day model climate change by constructing scale simulations of the Earth’s systems. The NSF commits approximately 3% of its budget, or $200 million annually, to the support of e-science through its Office of Cyberinfrastructure.
• Boost support for multidisciplinary research in areas such as the intersection of bio, info, and nanotechnologies. This is an area of potentially unique competitive advantage for the United States. Few countries have the depth and breadth of our excellence across different scientific and technological fields.

Direct the federal agencies to award prizes in order to accomplish specific innovation goals. The federal agencies should regularly use prizes to encourage innovation when there is a clearly defined goal and when there are multiple technological paths for achieving that goal. Prizes can attract non-traditional participants and stimulate the development of useful but under-funded technology. Hillary Clinton proposes to make prizes a part of the budgets at the research agencies.

Triple the number of NSF fellowships and increase the size of each award by 33 percent. At present, the NSF offers approximately 1,000 fellowships per year, similar to 1960s levels, although the number of college students graduating with science and engineering degrees has grown three fold. The NSF fellowship is the key financial resource for science and engineering graduate students. Hillary Clinton proposes increasing the number of fellowships to 3,000 per year. She also proposes increasing the size of each award from $30,000 to $40,000 per year (simultaneously, she proposes to increase the NSF award to each recipient’s school from $10,500 per recipient to $14,000 per recipient to help cover educational costs). It is estimated that this would increase the annual cost of the program from $122 million to $500 million. [Richard Freeman, the Hamilton Project, "Investment in the Best and Brightest," December 2006]

Support initiatives to bring more women and minorities into the math, science, and engineering professions. Increasing the educational attainment of women and minorities, particularly in math, science and engineering, is critical to our future as an innovative nation. Women comprise 43% of the workforce but only 23% of scientists and engineers. Blacks and Hispanics represent 30% of the workforce, but only 7% of scientists and engineers. Unless women and underrepresented minorities develop strong math, science, and engineering skills, the average educational attainment of the American worker will decline. Hillary Clinton proposes that the federal agencies adopt criteria that take diversity into account when awarding education and research grants. She also proposes that the federal government provide financial support to college and university programs that encourage women and minorities to study math, science, and engineering.

I can find nothing from John McCain or Mike Huckabeee about non-medical science funding.

6:19 AM #

Friday, February 08, 2008

 
Ten greatest Math Puzzles of All time- NOT

Posted by GASARCH

There is a book The Liar's Paradox and The Towers of Hanoi: The Ten greatest Math Puzzles of all Time Thats just two problems; however, the book does have 8 more puzzles. I list them below.

1. The Riddle of The Sphinx. Is this even a math puzzle? They say that it is since it involves making analogies.
2. The Alcuin River Crossing Puzzle. Trying to cross a river with a Wolf, Goat, and Head of Cabbage. Very old problem in what is now graph theory. This problem did not start graph theory, but could have.
3. Fibonacci's Rabbit Problem. Possibly the first recurrence.
4. Euler's Koningsberg Bridge Problem. This problem started graph theory.
5. The Four color problem. This generated alot of math of interest. They claim `the solution changed math as we know it'
6. Towers of Hanoi. A nice exercise (my wife coded it up when she took CS 1, I've taught it in Discrete Math), but not that big a deal.
7. Lloyd's get-off-the-earth puzzle. This is similar to Rubits cube in spirit. I never heard of it before this book.
8. Liar's paradox. Classic and very old. Could be the first serious study of self reference.
9. Magic Squares. C'mon, not that important!
10. Cretan Layrinth (Mazes). Very old, but again, not that important.

To ask if these are great math puzzles, you have to define great, math, and puzzle.
Great: Influential? Interesting Mathematically? Interesting Historically? Important? Intrinsic math value? Intellectually challenging? Other adjectives beginning with I? If great means influential then some of the above qualify: Fib Rabbits, Euler Bridge, Four-color, Liar's paradox. Others may also qualify- I would need to know more about the history of math to tell.

Math: I can't define it but I know it when I see it. Riddle of the Sphinx I would say no. The rest are reaonable to call math.

Puzzle: A non-math person can understand the question and think about it, and hopefully have fun with it. They all qualify.

10:53 AM #

Thursday, February 07, 2008

 
Movie Mathematicians

Posted by Lance

On Tuesday IMDB ran a poll on "Who is your favorite movie mathematician?" Let's consider the nominees, all white, male and American.

Dustin Hoffman has two roles, his revenge-seeking astrophysicist in Straw Dogs (which I haven't seen) and as Rain Man, an autistic savant. Shame on IMDB for confusing savants and mathematicians.

Russell Crowe gives an excellent portrayal of the hallucinating game theorist John Nash and Anthony Hopkins has a decent role as an older mathematician with dementia. But both these movies add to a stereotype connection between mathematicians and mental disease. Jake Gyllenhaal's math student in Proof (not nominated) better portrayed the excitement a mathematician feels.

Sean Penn gave a fine acting performance in 21 Grams, but the mathematics plays no role in the story or in how Penn portrays his character.

Jeff Goldblum in Jurassic Park plays the kind of scientist that always annoys me: lots of neat parables with no mathematical meat behind them.

I have heard nothing but contempt from my colleagues by the way Matt Damon's janitor turned mathematician is presented, and thus it wins the poll. At least Good Will Hunting does a nice job promoting the Fields Medal.

I did see Pi years ago but the movie was a confusing blur to me.

Which leaves my favorite, the TV crime-fighting mathematician Charlie Eppes portrayed by David Krumholtz. Reportedly Krumholtz hung out with Caltech mathematicians to prepare for the role and he gets it pretty close to right, a slightly shy, very smart and otherwise normal person who just has lots of fun talking and doing math.

10:14 AM #

Wednesday, February 06, 2008

 
This years Turing Award: Model Checking

Posted by GASARCH

Guest Post by Rance Cleavland, professor at University of Maryland at College Park, who works in Model Checking.

Earlier this week, the ACM announced the winners of the 2007 ACM Turing Award (awarded in 2008, for reasons that elude me). They are Edmund Clarke (CMU), Allan Emerson (U. Texas) and Joseph Sifakis (Verimag, in France). The award statement honors the contributions of these three to the theory and practice of model checking, which refers to an array of techniques for automatically determining whether models of system behavior satisfy properties typically given in temporal logic.

After first blanching at the application of an adjective ("temporal") to a term ("logic") that is usually left unqualified, a Gentle Reader may wonder what all the fuss is about. Is model checking really so interesting and important that its discoverers and popularizers deserve a Turing Award? The glib answer is of course, because the selection committee must have a fine sense of judgment. My aim is to convince you of a less glib response, which is that model checking is the most fundamental advance in formal methods for program verification since Hoare coined the term in the 60s.

What is "model checking"? In mathematical logic, a model is a structure (more terminology) that makes a logical formula true. So "model checking" would refer to checking whether a structure is indeed a model for a given formula. In fact, this is exactly what model checking is, although in the Clarke-Emerson-Sifakis meaning of the term, the structures - models - are finite-state Kripke structures (= finite-state machines, except with labels on state rather than transitions and no accepting states), and the logical formulas are drawn from propositional temporal logic (= proposition logic extended with modalities for expressing always in the future and eventually in the future").

The Clarke-Emerson-Sifakis algorithmic innovation was to notice that for certain flavors of temporal logic (pure branching time), model checking could be decided in polynomial time; this is the gist of the papers written independently in 1981 by Clarke and Emerson on the one hand, and Sifakis and Queille on the other. Subsequently, these results were improved to show that model checking for pure branching-time logic is proportional to the product of the size of the Kripke structure and the size of the formula (often, maybe misleadingly, called "linear time" in the model-checking community, since the size of the model dominates the product).

Of course, a linear-time algorithm (OK, I'm in the model-checking community!) is only of passing interest unless it has real application. This comment involves two questions.

1. Is the general problem one people want solved?
2. Can the algorithm produce results on the instances of the problem people want solved?

The answer to 1 is "YES YES YES". The ability automatically to check the correctness of a program/hardware design/communications protocol would offer incalculable benefits to developers of these systems. Early on, the answer to 2 for model checking was in doubt, however, for the simple reason that the size of Kripke structure is typically exponential in the size of the program used to define it. (State = assignment of values to variables, so num-of-states is exponential in num-of-variables, etc.) Throughout the 80s and 90s, the three winners worked on many techniques for overcoming the state-explosion problem: compositional techniques, symmetry reductions, etc. One of the most successful was symbolic model checking: the use of logic formulas, rather than linked lists, etc., in the model-checking process to represent large sets of states. While none of these techniques proved uniformly applicable, symbolic model checking found a home in the hardware-design community, and model-checkers are now standard parts of the design flow of microprocessor design and incorporated routinely in the design tools produced by companies like Cadence, Synopsys and The MathWorks.

So what to make of the Turing Award? I would say that the algorithmic innovation was deep and insightful, but not the source of the award. Rather, the combination of the initial insight, together with the persistence of the award winners in identifying engineering advances to further the state of the practice, is what earned them their, in my view well-deserved and maybe even over-due, prize.

2:57 PM #

Tuesday, February 05, 2008

 
WSEAS: A Greek Tragedy

Posted by Lance

This is a joint post by Lance AND Bill in response to this post on the Sfaka blog claiming "false and misleading information" on our blog (scroll down). We would like to set the record straight.

1. On November 27 GASARCH made two posts about bogus conferences. In the post Bogus or Not–You Decide, an anonymous commentor asked about whether it would be a turn-off if a WSEAS paper was on the resume.

   Some folks I worked with in the past published some of our work as a conference paper in WSEAS proceedings with my name on it. (I think they might not have known about junk conferences.)

   In the post Theoretical and Mathematical Foundations of Bogosity, Bill said

   I looked on the web for more info on [TMFCS08] and could not find anything saying it was bogus (By contrast you can find stuff about WSEAS being bogus). Anyone have any more information?

2. On Tuesday, January 15, Nikos Mastorakis, executive director of WSEAS, called Lance very angry about the November posts and comments. Mastorakis wanted us to remove the offending statements about WSEAS. We decided against this and sent him email offering him to do a Guest Post defending the conference. GASARCH and Lance also agreed that they would not make comments on his post, and would post it unedited. Mastorakis called Lance back the next day, still very angry and unhappy with our decision and threatened to complain to the "president of the United States". At which point Lance hung up on him.
3. Mastorakis tried to call Lance many times over the next couple of days but Lance refused to answer. He also called GASARCH at home, but having heard about this from Lance, GASARCH hung up immediately. GASARCH emailed him that calling at home is unacceptable, but calling at the office is fine, and also gave his office phone number. He never called at the office.
4. On Friday, Lance decided to answer the phone from Mastorakis. Mastorakis apologized, but still angry about the comments. He wanted to write the guest post but with the comments turned off. (That is, he could post defending the conference, but nobody could comment on it.) We refused and he said he would still send us a post. We haven't heard back from him since.
5. On January 29, a comment appeared on the first post defending WSEAS from someone claiming to be Shuchen Li, though his web page looks Greek to us.
6. Also on January 29, the SFAKA post appeared (without our knowledge) warning about false and misleading information and quoting the Bogus or Not post but with the following change: wherever the phrase `WSEAS' appeared it now says `GASARCH'. For example (compare with above)

   Some folks I worked with in the past published some of our work as a conference paper in GASARCH proceedings with my name on it. (I think they might not have known about junk conferences.)

Draw your own conclusions.

1:16 PM #

Monday, February 04, 2008

 
Short Cuts

Posted by Lance

I had planned on a post today on "What is Perfection?" but since the answer is not "The Patriots," I will wait for a more appropriate time.

The list of accepted papers for STOC 2008 is out. I have one accepted paper, an old-fashioned complexity result with Rahul Santhanam that I will blog about more at a future time. Strange fact: I haven't given a regular STOC-FOCS talk since FOCS '92. A combination of younger co-authors, some bad timing (missed STOC '98 for the birth of my younger daughter) and admittedly not as many STOC/FOCS papers as I would have liked. The streak will continue as I will miss STOC this year for my older daughter's Bat Mitzvah.

Meanwhile there are quite a few good complexity papers on the STOC list, Scott and Avi's Algebrization paper heads the must reads.

Microsoft announced the opening of a new research lab in Cambridge, MA in July headed by Jennifer Chayes. The lab will have a strong theory component. More broadly how would the proposed Microsoft acquisition of Yahoo! affect computer science research at both companies? One more thing to watch as we see the merger play out.

9:51 AM #

Friday, February 01, 2008

 
The Final Two

Posted by Lance

Run a tournament that does a series of comparisons to decide a winner. No matter what algorithm you use, there will always be that final comparison, before which we had exactly two possible candidates to emerge victorious.

In America we are seeing those final rounds play out in a variety of forums this week. The Republican and Democratic fields have been whittled down heading into Super Tuesday where nearly half the states, including Illinois, have their primaries. The Super Bowl on Sunday evening pits the final two football teams against each other.

So what will it be? Clinton or Obama? McCain or Romney? Patriots or Giants? Stay tuned.

6:08 AM #

Archives