Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 23 down vote favorite
6

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?

share|improve this question
1  
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 at 20:05
10  
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 at 22:53
3  
@Yury that could very well be an answer. – Suresh Venkat♦ Jan 12 at 23:14

13 Answers

up vote 13 down vote accepted

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.

share|improve this answer
That's a great example, I wasn't aware of this result - thanks! – Tom Gur Jan 13 at 20:29
up vote 20 down vote

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.

share|improve this answer
Hi Suresh, what do you mean by 'analyze the complexity'? – Andy Drucker Jan 13 at 5:33
2  
Ah I miswrote. I meant "analyze the combinatorial complexity of structures" - will fix. – Suresh Venkat♦ Jan 13 at 8:08
up vote 13 down vote

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.

share|improve this answer
up vote 6 down vote

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

share|improve this answer
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ɛffE Jan 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 at 21:40
5  
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ɛffE Jan 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 at 8:47
up vote 5 down vote

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.

share|improve this answer
up vote 5 down vote

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

share|improve this answer
up vote 5 down vote

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.

share|improve this answer
up vote 5 down vote

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

share|improve this answer
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 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 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 at 1:54
up vote 4 down vote

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.

share|improve this answer
up vote 3 down vote

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

share|improve this answer
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 at 22:40
up vote 3 down vote

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.

share|improve this answer
up vote 0 down vote

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

share|improve this answer
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.