Take the 2-minute tour ×
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.

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.

share|improve this question
According to what my friends say, real analysis is needed in information theory. However, if you leave out the basics it doesn't seems to be popular in tcs (atleast to me). –  singhsumit Feb 8 '12 at 20:21
Information theory is enough for me! If you can pull out a specific example, I'll mark your response as the answer.. –  robinhoode Feb 8 '12 at 20:32
There's also signal processing, graphics and what have you. What kind of techniques are you looking for? –  Shir Feb 8 '12 at 20:50
An example (not sure if that's what you're looking for) from Information Theory: $I(X;Y)\geq 0$, that is the mutual information of two random variables $X,Y$ is non-negative. This follows directly from the concavity of the $log$ function and Jensen's inequality. (see Elements of Information Theory, by Cover and Thomas, page 28) –  Shir Feb 8 '12 at 21:24
Are you also interested in applications of complex analysis? –  Raphael Feb 9 '12 at 11:25

11 Answers 11

Here are two related courses:

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

and the links on the top right corner.

share|improve this answer
These lecture notes are great! Good post! –  Nicholas Mancuso Feb 9 '12 at 2:49

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!

share|improve this answer
Good links, but isn't this more numerical analysis? –  Huck Bennett Feb 11 '12 at 0:47
this is completely analystical. –  Marcos Villagra Feb 11 '12 at 23:49

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

share|improve this answer
It's worth mentioning that theory of graph limits and, more broadly, analysis on graphs is a very hot topic, see e.g. math.ias.edu/cga –  Marcin Kotowski Feb 9 '12 at 3:43
nice pointer @MarcinKotowski. it's nice to have laci lovasz in the area :) –  Sasho Nikolov Feb 9 '12 at 4:27

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}$.


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.

share|improve this answer
note jensens inequality seems to be highly related to erd"os sunflower lemma [the discrete version seen in circuit lower bounds] although I dont think Ive seen that proved anywhere. –  vzn Feb 9 '12 at 3:04

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

share|improve this answer
I really like reading about work in this are -- exact real number computation offers an interesting perspective on what uncountable sets are, as well as some mind-blowing algorithms. –  Neel Krishnaswami Feb 9 '12 at 2:58
... by Andrej Bauer and Paul Taylor, please. –  Andrej Bauer Feb 10 '12 at 12:10
Oh hey, I can edit the post. Fixed. –  Andrej Bauer Feb 10 '12 at 12:10
stand corrected. used the author listed on paper. maybe you should put him as the coauthor of the paper –  vzn Feb 10 '12 at 15:49
It depends on whether the theory you try to prove it in is classical or constructive. Constructively, you just use the standard diagonalization argument to show that they are uncountable. Since real numbers have to be realized by computable processes, from a classical POV the constructive proof is telling us that the halting problem is undecidable. This is part of what I meant when I said that it offers interesting perspectives on what uncountable sets are..! –  Neel Krishnaswami Feb 10 '12 at 20:09

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
Concrete examples, please? –  Marcin Kotowski Feb 9 '12 at 17:16
I added 4 examples, though I think there are so many of them, we can really go all day long. –  Shir Feb 9 '12 at 20:38

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

share|improve this answer

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

share|improve this answer
why is this a separate answer from your first? Why not just edit? –  Artem Kaznatcheev Feb 9 '12 at 6:28
different area of application –  vzn Feb 9 '12 at 15:34

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

share|improve this answer

Your Answer


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.