$k$-SAT is one of the best known among a wide class of random
constraint satisfaction problems believed to exhibit a threshold
phenomenon where the control parameter is the ratio, number of
constraints to number of variables. There has been a large amount of
work towards estimating the 3-SAT threshold. We present a new \emph
{structural} (or \emph{syntactic}) approach aimed at narrowing the gap
between the exact threshold and upper bounds obtained by the first
moment method. This is based on the notion of \emph{typicity},
specific definitions of which may vary so as to encompass any purely
formal property of a random formula which holds with high probability.
The idea is that the formulae responsible for the gap tend to be
atypical, hence restriction to typical formulae will give a better
bound. In this paper, the method is carried through using an
uncomplicated definition in terms of the numbers of signed occurrences
of variables. We demonstrate its ability to combine with previous
techniques (locally extremal solutions) and make new ones practical
(the systematic unbalancing of signs in formulae), resulting in a
significant drop of the upper bound to 4.506. We also hint at its
versatility in applying to other problems, such as the colourability
of random graphs.
(This is the full version of a preliminary short paper which appeared
in the Proceedings of the Eleventh ACM-SIAM Symposium on Discrete
Algorithms, pages 124-126, San Francisco, California, January 2000.)