Relationship between Random Graph Theory and TCS

Question

Sorry for this large and vague question. I am a new grad probability student recently interested in random graph theory(RG). I heard from someone in math department that RG has close relationship to TCS, but he don't know what exactly is the relation. I am currently thinking about turning to a theoretical computer scientist in CS department to read something relative to RG, but since I don't know where RG is used in studying TCS, which is also a quite large field, I don't know who I should ask.

If possible, could you please explain a little bit about how RG is used in TCS? Like, in studying what problem, what link can be made between the original problem and random graph models, and what properties TCSers will look into for that random graph?

Answer 1

There are interesting open algorithmic problems in random graphs, which might even lead to nontrivial results about complexity classes.

For the sake of an example, consider the simplest random graph model: take $n$ vertices, and put in each edge randomly and independently with probability 1/2. This model is often denoted by $G(n,1/2)$. It is a known result from the theory of random graphs that the size of a maximum clique in $G(n,1/2)$ is asymptotically $2\log_2 n$, and the actual size is strongly concentrated on merely two neighboring integers.

That is, the clique number of $G(n,1/2)$ is (asymptotically) almost exactly determined. But how hard is it to find such a clique? It is unlikely to be NP-hard, because there are only $n^{O(\log n)}$ many subsets of this size, so we can do an exhaustive search in $n^{O(\log n)}$ time, which is still a sub-exponential algorithm. At the same time, no polynomial-time algorithm is known, either.

However, good constant factor approximation is possible: about half of the optimum, i.e. $\log_2 n$, can be achieved by a known polynomial-time algorithm, with high probability. On the other hand, for any fixed $\epsilon>0$, no polynomial-time algorithm is known that would find a clique of size at least $(1+\epsilon)\log_2 n$ with high probability in $G(n,1/2)$.

In general, I could imagine as an interesting research subject, the study of how various random graph algorithms could be reduced to each other. Are there such problems that could be identified as complete for certain appropriately defined classes?

Answer 2

Phase transitions in NP-complete (and other) problems. See this nice recent survey/intro by Cris Moore: https://arxiv.org/abs/1702.00467.

Many constructions in TCS (eg expanders come to mind) can be shown to exist by the probabilistic method. Getting efficient deterministic constructions to do the same is often challenging, interesting, and useful, but the proof of existence is a good start.

Answer 3

One very natural application of random graph theory in computer science comes from the analysis of cuckoo hashing. In the most basic form of cuckoo hashing (with one key per cell and two possible cells per key) the state of a cuckoo hash table can be described as a random graph with a vertex for each cell and an edge for each key. The ability to place all keys into their cells hinges on the likelihood that the resulting graph has no connected components with more than one cycle. More detailed analysis of cuckoo hashing and its variants extend to more complex questions about random graphs and random hypergraphs.

Answer 4

One famous connection of random graphs to TCS is network connectivity.

Random graphs such as the Erdős–Rényi model - https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model have the property that they are “well connected” - with high probability, most subsets of vertices have many edges across them.

See here: https://www.math.cmu.edu/~af1p/BOOK.pdf (p 69) for more precise information.

Answer 5

Another interesting connection between random graphs and TCS can be found in the concept of de-randomization. Generally, de-randomization means the approximation of truly random structures by deterministic ones.

In TCS these random structures are often random bit sequences, which play an important role in randomized algorithms. There is much interest in constructing pseudo-random bit generators, which may lead to the de-randomization of randomized complexity classes, such as BPP, RP, ZPP. It is a major open question whether the complete de-randomization of these complexity classes is possible or not.

In random graph theory there is also significant interest in finding deterministic graph constructions that resemble truly random graphs, see the paper Pseudo-random graphs by Krivelevich and Sudakov.

It seems that graphs have more structure than bit sequences. As a result, one can perhaps prove nicer results about pseudo-random graphs than about pseudo-random bit sequences. This may be only my personal taste, but if you read the above referenced paper, you might arrive at a similar conclusion.

It seems to me that TCS could still benefit from pseudo-random graph related results in the area of de-randomization. In the other direction, interesting pseudo-random graph constructions may arise from pseudo-random bit generators used in TCS, such as the Nisan-Wigderson generator.