Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra.
However, being a analysist, I wonder whether there are applications of analysis into this field, or maybe ideas inspired by analysis. All I know which slightly corresponds to this is the Fourier transform on Finite groups.
Can you help me?
Flajolet and Sedgewick published the book "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html. I don't know much about that topic, but people in the field use tools from complex analysis. So far, their applications seem more on analysis of algorithms, not on computational complexity, as far as I see.
Markov Chain Monte Carlo algorithms are a useful tool for finding approximation algorithms. Some techniques for showing that these Markov chains mix are inspired by or come directly from analysis - for example see the chapter on estimating the volume of a convex body in Mark Jerrum's book on counting.
There are analytic approaches to Szemerédi's lemma, which has a cute application to combinatorial property testing. Szemerédi's Lemma for the Analyst has a randomized algorithm for finding a weakly regular partition of a graph; also see Graph Limits and Parameter Testing.
Functional analysis is playing an increasingly important role in the theory of metric embeddings. While it's difficult to enumerate all aspects of the interaction, the major theme is the use of methods from functional analysis to understand how metrics embed into normed spaces. This latter problem comes up in the sparsest cut problem, which is an important graph optimization problem.
For more information, a good source is anything by Assaf Naor.
Not about computational complexity, but interesting nonetheless
Some approaches to the semantics of infinite computation are based on metric spaces. Googling "metric space semantics" turns up plenty. One (oldish) reference on the topic is Control Flow Semantics by de Bakker and de Vink. Some recent work has been done by our very own Neel, namely Ultrametric Semantics for Reactive Programs. The area is very different from those described above, but concepts from analysis certainly find home here.
The resource bounded measure theory developed by Jack Lutz is a great area for people who have background in analysis to work on. The original paper
Almost everywhere high nonuniform complexity, Jack H. Lutz, Journal of Computer and System Sciences, 1992.
generalize the notion of Lebesgue measure into complexity classes, and many following works can be found on the internet.
Intuitively, consider the $\mathsf{P}$ vs $\mathsf{NP}$ problem. If we can define (yes we can) a measure on complexity classes with respect to a large class, say $\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$, and prove that the measure of $\mathsf{P}$ is smaller than the measure of $\mathsf{NP}$, then $\mathsf{P} \neq \mathsf{NP}$. Moreover, we can prove statement like "almost all functions in $\mathsf{ESPACE}$ need $\Omega(2^n/n)$ gates", which extends Shannon bound to a restricted class $\mathsf{ESPACE}$.
People who are working in different areas of computer science may benefit from various subfields of analysis.
To give you a concrete example, I'll describe my own case. I'm conducting research in foundations of cryptography. In this field (as well as in the computational complexity), there's a construct called the random oracle (see also this page). Its various properties are sometimes studied by exploiting tools from measure theory, which is a subfield of analysis. Such treatment can be found in this paper, as well as in several papers which cite it.
You can also take a look at Basics of Algebra and Analysis for Computer Science by Jean Gallier. It's a book in progress, and tells you what's new in the field.
I believe the best connection between mathematical analysis and complexity theory is in the Blum et al's real computation model. It is still an open problem to separate NP_R from P_R, where the two classes are defined in the real computation model, in which every real number is an entity, and one regular operation (+,-,*,/) takes one step.
