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.
$\begingroup$
$\endgroup$
7
-
$\begingroup$ 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). $\endgroup$– singhsumitCommented Feb 8, 2012 at 20:21
-
$\begingroup$ Information theory is enough for me! If you can pull out a specific example, I'll mark your response as the answer.. $\endgroup$– robinhoodeCommented Feb 8, 2012 at 20:32
-
1$\begingroup$ There's also signal processing, graphics and what have you. What kind of techniques are you looking for? $\endgroup$– ShirCommented Feb 8, 2012 at 20:50
-
4$\begingroup$ 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) $\endgroup$– ShirCommented Feb 8, 2012 at 21:24
-
$\begingroup$ Are you also interested in applications of complex analysis? $\endgroup$– RaphaelCommented Feb 9, 2012 at 11:25
|
Show 2 more comments
11 Answers
$\begingroup$
$\endgroup$
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.
-
1$\begingroup$ These lecture notes are great! Good post! $\endgroup$ Commented Feb 9, 2012 at 2:49
$\begingroup$
$\endgroup$
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!
-
$\begingroup$ Good links, but isn't this more numerical analysis? $\endgroup$ Commented Feb 11, 2012 at 0:47
-
$\begingroup$ this is completely analystical. $\endgroup$ Commented Feb 11, 2012 at 23:49
$\begingroup$
$\endgroup$
2
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
-
2$\begingroup$ 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 $\endgroup$ Commented Feb 9, 2012 at 3:43
-
$\begingroup$ nice pointer @MarcinKotowski. it's nice to have laci lovasz in the area :) $\endgroup$ Commented Feb 9, 2012 at 4:27
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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. $\endgroup$– vznCommented Feb 9, 2012 at 3:04
$\begingroup$
$\endgroup$
6
how about Efficient Computation with Dedekind Reals by Andrej Bauer and Paul Taylor.
-
2$\begingroup$ 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. $\endgroup$ Commented Feb 9, 2012 at 2:58
-
$\begingroup$ ... by Andrej Bauer and Paul Taylor, please. $\endgroup$ Commented Feb 10, 2012 at 12:10
-
2$\begingroup$ Oh hey, I can edit the post. Fixed. $\endgroup$ Commented Feb 10, 2012 at 12:10
-
$\begingroup$ stand corrected. used the author listed on paper. maybe you should put him as the coauthor of the paper $\endgroup$– vznCommented Feb 10, 2012 at 15:49
-
1$\begingroup$ 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..! $\endgroup$ Commented Feb 10, 2012 at 20:09
$\begingroup$
$\endgroup$
2
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:
- 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.
- 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.
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.
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).
-
$\begingroup$ Concrete examples, please? $\endgroup$ Commented Feb 9, 2012 at 17:16
-
$\begingroup$ I added 4 examples, though I think there are so many of them, we can really go all day long. $\endgroup$– ShirCommented Feb 9, 2012 at 20:38
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ why is this a separate answer from your first? Why not just edit? $\endgroup$ Commented Feb 9, 2012 at 6:28
-
$\begingroup$
$\endgroup$
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".