{\huge Thanks For Sharing}

An exchange of expertise and gifts \vspace{.5in}

William Bradford was the first civic authority to proclaim a day of Thanksgiving in North America. He became governor of the fledgeling Plymouth Colony in 1621, a month after the settlers made a mutual-aid treaty with Massasoit, chief of the Pokanoket tribe. The Native Americans and settlers shared farming and hunting practices and technology, and provided for each others' defense. With half of the settlers having already perished of disease, cold, and starvation the first winter, the colony would not have survived without this help.

Today we wish to talk about sharing and gifts between fields. It may not be life-and-death, but at least it's our life.

Bradford was a co-author of the first paper ever published on U.S. soil, the Mayflower Compact, which was signed on November 21, 1620, by our modern calendar. Or at least he wrote two of the three versions by which it was preserved for posterity, the original manuscript having been lost. Bradford also wrote Of Plymouth Plantation, for which he has been called ``the father of American history.'' The manuscript for this work was apparently stolen by British soldiers during their occupation of Boston in 1780, and turned up 75 years later at the London residence of the Archbishop of Canterbury.

Both of us remember when research papers had manuscripts, but it is possible that many new people in our field do not. What we do have is unprecedented ability to share work and ideas as they come out. Still, one needs to seek where to find them and whom to talk to. This sometimes requires a voyage, not to another world, but perhaps to another conference.

Simple Gifts

Over many decades there are numerous results that we know, results we use or see used, but ones not everyone remains aware of. A bit like pumpkin pie on Thanksgiving we may enjoy them during this season, but forget about them the rest of the year. So here is one that is a quite powerful but simple idea.

The insight is this: It is possible to construct a polynomial in a single variable that has roots at $latex {1,\dots,m^{2}}&fg=000000$ and yet can be evaluated in time order $latex {m \log m}&fg=000000$. The point of this is that the polynomial can be evaluated in $latex {T}&fg=000000$ arithmetic steps, yet has almost $latex {T^{2}}&fg=000000$ number of roots. This idea has been used to create an early factorization algorithm that runs in time $latex {N^{1/4}}&fg=000000$: note that naively trying all numbers less than $latex {\sqrt N}&fg=000000$ is much worse than this method.

More recently the above idea has been used to break a crypto-system that relied on the difficulty of solving the so-called Approximate GCD problem. We have known since the Greeks that we can compute the greatest common divisor of two given numbers $latex {x}&fg=000000$ and $latex {y}&fg=000000$ in time polynomial in the number $latex {d}&fg=000000$ of digits. Of course they did not say this, but Euclid's algorithm does indeed run this fast. However, what if we perturb the value of $latex {x}&fg=000000$ by a small amount less than $latex {\Delta}&fg=000000$?

We may suppose that $latex {\Delta}&fg=000000$ is a small number, in particular of $latex {\mathsf{poly}(d)}&fg=000000$ magnitude and smaller than any divisor of $latex {x}&fg=000000$, but not tiny. The obvious algorithm given $latex {y}&fg=000000$ and $latex {z = x + \Delta}&fg=000000$ seemed---incorrectly---to be: compute the gcd of $latex {y}&fg=000000$ and

$latex \displaystyle z-1, z+1, z-2, z+2, \dots &fg=000000$

The cool insight of Yuanmi Chen, Phong Nguyen in their EUROCRYPT 2012 paper is that one can do better by using the above polynomial trick. Thus the approximate gcd is solvable roughly in time that is order not $latex {\Delta}&fg=000000$ but $latex {\sqrt {\Delta}}&fg=000000$. Here is a slightly different statement:

\includegraphics[width=4in]{eurotalk.png}

As usual we say to see their talk and paper for the full details, but here we can at least sketch how to ``bake'' the polynomial---that is give out the secret recipe. The idea is based on the well known result:

Theorem 1 Given a polynomial of degree $latex {d}&fg=000000$ there is an arithmetic algorithm that evaluates it at $latex {d}&fg=000000$ distinct integer points in order $latex {d \log d}&fg=000000$ steps.

The method is based on the FFT.

Consider the polynomial

$latex \displaystyle f(x) = (x+1)(x+2) \cdots (x+m). &fg=000000$

$latex \displaystyle g(x) = f(x) f(x+m) \cdots f(x + (m-1)m) f(x + m^{2}). &fg=000000$

This is the trick. Can you use it in complexity theory? Note that we went to a crypto conference to get it.

Linear Algebra Gets Physical

For over a decade people have noted theorems in non-quantum complexity theory whose first proofs were obtained through quantum mechanical techniques. As noted by Bill Gasarch here, Umesh Vazirani gives a whole talk on this theme. Our own skepticism on the feasibility of building large-scale quantum computers, and our year-long debate on this, do not diminish the value of sharing with those whose background is in physics.

It is facile to say that quantum mechanics is ``just'' linear algebra, so that these results could have been obtained by greater attention to linear algebra. Yes we feel there is scope for greater imagination within linear algebra, exemplified by our previous post on matrix rank. The point however is that physical intuition comes first and is then conveyed through the linear algebra to create the proofs.

An example is Scott Aaronson's alternate proof that the complexity class $latex {\mathsf{PP}}&fg=000000$ is closed under Boolean operations, via its equality to a quantum-inspired class $latex {\mathsf{PostBQP}}&fg=000000$ for which the closure is clear. This is so even though the operation of post-selection which inspires the class is not actually allowed in physics. The proof of equality is more informative than the earlier proof of the closure properties by polynomial manipulation, and it is also shorter: it fist on the above-linked Wikipedia page.

Occupying our attention now is a new paper by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf, the last of whom Ken knows from discussions of quantum circuits. We mentioned it in September. The link is to quantum communication complexity. For an analogy, Mauricio Karchmer and Avi Wigderson gave a new link between classical communication complexity and Boolean circuit depth that was used for many further results, indeed involving ideas of matrix and tensor rank. The new paper shows greater ramifications when qubits rather than bits are communicated, a subject benefiting from over two decades of study by quantum physicists and information theorists.

Some Thanks to Commenters

Now we give thanks to some poeple from other fields who have shared insights via comments in this blog. We did some for 2009 a year ago. Of course all this year we have had contributions by physicists in the posts of our quantum computing debate, and comments have continued through this week. The year 2010 kicked off with a comment from Cornell graduate student Mark Reitblatt, who does formal-language methods for network reliability, that voices our theme:

...Look at how often guys like Tim Gowers or Terry Tao have discussed or looked at interesting CS theory problems, then ask yourself the last time a mainstream theorist took a serious interest in algebraic geometry or representation theory or dynamical systems.

Some further input on formal methods was anchored here, while neighboring posts drew comments from retired engineer Américo Tavares. Our post on definitions drew views from several areas, including this by software developer and blogger Paul Homer, who continues contributing often. We had various views from industry on our Jan. 2010 post about online courses, such as this.

A oeniphile physicist pondered ``how mathematics relates to physics and reality,'' while a hardware view of matrix multiplication came here from Neil Dickson, a software optimizer who worked for a time at a commercial quantum computer company, and was replied to by its CTO/CEO. Robert Tucci envisions quantum software and often pitches in as here, while quantum medical engineer John Sidles is unmatched, and Cristopher Moore is already an interdisciplinary theorist. AI researcher Kevembuangga gave an object lesson on objects across several posts. A Polish dentist---or perhaps a relative?---gave some thoughts on security. Ken thanks many responders to his post on chess endgames, though we two have yet to develop the intended cross-field aspects much further.

We had input from all walkers of life on how amateurs might solve P versus NP, a month before the claimed proof of inequality by Vinay Deolalikar, whose website shows no change from when we looked last year. A followup to that episode drew a about Patriot missiles over two decades ago, and continued about algorithms on performance-enhancing drugs brought a response from economist and popular author Steven Landsburg among many others. Innovation consultant Vinay Dabholkar---name not to be confused---was among some diverse commenters about mathematical intuition. A crystallographer shared thoughts with others in our related post on notation and thinking. An even greater variety piled on our ``modest proposal'' about Wikileaks.

Occasionally we hear from an artist, such as Karen Parker on memory, where she was joined by a BSD developer. Among many ongoing comments in our various posts on Cantor's Theorem, we must mention this one with many references and even a video. Coming full-circle back to crypto, we had some general fixes from Martin Albrecht, and input from Alon Rosen referencing Jonathan Katz who also commented often.

The above singles out only some commenters across fields from 2010; there are many others we are thankful for. Yes we intended this for the 21st originally, but at least now it's it timely for ``leftovers'' that hopefully have new taste the second time.

Open Problems

Can you find more examples where physical intuition gives a big shortcut over a purely formal derivation?