Tuesday, June 30, 2009

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).

Monday, June 29, 2009

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.

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.

Friday, June 26, 2009

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.

Thursday, June 25, 2009

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!

Wednesday, June 24, 2009

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) - &sumk=1n(s+k-1 choose k)&sumi=0k-1(k-1 choose i)(-1)i (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.)

Tuesday, June 23, 2009

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.

Monday, June 22, 2009


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.

Friday, June 19, 2009

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.

Thursday, June 18, 2009

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 circuits1.

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.

Wednesday, June 17, 2009

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

Tuesday, June 16, 2009

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 &sumi=0&infin ai Conditionally Cvgs if it cvg but &sumi=0&infin |ai| does not cvg.

Recall the following theorem.

Cond Cvg Thm: Let &sumi=0&infin ai 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 Rd? 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 Rd, and V be a finite subset of B such that &sumv&isin V v = 0. Then there is an ordering v1, v2, ..., vn of the elements of V such that

v1 &isin dB

v1+v2 &isin dB

v1+v2+v3 &isin dB


v1+...+vn &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 a1, a2, a3,... &isin Rd and &sumi=0&infin ai conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of Rd.

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.

Monday, June 15, 2009

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?

Friday, June 12, 2009

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.

Thursday, June 11, 2009

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.1 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

Wednesday, June 10, 2009

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 2n, 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).

Tuesday, June 09, 2009

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.

Monday, June 08, 2009

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.

Saturday, June 06, 2009

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

Friday, June 05, 2009

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:

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.

Thursday, June 04, 2009

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.

Wednesday, June 03, 2009

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.

Tuesday, June 02, 2009

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 < 2k-d then φ is satisfiable. Moreover we can find that assignment in time polynomial in m and n.

Here's the algorithm:
Pick a random assignment of φ
While there is an unsatisfiable clause 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

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<2k-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.

Monday, June 01, 2009


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:
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.