Q:

Proving lower bounds by proving upper bounds

The recent breakthrough circuit complexity lower-bound result of Ryan Williams provides a proof technique that uses upper-bound result to prove complexity lower-bounds. Suresh Venkat in his answer to this question, Are there any counter-intuitive results in theoretical computer science?, provided two examples of establishing lower-bounds by proving upper-bounds.

What are the other interesting results for proving complexity lower-bounds that was obtained by proving complexity upper-bounds? 
Is there any upper-bound conjecture that would imply $NP \not\subseteq P/poly$ (or $P \ne NP$)? 

A:

One could turn the question around and ask what lower bounds aren't proved by proving an upper bound. Almost all communication complexity lower bounds (and streaming algorithm lower bound and data structure lower bounds that rely on communication complexity arguments) are proved by showing that a communication protocol can be constructively turned into an encoding scheme, with the length of the encoding depending on the communication complexity of the protocol, and the lower bound for the protocol follows from the fact that you cannot encode all n bit messages using n-1 bits or fewer.
The Razborov-Smolensky circuit lower bounds work by showing how to simulate bounded-depth circuits by low-degree polynomials.
A couple of candidates of lower bounds that are not proved with an upper bound could be the time hierarchy theorem (although, to get the tightest bounds, one needs an efficient universal turing machine, which is a non-trivial algorithmic task) and the proof of AC0 lower bounds using the switching lemma (but the cleanest proof of the switching lemma uses a counting/incompressibility/Kolmogorov-complexity)

A:

In a weird way, the PCP theorem itself is a good example of proving a lower bound via an upper bound. An "efficient" randomized strategy for verifying a proof using a constant number of probes of the proof and only $\log n$ random bits leads to a lower bound for approximating the number of satisfied clauses in an instance of 3SAT. 

A:

The incompressibility method is a method based on Kolmogorov complexity to prove lower bounds. One of the first application of this method was to prove that recognizing palindromes on a Turing machine with a single tape requires quadratic time. 
Loosely speaking, the idea of this method is to describe a procedure to find an input using the information contained in the run of an algorithm solving the problem we consider on this input. The better is the procedure, the higher is the lower bound on the original problem.
Of course, full details can be found in the textbook of Li and Vitanyi.

