# Tag Info

5

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

4

I'm not sure if claims about optimal constants are meaningful when trying to optimize all 3; often it is the case that one can be made better at the expense of another. One way to simplify the issue is to look at the expectation, so you only have to deal with one constant. This is the approach taken by Devroye-Lugosi (the book suggested by Clément). The ...

3

I don't know of a general approach to handle this, but in the case of $\omega$-regular languages, this has been done. One approach, which I think is first introduced in the paper Computing Conditional Probabilities in Markovian Models Efficiently is the following: Given the language $L$, let $D$ be a DPW for it. Now, start by constructing a Markov chain $M$ ...

3

Your question is essentially covered by Cor 9.5 in [1] which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G_1$. [1] Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large ...

3

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

2

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

2

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

1

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

Only top voted, non community-wiki answers of a minimum length are eligible