The NSF Annual Report

The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities related to their grants. The report is due 90 days before the anniversary of the start of the grant, so if you have a grant that started in the fall you are probably getting notices reminding you that your report is now overdue. 

There are few academic tasks more painful than filling out annual grant reports but best to just grit your teeth and do it or the NSF could cut off your money. Would you rather the alternative, not having to do a report because you don't have a grant?

Annual reports are used more for gathering information than for evaluation so you don't need to worry about the style as much as you might for a grant proposal. 

There is one confusing part of the reporting system on NSF Fastlane: There are separate sections for conferences and publications. Most of our conferences don't show up under conferences so best to just list your other conference papers as proceedings in the publications section, probably under "Books or Other One Time Publications".

Fastlane reporting is a one-size fits all system so it is not well designed for the way computer science handles conferences. But we computer scientists always know how to implement the Kludge.

Update 7/10: NSF Theory Program Director Richard Beigel makes available a Sample Report (Dan Spielman) and Sample Findings (Mihir Bellare).

Re-request/when to include a known proof in a paper?

In my post of June 24 I requested some help on a sum (among other things). In particular, we had a summation result that we were using in a paper and we wanted to know if it was new or not. We got three comments relevant to it

1. Method of differences due to Pascal
2. discrete calculus analog of the fact that the nth degree Taylor expansion of a polynomial is the polynomials.
3. The first lemma is a direct consequence of the method of finite differences; it says that the nth forward difference of a polynomial of degree n-1 is identically zero. The inner summation in the second identity is basically computing the coefficients of the Newton Form of the polynomial, although you seem to be using a slightly different basis. Nevertheless, these results are quite standard.

This raises a request and some question.

REQUEST:

Authors of those comments (and others who know stuff)--- please email me more exact references. I found some things on Google but it would be good to know what to read and what is a good source to reference. Preferable online.

QUESTION: In a paper if you are using a result that is known how much detail should you put in?

1. Clearly put in that it is known and provide a references. I would not want to frustrate my readers with This is easily derived from the method of differences. without providing a reference. In this day and age an online reference if you can mange it.
2. If the result is not quite written down anywhere but your readers could easily derive it using known techniques, then you do not need to supply a proof. But this is not as clear a statement as it sounds- it depends on how you define readers, easily, known, and technique.
3. If the result is known but you have a cute proof of it which seems new (hard to tell) then what do you do?
4. If the proof is short then I am more inclined to include it. If its an e-journal than length matters less. (This topic has been raised in a different form before---if Conferences proceedings are CD's then why have a page limit?)
5. If there are no online references then I am more inclined to include a proof.
6. My only real point here is that its a QUESTION- what is the cutoff for what is worth including? There is no one answer.

Tales of Two Theories

I finished reading two very different books about two theories in physics, The Age of Entanglement: When Quantum Physics Was Reborn by Louisa Gilder and “Gina Says,” Adventures in the Blogsphere String War "selected and edited" by Gil Kalai. While vastly different in style they both feature scientists happy to talk about and defend their own points of view in controversy theories but rarely willing to reconsider those views.

Louisa Gilder's book takes a detailed look at the early years of quantum theory using an interesting technique: Creating imagined conversations between the leading scientists of the time based on their writings. These conversations make the development of the theory an exciting story when greats like Einstein, Bohr and Heisenberg struggle over the right ways to handle the seemingly paradoxical nature of quantum effects. As Bohr gets quoted in the book during a Copenhagen trolley ride with Einstein and Sommerfeld, "I suppose that during a stage in science where everything is in ferment, it cannot be expected that everybody has the same view about everything". 

Gilder's book gives a detailed year by year development through the 1935 Einstein-Poldolsky-Rosen paper but then moves much quicker through David Bohm's theories from his exile in Brazil (due to McCarthyism), the Bell inequalities and related experiments, and the development of quantum cryptography and computing. The computer science aspects are particularily short with only a brief mention of "the reclusive Peter Shor and the witty Luv Grover". She doesn't ignore the political backdrops of the times but thankfully she doesn't overly emphasize it either.

You won't learn more than the broad strokes of quantum physics with this book but you get to relive the development of a discipline as brilliant minds argue the right way to model a new phenomenon. 

Gil Kalai's book is a quick read from the viewpoint of "Gina" a non-expert who comments on the blogs of mostly string theory skeptics. It certainly was a fun read but I finished not sure of the purpose of the book. Seemed to focus more on the role of bloggers and commentors than the philosophical questions of developing a complicated theory that seemingly can't be tested. Where's Occam's Razor when you need it? Kalai had some interesting digressions to areas like Godel's incompleteness theorem and Bayesian learning but those just added to the disjointness of the book. Kalai's book does have the big advantage of being a free download.

So I'd recommend Gilder's book if you want a detailed almost novel-like development of a field and Kalai's book if you want a quick fun free read on how some skeptics defend their skepticism. 

Both books remind us that theoretical research must go beyond just doing the math, in finding the simplest models that best capture the concepts we study. Lessons that hold as much in computer science as they do in physics.

Complexity Report from DNA 15

Guest post by Aaron Sterling

I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the University of Arkansas. The co-chairs of the organizing committee were Rusell Deaton and Jin-Woo Kim, who I thought did a great job. The research presented, and the backgrounds of the attendees, were diverse from experimental nanochemistry to theoretical computer science. I'll highlight a few elements of the program that had TCS and complexity flavor.

Jim Aspnes and Kenichi Morita gave TCS plenary talks. Aspnes introduced the audience to the computational theory of “population protocols” (see here for a survey) a theory of computation over a large network of agents who each possess very limited computational power. This theory can model ad hoc wireless networks, and (potentially) smart molecules interacting in solution. Morita surveyed results on reversible cellular automata and presented animations that showed the inner workings of several such devices. A reversible computation device is one in which each noninitial configuration has exactly one preceding configuration. Many models of natural computing are reversible models.

NP-completeness of the Direct Energy Barrier Problem Without Pseudoknots, due to Manuch et al., was presented by Anne Condon. The Energy Barrier Problem is decision problem about molecular folding. Given a structure in some initial configuration, does there exist a pathway through subsequent configurations to a final configuration, such that the step from each configuration to the next requires at most energy k, for some fixed k. The paper reduces a simplified version of the Energy Barrier Problem to 3-Partition, a known NP-complete problem.

Several papers discussed the theory and practice of building DNA-based circuits. I would like to focus on Signal Propagation and Propagation Delays in Molecular Circuits by Seelig and Soloveichik, as it puts forth the thesis that circuit depth is not the correct measure of time complexity for chemical circuits (in contrast to electronic circuits, or classical circuit complexity). They present a theoretical model to capture something that has been observed in the lab: when there are just a few molecules of a certain species in solution, the reactions that depend on them will be slow, because the species will interact with low probability, since contact with it is so rare. As a result, stepping through a circuit is not a linear process. Approach to completion of a circuit becomes increasingly slow the deeper the circuit is, because the later layers require the output of all the earlier layers. One possible fix for this is to catalyze the reactions in question, so the reactions occur quickly even if there is only a small amount of species present. The drawback to this is leakage: if a chemical species is not fully consumed at an earlier stage, its presence can build exponentially at later stages, leading to the circuit providing incorrect answers. All in all, an intriguing model that raises a lot of questions.

DNA 16 will take place in Hong Kong, and DNA 17 will be organized by Erik Winfree at CalTech. I'm looking forward to them both!

Two requets: A sum and a reference

I have two requests from my readers. Both are essentially help tracking things down.

First: We (Bill Gasarch, Clyde Kruskal, Justin Kruskal) have in a paper of ours a summation that we proved. Is it new? Here is the summation: (It uses a sum that I previously inquired about here and got useful information, including that it was originally proved by Euler.)

Let p(x) &isin Z[x] be a polynomial of degree n with constant term 0.

p(s) - &sum_k=1ⁿ(s+k-1 choose k)&sum_i=0^k-1(k-1 choose i)(-1)ⁱ (p(s+i+1) - p(s+i)) = 0

Our proof is here.

(Side Request: How do you do a choose-sign in html?)

Second: I am, as always, tracking down lower bounds on the VDW numbers. I need the article An application of the Lovasz Local Lemma, a new lower bound for the Van der Warden numbers by Zoltan Szabo, Random Structures and Algorithms, 1990. Electronic preferred, but will take what you got. SO, if someone has it please email me article or pointer or whatnot. (Pointer might not work if your library has access to this journal, since ours does not have it in electronic or hardcopy.)

Annoucing YATB (Yet Another Theory Blog)

Jon Katz has a blog Random Bits

We've put it on our blogroll.

What will it be about? To quote Jon himself:

The blog will cover random topics, but especially crypto. It was started because there are currently no (active) crypto blogs and I hope this will become, to paraphrase Lance, a meeting place for the crypto community where we would have some discussions, sometimes quite heated, over the issues of concern to our community

Some advice for Jon and any new blogger:

1. In your technical posts try to have the first paragraph so that if someone doesn't want to read the rest of it they still get something out of.
2. Spellcheck!
3. Will you post every day but almost never make comments on the blog (Bill and Lance model)? Will you post once a week but make lots of comments on your own blog (Scott Aaronson model)? Will you post class notes? (Luca does that. Scott sometimes.) Will you be controversial or stear clear of controversy? (I'll let you guess who does what, it varies at times.) Do you have guest posts? What is your policy on anonymous commenters? There are no right and wrong answers; however, you should have answers.
4. If you have an idea for a blog try to write it up as soon as possible while you still are enthused about it. If it doesn't work then put it aside--- it may combine well with another idea later.
5. Keep a backlog of blogs that are timless.
6. Don't get upset at lack of comments, stupid comments, comments that misinterpret your post, or off-topic comments. You will get all of these.
7. If you try to make each blog perfect you will have a hard time getting anything out.
8. Technical posts are harder to write then others and may get tiring (though Lipton's doing just fine with them). Pace yourself on those.

SIGACT

I'm honored to have been elected as the new chair of SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. The rest of the executive committee (as of July 1) will be Cynthia Dwork, Anna Lysyanskaya, Michael Mitzenmacher, Mike Saks and Richard Ladner as previous chair. I look forward to working with all of them. 

A fond goodbye and thanks to those leaving the committee: Richard Cole, Joan Feigenbaum, Éva Tardos and Hal Gabow. We will have a difficult act to follow.

SIGACT has a small number of formal responsibilities: Running the STOC conference, co-sponsoring and cooperating with several other conferences, handling prizes and awards, publishing SIGACT News and acting as the theory liaison to the ACM mostly in dealing with publications. But SIGACT plays a more important role, as the organization that addresses and protects the interests and needs of the theoretical computer science community, the whole community, not just those who come to our conferences regularly. 

So please let us know what issues you think are important to the theoretical computer science and how SIGACT can help address these needs. Feel free to contact me or any other member of the executive committee. SIGACT exists to serve you.

The Story of the Blog

Google is celebrating the 10th anniversary of Blogger by asking its users to write the stories of their blogs. I'll bite as this blog has become such a a large part of my life and I like to think a part for the theoretical computer science community and beyond.

In 2002 I read a Newsweek article on then new phenomenon on blogging. I decided to give it a try. I wanted to blog on a specific topic and so I started blogging on the topic I know best. On August 22, 2002 I started "My Computational Complexity Web Log", the first major blog devoted to theoretical computer science. The blog gained in readership after a sardonic mention in Jason Kottke's popular blog. All of a sudden I had thousands of readers interested in computational complexity. In that first year I wrote mostly technical posts. I did a set of posts entitled Foundations of Complexity giving an introduction to the field and a series Complexity Class of the Week where I would review results and questions about a specific complexity class. Later on I wrote a monthly series of my Favorite Theorems in the field.

But the technical posts take considerable effort to write and proofread so I started writing more opinion and academic-oriented posts. The blog became a meeting place for the theoretical computer science community where we would have some discussions, sometimes quite heated, over the issues of concern to our community. Most of the young people I would meet at conferences knew me more for the blog than for my research. For a while a Google search on my name led to the blog before it led to me.

Changes happen. I shortened the name of the blog and experimented with podcasting. In March of 2007 after a post on turtles, I realized I was just going through the motions and decided to retire from blogging. Bill Gasarch took over the blog and kept it going. But I had too much I wanted to say and rejoined the blog in January 2008. Since then Bill and I have co-written this blog trying to get out a post every working day.

Now we have many excellent blogs in theoretical computer science ranging from very technical to very amusing. We strive to be the blog of record, the weblog people turn to to learn about the issues and happenings in the community. Weblogs have become the places that brings our ever growing academic community together in a way our conferences no longer can. I'm glad this blog is able to play its part in that effort.

Nondeterministic Parallelism

A reader asks

Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.

NC is Nick's Class (named after Nick Pippenger) and can be characterized by either a PRAM model with polynomial processors and poly-logarithmic time or by polylogarithmic-depth polynomial-sized circuits¹.

So what about nondeterministic NC or NNC? NNC is just the same as NP.

First let's consider randomized NC, RNC. Here each processors each had a limited number of random bits but they can share their random bits through memory, a technique used for example to find maximal matchings.

NNC, particularly if you want to have RNC ⊆ NNC, needs to have a similar definition. Suppose all the processors could act nondeterministically. Here is an NNC algorithm for 3SAT with n variables and m clauses.

1. Processor i (1 ≤ i ≤ n) guesses the ith bit of a potential satisfying assignment and writes it in memory location i.
2. Processor j (1 ≤ j ≤ m) checks whether this assignment makes clause j true.
3. If all processors in the second round accept than accept (which takes another log m rounds).

Since 3SAT is NP-complete under reductions computable easily in parallel, we have NNC = NP. The reverse direction is a simple simulation.

A simple observation but a very important point: Every nondeterministic computation has an easy nondeterministic parallelization. 

Alternately you can define RNC or NNC with an additional random or nondeterministic input (in either the circuit or parallel model) and get the same classes. 

RL and NL on the other hand handle randomness and nondeterministic differently. Here you have one processor using polynomial time and logarithmic space. While the processor can use a polynomial number of random/nondeterministic bits, the processor cannot remember them all. So RL and NL are considerably weaker, in particular both are contained in P.

Noam Nisan wrote paper On Read-once vs. Multiple Access to Randomness in Logspace that explores these definitions of randomness in more depth.

---

1. I'm ignoring uniformity issues in this post.

Do laypeople know what Prisoner's Dilemma is? Now they might

(Our blog has ALWAYS been green.)

This is a continuation of the topic in this blog entry.

In the June 17, 2009 issue of The New Republic, in an article called Plan of Attack, the term Prisoner's Dilemma was used and not explained. Does the public know what the term means? Are they supposed to learn what it means from context? I am asking these questions non-rhetorically. Here is the context and exact quote.

Context: Bob Woodward is going to do a book about the Obama White house. If you work in the White house, do you cooperate with him or not?

He (Bob Woodward) flashes a glimpse of what he knows, shaded in a largely negative light, with the hint of more to come, setting up a series of prisoner's dilemmas in which each prospective source faces a choice: Do you cooperate and elaborate in return for (you hope) learning more and earning a better portrayal-- for your boss and yourself? Or do you call his bluff by walking away in the hope that your reticence will make the final product less authoritative and therefore less damaging? If no one talks, there is no book. But if someone talks--- then everyone-- always talks.

1. Do people who are not involved with game theory on some level know what The Prisoner's Dilemma is? Some do, but I wonder how many.
2. Does it matter? Are writers freer to use terms the audience might not know since the writers know the readers can look it up easily. This is even more true if you are reading online and the writer provides links. However, in that case you may get distracted and not finish the article.
3. Will writers do this more often and will this educate the public?
4. I have also seen this on TV. If a show mentions some fact I didn't know, I might look it up. Sometimes its fictional, but sometimes its true. And sometimes you may get a skewed view of the issue: I once saw the 25th amendment used three times in one month of TV (West Wing, 24, and a repeat of 24) and always in a dramatic fashion. I looked it up and now know it; however, in real life, it has never been used in a dramatic fashion.
5. The article right after the Woodward one was about what to do with the detainees at Gitmo. The name of the article: Prisoner's Dilemma

Cond. Cvg Sequences in R^d AND real applications!

We present some PURE math that was APPLIED in a real way. I am more surprised by these things than I should be.

Recall that a summation &sum_i=0^&infin a_i Conditionally Cvgs if it cvg but &sum_i=0^&infin |a_i| does not cvg.

Recall the following theorem.

Cond Cvg Thm: Let &sum_i=0^&infin a_i be a cond. cvg sum. Let A &isin R. Then there exists a way to rearrange the summation such that it cvg to A.

What happens if instead of reals you have points in R^d? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)

Steinitz's Lemma Let d be a natural number, B be the unit ball in R^d, and V be a finite subset of B such that &sum_{v&isin V} v = 0. Then there is an ordering v₁, v₂, ..., v_n of the elements of V such that

v₁ &isin dB

v₁+v₂ &isin dB

v₁+v₂+v₃ &isin dB

etc.

v₁+...+v_n &isin dB

End of Statement of Steinitz's Lemma

This can be used to show the following:

d-dim version of Cond Cvg Theorem If a₁, a₂, a₃,... &isin R^d and &sum_i=0^&infin a_i conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of R^d.

This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.

1. A vector sum theorem and its application to improving flow shop guarantees. By I. Barany. Math. Oper. Res. Volume 6, 1981, 445-452. downloadhere or if it goes away or does not work then here
2. Bibliography: Series of vectors and Riemann sums. By I. Halperin and T. Ando. Sapporo, Japan, 1989
3. On approximate solutions of a scheduling problem. by S.V. Sevastyanov. Metody Diskr. Analiza Volume 32, 1978, 66-75. (In Russian).
4. On some geometric methods in scheduling theory: a surey, Discrete Applied Math, Volume 55, 1994, 59-82.

Conference Proceedings should have final version in Journal! (Guest Post)

(Guest Post by Samir Khuller.)

I have noticed that even though in the 80's and 90's a large number of FOCS, STOC, and SODA papers eventually appeared in journals (David Johnson even kindly edited a book that gave pointers to the journal versions of FOCS and STOC papers), the percentage appears to have declined significantly (I have not done a systematic analysis, but when I look for papers I often find that no journal version appeared.)

Most conference papers (even the top conferences) are not reviewed extremely carefully for correctness. The PC has a limited amount of time, and a large volume of papers to review.

What is the reason for this decline?

Are we so desperate to publish papers that we do not want to do a thorough job writing up the proofs after "staking our claim"?

Its very frustrating when when you are reading a paper and details are omitted or missing. Worse still, sometimes claims are made with no proof, or even proofs that are incorrect. Are we not concerned about correctness of results any more? The reviewing process may not be perfect, but at least its one way to have the work scrutinized carefully.

Now that proceedings are on CD's do we still need a strict 10 page limit on the conference version? Is this limit there to simply encourage people to submit to journals? If so, I am not sure its working.

What can we as a community do to ensure that results get properly reviewed and published in full in journals after they are published at a conference?

Math on Kindle DX

My Kindle DX arrived yesterday. I loved my first Kindle which I used for reading books and the New York Times. But the Kindle couldn't handle mathematical papers. The DX has native PDF support. So how well does it do for our community's papers?

I tested the DX on PDF documents, postscript won't work. I chose papers from STOC, CACM, Springer and Elsevier journals, ECCC, my own PDFlatex generated papers and the open access Theory of Computing and the ACM Transactions on Computation Theory journals. 

The math looks great. The resolution (1200x824) looks fine, the formulas and diagrams show up as good as on regular paper. No color but that's not an issue for most of our papers.

The papers take a couple of seconds to load and usually (but not always) quick to change pages. I had the worst experience on a scanned paper (Valiant's permanent paper) which took a very long time to load and change pages and looks as lousy on the Kindle as it does printed.

There are two ways to view a paper: portrait and landscape. Let me discuss each separately.

Portrait: A page of the PDF is filled into the screen area. The screen is about 3/4 the height and 2/3 the width of the US standard 8.5x11 paper so some papers are slightly squished, particularly multicolumn STOC and CACM papers have this problem. The ToC and ToCT papers looked the best. The text, formulas and diagrams are also shrunk but still quit readable as long as I am using my reading glasses (yes I've gotten old).

Landscape: You get to landscape mode simply by turning the screen (or manually with the Aa button). The landscape mode keeps the original aspect ratio but you only see part of the page. The width of screen in landscape mode is about the same as the width of regular paper so the type size is about right. You can move through the rest of the page with the Next Page/Prev Page buttons but otherwise no scrolling. The 5-way button seems to have no effect on PDF documents.

Extras: You can do a basic text search within a PDF document but not between documents or in scanned documents. Unlike normal Kindle documents you can't change the type size, add notes, highlight text, convert text to speech or move to a word to get its definition. You can bookmark a page but otherwise the only way to navigate is via the next page/prev page buttons. No way to click on links within a PDF file.

You can move documents quickly through the USB cable. The Kindle has tons of memory and can hold lots of PDF files. You can move whole directories but the Kindle flattens them out listing every file (by file name) separately on the main home page. You can also email papers at $0.15/MB and most of our papers are well under a megabyte.

Many of the issues above could be fixed by software updates but no guarantees Amazon will do so. Also it shouldn't be hard to produce DX-friendly PDF documents, with the right aspect ratio and large font size. If the DX gets popular than publishers might start producing Kindle-friendly versions of their papers. The old Chicken v. Egg problem.

The Great Oracle Debate of 1993

In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still unpublished paper with Sanjeev Arora and Umesh Vazirani. Bill asked me if I knew about the controversy and I said I'd answer in a blog post.

The Arora-Impagliazzo-Vazirani paper was submitted to the 1993 Complexity conference (then called Structure in Complexity Theory) which was part of the first FCRC conference in San Diego. The AIV paper tried to explain why the then recent interactive proof results (IP=PSPACE, MIP=NEXP, PCP theorem) don't relativize. I somehow got hold of a copy of the paper and thought AIV completely missed the mark, focusing on local checkability instead of the algebraic transformation of formulas. Also the AIV paper seemed down on relativization, a common theme, and I thought a response necessary. So I quickly wrote up my own response paper The Role of Relativization in Complexity Theory. 

The PC didn't accept the AIV paper but they set up a debate between Russell and myself at the conference. Russell and I spent several wonderful hours before the debate overlooking the ocean and talking about our models.¹ We did find some common ground during the day which unfortunately led to a debate without much fireworks.

After the debate, Juris Hartmanis asked me to submit my paper to the Complexity Column he ran for the Bulletin of the EATCS and so it appeared there. AIV is still going through revisions and Russell said during the STOC talk (that's last week's STOC) that they still planned to publish it. 

To continue the debate: Russell gave his STOC talk explaining that limiting the types of relativization would lead to "worlds" closer to our own. But you get a trade-off: While a few more techniques relativize in this model, it becomes much harder to create oracles, most of the oracles we have in the traditional model don't go through for the restricted model. Since the 1993 debate there have been many oracles in the traditional model published. Local checkability, algebraic methods and every other technique has failed to crack any of those oracles after they've been published. So why restrict our worlds when we still get so much more mileage in the traditional model?

---

1. The beach resort where we had the first FCRC was so much nicer than the inland location of the last two San Diego FCRCs

Can we make this problem FUN?

Consider the following cute problem:

Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone can see the numbers that are NOT on their own forehead. Call the three numbers x,y,z. They wish to determine if x+y+z is divisible by 1,000,000,000,000. There is an easy solution: Alice can just say Bob, your number is .... This would take 13 digits of communication. Can they do better?

Chandra, Furst, and Lipton showed that if instead of 1,000,000,000,000 was replaced by 2ⁿ, and if n is large, then do this in roughly \sqrt n bits. They were more interested in the k-party lower bound of &omega(1) since this leads to lower bounds on branching programs. (NOTE: They studied a variant of the the problem above, but everything they did applies hear also.) See their paper or my writeup for JUST the upper bound or my writeup of the upper and lower boundand its application to branching programs for more information.

The problem stated above with people having numbers on their foreheads sounds like it could be a fun problem for the layperson. BUT: The problem with this problem for the layperson is two fold: (1) The original problem involves 3-free sets. While our community might say Wow, an application of stuff coming out of van der Waerden's theorem (or at least I would say that), the layperson would not think of it or care. (2) Frankly, I don't know if 13 digits numbers are big enough for the asymptotics to kick in and give a better answer than 13.

SO- here is my challenge: Is there a solution to this problem (or perhaps one with larger numbers) where the solution is non-trivial--- that is, you do not communicate all of the numbers, but is also FUN! FUN means you can tell it to your non-mathematical-nephew, or perhaps your 10-years-old-great-niece-who-likes-math. Quite okay if its far worse than \sqrt(n).

Fifty Years of Mathmagic Land

I finally succumbed to Twitter. I plan to use my twitter account to supplement the blog with bite-sized items. I may sometimes expand those tweets into longer blog postings like today.

My 11-year old daughter talked about using straight lines and angles to improve her mini-golf game. That reminded me of the billiard ball scene in a Donald Duck math movie I saw many times over during my grade school years. Off to YouTube where we watched Donald in Mathmagic Land which coincidentally turns fifty years old this month.

Holds up pretty well after fifty years though the modern music, art, architecture and technology aren't so modern any more. Catch the Turing machine (reel-to-reel computer) near the end.

It was this movie and a Time-Life book on mathematics (which had a really cool chapter on probability) that got me excited by the fun of math which, of course, helped shape my future academic career.

The movie has a scene where Donald tries to open some locked doors that the narrator says represents knowledge yet to be discovered. Cool to think that I have now witnessed many of those door opened, some with my own hands.

Are there any longstanding conjectures that ended up being false?

Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true:

1. Fermat's last theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
2. Baudet's' Conjecture is now VDW's Theorem.
3. The Modell Conjecture is now Faltings Theorem.
4. I could list more, so could you.

Are there any conjectures that ended up being false? Yes, though none listed below is really a clean story.

1. Hilbert's 10th problem asked for an algorithm that would, given a poly in many variables over Z, determine if it has a Diophantine solution. We now know this cannot be done. While this may have surprised Hilbert, he was aware of this sort of thing happening. See the preface to his problems, or better see his entire address here.
2. Same with the Ind of CH from ZFC. Hilbert thought it was true. More to the point, Hilbert certainly thought it had an answer. Now we know that it does not. Or at least that its ind of ZFC.
3. NL=coNL surprised alot of people.
4. In 1986 most people thought that P\ne BPP (hard to believe!). One notable exception was Mike Sipser. Now most people think that P=BPP. Of course, not resolved yet.

I have not been able to find a dramatic example of a long standing conjecture that a large community believed ending up being false. Do you know of any?

I doubt that any of the Clay problems will end up being false. I doubt that any serious mathematician thinks that any will end up being false. That might be self-correcting: if someone did we would label him (perhaps unfairly) non-serious.

Rajeev Motwani

Tragic news from Jennifer Widom via Paul Beame.

I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a swimming pool accident at his home. He will be remembered by the large number of professional colleagues, faculty colleagues, and students whose education and lives have been enriched tremendously by his.

A tremendous loss for the theory community as well. Rajeev Motwani had an incredible publication record particularly in algorithms, wrote major textbooks, served our community well and was a true bridge between theory and practice. He received the Gödel prize in 2001 for the PCP paper. We lost one of the great ones.

Update: Suresh, one of Rajeev's former students, writes a very nice personal remembrance. 

Not about STOC/Funny Stuff people have send me

The other bloggers have done such a great job covering STOC that I won't add anything, except to say that I agree most of whats been said: Moser's talk and result were GREAT, the Innovations in Computer Science Conference has to be better defined, and Lance has both lost weight AND gotten a haircut

People often send me funny short math things and say this would be great for your blog!. Here is a collection of things people send me over the last year. XKCD comics:

1. RANDOM NUMBER
2. OPEN SOURCE
3. HAMILTONIAN
4. LABYRINTH PUZZLE
5. ONLINE COMMUNITIES
6. SECURITY
7. DUTY CALLS

A song about Mandelbrot Sets, although one of the comments on it claims that the song is actually about Julia sets. The person who send it was amused that there is a curse word in it. But he's young and easily amused--- he's 32.

A recursive music video.

A Failure of Social Networks?

One of Northwestern's professors made quite a splash a month ago with his group's predictions on the spread of the Swine Flu (now called H1N1). Dirk Brockmann claimed a worst-case scenario of 1700 flu cases by the end of May. Another group in Indiana made similar predictions. The research got picked up on a front page New York Times article. Brockmann's group used data from Where's George, a site that tracks movement of dollar bills, to understand interactions that would lead to the spreading of disease.

So how did these groups do? Not even in the right ballpark, off by two orders of magnitude. As a follow-up article in Tuesday's Science Times the CDC estimated there were well over 100,000 cases by the end of last month. What went wrong? In short Brockmann claims faulty initial data. Nevertheless I always worry that bad predictions from scientists make it harder to have the public trust us when we really need them to.

Might this be an instance where prediction markets greatly out-performed the experts? In short, no. There were relevant markets but two big problems: 

• No one thought to create a market for the number of flu cases over a couple of thousand. 
• Prediction markets require a verifiable outcome so they were based on CDC confirmed cases. But after the flu turned out not to be that dangerous, the CDC stopped confirming most cases and there were less than 7500 confirmed cases by the end of May.

Thoughts from STOC

I haven't been to STOC/FOCS since FCRC in San Diego two years ago. Since then I dropped thirty pounds and got a haircut last week. Amazing how many people thought something looked different about me and asked about the haircut.

I missed the Valiant celebration but it brought a large number of senior theorists who don't often attend STOC/FOCS. I enjoyed seeing and talking with them. Still, despite a relatively easy to reach location (say compared with last year's Victoria), STOC only attracted about 260 attendees, nearly half students. We just don't get draw many non-local attendees who don't have papers in the conference. Though David Johnson told me he's attended every STOC since the early 70's.

I don't attend many talks at STOC, I prefer to hang in the hallways chatting with people, about research, politics, gossip and baseball. The talks I did attend usually had about five or so good minutes of motivation and results followed by technical details for experts in that particular area. That's probably the right way to give those talks but I was rarely one of those experts.

And then I see a talk as amazing as Moser's and I realize: This is why I love theory.

A Kolmogorov Complexity Proof of the Lovász Local Lemma

Robin Moser gave one of the best STOC talks ever in his award-winning paper A Constructive Proof of the Lovász Local Lemma. Not only an amazing result but also an incredibly inventive simple proof that he came up with while preparing the talk.

Here is a sketch of Moser's proof written as a Kolmogorov complexity argument. This is not the full Lovász Local Lemma but captures the main principle.

Theorem: Suppose we have a k-CNF formula φ with n variables and m clauses and each clause shares a variable with at most r other clauses. Then there is a constant d such that if r < 2^k-d then φ is satisfiable. Moreover we can find that assignment in time polynomial in m and n.

Here's the algorithm:
Solve(φ)
Pick a random assignment of φ
While there is an unsatisfiable clause C
         Fix(C)
Fix(C)
Replace the variables of C with new random values
While there is clause D that shares a variable with C that is not satisfied
        Fix(D)

Assume Fix(C) always terminates. Every clause that was satisfied before we called Fix(C) will still remain satisfied and C will also now be satisfied. So Solve makes at most m calls to Fix.

We need to show all the Fix(C) terminate. Suppose the algorithm makes s Fix calls including all the recursive ones. We will show s is bounded and thus the algorithm terminates.

Fix a Kolmogorov random string x of length n+sk (random relative to φ, k, s, r, m and n) and assume the algorithm uses the first n bits as the initial assignment and k bits each to replace the variables in each Fix call.
If we know which clause is being fixed, we know the clause is violated so we know all the bits of this clause and thus we learn k bits of x. We then replace those bits with another part of x.

So we can describe x by the list of clauses we fix plus the remaining n bits of the final assignment. We can describe the C such that Fix(C) is called by Solve by m log m bits and the remaining fixed clauses by log r + O(1) bits because either it is one of r clauses that intersects the previous clause or we indicate the end of a recursive call (keeping track of the recursion stack).

So we must have m log m + s(log r+O(1))+n ≥ n+sk or s(k-log r-O(1)) ≤ m log m.

To show s is bounded, we need k-log r-O(1) to be positive or r<2^k-d for some constant d.

Note this in fact shows s = O(m log m) so the algorithm runs in polynomial time. We choose the x randomly which with high probability will be Kolmogorovly random. QED

In the talk, Moser gives the bound r<2 ^k-3 and in follow-up work with Gábor Tardos shows r<2 ^k/e (e = 2.71…) which is the best that comes out of the original Lovász Local Lemma.

STOC

Howdy from Bethesda. Lots of theory bloggers here and I don't want to spend too much time on the computer so today just some announcements from an uncontroversial business meeting. 

Sampath Kannan gave a long talk about the NSF. In short, they have money, you should apply.

Salil Vadhan gave us a preview of the research nuggets from the Visioning Workshop held right before STOC 2008.

Shafi Goldwasser gave the Athena Lecture. The Gödel Prize was awarded.

Mitzenmacher gave the PC report: 77 papers accepted out of 321 submissions. Best Paper award jointly to:

• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem, Chris Peikert (SRI International)
• A Constructive Proof of the Lovász Local Lemma, Robin A. Moser (ETH Zürich)

Moser also won the Danny Lewin best student paper award.

Mitzenmacher mentioned a number of PC issues that he plans to discuss on his blog. Definitely worth following.

Aravind Srinivasan discussed local arrangements (which have been excellent). 255 attendees including 116 students. He suggested STOC could be held at universities in the future to keep costs down.

Richard Ladner gave the SIGACT report. About 1300 profession members and 160 student memberships down from 240 in 2004. To get the numbers up, student registrants at SIGACT sponsored conferences will get an automatic one-year membership.

You can still vote for me (or Madhu) in the SIGACT Elections until June 15.

Get your calendars ready:

• FOCS 2009 will be in Atlanta October 24-27.
• STOC 2010 will be in Cambridge, Massachusetts June 6-8. Complexity will also be held in Cambridge immediately afterwards.
• STOC 2011 will be part of FCRC June 4-11 which will also include Complexity, COLT, SPAA and EC.
• Silivio Micali announced a new conference, Innovations in Computer Science to be held January 4-7, 2010 in Beijing.
• Russell Impagliazzo publicly announced the Barriers Workshop, August 25-29, 2009.

The Alpha

"I'm not keen on the hype" says Stephen Wolfram, this from the man whom I once heard exclaim "First there was Euclid. Then there Gödel. Then there was Mathematica". Despite the quote, Mathematica doesn't really help you prove new theorems but I found it quite useful when trying a few simple cases, simplifying messy expressions, optimizing parameters and checking other people's proofs.

But then Wolfram wrote that book that Scott Aaronson read so I didn't have to, and had that silly Turing machine contest. Now he comes out with the modestly named WolframAlpha.

WA is not a search engine, it isn't sure what to do with computational complexity and functionality for P=NP is under development. Good luck with that.

On the other hand it has considerable built in data and calculations. Type in sunset Chicago and I'll get useful information that used to take multiple clicks on Google.

More importantly WA is Mathematica Lite. We have a site license for Mathematica at Northwestern but the convoluted process to download it dominates its value to me. But I can just simplify and maximize directly into WA. solve x=4y^2-7, y=x+5 gives clean solutions. I had a little trouble maximizing probabilities with max p(1-2p) but change p's to x's and everything works fine. It solves all my daughter's homework questions on solving quadratic equations and simplifying radicals (but she's smart enough to know not to use it).

So kudos to Wolfram for producing something useful and free. Hope he keeps it that way.

Randomness in Madison

I'm at the University of Wisconsin for the second FRG Workshop on Algorithmic Randomness. FRG stands for "Focused Research Group", in our case a 12 PI NSF-funded project to study the properties or random reals, essentially Kolmogorov complexity on infinite strings. Most of the PIs are logicians from the computability theory community but a handful of us (Eric Allender, John Hitchcock, Jack Lutz and myself) have a computational complexity background. The workshop draws well beyond the PIs including foreign researchers and students.

Both the deep theory and connections of algorithmic randomness to other research areas (such as expert algorithms, extractors, measure theory and Hausdorff dimension) has grown tremendously in the past several years. The Kellogg business school at Northwestern just hired a new assistant professor Tai-Wei Hu from Penn State Econ whose job talk paper applies algorithmic randomness that he learned in a logic class from Steve Simpson to understand probability in repeated games.

I've only seen one talk here so far but it was a good one: Alexander Shen showed how to convert many basic questions about Kolmogorov complexity into who wins a certain kind of game.

Unfortunately because of teaching and STOC, I won't be at the workshop long. I've giving a short talk here tomorrow that doesn't directly relate to the topic at hand but kind of a cute not too difficult result: There is a computably enumerable, non-computable oracle A, such that P^A-P has no computable sets. Ponder it and I'll post the proof someday when I get it written up.

Games from the Eco-Daughter

My 11-year old daughter took a some courses on computer gaming that used the Greenfoot system and wrote a eco-themed game Trees (requires Java, click "play" then press "enter" to start). It's no Ribbit but then again when I was 11 I hadn't even seen a computer in person, much less programmed one.

The Greenfoot system uses Java with some built in objects so my daughter with simple coding can create interesting games while learning the basics of object-oriented programming. Pretty cool. Earlier she tried out Alice but found it too much hand holding.

On the eco theme, my daughter had me watch The Story of Stuff, a twenty minute animation of how consumerism is literally destroying the world. When I tried to argue a few points about the movie with her, she shot back "That's the truth. If you don't like the truth, well neither do I. That's why we have to change it." That's my little Al Gore.

Oracle Results are Good For You

For a short time in the 70's, some believed that oracle results would lead to true independence results in computational complexity. Richard Lipton in his post I Hate Oracle Results bemoans the fact that oracles haven't lived up to this hype. But "Hate" is an awfully strong word to apply to one of the most powerful tools in computational complexity.

Let me illustrate by an example. Consider the following open problem:

Does P=NP imply P=PSPACE?

Here's an approach: Chandra, Kozen and Stockmeyer characterized PSPACE by alternating polynomial time and one could possibly use the P=NP assumption to eliminate those alternations one at a time.

This approach doesn't work and in fact no similar approach can work. How do I know that? Because of the following relativization result due to Ker-I Ko.

There is an oracle A such that P^A=NP^A≠PSPACE^A.

If you are an oracle-naysayer, Ko's result shouldn't stop you from working on the problem. Let's try non-relativizing techniques. The tools of interactive proofs don't seem to work here. How about other non-relativizing techniques? We don't have any other non-relativizing techniques.  CKS is nearly 30 years old, Ko's oracle is 20 years old and this problem remains completely open.

There are hundreds of like problems which we cannot settle with non-relativizing techniques. If you feel oracle results no longer play a major role in computational complexity than we should have been able to settle scores of these problems. But in fact we have only twice proven a result in computational complexity when there was a previously known oracle going the other way, both directly related to interactive proofs.

I agree with Lipton that it would be nice to have a formal logical characterization of a "relativizing technique" but just because we don't doesn't mean oracle results don't properly guide our research efforts. More from my 1994 relativization manifesto that I still stand by today.

Raymond Smullyan's Birthday

CLYDE: I met Raymond Smullyan in the around 1985. He was old then. When did he pass away?

BILL: Lets look it up on Wikipedia. (He does.) OH, he didn't! He is still alive! And his birthday is May 25. He turns 90! (thats not 90 factorial). OH, I can post about it ON his birthday.

CLYDE: What will you say?

BILL: I will say that he wrote many popular books on self-reference which were quite good, but after a while somewhat repetitive. And that he his latest book, Logical Labyrinths came out this year, and claims to bridge the gap between the type of logic in his popular books and serious logic. WOW, looks like he is still active!

CLYDE: Isn't that a short post?


BILL: I'll find other stuff to put around the post to make it a bit longer.

Get Your Stimulus Money Here

"Are you taking full advantage of President Obama's stimulus package?" asks a recent robocall. So are you? If not the National Science Foundation has some ways to help.

The NSF gave the CRA $15 Million to start the Computer Innovation Fellows project, basically 60 CS postdoc positions for next year. A little late in the season but if you haven't nailed down a job for next year yet be sure and apply by June 9th. If you are willing to hire a postdoc paid by this program, sign up as a mentor.

Are you still in school? The NSF is greatly expanding the Graduate Research Fellowship Program and the Research Experiences for Undergrads. 

Already have an academic job? Apply for the CAREER award if you are eligible (CS deadline July 21), a regular theory proposal (August deadline for medium, November for large, December for small) or one of the many other CISE programs.

The NSF budget is on track to improve dramatically over the next decade but politics have and can get in the way. Be sure and take advantage now while you have the chance.

Gödel Prize

This year's Gödel Prize has been awarded to two papers.

• Undirected Connectivity in Log-Space by Omer Reingold
• Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders by Reingold, Salil Vadhan and Avi Wigderson

I consider Reingold's paper the second best result of the decade (after "Primes in P" which won the prize in 2006). Reingold settled a long-standing open question deterministically showing how to get from point A to point B in an undirected graph using memory equivalent to remembering a constant number of vertices.

The zig-zag paper developed a new construction of constant-degree expanders. We already had simpler expander constructions but the zig-zag technique gave us a recursive way to think about expanders that Reingold drew on for his paper.

This is the first Gödel prize for each of these authors and I'm especially happy to see Wigderson, perhaps the best complexity theorist of our generation, take the prize. Avi could have easily won it earlier for his work on zero-knowledge, derandomization, circuit complexity or many other topics.

Congrats to All!

Is FKS and other Data Structure Algorithms actually being used?

MEM PROBLEM: Let n,U be such that n < < U. We want to do the following: For all sets A &sube {1,...,U} such that |A|=n we want to store A in s(n,U) cells and be able to tell MEMBERSHIP in q(n,U) probes where a probe is just LOOKING at the contents of a cell. A cell may have O(log U) bits in it.

Fredman, Komlos, and Szemeredi showed (in this paper) that MEM PROBLEM can be done with s=O(n) and q=O(1).

1. They actually showed something stronger, that you can get s=n+o(n) and q=O(1). But this does not concern us.
2. The result with s=O(n) and q=O(1) is a simple algorithm with reasonable constants.
3. Part of the algorithm involves showing that a randomly picked hash function works with nonzero probability; however, with a slight change in some parameters you can get that most hash functions work (of the type they use) work, so this is not an obstacle to actually using their algorithm.
4. SO, here is my question/answer/new question:
   1. Is anyone actually using the algorithm?
   2. I would suspect NO because it does not allow for INSERT and DELETE. However, if you just INSERT or DELETE a few things I think it should be fine. So maybe YES.
   3. This paper does MEM in O(1), space O(n), and INSERT/DELETE in amortized expected time O(1).
   4. There has been alot of work on data structures with this model. The model seems reasonable, the problems seem like ones people in the real real world want to do quickly. SO--- are the data structures being used? If not, then are variants being used? This seems like an area where the gap between theory and practice is small and could be bridged. Has it been? If not why not?

Lessons from EC

We just posted the talk schedule for the 2009 ACM Electronic Commerce Conference. Early registration deadline is June 12th and hotel deadline is June 5th.

The EC conference covers a broad range of work connecting computer science and economics. While a large part of the EC community draws from the from the theoretical computer science community, it also draws from AI, computer-human interaction and economists. So the PC process works a little bit differently than in other conferences. Some thoughts.

PC co-Chairs: We had two PC chairs (Pearl Pu and myself) to spread the workload and add some diversity. The workload wasn't that much less but having different viewpoints definitely helped. I worried about what would happen if we had irreconcilable differences but we managed to work around our disagreements. I have nothing but great things to say about working with Pearl, but I would suggest future conferences avoid having PC co-chairs seven time zones apart.

Multilayered Committee: We had a dozen Senior PC members and a very large (about 90) PC members. We let the Senior PC members choose their PC members. Most papers were assigned to two senior PC members who submitted it to two PC members each, some of whom sent it out to outside reviewers. There was discussion between the PC member and sometimes the senior PC members before Pearl and I made the final decisions. The system seemed to work well for this diverse community.

Author Rebuttal: We sent the reviews to the authors before the final decisions and allowed them to give a 500-word rebuttal. Some papers were helped (or hurt) by the author's ability (or inability) to argue against the criticisms given by reviewers. I found the rebuttals quite useful but we did hear some complaints about the extra work required of the authors and the PC.

Would these ideas work for pure theory conferences? I suspect they would work best for the more diverse conferences like STOC/FOCS/ICALP where for any given paper, most of the PC do not have expertise in that paper's area.

Halt is Undecidable in Verse (YES, you've seen it before)

About a month ago I came across a proof that HALT is undecidable in verse! I thought what a great post that would make! Last week I tried to find it again but, alas, I could not. This link did not work on my school computer, but it did on my home computer. I am tempted to say thats odd but its not--- odd computer things that don't make sense are so common that they are no longer odd. Just to make sure I always had a copy I made my own copy which is here.

While searching the web for this poem I came across a posting about it by Lance here. However, the link there no longer works. (Though Lance may read this and fix it.)

If you find something on line that you like SAVE IT! It may go away. Especially if its a Dr. Suess Style poem See this post).

The Quadratic Formula

A few weeks ago my eighth-grade daughter learned about the quadratic formula for solving ax²+bx+c=0. She's impressed I can still rattle it off like a song "Negative bee plus or minus the square root of bee squared minus for-ay-see all over two-ay". She then asked the question I love to hear, "How did anyone come up with that formula?" So I decided to show her how to derive it but couldn't figure it out on the spot. How embarrassing! I did manage to figure it out later and showed her the next day.

Her textbook gives conditions to use the quadratic formula.

1. b²-4ac≥0.
2. a≠0.

The first because they haven't learned complex numbers in the eighth grade. How about the second? After all the solution for a=0 is well defined at x=-c/b (assuming b≠0). What happens when you take the limit as a goes to zero? For the square root with sign opposite of b the limit doesn't exist going to plus or minus infinity depending on whether you approach zero from above or below. But for the other square root after applying l'Hôpital's rule and greatly simplifying you do get -c/b. Possibly the most complicated way to solve bx+c=0.

The Prime Number Theorem

Recall the Prime Number Theorem (PNT).

Let &pi(n) be the number of primes that are &le n. As n goes to infinity &pi(n) approaches n/ln(n).

Note that we did not say &theta(n/ln(n)) or n/ln(n) + &theta(1). We really said n/ln(n) (NOTE: Comments on this post have correctly refuted this comment about ``really said n/ln(n)'') However, I will have need to refer to a Weak PNT:

Let &pi(n) be the number of primes that are &le n. There exists constants A and B such that As n goes to infinity An/ln(n) &le &pi(n) &le Bn/ln(n).

In Hardy and Wright's treatement of PNT (and others) they prove the very badly named Bertrand's Postulate (BP) on the way to proving PNT.

(BP) for all n&ge 3 there is a prime between n and 2n.

1. The first proofs of PNT used Complex Analysis and were considered to be not elementary. Erdos and Selberg (ind? not ind?- see this paper for the history) found elementary proofs that question the use of the word elemenatary since they were quite difficult. It is hard to pin down the term elementary since, Oliver Sudac (TCS, The Prime Number Theorem is PRA Provable, Vol 257, NOT Online) showed there is a proof in Primitive Recurive Arithmetic which is weaker than Peano Arithmetic. An interesting article on this which IS online is by Jeremy Avigad on all of this is at Number Theory and Elementary Arithmetic.
2. Applications of PNT. Are there any? The Tao-Greene theorem (there are arb long arithmetic progressions of primes) uses it, though I suspect Weak PNT would suffice. QUESTION: Is PNT, not Weak PNT, ever actually needed?
3. WEAK PNT has a much easier proof. Here are my notes on it. The constants in this presentation are reasonable.
4. From the proof I present of the Weak PNT you can obtain that for large n there is a prime between and 3n.
5. Bertrands Postulate is used in Computer Science sometimes to show that you can get hold of a prime. (E.g., the proof that EQ has Comm Complexity O(log n).) QUESTION Is full BP ever actually needed?
6. Better results are known: Baker, Harmon, Pintz showed that, for large n, there is always a prime between n and n+n^{0.525}. See their paper.
7. I have not been able to find why Bertrand's Postulate is called that. History: Conjectured by Joseph Bertrand in 1845, proven by Chebyshev in 1850.

Shaving Logs with Unit Cost

A grad student asked me the following question about how to measure running times.

A paper in POPL 08 claims to have broken the long-standing n³ barrier on a problem in programming languages, bringing it down to n³/log n. The algorithm has a lot of details, but the main pillar it stands on is the so-called 'fast set' data structure.

This data structure is used to represent sets as bitmaps of its elements (so a set {1,2} over the domain 0-7 is represented as 01100000), and supports three operations, where one is important for my question: set difference. Set difference can be performed by going through the bits of each set. Here's the claim I have a question about: The author says, assuming an architecture with word size Θ(log n) bits, we can split the bitmaps of each set into (n/log n) chunks of size (log n) bits each, and since the word size is Θ(log n), these chunks will be stored in a word each, and operating on each word is a constant. Hence, set difference can be performed in Θ(n/log n) time. This is the whole gist of the algorithm to break the previous known barrier.

I was appalled by this argument, since my primitive techniques would easily 'prove' that set difference has a lower bound Ω(n), since you have to 'touch' each element of the set. I contacted the author, and he said assuming this word size is standard in algorithms literature, such as saying that depth-first search takes O(e+v) time ignores the log v time needed to spend to retrieve each vertex.

I talked to a few people in my department with varied responses, some said it is cheating since algorithms such as DFS do not depend on the logarithmic word size, it is just ignored; and some said it is probably a good argument.

The simple question is, what do you think as a complexity researcher? Is the complexity given a valid one? I am worried that you will say no, because a lot of people are citing this paper and everybody thinks the n³ barrier for that problem has been broken. I am also worried that you will say yes, as a person not particularly in the complexity field, but thinks he has a decent knowledge and sense of algorithms.

I remember complaining as a student that sorting actually takes O(n log² n) time since one needs O(log n) time to do a comparison but my complaints fell on deaf ears.

In algorithms you use the unit-cost RAM model where basic register operations over O(log n) bit registers count as a single computation step. There are some good arguments for this: As technology improves for us to handle larger input sizes, the size of the registers tend to increase as well. For example, registers have grown from 8 to 64 bits on microprocessors over the past few decades.

You can do set difference of two register bitmaps A and B by the bitwise AND of A with the bitwise complement of B, all standard register operations. So the author has a legitimate O(n³/log n) time algorithm in the standard algorithmic unit-cost model.

I understand the student's frustration. The algorithm seems like a cheat and would not be in DTIME(O(n³/log n)) on a multi-tape Turing machine as I teach it in an introductory complexity course. But as an algorithmic result on the standard algorithmic model, the author stands on solid ground.

My Obligatory Star Trek Post

Hard to believe I have yet to make a Star Trek post in this weblog. Bill had a guest post The End of an Era? back in 2005 back when Enterprise ended its run. The new movie starts another Star Trek era. I saw it Saturday and my three-word review: go see it.

I was but a toddler when the original series premiered but by the time I was in middle school Star Trek fever had taken over. The local TV station showed Star Trek nearly every day and I watched as often as I could (back in the era before Hulu, Tivos, DVDs, VCRs or even remote controls). I memorized the episodes, read the novelizations, tried to catch the animated episodes though time conflicts usually saved me from that disaster. This was the show young nerdy teenagers talked about. 

I had great fun seeing the first movie just to see the cast back together. Caught Wrath of Khan on its first showing in New Jersey at a surprisingly empty theater. Ricardo Montalban was one of those actors on the original series who went on to greater fame, in this case on Fantasy Island. Great to see him reprise his role on Star Trek in the best movie with the original cast. 

In grad school we had a party for the first episode of Next Generation. I watched most of that series as well as Deep Space Nine and Voyager before giving up on Enterprise well before it ended its run. In 2005 Star Trek seemed to have run its course.

J.J. Abrams took Star Trek back to its roots, recasting the original cast and rebooting the series. I forgive the various issues of canon for a very enjoyable movie and the return of the most important Sci-Fi franchise of my generation. 

Requst for Info on Prob Hypergraphs

A grad student recently asked me for some refs on probabilistic hypergraphs. I didn't know any, but I suggested we harness the power of the internet and of the blog. Here are his questions. If you know any refs please comment.

(Here are his questions.)

I have a problem that deals with coalitions. The basic idea is to have a hypergraph with a bunch of nodes representing actors and edges representing coalitions. Such a hypergraph would have the following properties:

1. non-regular (edges can have any number of nodes, and different edges in the same graph can have different numbers of nodes)
2. down-set (the existence of an edge implies the existence of all edges that are a subset of that edge)
3. finite
4. probabilistic EDGES (I had found previous work on probabilistic nodes, but not for edges)

Does anyone know of any work on these types of hypergraphs? ~

New URL Same Blog

The Computational Complexity weblog has a new URL blog.computationalcomplexity.org. This change should increase reliability of posting, commenting and loading the blog.

All the old weblog.fortnow.com URLs will now forward to the appropriate new URL (or go back to the original files if needed) so you don't have to change your bookmarks, links or feeds. You can access the old files at oldblog.computationalcomplexity.org but that site will no longer be updated.

The URLs computationalcomplexity.org and www.computationalcomplexity.org will continue to point to the Conference on Computational Complexity so you still can easily register for the upcoming conference in Paris.

Doctor for Two Decades

I measure academic age by years since Ph.D. and by that measure I just turned twenty. I passed my Ph.D. defense on May 5, 1989 (though technically I didn't graduate until June).

20 years. Wow. 20 years before my Ph.D. we didn't have a P vs. NP problem. Does the PCP theorem seem as ancient to today's grad students as Cook's theorem was to me?

In those 20 years we had incredible advances in 

• Complexity of approximations which includes developments of interactive proofs, probabilistically checkable proofs, the parallel repetition theorem, semi-definite programs, and unique games.
• Great advances in coding theory in particular list-decoding codes.
• Tight connections between circuit hardness and derandomization. And we don't need random coins anymore for primality. 
• Explicit constructions of extractors, expanders and various other combinatorial objects with SL=L coming out of this theory.
• Quantum computing.
• Proof Complexity.
• Cryptography. Almost anything you can imagine you can implement cryptographically, at least in theory.
• The applications of computation theory to economic theory and vice versa.
• Amazing connections between all of the above.

And I got to watch it all in real time.

I've seen the Internet go from E-mail to Twitter. I've seen fax machines and CDs go from amazing technologies to has beens. And computers got much faster and smaller. I no longer have time for a restroom break when I LaTeX a paper.

Technology that hasn't changed much: Transportation. I still get from point A to point B the same way I did twenty years ago though now without being fed. 

What will the next twenty years bring? Many great theorems. Definitely. Multi-core computers with millions of cores. Probably. Large-scale quantum computers. Doubtful. A proof that P≠NP. Don't count on it.

New York THEORY DAY 2009

Dear Organizers of IBM Research|NYU|Columbia Theory Day,

You emailed me the ad for Spring 2009 Theory Day. THANKS!
You did this about a week ago. Hence, as is often the
case this is too much short notice to go.
Please announce it earlier in the future.

Also, I could not find on your website a pointer to the
abstracts of this years talks (If I missed it then please
let me know.  Other readers, also let me know.)

And lastly, your page on Recent and Upcoming Theory Days
should be retitled
Theory Days from 2003-2007 or be updated.

                                        bill gasarch

P.S. The talks look AWESOME!


                 The IBM Research|NYU|Columbia Theory Day
                         Friday, May 22, 2009


The Theory Day will be held at the Davis auditorium,
412 Schapiro (CEPSR) building, Columbia University, New York.

                                  Program

9:30   - 10:00    Coffee and bagels

10:00  - 10:55    Dr. Dana Moshkovitz (IAS)
                  Two Query PCP with Sub-Constant Error

10:55  - 11:05    Short break

11:05  - 12:00    Dr. Craig Gentry (IBM Research)
                  Fully Homomorphic Encryption Using Ideal Lattices

12:00  -  2:00    Lunch break

 2:00  -  2:55    Dr. Mark Braverman (Microsoft Research)
                  Approximating bounded depth circuits with polynomials

 2:55  -  3:15    Coffee break

 3:15  -  4:10    Dr. Muthu Muthukrishnan 
                  (Google Labs and Rugers University)
                  3 Problems in Internet Ad Systems

For directions, please see DIRECTIONS

To subscribe to their mailing list, follow instructions at HERE

Organizers:
Yevgeniy Dodis   dodis@cs.nyu.edu
Rocco Servedio   rocco@cs.columbia.edu
Tal Rabin        talr@us.ibm.com
Baruch Schieber  sbar@us.ibm.com

My Kindle

As an MIT alum I have an automatic subscription to Technology Review, a pretty nice perk. Wrapped around the current issue was a note that I could trade my printed issue for access to the digital issue, with more content and earlier availability. I'll keep the printed issue because I can't read documents on the screen for long periods of time. I get a complementary digital issue of Scientific American by being part of their blog network but end up just skimming it and printing out any articles I really want to read.

But I found I can read for long periods from the Kindle which I got when Amazon released their second edition a few months ago. I've fallen in love with the device. I cancelled my paper subscription to the New York Times and read it now on the Kindle and have downloaded and read several books on the device. Often I'll send text documents to the Kindle for reading. The Kindle has resparked my interest in reading and I love many of the features including automatic bookmarking and easy dictionary look up where before I rarely put in the effort.

I saw recently that the Kindle attracts a much higher age demographic than most new electronic devices. My guess is that us older people have never gotten used to reading off a computer screen and are willing to spend money on a device that just lets you read.

But the Kindle doesn't work for much of my reading—mathematical research papers. The Kindle doesn't do formatting well, just converting PDFs to text. 

Today Amazon will announce the new Kindle DX with a larger screen, true PDF formatter and supposedly textbook friendly and thus I assume math friendly. Imagine for example putting conference proceedings on a Kindle-like device instead of having a heavy book or proceedings one has to use a laptop to look at. Or putting all the papers you need to referee/review on such a device. Would that make it more or less likely you will get the reviews in on time?

But how do I justify getting a new Kindle when I already own one? Sometimes being slightly ahead of the technology curve works against you.

My Publications

I spent some time this weekend updating my publications page. I did well in the summer conference season: An ICALP paper and two each in Complexity and TARK. Not to mention my first ever Algorithmica paper was just accepted for publication.

My proudest 2009 publication: The Complexity of Forecast Testing written with Rakesh Vohra that appeared in the January issue of Econometrica, generally considered the top journal in economic theory. Consider the problem of testing a forecaster (like a weatherperson) who give a probability each day of an even that happens the next day. Alvaro Sandroni proved a strong negative result: Suppose a tester T makes decisions in a finite number of steps and passes (with high probability) any forecaster that correctly predicts nature. Then there is a probabilistic forecaster that will, with high probability, pass test T without any knowledge of nature, even if nature is adversarial.

Sandroni's forecaster requires solving exponential-sized linear programs. Vohra and I showed that Sandroni's theorem doesn't hold if we limit both the tester and forecaster to be efficiently computable (under generally believed hardness assumptions). We created efficiently computable testers so that for some distributions for nature, a forecaster would have to factor numbers or solve PSPACE-hard problems to pass the test.

This paper represents a large part of my current research: Applying the ideas and tools of computational complexity to economic theory, in particular seeing what happens in a wide variety of economic models with when we require the agents to be computationally efficient. Given the success of this paper (and others), perhaps some economists are beginning to realize the importance of capturing computation costs in their models.

A new way to educate the public

How well known is the concept of the Turing Test? Readers of this blog know what it is. On Google it gets 2,360,000 hits. It has a Wikipedia entry: here. None of these mean that the public knows what it is.

I didn't think it was well known. However, in Roger Ebert's review of the movie X-men Origins: Wolverine he titles the review

A monosyllabic superhero who wouldn't pass the Turing Test.

In the review he never mentions the Turing Test or what it means. Does he expect his readers to know? Do they? Does the general public know what the Turing Test is? Will readers of the Ebert's column go to Wikipedia to find out? Might this be a way to educate people?

CHALLENGE TO MY READERS: find a movie whose review could illustrate a computer science or math concept. Here is one: The Usual Suspects:

As complicated an enjoyable as the classical proof of van der Waerden's theorem.

Foundations of Complexity

In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that links to them all. 

1. What is a Computer?
2. Computable and Computably Enumerable Languages
3. Universal Turing Machines and Diagonalization
4. Noncomputable Computably Enumerable Languages
5. Reductions
6. The Halting Problem
7. The Recursion Theorem
8. Efficient Computation
9. Nondeterminism
10. The P versus NP Problem
11. NP-Completeness
12. Turing Machine Redux
13. Satisfiability
14. CNF-SAT is NP-complete
15. More NP-complete Problems
16. Ladner's Theorem 
17. Space Complexity
18. Savitch's Theorem
19. The Immerman-Szelepcsényi Theorem

I hope to add more lessons in the future.