32
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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). $\endgroup$
    – Colin McQuillan
    Commented Jan 12, 2013 at 20:05
  • 12
    $\begingroup$ 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 $\endgroup$
    – Yury
    Commented Jan 12, 2013 at 22:53
  • 4
    $\begingroup$ @Yury that could very well be an answer. $\endgroup$
    – Suresh Venkat
    Commented Jan 12, 2013 at 23:14

15 Answers 15

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's a great example, I wasn't aware of this result - thanks! $\endgroup$
    – user887
    Commented Jan 13, 2013 at 20:29
27
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Hi Suresh, what do you mean by 'analyze the complexity'? $\endgroup$
    – Andy Drucker
    Commented Jan 13, 2013 at 5:33
  • 2
    $\begingroup$ Ah I miswrote. I meant "analyze the combinatorial complexity of structures" - will fix. $\endgroup$
    – Suresh Venkat
    Commented Jan 13, 2013 at 8:08
15
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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"? $\endgroup$
    – Jeffε
    Commented Jan 13, 2013 at 20:20
  • $\begingroup$ 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. $\endgroup$
    – chazisop
    Commented Jan 13, 2013 at 21:40
  • 6
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Commented Jan 13, 2013 at 23:16
  • $\begingroup$ 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. $\endgroup$
    – chazisop
    Commented Jan 14, 2013 at 8:47
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – arnab
    Commented Feb 13, 2013 at 1:51
  • $\begingroup$ (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. $\endgroup$
    – arnab
    Commented Feb 13, 2013 at 1:51
  • $\begingroup$ (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.) $\endgroup$
    – arnab
    Commented Feb 13, 2013 at 1:54
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Jelani Nelson
    Commented Feb 12, 2013 at 22:40
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

The topic of trace reconstruction for the deletion channel relies crucially on complex analysis. (In reference [6] cited below, these methods are also used by Z. Chase to improve the state of the art on the word separation problem in automata theory.)

[1] Nazarov, Fedor and Peres, Yuval
Trace reconstruction with exp(O(n^{1/3})) samples. STOC'17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 1042–1046, ACM, New York, 2017 See https://dl.acm.org/doi/pdf/10.1145/3055399.3055494 or https://arxiv.org/pdf/1612.03599.pdf

Corresponding video and slides:

https://www.youtube.com/watch?v=4wxpFb4BKn4

https://yuval-peres-presentations.com/trace-reconstruction-for-deletion-channels/

The key fact used in the proof is a lower bound on the maximum of a complex polynomial on a small arc of the unit circle.

The same result was obtained independently in

[2] De, Anindya, Ryan O'Donnell, and Rocco A. Servedio. "Optimal mean-based algorithms for trace reconstruction." Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 2017.

Later refinements also use complex analysis heavily:

[3] Peres, Yuval, and Alex Zhai. "Average-case reconstruction for the deletion channel: subpolynomially many traces suffice." In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 228-239. IEEE, 2017.

[4] Holden, Nina, Robin Pemantle, and Yuval Peres. "Subpolynomial trace reconstruction for random strings{and arbitrary deletion probability." In Conference On Learning Theory, pp. 1799-1840. PMLR, 2018.

[5] Hartung, Lisa, Nina Holden, and Yuval Peres. "Trace reconstruction with varying deletion probabilities." In 2018 Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 54-61. Society for Industrial and Applied Mathematics, 2018.

[6] Chase, Z., 2021, June. Separating words and trace reconstruction. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 21-31).

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

[Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems][1]

From abstract: In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. [1]: https://arxiv.org/abs/1812.07769

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.