An exchange of expertise and gifts

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.

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 ${1,\dots,m^{2}}$ and yet can be evaluated in time order ${m \log m}$. The point of this is that the polynomial can be evaluated in ${T}$ arithmetic steps, yet has almost ${T^{2}}$ number of roots. This idea has been used to create an early factorization algorithm that runs in time ${N^{1/4}}$: note that naively trying all numbers less than ${\sqrt N}$ is much worse than this method.

More recently the above idea has been used to break a cryptosystem 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 ${x}$ and ${y}$ in time polynomial in the number ${d}$ 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 ${x}$ by a small amount less than ${\Delta}$?

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

$\displaystyle z-1, z+1, z-2, z+2, \dots$

The cool insight of Yuanmi Chen and 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 ${\Delta}$ but ${\sqrt {\Delta}}$. Here is a slightly different statement:the problem the problem as stated on their slides:

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 this well-known result:

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

The method is based on the FFT. Consider the polynomial

$\displaystyle f(x) = (x+1)(x+2) \cdots (x+m).$

This can be evaluated at any ${m}$ points in order ${m\log m}$ time. Now look at the polynomial ${g(x)}$ defined by

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

Clearly ${f(x)}$ can be evaluated in order ${m\log m}$ steps at the points ${0,m,2m,\dots,m^{2}}$ in time order ${m \log m}$. But then multiplying them together yields ${g(x)}$.

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 ${\mathsf{PP}}$ is closed under Boolean operations, via its equality to a quantum-inspired class ${\mathsf{PostBQP}}$ 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 fits 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 in commented contributions, 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 comment from MITRE Corp. software engineer Robert Eachus, who was writing about Patriot missiles over two decades ago, and continued about algorithms here. Our post 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 post for Nov. 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?

1. November 26, 2012 3:01 am

You are staing at some distance from the shore, and there is small island in the sea. You can run with speed v1 on the land, and seem with speed v2 on the sea. Find the fastest path to the island. The physical solution takes 1 line.

November 26, 2012 5:34 am

Question: Given a triangle (with angles maximum total of hanging rope => minimal gravitational potential energy => equilibrium => vector sum of forces on the tie is zero, where all the forces’ magnitudes are equal => 120 degrees between ropes.

November 26, 2012 5:35 am

My comment got corrupted for some reason.

3. November 27, 2012 10:41 pm

I believe the statement of Theorem 1 is off by a log(d) factor (at least). That is, the fast multipoint evaluation results I am aware of show that it can be done in O(M(d)log(d)), where M(d) is the complexity of polynomial multiplication, which using FFTs can be shown to be O(d log(d)) over the complex numbers, and O(d log(d) loglog(d)) in general. I believe nothing better is known.

4. November 28, 2012 5:44 am

One of the powerful tools in physics is the dimensionality analysis. Many physical laws can be just written down using units relationship. In hard questions, like P vs NP, I have filling (reading this blog) that the main idea is missing – there is no intuition! In one of the blogs it is written – what we know is trivial, and what we do not know is a Field medal. Below is the rough intuition, I’m not capable of doing detailed analyses technically correct (would be glad if someone can lead me, although I believe that mathematics is sparse, and mathematicians are so busy with their problems, that they are rarely comment on other works, until it comes to proof check), so save your time and just skip the rest of the comment, if you think crackpot cannot have (any/interesting) ideas. I apologize if it takes more than 5 minutes.

Many NP-complete problems can be encoded in the system of polynomial equations. Some examples are in the introduction here. Basically the idea is to encode binary variables in the equations $f_k= x_k^2-1= 0$, or $f_k = x_k^2-x_k=0$, and add one or more quadratic equations ($g_k=0$) encoding decision problem. Since the system can have exponentially many solutions finding them is hard. On the other hand, we can try to figure out if the system has solutions at all. One of the approaches is to use Nulstellensatz certificate, e.g. find the set of polynomials $P_k, P'_k \in \mathbb{K}[x_1,...x_n]$, where $\mathbb{k}$ is an algebraically closed field, for example $\mathbb{C}$ such that the following equation is satisfied $1= \sum_k P_k f_k +\sum_m P'_m g_m$. The problem with this approach is that one need very high degree polynomials $P_k, P'_k$ and the certificate has exponentially many monomials. The intuition here is following. The problem is hard since all variables are influencing other variables, otherwise the problem can be split into independent subproblems. Since all off them are important the term with monomial $x_1 ... x_n$ has to appear in the certificate. That lead to the certificate of degree $n$, which has too many monomials. There is no clear way of selecting right monomials, and we need to use all of them. So the problem is that by increasing the degree of certificate the “mixing” of variables is too slow!!! And we need a way to speed-up mixing of the variables.

Here it is. We do usual trick of linearizing quadratic equations in terms of quadratic monomials (for 3-SAT we need cubic monomials), e.g. $y_{x_k,x_m}= x_k x_m,\ k, m = 0..n,\ x_0=1$. This linear system has $\approx n^2$ linear variables (monomials), and $\approx n$ equations, e.g. highly under-complete. The solution of this (homogenised) linear system is $\approx n^2$ dimensional projective space. The original system has a solution iff there is a point $c \in \mathbb{C}^{\approx n^2}$ in this projective space such that all corresponding equations on $y_{x_k,x_m} = y_{x_0,x_k} y_{x_0, x_m}, y_{0,0}=1$ are satisfied. This are quadratic equations on $c$, so we can write all the quadratic in $c$ constraints. For example, $y_{x_k,x_m} y_{x_p,x_q}= y_{x_k,x_p} y_{x_m,x_q}= y_{x_k,x_q} y_{x_p,x_m}$ (So we using tautologies, instead of deriving them as done in propositional proof systems). Therefore, we have $\approx \frac{2}{3} n^2$ quadratic equations with $\approx n^2$ indeterminates $c_k$. Now we have equivalent, in terms of satisfiability, system of quadratic equations with $O(n^4)$ equations and $O(n^2)$ variables, and before we had $O(n)$ quadratic equations with $O(n)$ variables. In other words, now we have $O(1) > C$ equations in terms of the number of monomials, and before we had $o(1)$ equations in terms of monomials.

Now we can write Nulstellensatz certificate for the new system. The number of independent coefficients grow faster then the number of monomials with increasing the certificate degree. Therefore, there is a fixed (independent of $n$) degree of certificate that depend on $C$. If the above arguments are correct, it would be possible to check whether NP-complete problem has a solution in polynomial time, with all consequences.