Let S be either a sphere with greater than or equal to 5 punctures or a torus with greater than or equal to 3 punctures. We prove that the automorphism group of the complex of curves of S is isomorphic to the extended mapping class group M-S*. As applications we prove that surfaces of genus less than or equal to 1 are determined by their complexes of curves, and any isomorphism between two subgroups of M-S(*) of finite index is the restriction of an inner automorphism of M-S(*) We conclude that the outer automorphism group of a finite index subgroup of M-S(*) is finite, extending the fact that the outer automorphism group of M-S(*) is finite. For surfaces of genus greater than or equal to 2, corresponding results were proved by Ivanov (MES/M/89/60, Preprint). (C) 1999 Elsevier Science B.V. All rights reserved.