This is the August edition of Favorite Theorems.

Perhaps you could easily find a satisfying assignment of a Boolean formula when only one solution exists, somehow using the uniqueness to cleverly guide your search. Valiant and Vazirani show that any such procedure would give a randomized algorithm for general satisfiability and put the class NP in RP.

Valiant and Vazirani show there is some efficient randomized algorithm f mapping Boolean formula to Boolean formula such that for all formula φ,

• f(φ) will always have the same set of variables of φ and every satisfying assignment of f(φ) is a satisfying assignment of φ. In particular if φ is not satisfiable then f(φ) is never satisfiable.
• If φ is satisfiable then Pr(f(φ) has exactly one satisfying assignment) ≥ 1/(4n), where n is the number of variables of φ.

Valiant and Vazirani's proof takes random half-spaces of the solution set and argues that with some reasonable probability repeating this process will yield a single solution. The techniques are quite general and one can get similar results for nearly every known NP problem.

Mulmuley, Vazirani and Vazirani prove an "isolating lemma" which one can use to give an alternate proof of a similar theorem by putting random weights on edges and with some reasonable probability there is a unique maximum weight clique. Mulmuley et. al. use the isolating lemma to give a simple randomized parallel algorithm for maximum matching.

Besides the immediate hardness of finding unique solutions, Valiant-Vazirani has had impact in complexity in many ways. Just a couple:

• One can use Valiant-Vazirani to find a satisfying assignment of a formula using non-adaptive queries to SAT.
• Valiant-Vazirani gives the base case of Toda's theorem.
• Similar ideas show how to create a low-degree polynomial that correctly computes the OR function at most inputs (which one can extend to AC⁰ by recursion).

We are finalizing the budget for FOCS 2007 in Providence. The traditional Saturday evening reception will cost at least $53 per person. The alternative is to skip the reception altogether. I would like to poll the Theory community and hear what they would prefer. Can you give your comments or preferences?

--
Posted by Lance to Computational Complexity at 9/01/2006 02:54:00 PM

Not everything about the container world rings positive. Most dock workers and many domestic manufacturing workers have lost their jobs. Cities and countries that didn't modernize their docks for containerships got left behind. We can't inspect every container arriving into the US, some of which might contain illegal or deadly weapons. Used containers litter parts of our landscape. Nevertheless containers have greatly increased wealth in several undeveloped countries while delivering many developed countries with low-cost goods.

The Internet shares many parallels with shipping containers. It matters little whether a shipping container has stuffed animals, MP3 players or automobile parts, likewise the internet doesn't care whether it delivers email, pictures, music, movies, blogs and the like. The Internet has allowed many service jobs to move to developing countries. One can hide malicious programs and websites that appear to be something else on the Internet easier than one can hide a bomb in a shipping container.

Increased commerce have led to bigger and bigger ships and calls to expand or replace the Panama canal, now too small and crowded to handle all of the shipping from Asia to the East Coast. Likewise we have to continually increase the volume and speeds of the Internet to meet growing demands. As we learn to take advantage of new technology, especially those that help quickly and cheaply move goods and information, we learn to use it for purposes beyond expectations and we have to cope with expanding the good while limiting the bad uses of such technologies.

--
Posted by Lance to Computational Complexity at 9/05/2006 03:58:00 PM

The United States, outside of the military academies, does not run any universities directly. Rather most universities are either run privately or by individual states. These schools form a near continuum of quality from the best research schools in the world down to small community colleges. We have no large gaps, if a student just fails to get accepted to school A then they can go to school B with nearly as strong a program. Also universities in the US often have strength in different areas; one can find schools whose CS department have a much greater reputation than their university as a whole (and vice versa).

Since US universities report to different masters they compete, trying to increase the reputation of their schools both informally and in published lists like the US News Rankings. Some of this competition leads to spending not directly related to education or research such as athletic programs and student amenities. But much effort does go into recruiting top faculty and students including from outside the US.

Fifty computer science departments have a stated goal of becoming a top ten department in the long term. 80% of them will fail but the process will strengthen CS research across the board.

--
Posted by Lance to Computational Complexity at 9/06/2006 02:04:00 PM

Haystack: What's with you people? Why are you all obsessed with that stupid little thing!? What about wonderful me!? Love me! Give me love!
Caption: The haystack is upset that the needle gets all the attention.

--
Posted by Lance to Computational Complexity at 9/07/2006 07:52:00 AM

SODA accepted papers have been posted. STACS submission deadline (September 17) is fast approaching.

A few call for papers for next summer's FCRC conferences: Complexity and Electronic Commerce. Still waiting on some others including STOC and COLT.

Harvard theory professor and former dean Harry Lewis (of Lewis and Papadimitriou fame) will be on BookTV on CSPAN 2 Sunday at 1:00 PM EDT talking about his new book Excellence Without a Soul: How a Great University Forgot Education. You can also stream CSPAN 2 and sometime after the program airs the video will be available.

Thanks to all who sent me pointers.

--
Posted by Lance to Computational Complexity at 9/08/2006 10:04:00 AM

Prelude. I was packing up my hotel room in Würzburg after the 1993 STACS conference. I flipped on the TV, the hotel only had German stations, and saw police and fire engines around the World Trade Center and caught the word "explosion". It wasn't until I reached the airport later that day that I learned the towers suffered no significant damage.

In 2001 I worked for the NEC Research Institute in New Jersey. In September I attended the first EQIS workshop in Tokyo and the following week visited the quantum computing group near the University of Tokyo. On the 11th I took a day trip to visit the quantum computing group at the NEC Lab in Tsukuba. The first plane hit the towers at 9:45 PM Japan time after I had returned to Tokyo and I went to bed that night unaware of the events unfolding back in the states. I learned the news when I booted up my laptop the following morning. I then turned on the Japanese TV (I never get CNN when I really need it) and saw the shocking images all at once.

Tokyo had a normal day on September 12 when I wanted to world to stop. I was the only remaining American visiting the group and I felt quite alone. During lunch one of the non-Japanese asked what America had done to deserve this. I almost slugged him.

I gave a talk as scheduled in the afternoon still in quite a daze. That night I insisted on doing something completely mindless and the Japanese complied, taking me to a small Karaoke bar.

I returned to the states on the 16th, three days later than my original schedule. As the plane approached Newark I had a clear view of Southern Manhattan and saw a plume of smoke still arising from where the World Trade Center had stood. The America I was returning too was vastly different from the one I had left two weeks earlier.

As many of you know we lost a member of our community that fateful day, Danny Lewin, an MIT graduate student and co-founder of Akamai. The STOC best student paper award now bears his name.

--
Posted by Lance to Computational Complexity at 9/11/2006 06:19:00 AM

Most proofs seem simple once we've proved them. With some notable exceptions, every proof has (at most) one new idea, the rest just connecting the dots through techniques we've seen before.

From the outside or from the eyes of a young graduate students, research seems like a magical process that mathematicians somehow pull proofs out of a hat. Successful theorists are not magicians, just people who have read and understood techniques from a variety of sources and find news ways to put those techniques together to solve the problem on hand.

--
Posted by Lance to Computational Complexity at 9/13/2006 05:37:00 AM

As I write this the Yankees have 88 wins and Boston with 68 losses which means the Yankees current magic number is 162+1-(88-68)=7. This means any combination of 7 Yankees wins and Red Sox losses would guarantee that the Yankees win their division.

Yesterday I got the following email.

I'm in disagreement with my brother—and, apparently, all major media—regarding the Yankees' magic number. My reasoning is that if the Red Sox win all their remaining games, that's 94 victories. Since the Yankees lead the season series and will thus win the division in the case of a tie with Boston, they'll clinch the division with 94 wins. They have 88, so only need eight more…thus, a magic number of six.

The formula you reference (with the "+1"), which I guess others use as well, doesn't account for the fact that a team only need to tie for first if they've won the season series vs. the other team.

In the event of a tie in the standings at the close of the regular season, league rules provide for a one-game playoff (with the home field determined by coin flip) to determine which of two teams participate in the Division Series. If three teams are involved in a tie, a two-game playoff may be played. If two teams are tied, but a tiebreaker would result in both participating in the Division Series anyway (due to one being division champion and the other being wild card), then no playoff is played and seedings are determined by head-to-head record.

The situation is different in the AL Central where the second place team will likely win the wild card. Detroit has 87 wins and Minnesota has 60 losses and Detroit has the better head-to-head. So Detroit only needs 162-(87+60)=15 wins and/or Twins losses to clinch the division since they win the division in case of a tie. No "+1" here.

Now if the Twins fade and my White Sox (with 62 losses) get into contention then Detroit needs 162+1-(87+62)=14 wins and/or White Sox losses to clinch over the White Sox. Why? Because the White Sox will have the better head-to-head over Detroit.

Nothing like Major League Baseball and their wild-card rules to ruin the beauty of the magic number.

--
Posted by Lance to Computational Complexity at 9/14/2006 08:13:00 AM

One teacher talked about the need to improve the students' "keyboarding" skills. Too bad the typing lessons I took in high school have gone to waste.

In the math classroom the teacher had two problems on the board and asked the parents to solve them.

1. 1/2×2/3×3/4×4/5×5/6×6/7×7/8
2. What is the next three letters in this sequence: T F S E

I got caught a little off guard on how the other parents struggled with the questions, at least those that tried. No wonder math education suffers when the parents, most of whom have professional careers, don't use much math techniques past the sixth grade level. How can they stress the importance of continuing mathematical education when they don't use it themselves.

Or do they? Math teaches more than just how to multiply fractions and solve equations. Learning math involves seeing how to tackle a problem, logically analyzing it and finding the right approach and then applying that approach. The tools students learn in math class will help them in their careers even if the problems don't involve numbers at all.

--
Posted by Lance to Computational Complexity at 9/18/2006 08:17:00 AM

• Luis von Ahn, Carnegie-Mellon cryptography, who has worked in steganography but best known for Captcha and The ESP Game.
• Recent Fields Medalist Terence Tao.
• Claire Tomlin, Stanford Aeronautical Engineer and Berkeley EECS Ph.D. From the announcement.

  Much of Tomlin's research concentrates on aeronautical applications of hybrid systems research, particularly aircraft flight control and air traffic conflict resolution. As the number of variables increases and their interactions become more complex, it becomes ever more difficult to guarantee that systems will always be within safe limits. Tomlin has developed practical algorithms for determining when unsafe conditions may arise, and for establishing feedback control laws for a hybrid system guaranteed to remain within a safe subset of all reachable states.

Dr. Yau has demanded that The New Yorker and Nasar make a prominent correction of the errors in the article, and apologize for an insulting illustration that accompanied it.

"Beyond repairing the damage to my own reputation, we seek to minimize the damage done to the mathematics community itself, which is ludicrously portrayed as contentious rather than cooperative and more competitive than collegial," Dr. Yau said. "Mathematicians from the foremost institutions – from Beijing to Berkeley – have been appalled at the fictionalizing of our profession."

"Manifold Destiny," a 10,000-word article by Sylvia Nasar and David Gruber published in the August 28, 2006 issue of The New Yorker, is the product of more than four months of thorough, careful reporting and meticulous fact-checking. Ms. Nasar and Mr. Gruber spent over twenty hours interviewing Dr. Yau; they conducted approximately 100 other interviews with people in the field; corresponded by email with Dr. Yau and many others; and traveled to China where they conducted interviews and attended speeches and events discussed in the article. In addition, the magazine's fact-checkers spoke with Dr. Yau for approximately eight hours, they examined notes, tapes, and documents gathered by the authors, and the checkers conducted their own thorough research. Contrary to Dr. Yau's assertions, the article is nuanced and fair, and was prepared using ethical standards of journalism. Dr. Yau, his supporters and his point of view were given ample space in the article.

Sanjeev Arora and Boaz are nearing completion of their complexity book and they need your help. Please send them comments big and small. They particularly need you readers who are not (yet) experts in complexity to gauge the readability of the text.

The Royal Society has placed all of their journals online with free access through December. Their archives go back to '65 (that's 1665) in case you want to read Ben Franklin's paper on electricity.

--
Posted by Lance to Computational Complexity at 9/21/2006 07:11:00 AM

In the 70's we had essentially no super-polynomial lower bounds for natural problems on general circuits beyond depth 2. Two papers kick started circuit complexity by independently showing no polynomial-size constant-depth family of circuits can compute the parity function (inputs with an odd number of ones).

Furst et al. developed random restrictions, i.e., randomly choose a set of variables and set them to 0 and 1 randomly. This will create a circuit on a smaller set of variables. For the parity function any such restricted circuit will compute parity (or its negation) on the unrestricted variables. They argue that the restricted circuit will give a polynomial-size circuit for parity of smaller depth. This leads to a contradiction because one can easily show that parity requires exponential-size depth-2 circuits.

Ajtai showed lower bounds against expressions described by first-order formula, equivalent to a uniform version of constant-depth circuits. I believe Ajtai's proof carries to the nonuniform case as well.

Furst et al. also show that super-quasipolynomial bounds for constant-depth parity circuits would imply an oracle relative to which the polynomial-time hierarchy differs from PSPACE. They don't achieve these stronger bounds but Yao does a few years later.

Håstad used a more clever random restriction and much more difficult analysis to create a switching lemma that implies essentially tight exponential lower bounds for parity on constant depth circuits. Razborov gives a simpler proof of the switching lemma. Paul Beame has a nice self-contained write-up of Razborov's proof and Fortnow and Laplante has a version using Kolmogorov complexity. The simplest proof of the original Furst-Saxe-Siper-Ajtai result comes from the lower bounds on circuits with modulo p gates for some fixed prime p due to Razborov (in Russian) and Smolensky. Alas, Razborov and Smolensky's 1987 papers mark the last major super-polynomial lower bounds for general circuit models.

--
Posted by Lance to Computational Complexity at 9/24/2006 12:01:00 PM

Authors should submit an extended abstract (not a full paper).

An abstract just states the main results of a research paper. An extended abstract gives a little motivation, background and a hint of the proofs. The extended abstract serves not as a paper in itself but as an advertisement of the journal paper to come. If one had a full paper published in the proceeding than one couldn't publish the same results in a journal later on. That's the way conferences work.

Actually that's the way conferences work in all fields except computer science. In CS conferences play a more important role than journals; in most cases people judge the quality of a paper based more on the conference than the journal. Many conference papers never see a journal at all and many journal submissions are only slight variations of the conference proceedings version.

You really need to send something closer to a full paper to STOC if you hope to get accepted. You need to convince the committee that the results are new, important, correct and nontrivial. Most people submit a rough draft of a final paper, using the appendix if needed to put in their proofs.

Why do we keep the fiction of the extended abstract? Ethical and copyright rules prohibit us from publishing the same results in multiple places. We call the proceedings version an "extended abstract" so we can believe we don't violate these rules.

Non-theory conferences don't even pretend. The EC Conference, for example, solicits full papers though they do include the following note.

To accommodate the publishing traditions of different fields, authors may instead submit working papers that are under review or nearly ready for journal review. These submissions will be subject to review and considered for presentation at the conference but not for publication in the proceedings. These submissions need not conform to the conference paper format. Abstracts of accepted working papers will be included in the proceedings and must be coupled with a URL that points to the full paper and will be reliable for at least two years.

In multi-authors publications from other fields (biology, physics), the order of the author's names roughly indicates the importance of the contribution from each author, while this is not the case in CS. I was told that it was to avoid meaningless fights about the order, but in my personal experience I found out that it created other conflicts, mainly the frustration of the main author toward co-author who did not "contribute enough."

The fact is, not recognizing the difference of importance in relative contributions pushes to two quite negative behaviors:

1. Some authors will expect all co-authors to contribute an equal part to the paper, and be disappointed and frustrated when it is not the case. This is bad either way: having a frustrated co-author is not a nice experience, but on the other hand trying to balance the work so that each co-author contributes the same amount does not necessarily corresponds to the balance of skills for the particular publication, and may not be the most efficient way to work on a paper.
2. Authors have an incentive to play the game of the "minimum contribution deserving authorship", eventually (for the highest in the academic hierarchy) pushing the other authors to contribute more in exchange of immaterial promises (such as future recommendations, or the "teaching" by experience). I was explained by a senior faculty that "students have to accept to eat a lot of shit (meaning, do a lot of stupid work), and young faculty to eat some shit but to pass down to their student most of it".

One obvious solution would be to add a paragraph at the end of each paper, in a similar way to the "acknowledgement" paragraph commonly added, describing the contribution of each author. It would be a natural way to create an incentive for each author to contribute as much as this paper is worth to him, inversing the "minimum contribution deserving authorship" incentive, and remove most of the frustration. It would remove the ambiguity on "who did what", that we have anyway to explicitly remove when writing recommendation letters or applying for "best student paper". From a game theory point of view (for the little of game theory that I know), it would make the publication mechanism "truthful", and anybody opposing this mechanism would risk to look bad.

Now, I assume that this solution has some hidden drawback(s) (other than taking an additional five lines in each publication), as otherwise some field or other would already have adopted it. Or is it just that senior faculty members would not support such a measure?

--
Posted by Lance to Computational Complexity at 9/26/2006 03:54:00 PM

The workshop had a panel discussion Models for Sponsored Search: What are the Right Questions? organized by Rakesh Vohra and yours truly. Panelists were Kamal Jain (Microsoft), David Pennock (Yahoo!), Michael Schwarz (Yahoo, UC Berkeley) and Rakesh Vohra (Kellogg School at Northwestern). The panel was moderated by Jason Hartline.

Jason recorded the discussion which I converted to MP3 (98 minutes, 17 MB).

Alternatively you can read the transcript (PDF, postscript). Thanks to Nina Balcan, Jianqing Chen, Nikhil Devanur, and Anuj Kumar for their hard work transcribing the audio.

--
Posted by Lance to Computational Complexity at 9/27/2006 05:21:00 PM

In the past few years, a host of prediction markets, as they're usually called, have appeared online, offering people the chance to speculate on subjects ranging from the box-office performance of Hollywood films to the outcome of Presidential elections and the spread of bird flu. These markets' forecasts have proved remarkably accurate—just as bettors collectively do an exceptionally good job of predicting sports results. (In 2004, for instance, Tradesports, a Dublin-based prediction market, called thirty-three out of thirty-four races in the Senate correctly, and called all fifty states correctly in the results for the electoral college.)

The original NSF solicitation focused on large-scale infrastructure but a CCC white paper, while purposely vague, seems to take a broader view.

Compelling visions take many forms. History has amply demonstrated the importance of entrepreneurial, grassroots efforts as creative engines in computing research. History has also demonstrated the value of large teams, large facilities, and large amounts of funding. Many see an increasing need for shared research facilities and teams in our field to allow us to tackle certain "grand challenge" problems. Planning for large-scale research should not, and need not, harm smaller-scale efforts or place them at a disadvantage.

The challenge for the Computing Community Consortium is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to articulate those research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with funding organizations to move the challenges and visions toward funding initiatives. The CCC will do this without harming the research environment that has created the computing world of today.

1. Can you submit a paper to a conference that you are not sure you can attend?
2. You have agreed to give an invited talk at a conference. But you find yourself traveling too much. Can you cancel your talk?
3. You have accepted a tenure-track job at a good school but then you get an offer at a more desirable place? Can you take back your acceptance at the first place?
4. You promised to referee a paper by a specific date. But life gets busy. Can you let the deadline slide?

Many members of our community treat such commitments quite seriously but unfortunately too many of us don't. For the latter group put yourself on the other side. Think of the editor dealing with referees who aren't refereeing and the author not getting his paper reviewed in a reasonable amount of time. Think of the department that has stopped their job search believing they have filled their opening. Think of the conference organizers having to reshuffle their program for talks not given.

Sometimes you have extenuating circumstances, like an illness, that do give you reasonable excuse. And you could always ask; people will often modify or let you out of your commitments if you make a polite request. But you must make every effort to honor your commitments. If you don't think you can then you shouldn't commit in the first place.

The ultimate commitment you make is the commitment to research. Once you start graduate school you make a promise to focus on science and your research as your main objectives. Only by keeping that commitment can you truly succeed as a scientist.

How much commitment do you need? In a ham and cheese omelet the chicken and the cow are involved but the pig is committed.

--
Posted by Lance to Computational Complexity at 10/03/2006 07:34:00 AM

The big CS news of the week: Netflix, the online DVD subscription rental site, has announced a million-dollar prize for substantially improving their movie recommendation system. The New York Times has the story, NPR has an interview with James Bennett, Netflix vice-president of recommendation systems, and John Langford gives his take.

Recommendation Systems (or Collaborative Filtering) tries to match one person's interests based on the interests of a large collection of other users. At first this seems like an easy task, just trying to match vectors. But the simple ideas don't work very well. The AI community have developed much more sophisticated techniques that have been implemented in companies that take recommendation systems seriously, like Amazon and Netflix. Apparently these techniques have reached the point of diminishing returns, thus the contest.

I understand that Amazon wants to sell more stuff, but why does Netflix take the problem so seriously, to the point of having a VP of recommendation systems as well as running this contest? They only recommend to already paying subscribers, the amount of extra business they get or keep by a strong recommendation system seems minimal.

But I shouldn't complain. Too often the public thinks of computer science as simply writing programs and making them run quickly. The Netflix contest sheds light on a different view of CS that shows the depth in a seemingly simple problem.

The million-dollar prize puts recommendation systems in the same class as the P versus NP Millenium Prize. Though if you could show P = NP by giving a quick algorithm for NP-complete problems, you can use that algorithm to develop a great recommendation system and collect a cool two mill.

--
Posted by Lance to Computational Complexity at 10/04/2006 08:10:00 AM

"Embargoed Science" refers to articles that some journals such as Science or Nature send to science writers in advance of publication under strict rules not to write about the article until publication date. The embargo supposedly gives writers a chance to do interviews and background research before they have to write the stories. Kiernan argues that embargoes misdirect science journalists.

There are lots of problems with embargoed science, but the biggest issue is that it misdirects journalists. It sets up a system by which journalists are given powerful incentives to cover a certain kind of story about science – the latest "eureka moment," and those eureka moments come several times each week. And so the journalists are directed toward those stories and away from critical, skeptical coverage of science as an enterprise, with all its fraud, with all its successes, with all the ethical issues…Lots of very, very good science gets published in many, many journals. There are literally thousands of journals, and journalists monitor 30, 40, if they're lucky – the ones with embargoes. The ones that are not embargoed, that also publish very, very good science, like a bunch of geophysical journals, they are largely ignored by journalists.

The brochures look the most impressive, for example Wisconsin-Madison with 36 glossy pages including a two-page spread on Jin-Yi Cai and the P vs. NP problem.

The thrill is in the chase for Cai and others in Theory of Computing. He describes his research with the language of an artist, drive by "elegance, internal logic and beauty." The usefulness of the findings in this field can often be transformational, but they may not be evident until decades later.

The posters have a more specific function like advertising the graduate program or announcing distinguished lecturers. They can't really expect us to travel a thousand miles to see a single talk. I suspect the distinguished lecturer posters really say "We are a real department because famous computer scientists visit us."

Brochures, newsletters and posters all have the same true purpose of branding, so we think of those departments when we recommend graduate schools for our undergrads, faculty jobs for our Ph.D. students and when we fill out those questionnaires that lead to departmental rankings.

The departmental web page has become the true portal that potential students and faculty go to to explore a department. Most CS departments that home pages high on content but often low on visual appeal. Departments should put as much effort into the style of their web pages as much as they do for those brochures, newsletters and posters.

--
Posted by Lance to Computational Complexity at 10/07/2006 04:41:00 PM

• Recommendation Letters. Should only be read by during the recruiting process and never by the candidate except as required by law. If someone other than the candidate asks you for a recommendation you shouldn't even mention to the candidate that you were asked.
• Referee Reports. While the reports themselves are furnished to the author, the identity of the referees must be kept secret. Any discussion between the referees and authors should go through the editor.
• Committees. Any discussion in a program committee (or any other kind of committee) should remain closed except as agreed upon in the committee. This allows the committee members to speak freely. In a PC you shouldn't even mention whether a paper was submitted.
• NSF Panels. You should not disclose any discussion during an NSF panel, or even the fact that you were a panelist.
• Salaries. You can announce your own salary but you shouldn't mention other people's salaries. Exceptions for surveys and states that require that the public have access to the salaries of all of their employees including state university professors.
• Personal Information. Disabilities, Illnesses physical and mental, Gender, Sexual Orientation, Marriage, Children, Religion, Race and other related issues except as necessary or as already publicly known.
• Email and Personal Discussions. You should reveal research or other discussions with someone else without their permission.

If you truly want things you say to remain private then don't say it. With many theorists having loose lips and the minimal security of email you cannot count on the fact that what you say that should not be spread will remain unspread.

--
Posted by Lance to Computational Complexity at 10/09/2006 01:30:00 PM

Afterwards in my class I used the phrase "For every natural number n" and then stopped myself and asked the class about what natural and whole means to them. The class had diverse opinions and also mentioned something called counting numbers. Searching various web sources seem to agree for the most part that whole numbers start with 0 but are less clear on the natural and counting numbers.

For that class and in most of what I do the distinction is irrelevant since we usually only care about "sufficiently large" n. But if you are using a context where 0 matters, please use the terms "nonnegative integers" and "positive integers" so as to not confuse those of us who can't keep our whole and naturals straight.

--
Posted by Lance to Computational Complexity at 10/10/2006 01:56:00 PM

As an added bonus participating in a project can only help your grad school applications as many Ph.D. programs like to see some research experience. Submission deadline is not until February 23 but you'll have to start very soon to get a project ready in time. So go find some ideas from a friendly CS theory professor at your university and get cracking. See you in San Diego.

--
Posted by Lance to Computational Complexity at 10/11/2006 10:34:00 PM

As the web developed CS departments started putting their tech reports online. But why should you have to go to individual department web sites to track down each report? So people developed aggregators like NCSTRL that collected pointers to the individual paper and let you search among all of them. CiteSeer went a step further, automatically searching and parsing technical reports and matching citations.

But why have technical reports divided by departments? We each live in two communities—our university and our research field. It's the latter that cares about the content of our papers. So now we see technical reports by research area, either area specific systems like ECCC or very broad report systems like arXiv that maintain specific lists in individual subareas.

What's next? Maybe I won't submit a tech report at all letting search engines like Google Scholar or tagging systems like CiteULike organize the papers. Departmental tech reports still exist but don't play the role they once did and who can predict how we will publish our new results even five or ten years down the road.

--
Posted by Lance to Computational Complexity at 10/13/2006 06:11:00 AM

In the real academic world you rarely see two people collaborate almost exclusively over a long period of time. We all have certain people with whom we collaborate often because we have similar interests, complement each other's skills, or simply that we work well together. But having a single collaborator can lead to narrow research, using the other as a crutch and worrying that outsiders won't know which one is the stronger researcher. But most importantly we thrive on variety and having different collaborators keeps research exciting.

--
Posted by Lance to Computational Complexity at 10/15/2006 08:09:00 PM

What is the best a probabilistic algorithm can do for the worst-case input? Perhaps it might be easier to show the limitations of a deterministic algorithm on the average over an adversarially chosen distribution of inputs. Andrew Yao observed these values are one and the same.

Best to view this result as a zero-sum game. Alice chooses a deterministic algorithm A and Ian chooses an input I. Ian receives t dollars from Alice where t is the "cost" of algorithm A on input I. By applying von Neumann's minimax theorem Ian and Alice have probabilistic equilibrium strategies. That is Ian has a distribution of inputs that achieve an expected cost t no matter what algorithm Alice chooses. Also Alice has a probabilistic algorithm (a randomized choice of deterministic algorithms) that will achieve an expected cost of the same t no matter what input Ian chose.

The Yao Principle applies when we don't consider the algorithmic complexity of the players. For example in communication complexity we have two players who each have a separate half of an input string and they want to compute some function of the input with the minimum amount of communication between them. The Yao principle states that the best probabilistic strategies for the players will achieve exactly the communication bounds as the best deterministic strategy over a worst-case distribution of inputs.

The Yao Principle plays a smaller role where we measure the running time of an algorithm since applying the Principle would require solving an extremely large linear program. But since so many of our bounds are in information-based models like communication and decision-tree complexity, the Yao Principle, though not particularly complicated, plays an important role in lower bounds in a large number of results in our field.

--
Posted by Lance to Computational Complexity at 10/16/2006 03:26:00 PM