Did "Where the really hard problems are" hold up? What are current ideas on the subject? I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually are either very under- or very overconstrained, both of which are relatively easy to solve. It then proposes for a few problems a measure of 'constrainedness'. Those problems appear to have a 'phase transition' from 0 likelihood of a solution to 100% likelihood. It then hypothesizes:


That all NP-complete (or even all NP-problems) problems have a measure of 'constrainedness'.
That for each NP-complete problem, you can create a graph of the probability of a solution existing as a function of the 'constrainedness'. Moreover, that graph will contain a phase-transition where that probability quickly and dramatically increases. 
The worst case examples of the NP-complete problems lie in that phase-transition.
The fact whether a problem lies on that phase-transition remains invariant under transformation of one NP-complete problem to another.


This paper was published in 1991. My question is was there any follow-up research on these ideas the last 25 years? And if so, what is the current mainstream thinking on them? Were they found correct, incorrect, irrelevant?
Here is a rough summary of the status based on a presentation given by Vardi at a Workshop on Finite and Algorithmic Model Theory (2012):

It was observed that hard instances lie at the phase transition from under- to over-constrained region. The fundamental conjecture is that there is strong connection between phase-transitions and computational complexity of NP problems. 

Achlioptas–Coja-Oghlan, found that there is a density in the satisfiabe region
where the solution space shatters into exponentially many small clusters. Vinay Deolalikar based his famous attempt to proof $P \ne NP$ on the assumption that shattering implies computational hardness. Deolalikar’s Proof was refuted by the fact that XOR-SAT is in $P$ and it shatters. Therefore, shattering can not be used to prove computational hardness.

The current mainstream thinking seems to be (as stated by Vardi) that phase-transitions are not intrinsically connected to computational complexity. 

Finally, Here is an article published in Nature which investigates the connection between phase-transitions and computational hardness of K-SAT.