Are there any applications of techniques in real analysis to theoretical computer science?

Question

I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do I actually find uncountable sets as the object of study by computer scientists, and therefore leading up to the need for techniques from analysis.

Answer 1

Here are two related courses:

• Analytical methods in combinatorics and CS by Ehud Friedgut at University of Toronto (2009),
• Analytical Methods in Combinatorics and Computer-Science by Irit Dinur and Ehud Friedgut at Hebrew University (2006).

Also check Ryan O'Donnell's notes for his book:

• Analysis of Boolean Functions by Ryan O'Donnell.

and the links on the top right corner.

Answer 2

See the book Concrete Mathematics - A Foundation for Computer Science by Graham, Knuth and Patashnik. In Chapter 9 they explain the Euler-Maclaurin summation formula. This is a technique that allows you to approximate a finite sum by using integrals. In the same chapter, page 466, they use this technique to approximate the harmonic number (which appears a lot in several areas of TCS). It happened to me one time were I had to use it, and ended up solving an integral using asymptotic approximation techniques for differencial equations!

Answer 3

There is the theory of limits of dense graph sequences, developed in the work of Lovasz and B. Szegedy. It has implications for certain property testing problems on graphs. See http://www.cs.elte.hu/~lovasz/hom-stoc.pdf. Basically the idea is that they define a suitable metric on graphs and a notion of taking limits of graph sequences, and then they show that a graph property is testable if the function that maps a graph to the edit distance to the property is continuous in the metric space on graphs that was defined.

And then there is of course Flajolet and Sedgewick's magnum opus dedicated entirely to using analytic methods for asymptotic analysis of combinatorial structures, including analysis of algorithms. This is mostly generating function tricks relying on complex analysis

Answer 4

As Shir mentioned Jensen's Inequality shows up all the time. Especially in proving bounds in combinatorial problems. For example consider the following problem:

Given a family of $S_1, \ldots, S_n$ of subsets of $V = \{1, \ldots, n\}$, its intersection graph $G = (V, E)$ is defined by $\{i, j\} \in E$ if and only if $S_i \cap S_j \neq \emptyset$. Supposed that the average set size is $r$ and that the average size of the pairwise intersections is at most k. Show that $|E| \geq \frac{n}{k} \cdot \binom{r}{2}$.

Proof:

Let us count the pairs $(x, (S_i, S_j))$ such that $x \in V$ and $x \in S_i \cap S_j$. Let us first fix $(S_i, S_j)$, we see that there are at most $k$ such choices. Taking all values of $(S_i, S_j)$ as well, we have an upper bound of $k \cdot \binom{n}{2} = k \cdot |E|$. We now fix x. It is easy to see that each $x$ has $\binom{d(x)}{2}$ ways to choose $(S_i, S_j)$. By Jensen's inequality we have:

$n \cdot \binom{r}{2} = n \cdot \binom{\frac{1}{n}\sum_x d(x)}{2} \leq \sum_x \binom{d(x)}{2} \leq k \cdot |E|$.

We finally combine terms to have $\frac{n}{k} \cdot \binom{r}{2} \leq |E|$.

While this is a little more "mathy" than CS it serves to show how a tool for convex functions can be used--in combinatorial optimization, especially.

Answer 5

how about Efficient Computation with Dedekind Reals by Andrej Bauer and Paul Taylor.

Answer 6

If I recollect correctly Noga Alon's theorem on splitting necklaces uses the continuous version of the problem.

See: http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf

There is also a mention of that in the wiki page here: http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem

Answer 7

The field of Resource-bounded measure applies Lebesgue measure to complexity classes. The idea is to obtain separations among complexity classes by talking about the relative "sizes" of these sets.

Answer 8

There is a beautiful paper, Quantum One-Way Communication is Exponentially Stronger Than Classical Communication by Boaz Klartag & Oded Regev, which uses a rather large number of techniques from real analysis which are uncommon in TCS, including the Radon transform, spherical harmonics & hypercontractive inequalities on the (non-discrete) unit sphere

Answer 9

An Exponential Lower Bound for the Size of Monotone Real Circuits (1997) by Haken, Cook

Answer 10

A very common and often useful technique when approaching a problem in discrete math is embedding it in a continuous domain, as this allows a richer choice of mathematical tools to be employed. So, correcting my answer: other than the fields that real analysis will appear naturally in (graphics, signal processing and other fields that mimic or interact with the physical world), it pops up basically everywhere, and in places it hadn't - my guess is it will in the future.

Some quick examples:

1. Error correcting codes: Reed solomon codes use polynomials. Some bounds on codes involve viewing the indicator function of the code as a function from the discrete cube to the reals, thus applying Fourier transform and other techniques.
2. The probabilistic method - measure concentration theorems (an analytic tool) are used to show various properties of random graphs (e.g. chromatic number). See Alon and Spencer's book.

3. The intersection theorem (this is more related to Combinatorics, but anyway)- a graph with $v$ vertices and $e$ edges has at least $\frac {1}{61} \cdot \frac {e^3} {v^2}$ intersections. The proof involves taking a random graph, and optimizing the parameters via derivation.

4. Shamir's secret sharing uses the fact that a non-zero degree $k-1$ polynomial is uniquely defined by $k$ points (it relies on the fact that $k-1$ points provide virtually zero information).

Answer 11

I always found the connections between regular / context-free languages and function theory ((formal) power series) quite exciting: that is why the French call these language classes "rational" and "algebraic". This also indicates connections to fractal geometry. In a similar vein, e.g., finite automata might define languages on infinite words that have nice topological properties when equipped with the standard metric topology.

Another connection might be the recently developed theory of "set convolutions" that allow to speed up several algorithms similar to what is known from Fourier transforms. I assume that these are at least "inspirational similarities".