<p>Here are two related courses:</p>

<ul>
<li><a href="http://www.ma.huji.ac.il/~ehudf/courses/anal09/anal.html">Analytical methods in combinatorics and CS</a> by Ehud Friedgut at University of Toronto (2009),</li>
<li><a href="http://www.cs.huji.ac.il/~analyt/">Analytical Methods in Combinatorics and Computer-Science</a> by Irit Dinur and Ehud Friedgut at Hebrew University (2006).</li>
</ul>

<p>Also check Ryan O'Donnell's notes for his book:</p>

<ul>
<li><a href="http://www.contrib.andrew.cmu.edu/~ryanod/">Analysis of Boolean Functions</a> by Ryan O'Donnell.</li>
</ul>

<p>and the links on the top right corner.</p>

CC BY-SA 3.0
2012-02-09T02:49:08.123Z
These lecture notes are great! Good post!
Nicholas Mancuso
CC BY-SA 3.0
2012-02-09T02:18:06.413Z
2012-02-09T03:14:24.510Z
2012-02-09T03:14:24.510Z
Kaveh
<p>See the book <a href="http://rads.stackoverflow.com/amzn/click/0201558025">Concrete Mathematics - A Foundation for Computer Science</a> by Graham, Knuth and Patashnik. In Chapter 9 they explain the <a href="http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula">Euler-Maclaurin summation formula</a>. 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 <a href="http://en.wikipedia.org/wiki/Harmonic_number">harmonic number</a> (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 <a href="http://books.google.co.jp/books/about/Asymptotic_approximations_of_integrals.html?id=KQHPHPZs8k4C&amp;redir_esc=y">asymptotic approximation techniques</a> for differencial equations!</p>

CC BY-SA 3.0
2012-02-11T00:47:18.533Z
Good links, but isn't this more numerical analysis?
Huck Bennett
CC BY-SA 3.0
2012-02-11T23:49:34.700Z
this is completely analystical.
Marcos Villagra
CC BY-SA 3.0
2012-02-09T03:19:32.333Z
2012-02-09T03:19:32.333Z
Marcos Villagra
<p>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 <a href="http://www.cs.elte.hu/~lovasz/hom-stoc.pdf">http://www.cs.elte.hu/~lovasz/hom-stoc.pdf</a>. 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. </p>

<p>And then there is of course Flajolet and Sedgewick's <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf">magnum opus</a> 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</p>

CC BY-SA 3.0
2012-02-09T03:43:14.797Z
It's worth mentioning that theory of graph limits and, more broadly, analysis on graphs is a very hot topic, see e.g. http://www.math.ias.edu/cga
Marcin Kotowski
CC BY-SA 3.0
2012-02-09T04:27:06.723Z
nice pointer @MarcinKotowski. it's nice to have laci lovasz in the area :)
Sasho Nikolov
CC BY-SA 3.0
2012-02-09T03:12:52.323Z
2012-02-09T03:38:24.850Z
2012-02-09T03:38:24.850Z
Sasho Nikolov
<p>As Shir mentioned Jensen's Inequality shows up all the time. Especially in proving bounds in combinatorial problems. For example consider the following problem:</p>

<p>Given a family of $S_1, \ldots, S_n$ of subsets of $V = \{1, \ldots, n\}$, its <em>intersection</em> 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}$.</p>

<p><strong>Proof:</strong></p>

<p>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:</p>

<p>$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|$. </p>

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

<p>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.</p>

CC BY-SA 3.0
2012-02-09T03:04:04.987Z
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
CC BY-SA 3.0
2012-02-08T22:36:28.883Z
2012-02-08T23:11:48.997Z
2012-02-08T23:11:48.997Z
Nicholas Mancuso
<p>how about <a href="http://math.andrej.com/wp-content/uploads/2008/08/abstract-cca2008.pdf" rel="nofollow">Efficient Computation with Dedekind Reals</a> by Andrej Bauer and Paul Taylor. </p>

CC BY-SA 3.0
2012-02-09T02:58:05.803Z
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
CC BY-SA 3.0
2012-02-10T12:10:25.103Z
... by Andrej Bauer **and Paul Taylor**, please.
Andrej Bauer
CC BY-SA 3.0
2012-02-10T12:10:44.277Z
Oh hey, I can edit the post. Fixed.
Andrej Bauer
CC BY-SA 3.0
2012-02-10T15:49:01.020Z
stand corrected. used the author listed on paper. maybe you should put him as the coauthor of the paper
vzn
CC BY-SA 3.0
2012-02-10T16:06:02.060Z
@NeelKrishnaswami Aren't the set of computable real numbers countable?
robinhoode
CC BY-SA 3.0
2012-02-10T20:09:18.240Z
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
CC BY-SA 3.0
2012-02-09T02:34:42.167Z
2012-02-10T12:10:52.467Z
2012-02-10T12:10:52.467Z
vzn
<p>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.</p>

<p>Some quick examples:</p>

<ol>
<li>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.</li>
<li>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.</li>
<li><p>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.</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing" rel="nofollow">Shamir's secret sharing</a> 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).</p></li>
</ol>

CC BY-SA 3.0
2012-02-09T17:16:33.670Z
Concrete examples, please?
Marcin Kotowski
CC BY-SA 3.0
2012-02-09T20:38:27.493Z
I added 4 examples, though I think there are so many of them, we can really go all day long.
Shir
CC BY-SA 3.0
2012-02-09T10:36:58.620Z
2012-02-09T20:36:52.800Z
2012-02-09T20:36:52.800Z
Shir
<p>The field of <a href="http://arxiv.org/abs/1101.5455" rel="nofollow">Resource-bounded measure</a> applies Lebesgue measure to complexity classes. The idea is to obtain separations among complexity classes by talking about the relative "sizes" of these sets.</p>

CC BY-SA 3.0
2012-02-09T16:48:14.817Z
2012-02-09T16:48:14.817Z
mikero
<p>If I recollect correctly Noga Alon's theorem on splitting necklaces uses the continuous version of the problem.</p>

<p>See: <a href="http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf" rel="nofollow">http://www.cs.tau.ac.il/~nogaa/PDFS/nocon.pdf</a></p>

<p>There is also a mention of that in the wiki page here: <a href="http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Hobby%E2%80%93Rice_theorem</a></p>

CC BY-SA 3.0
2012-02-08T23:29:19.157Z
2012-02-08T23:29:19.157Z
Aryabhata
<p>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.</p>

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

CC BY-SA 3.0
2012-02-10T16:43:10.547Z
2012-02-10T16:43:10.547Z
Henning Fernau
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.3932" rel="nofollow">An Exponential Lower Bound for the Size of Monotone Real Circuits (1997)</a> by Haken, Cook</p>

CC BY-SA 3.0
2012-02-09T06:28:20.630Z
why is this a separate answer from your first? Why not just edit?
Artem Kaznatcheev
CC BY-SA 3.0
2012-02-09T15:34:46.270Z
different area of application
vzn
CC BY-SA 3.0
2012-02-09T05:43:51.277Z
2012-02-09T05:43:51.277Z
vzn
<p>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.</p>

CC BY-SA 3.0
2012-02-08T20:21:47.240Z
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
CC BY-SA 3.0
2012-02-08T20:32:30.453Z
Information theory is enough for me! If you can pull out a specific example, I'll mark your response as the answer..
robinhoode
CC BY-SA 3.0
2012-02-08T20:50:18.840Z
There's also signal processing, graphics and what have you. What kind of techniques are you looking for?
Shir
CC BY-SA 3.0
2012-02-08T21:24:23.853Z
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
CC BY-SA 3.0
2012-02-09T11:25:38.323Z
Are you also interested in applications of complex analysis?
Raphael
CC BY-SA 3.0
2012-02-12T06:46:09.463Z
Real analysis is extensively used in analyzing of the performance of LDPC codes under message passing decoding (density evolution, EXIT charts, etc). Check the "Modern Coding Theory" book by Rüdiger Urbanke and Tom Richardson  
ipg.epfl.ch/lib/exe/fetch.php?media=en:publications:mct-new.pdf
Dimitris
CC BY-SA 3.0
2012-02-12T06:57:42.817Z
More:
1) Spectra of random matrices (google: eigenvalues MIMO channels)
2) Approximation guarantees for convex approximations (google: low rank matrix completion)
3) Machine learning and graphical models (some examples can be found in here: http://www.cs.berkeley.edu/~wainwrig/Pubs/publist.html)

it actually never ends.. :)
Dimitris
<co.combinatorics><big-picture>
Are there any applications of techniques in real analysis to theoretical computer science?
robinhoode
# Are there any applications of techniques in real analysis to theoretical computer science?

(Asked by: username_0 on 2012-02-08)

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.

**Tags:** co.combinatorics, big-picture
> **Comments:**
> **username_1**: 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).  
> **username_0**: Information theory is enough for me! If you can pull out a specific example, I'll mark your response as the answer..  
> **username_2**: There's also signal processing, graphics and what have you. What kind of techniques are you looking for?  
> **username_2**: 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)  
> **username_3**: Are you also interested in applications of complex analysis?  
> **username_4**: Real analysis is extensively used in analyzing of the performance of LDPC codes under message passing decoding (density evolution, EXIT charts, etc). Check the "Modern Coding Theory" book by Rüdiger Urbanke and Tom Richardson   ipg.epfl.ch/lib/exe/fetch.php?media=en:publications:mct-new.pdf  
> **username_4**: More: 1) Spectra of random matrices (google: eigenvalues MIMO channels) 2) Approximation guarantees for convex approximations (google: low rank matrix completion) 3) Machine learning and graphical models (some examples can be found in here: http://www.cs.berkeley.edu/~wainwrig/Pubs/publist.html)  it actually never ends.. :)  

---

## 10 answers

### Answer by username_5 on 2012-02-09. Score: 18

Here are two related courses:

* [Analytical methods in combinatorics and CS](http://www.ma.huji.ac.il/~ehudf/courses/anal09/anal.html) by Ehud Friedgut at University of Toronto (2009),
* [Analytical Methods in Combinatorics and Computer-Science](http://www.cs.huji.ac.il/~analyt/) by Irit Dinur and Ehud Friedgut at Hebrew University (2006).

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

* [Analysis of Boolean Functions](http://www.contrib.andrew.cmu.edu/~ryanod/) by Ryan O'Donnell.

and the links on the top right corner.

> **Comments:**
> **username_6**: These lecture notes are great! Good post!  

---

### Answer by username_7 on 2012-02-09. Score: 11

See the book [Concrete Mathematics - A Foundation for Computer Science](http://rads.stackoverflow.com/amzn/click/0201558025) by Graham, Knuth and Patashnik. In Chapter 9 they explain the [Euler-Maclaurin summation formula](http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_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](http://en.wikipedia.org/wiki/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](http://books.google.co.jp/books/about/Asymptotic_approximations_of_integrals.html?id=KQHPHPZs8k4C&redir_esc=y) for differencial equations!

> **Comments:**
> **username_8**: Good links, but isn't this more numerical analysis?  
> **username_7**: this is completely analystical.  

---

### Answer by username_9 on 2012-02-09. Score: 9

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](http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf) 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

> **Comments:**
> **username_10**: It's worth mentioning that theory of graph limits and, more broadly, analysis on graphs is a very hot topic, see e.g. http://www.math.ias.edu/cga  
> **username_9**: nice pointer @MarcinKotowski. it's nice to have laci lovasz in the area :)  

---

### Answer by username_6 on 2012-02-08. Score: 8

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.

> **Comments:**
> **username_11**: 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.  

---

### Answer by username_11 on 2012-02-09. Score: 7

how about [Efficient Computation with Dedekind Reals](http://math.andrej.com/wp-content/uploads/2008/08/abstract-cca2008.pdf) by Andrej Bauer and Paul Taylor.

> **Comments:**
> **username_12**: 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.  
> **username_13**: ... by Andrej Bauer **and Paul Taylor**, please.  
> **username_13**: Oh hey, I can edit the post. Fixed.  
> **username_11**: stand corrected. used the author listed on paper. maybe you should put him as the coauthor of the paper  
> **username_0**: @NeelKrishnaswami Aren't the set of computable real numbers countable?  
> **username_12**: 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..!  

---

### Answer by username_2 on 2012-02-09. Score: 3

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](http://en.wikipedia.org/wiki/Shamir%27s_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).

> **Comments:**
> **username_10**: Concrete examples, please?  
> **username_2**: I added 4 examples, though I think there are so many of them, we can really go all day long.  

---

### Answer by username_14 on 2012-02-09. Score: 2

The field of [Resource-bounded measure](http://arxiv.org/abs/1101.5455) 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 by username_15 on 2012-02-08. Score: 2

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 by username_16 on 2012-02-10. Score: 1

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


---

### Answer by username_11 on 2012-02-09. Score: 1

[An Exponential Lower Bound for the Size of Monotone Real Circuits (1997)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.3932) by Haken, Cook

> **Comments:**
> **username_17**: why is this a separate answer from your first? Why not just edit?  
> **username_11**: different area of application  

---

