6

It appears, via code, that if you take a random string $x$ and then form $y$ by flipping only the first bit of $x$, then a random DFA on $n/5$ states fails to separate $x,y$ with high probability. So, in particular, there exists a pair $x,y$ such that a random DFA on $n/5$ states fails to separate $x,y$ with high probability.


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


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


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


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