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? 
Did Where the really hard problems are hold up? What are current ideas on the subject?
np hardness;worst case
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. AchlioptasCoja-Oghlan, found that there is a density in the satisfiabe regionwhere 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. Deolalikars 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.