# Complex analysis in theoretical computer science

There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't think of any result in TCS that relies on complex analysis (outside of quantum computing, where complex numbers are intrinsic in the model). Does anyone has an example of a classical TCS result that uses complex analysis?

-
Great question! I would suggest it would be better to exclude results related to number theory - e.g. any use of the Riemann hypothesis - rather than quantum computing, which tends to be about finite-dimensional systems (as far as I know). –  Colin McQuillan Jan 12 '13 at 20:05
We use complex analysis in a paper “The Grothendieck Constant is Strictly Smaller than Krivine's Bound,” which (from a TCS viewpoint) gives an approximation algorithm for the problem of maximizing $\sum_{i,j} a_{ij} x_i y_j$ subject to $x_i, y_j\in \{\pm 1\}$. See ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf –  Yury Jan 12 '13 at 22:53
@Yury that could very well be an answer. –  Suresh Venkat Jan 12 '13 at 23:14

Barvinok's complex-based algorithm for approximating the permanent Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor.

Also, obviously, complex operators (and some complex analysis) are important in quantum computing.

Let me recommend also this book: Topics in performence analysis by Eitan Bachmat with a lot of great relevant issues and great other things.

-
That's a great example, I wasn't aware of this result - thanks! –  Tom Gur Jan 13 '13 at 20:29

It's not a single problem, but the entire field of analytic combinatorics (see the book by Flajolet and Sedgewick) explores how to analyze the combinatorial complexity of counting structures (or even algorithm running times) by writing down an appropriate generating function and analyzing the structure of the complex solutions.

-
Hi Suresh, what do you mean by 'analyze the complexity'? –  Andy Drucker Jan 13 '13 at 5:33
Ah I miswrote. I meant "analyze the combinatorial complexity of structures" - will fix. –  Suresh Venkat Jan 13 '13 at 8:08

Jon Kelner won the STOC Best Student Paper Award in 2004 for his paper "Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus"

I'll just quote from the abstract:

As our main technical lemma, we prove an O(g/n) bound on the second smallest eigenvalue of the Laplacian of such graphs and show that this is tight, thereby resolving a conjecture of Spielman and Teng. While this lemma is essentially combinatorial in nature, its proof comes from continuous mathematics, drawing on the theory of circle packings and the geometry of compact Riemann surfaces.

The use of complex analysis (and other "continuous" math) to attack "traditional" graph separator problems was memorable and is the main reason this paper stuck in my head even though it is completely unrelated to my research.

-

I guess that you might be more interested in complex analysis used directly in the proof. However, here are two examples from a graduate level Algorithms class I am currently attending:

a) Fast Fourier Transform, for example used in polynomial multiplication. Although the implementation can be done with modulo arithmetic or floating point (and some arithmetic analysis), the proof is best understood in terms of complex numbers and their roots of unity. I have not delved into the subject, but I am aware that FFT has a wide range of applications.

b) In general, equipping the RAM model with the ability to handle complex numbers in constant time (the real and imaginary parts still have finite precision) allows one to cleverly encode problems and exploit properties of the complex numbers that might reveal a solution (see also the comments why this won't allow you to be faster).

-
Do you have an example of the second observation? It's trivial to add a "complex O(log n)-bit integer" class to the standard RAM with constant-time operations. Or by "faster", do you mean "faster by a factor of 2"? –  JɛﬀE Jan 13 '13 at 20:20
This was an exercise from the lecture: "Assume you are dealing with an extended RAM that can compute with complex numbers at unit cost per multiplication, division, addition, and subtraction. In addition it can also compute the absolute value |c| of a complex number c in unit time. Moreover it “knows” the complex constants 0, 1, and i. Show that given a positive integer n on such an extended RAM the number n! can be computed in $O( \sqrt{n} \log ^{2} n)$time. The solution uses polynomial multiplication, from what I know this is faster than the standard RAM model. –  chazisop Jan 13 '13 at 21:40
The proposed algorithm requires constant-time infinite-precision real arithmetic. (You can't compute a $\Omega(n\log n)$-bit integer in $o(n)$ time using a machine with $O(\log n)$-bit words, because you wouldn't even have time to write down the output!) The question is asking you to add square roots to the real RAM model, not complex numbers per se. –  JɛﬀE Jan 13 '13 at 23:16
Thanks for the comment, it is very enlightening. I think I should update my answer to the part of only cleverly encoding a problem with complex numbers, i.e. to see a solution you would miss otherwise. –  chazisop Jan 14 '13 at 8:47

Perhaps this application is somewhat between TCS and Disc math, but I was slightly surprised when I read the paper "On the bent Boolean functions which are symmetric" by Petr Savicky (http://www2.cs.cas.cz/~savicky/papers/symmetric.ps). The theorems are only concerning Boolean functions, however one of the proofs uses complex numbers.

-

We use Cauchy's Residue Theorem from complex analysis as the main technical tool in our paper "Approximating Linear Threshold Predicates".

-

The Koebe-Andreev-Thurston circle packing theorem is originated in Riemann-mapping theorem and has various algorithmic aspects. For examle, it allos a proof of the Lipton-Tarjan seperor theorem for planar graphs.

-

Fresh from the oven:

A Polynomial Time Algorithm for Lossy Population Recovery By: Ankur Moitra, Michael Saks

Quoting from the paper: "Here we will prove the uncertainty principle stated in the previous section using tools from complex analysis. Perhaps one of the most useful theorems in understanding the rate of growth of holomorphic functions in the complex plane is Hadamard’s Three Circle Theorem..."

-
Let me give a quick sketch of how the Three Circle Theorem is used in this paper. In order to minimize a quantity $\sigma$ that satisfies some linear constraints, they look at the dual of this LP. Viewing the dual variables as coefficients of a polynomial, this becomes equivalent to maximizing $p(0) - \epsilon \|p\|_1$ over all degree $n$ polys $p$ satisfying $\|q\|_1 \leq 1$ where $q$ is $p$ composed with an affine transformation and $\|\cdot\|_1$ denotes the sum of abs value of coefficients. –  arnab Feb 13 '13 at 1:51
(contd.) Now, the beautiful observation is that $\|p\|_1 \geq \|p\|_{sup}^{D_1}$ where $D_1$ is the unit disc in the complex plane of radius 1. If we use this relaxation, the problem boils down to maximizing $p(0) - \|p\|_{sup}^{D_1}$ subject to $p$ being bounded by $1$ over a smaller disc inside $D_1$. Making a coordinate transformation, we find ourselves in the setting of the Three Circle theorem: a holomorphic function is bounded on points in two concentric circles, bounding the function on any circle of intermediate radius. –  arnab Feb 13 '13 at 1:51
(contd.) For the problem, this implies that $\|p\|_{sup}^{D_1} \geq |p(0)|^{\Omega(1)}$ if $p$ is bounded by $1$ over a smaller disc inside $D_1$. (Thanks to a wonderful talk by Mike Saks explaining the paper.) –  arnab Feb 13 '13 at 1:54

There is use of complex numbers and analysis in a recent paper by Naor, Regev and Vidick, yielding results in approximation algorithms for NP-hard optimization problems: http://arxiv.org/abs/1210.7656

-
Yet another paper that makes use of random roots of unity is Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting Arbitrary Subgraphs in Data Streams. ICALP 2012. –  Jelani Nelson Feb 12 '13 at 22:40

In Section A.4 of this paper we use complex analysis, which leads us to a derandomization of Indyk's algorithm for $\ell_p$ estimation in data streams ($0 < p < 2$) that provides optimal space guarantees:

Daniel M. Kane, Jelani Nelson, David P. Woodruff. On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA 2010.

You can get away with writing a proof that doesn't mention complex analysis explicitly (see the first bullet in the "notes" section for that paper on my webpage), but even that proof has complex analysis lurking under the covers.

-

Recently Vishnoi gave an algorithm which finds TSP tours of length at most $n + O(n/\sqrt{k})$ in a $k$-regular simple graphs (talk & blog). The analysis crucially uses the van der Waerden conjecture (aka the Egorychev-Falikman theorem): the permanent of any doubly stochastic $n \times n$ matrix is at least $n!/n^n$. Egorychev and Falikman's proofs used deep results in convex geometry (in particular the Alexandrov-Fenchel inequality). On the other hand, a recent proof by Gurvits uses only elementary complex analysis and is quite a gem (nice presentation by Laurent and Schrijver in the MAA Monthly). Leaving the real line for the complex plane seems essential to Gurvits's proof and simplifies matters a lot.

-

there is some research showing undecidability associated with various aspects of computation of the Mandelbrot set, a famous, prototype fractal which is computed using complex numbers and counting the number of iterations associated with the equation $z \leftarrow z^2 + c$ to reach an unbounded increasing sequence. a detailed account and survey can be found in [1], which appeared in a physics journal but with heavy use of TCS concepts eg Turing Machines etc. an early ref [2] by Blum concludes that the Mandelbrot set is not decidable.

[1] Inaccessibility and undecidability in computation, geometry, and dynamical systems Asaki Saito, Kunihiko Kaneko

[2] A theory of computation and complexity over the real numbers Lenore Blum, 1990

-

Nister, Hartley, and Stewenius used Galois theory to prove the optimality of certain algorithms in computer vision. While not specifically an instance of Complex Analysis, this work is intimately associated with $\mathbb{C}$ because of the fundamental theorem of algebra.

-