NSF Theory Solicitation Announced

The NSF posted the new Theoretical Foundations program solicitation, due date May 25.

The solicitation divides the program into three areas, "Scientific Foundations for Computing", "Scientific Foundations for Communication" and a new area "Scientific Foundations for Internet's Next Generation" (SING) part of the GENI Initiative. Computational Complexity falls into the first area though all of these areas ask important theoretical questions.

The NSF now allows you to submit via Grants.gov instead of Fastlane unless you have a (A) Collaborative Proposal or (B) Subawards. They should also add (C) Don't use Windows.

Deal or No Deal Redux

The NBC game show Deal or No Deal resumes with new episodes tonight. I described the game when it first ran in December where we discussed the game from the player's perspective. Now let's look at the game from the view of the Banker.

Suppose the Banker always offered the expected value of the remaining cases. Could a player somehow make smart choices to increase his or her expected winnings? No. Let X be the random variable representing the value of the briefcase held by the player. Let Y be the random variable describing the briefcases open so far. A well known equality states E(E(X|Y))=E(X), i.e., the expectation of the expected value of the briefcase given the current game situation is just the original expectation of the briefcase. Any strategy by the player will yield exactly the same expected winnings, about $131,477.54.

Usually the Banker gives an offer below the current expected value of the briefcase. Why? As I mentioned in the previous post, the players are risk adverse and may accept a smaller guaranteed amount now. But more importantly a lower amount will increase the chances that a player will not accept the deal and play longer. The Banker pays an expected $131K per player not per episode and thus pays out less per episode the longer each player plays.

Computational Complexity Accepts

The accepted papers for the 2006 Conference on Computational Complexity have been announced. Some very exciting looking papers. I'll highlight some of them in a future post.

See you all in Prague.

Globalization and Offshoring

The ACM released a report today Globalization and Offshoring of Software. The New York Times has coverage. Definitely read over the executive summary of the report that dispels the myth that offshoring is leading to lesser need of information technology workers in the US. The overview has advice for current and future IT professionals.

One might wonder whether IT is still a good career choice for students and workers in countries that offshore software and IT services work. Despite all the publicity in the United States about jobs being lost to India and China, the size of the IT employment market in the United States today is higher than it was at the height of the dot-com boom. Information technology appears as though it will be a growth area at least for the coming decade, and the US government projects that several IT occupations will be among the fastest growing occupations during this time. There are some things that students and workers in this field should do to prepare themselves for the globalized workplace. They should get a good education that will serve as a firm grounding for understanding the rapidly changing field of IT. They should expect to participate in life-long learning. They should hone their "soft skills" involving communication, management, and teamwork. They should become familiar with an application domain, especially in a growth field such as health care, and not just learn core technical computing skills. They should learn about the technologies and management issues that underlie the globalization of software, such as standard technology platforms, methods for re-using software, and tools and methods for distributed work.

Update 3/1: The New York Times now has an editorial based on the report.

Oh Canada

This week I'm in Vancouver visiting Simon Fraser University which has a nice complexity group: Valentine Kabanets, Arvind Gupta, Gábor Tardos who just moved here from Hungary, Funda Ergun who visited the NEC Research Institute often when I was there and several postdocs including my former student Rahul Santhanam.

One of the big stories in Canada this week (besides the Olympics which will be held in Vancouver in 2010) are the legal problems of Research in Motion, the Canadian company famous for the Blackberry. Many of my lawyer/banker friends have these devices which they religiously check every time they get the comforting buzz of new email. There is a chance Blackberry users in the US may have their service cut off as early as Friday after a judicial hearing on a patent dispute.

Most academics have avoided the Blackberry craze but still the company plays an important role in computer science. Research in Motion executives have been heavy funders of the Perimeter Institute for Theoretical Physics and the Institute for Quantum Computing which have made Waterloo a major center of quantum computation. The IQC employs a large number of computer scientists in quantum computing such as fellow blogger Scott Aaronson.

So when you ride on the bus and hear your neighbor's Blackberry buzz, remember it's buzzing for science.

ACM Awards

The 2005 ACM Awards have been announced. Omer Reingold received the Grace Hopper Award given to the best "outstanding young computer professional of the year, selected on the basis of a single recent major technical or service contribution" in this case for his log-space algorithm for undirected connectivity. The previous theoretician to receive the award was Shafi Goldwasser in 1996 and before that Donald Knuth in 1971. Congratulations Omer!

Peter Naur won the Turing Award (the closest CS has to a Nobel Prize) for his work on Algol 60.

Gerald Holzmann, Robert Kurshan, Moshe Vardi and Pierre Wolper won the Paris Kanellakis Theory and Practice Award for their use of automata theory in program verification.

Thanks to Moni Naor for the pointer.

Accuracy of Predicted Probabilities

I stumbled upon the so called College Admissions Services which will give, for a fee, your percent chance of being admitted to undergraduate colleges in the US. I can't vouch for or against this service but I did catch an interesting claim of being 98% accurate. What does 98% accurate mean when you give probabilities? There are some reasonable answers to this question but not the one used by this site.

They do give the formula they use, roughly the fraction of people who didn't get refunds. Someone is eligible for a refund if the prediction was at least 51% and they didn't get in or the prediction was less than 50% and they were accepted.

What's wrong with this picture? Suppose everyone who was eligible for a refund got one. Consider people who they predict have a 60% chance of acceptance. This means 40% of them should not be accepted. But if they are all accepted they would have considered this a perfectly accurate prediction though it clearly is not. Conversely if 60% of them were accepted, this is what you expect but they would consider that only a 60% accuracy rate. And if they predict 50% the formula counts this as an accurate prediction even if all or none of them were accepted.

Either we have the very unlikely scenario that the rounding to zero or one of the prediction is a very good predictor or more likely that not many people claim the refunds they are entitled to. When you make a claim to accuracy that doesn't match the service you provide you end up giving no claim to accuracy at all.

Why Computer Science Theory Matters?

At the AAAS Annual Meeting on Friday, the CRA organized a session Computer Science Behind Your Science. Bernard Chazelle gave one of the talks Why Computer Science Theory Matters? based on an essay he wrote for the undergraduate magazine Math Horizons. In a pre-talk interview Chazelle argues that algorithms can help us explain scientific ideas in a fundamentally different way than simple mathematical formula.

Computer science is a new way of thinking, a new way of looking at things. For example, mathematics can't come near to describing the complexity of human endeavors in the way that computer science can. To make a literary analogy, mathematics produces the equivalent of one-liners – equations that are pithy, insightful, brilliant. Computer science is more like a novel by Tolstoy: it is messy and infuriatingly complex. But that is exactly what makes it unique and appealing — computer algorithms are infinitely more capable of capturing nuances of complex reality in a way that pure mathematics cannot.

When one asks scientists in other disciplines what role computer science has for them, one usually sees CS as a way to solve their large computational problems, like large matrix computations. The more enlightened realize the importance of algorithmic issues and even have a rough understanding of NP-completeness and what that means for the problems they would like to solve. But we haven't on a large scale made scientists in other fields realize that computation exists within the systems they study. Protein folding, economic markets, the ways astronomical bodies interact are all computational processes and once we can make this case, the ideas and tools of computational complexity and theoretical computer science can help them understand the strengths and limitations of these processes.

Suresh and Jeff have more on Bernard's talk and Scott has an interesting and not-unrelated post.

Great NSF Theory News

Sanjeev Arora has some good NSF news in the first post on a new moderated mailing list tcs-funding.

There will be a call for proposals in the NSF theory program this spring and grant sizes are expected to be larger than before. So please apply and send good proposals.

A SIGACT funding committee report outlines things you can do to help improve funding for TCS (please read and act upon). It also describes initiatives launched by the committee to help bring more funding to TCS.

Looks like I jumped to conclusions last month. Never happier to have been wrong.

A Referee's Boycott

As an editor of Information and Computation I made a request to a scientist to referee a paper. I got the following response.

I while ago I decided that I would no longer provide my unpaid referee services to certain publishers like Information & Computation's Elsevier, so I can't help you with this.

Be careful what you wish for. JCSS floated a proposal to pay editors and referees but rescinded it after backlash from the editorial board and the community.

The authors have submitted their paper to I&C, a respected journal, and deserve to have their paper properly reviewed. We all have a responsibility to do our fair share of refereeing and it takes no more effort to referee a paper for I&C than for any other journal.

If you truly dislike a certain publisher then don't submit your papers to their journals. But to take a symbolic stand by not refereeing papers only hurts the authors and our community.

Favorite Theorems: Alternation

Introduction

Physicists continue to grapple over the relationship of time and space. In computational complexity we settled that question three decades ago: Space is just alternating time.

Chandra, Kozen and Stockmeyer, Alternation, JACM 1981. Based on two 1976 FOCS papers.

An alternating Turing machine is a nondeterministic machine with states marked either existential or universal. Consider a game where player 1 chooses the next legal configuration from existential states and player 2 chooses the next legal configuration from the universal states and player 1 wins if the machine halts in an accept state. The machine accepts those inputs where player 1 has a winning strategy.

Chandra, Kozen and Stockmeyer show

• ATIME(t(n)) ⊆ DSPACE(t(n)) ⊆ NSPACE(t(n)) ⊆ ATIME(t²(n))
• ASPACE(s(n)) = ∪_cDTIME(c^s(n))

Alternation causes a shift in the time-space hierarchy of classes: P = AL, PSPACE = AP, EXP = APSPACE, EXPSPACE = AEXP, etc. More importantly the two fundamental resource bounds of time and space are really just the same concept on different models.

Alternation allows us to show the PSPACE-completeness of many game-based problems. Also alternating machines set the stage for interactive proof systems which led to probabilistically checkable proofs, perhaps the most productive line of research in complexity over the past fifteen years.

The paper also characterizes the polynomial-time hierarchy using bounded alternation and shows that alternating finite automata still accept just regular languages (with a double-exponential blow-up in the number of states).

Weapons of Math Instruction

Making the rounds.

At New York's Kennedy airport today, an individual later discovered to be a public school teacher was arrested trying to board a flight while in possession of a ruler, a protractor, a compass, a slide rule, and a calculator. At a morning press conference, the attorney general said he believes the man is a member of the notorious Al-gebra movement. He is being charged by the FBI with carrying weapons of math instruction.

"Al-gebra is a fearsome cult," a Justice Department spokesman said. "They desire average solutions by means and extremes, and sometimes go off on tangents in a search of absolute value. They use secret code names like 'x' and 'y' and refer to themselves as 'unknowns', but we have determined they belong to a common denominator of the axis of evil with coordinates in every country. As the Greek philanderer Isosceles used to say, 'there are 3 sides to every triangle'."

When asked to comment on the arrest, President Bush said, "If God had wanted us to have better weapons of math instruction, He would have given us more fingers and toes".

Advanced Placement

The CRA notes that while the number of students who take Advanced Placement exams has surged over the last few years, the number taking the Computer Science AP exams has dropped a bit, perhaps foreshadowing an even more dropping interest in undergraduate CS.

In many American high schools one can take AP courses that lead to standardized exams in a variety of topics that many universities will use to allow students to place out of some introductory courses. At least that was the purpose when I went to high school, but since then the AP exam has become a mainstay of the high school curriculum. Nearly a quarter of all high school students take at least one of 35 different AP exams. Student applying to good universities had better have several AP courses and exams on their record. Bush made AP exams a goal in his state of the union and Newsweek uses the AP test to rank high schools.

I have nothing against the AP exam in its original form, I took exams in math, physics and chemistry in high school and they saved me from some courses in college. But these exams have their drawbacks, as one has to teach to the exam. Gone in these course is the ability of teachers to experiment and students to excel in different ways.

We have this particular problem with the AP Computer Science A and AB exams. These exams force teaching in a specific language, currently Java, where teachers might have found other languages betters suited for presenting a variety of computer science concepts. The CS A exam focuses mostly on programming in Java, the CS AB exams does add some data structures and running-time analysis.

In high school (before the AP CS exam existed) I had a wonderful course that combined computer programming and probability. We don't see these kinds of interesting classes where the advanced classes in US high schools have to focus on exams.

Advising

David Molnar asks about how to evaluate an advisor. There is no objective method to evaluate advisors, faculty have different students to start with so one cannot directly compare the quality of their Ph.D.s. It's easy to advise a very intelligent hard-working student; it's advising the others that really separates the great advisors from the good ones.

To best evaluate an advisor, ask their students—both the successful ones and the ones that struggle. Keep in mind that an advisor's style that works with one kind of student might not work with another so listen to why a particular advisor is good or bad. These are especially good questions for undergrads to ask current Ph.D. students when the visit potential graduate schools.

Molnar also notes that he hasn't found many resources on how to be a good advisor. We all have different approaches and one could write a book on the topic but here are general techniques (many of which I learned from my own advisor Michael Sipser).

Have students work on problems that interest them not just you. I like to hand them a proceedings of a recent conference and have them skim abstracts to find papers they enjoy. However if they stray too far from your research interests, you will have a hard time pushing them in the right directions. And don't work on their problems unless they want you to.

Keep your students motivated. Meet with them on a regular basis. Encourage students to discuss their problems and other research questions with other students and faculty. Do your best to keep their spirits high if they have trouble proving theorems or are not getting their papers into conferences. Once they lose interest in theory they won't succeed.

Feel free to have them read papers, do some refereeing and reviewing, give talks on recent great papers. These are good skills for them to learn. But don't abuse them too much.

Make sure they learn that selling their research is as important as proving the theorems. Have them write the papers and make them rewrite until the paper properly motivates the work. Make them give practice talks before conferences and do not hold back on the criticism.

Some students will want to talk about some personal issues they have. Listen as a friend and give some suggestions without being condescending. But if they have a serious emotional crisis, you are not trained for that; point them to your university counseling services.

Once it becomes clear a student won't succeed working with you, or won't succeed as a theorist or won't succeed in graduate work, cut them loose. The hardest thing to do as an advisor is to tell a student, particular one that tries hard, that they should go do something else. It's much easier to just keep them on until they get frustrated and quit, but you do no one any favors that way.

Surprising Gasarch

In the fourth Complexitycast, Bill Gasarch returns and discusses his Surprising Results post and his recent guest blogger experience.   MP3 (25:42, 4.4MB)

Sauer's Lemma

The recent post Discovering the Discovered reminded me of one of my favorite combinatorial lemmas known as Sauer's Lemma.

Sauer's Lemma roughly states that if a collection of sets has VC dimension bounded by d then any set of n elements can only be split n^d ways. More precisely

Fix a collections Φ of subsets of U such that for all x₁,…,x_k in U, |{S∩{x₁,…,x_k} | S∈Φ}| < 2^k then for all x₁,…,x_n in U, |{S∩{x₁,…,x_n} | S∈Φ}| ≤ O(n^k-1)

This lemma has many important applications, most notably a famous result of Blumer, Ehrenfeucht, Haussler and Warmuth showing that if you don't care about computation costs then one can PAC learn a concept class iff the VC dimension of that class is bounded.

Why is Sauer's lemma connected to Discovering the Discovered? According to Till Tantau,

Vapnik and Chervonenkis appear to have been the first to discover it. They published it in 1968 in Russian and 1971 in English. Sauer, whose paper was published in 1972, claims that Erdös was the first to have conjectured the lemma. Subsequently, Sauer's Lemma has been rediscovered by Clarke, Owings, and Spriggs, and later again by Beigel.

Computational Complexity: A Modern Approach

Sanjeev Arora has posted a draft of his new textbook. A welcome addition to those who wish to learn or teach complexity.

Discovering the Discovered

Gina Kolata has a New York Times article Pity the Scientist Who Discovers the Discovered. The article had its genesis from a SODA invited talk by Rakesh Vohra. I like the closing quote from Larry Shepp, "Yes, but when I discovered it, it stayed discovered." Reminds me of the Christopher Columbus principle.

We have often seen theorems proven multiple times in our field, because the result was proven on both sides of the iron curtain (e.g. Cook and Levin), sometimes it is just easier to prove a lemma then work through the literature, or we just simply didn't realize someone else had thought about the same problem. We have a considerable number of published work in our field and you cannot hope to know every "known" result, even in an area where you are considered an expert.

There is no ethical breech if you reprove someone else's theorem as long as you make good once you learn the result already existed. Although I have occasionally reproven theorems I had seen previously in talks or papers I've reviewed and that's just downright embarrassing.

Announcements

How do we announce important activities in theoretical computer science? With research results we have pretty good systems through various paper archives. But how about conferences (deadlines, accepted papers, registration), grants, jobs, deaths and other information important to the community. With the Internet we expect easy ways to distribute such information and we have several such schemes but none really do a great job.

• Email Lists such as Theorynet and DMAnet will deliver all sorts of news directly to your inbox. Though moderated both lists have pretty high volume so many people don't subscribe.
• Search Engines. Want to know the upcoming deadline for ICALP? Just Google on "ICALP 2006". This only works for conferences you already know and won't help with other information.
• Websites like the Theory Calendar and CRA Job Announcements. These sites are not always up-to-date or complete and only cover a small segment of announcement topics.
• Newsletters like SIGACT News have a time lag and not everyone is a SIGACT member (though shame on your who aren't).
• Graduate Students. Some professors use their students to filter the Internet for them. But students are imperfect filters and not everyone has them available.
• Weblogs. Some people use this and other weblogs to keep up with what is happening in the community. While I try to make sure important news gets heard I certainly am not comprehensive and you might not share my biases.

What we need is a VGS (Virtual Grad Student), an intelligent program that scours the Internet and reports back to me exactly the information that I would find relevant. Until such agents exist, you'll have to choose your poison from the above or just remain blissfully ignorant.

Science in the Union

From Bush's State of the Union address last night.

And to keep America competitive, one commitment is necessary above all: We must continue to lead the world in human talent and creativity. Our greatest advantage in the world has always been our educated, hard-working, ambitious people—and we are going to keep that edge.

Tonight I announce the American Competitiveness Initiative, to encourage innovation throughout our economy, and to give our nation's children a firm grounding in math and science.

First: I propose to double the federal commitment to the most critical basic research programs in the physical sciences over the next 10 years. This funding will support the work of America's most creative minds as they explore promising areas such as nanotechnology, supercomputing, and alternative energy sources.

Second: I propose to make permanent the research and development tax credit, to encourage bolder private-sector investment in technology. With more research in both the public and private sectors, we will improve our quality of life—and ensure that America will lead the world in opportunity and innovation for decades to come.

Third: We need to encourage children to take more math and science, and make sure those courses are rigorous enough to compete with other nations. We have made a good start in the early grades with the No Child Left Behind Act, which is raising standards and lifting test scores across our country.

Tonight I propose to train 70,000 high school teachers, to lead advanced-placement courses in math and science, bring 30,000 math and science professionals to teach in classrooms, and give early help to students who struggle with math, so they have a better chance at good, high-wage jobs.

If we ensure that America's children succeed in life, they will ensure that America succeeds in the world.

Preparing our nation to compete in the world is a goal that all of us can share. I urge you to support the American Competitiveness Initiative and together we will show the world what the American people can achieve.

As part of the initiative the budget of several agencies including the National Science Foundation will double over ten years and be raised over 9% in the upcoming year.

There is a long road from SOTU to reality, but this looks like good news for science in America. More from the CRA and USACM.

Update 2/2: The NSF will have a 7.8% increase in the White House proposed budget for next year.