Authors should submit an extended abstract (not a full paper).and asked why we theorists only wanted extended abstracts and why she couldn't submit a full paper if it met the page limit.
An abstract just states the main results of a research paper. An extended abstract gives a little motivation, background and a hint of the proofs. The extended abstract serves not as a paper in itself but as an advertisement of the journal paper to come. If one had a full paper published in the proceeding than one couldn't publish the same results in a journal later on. That's the way conferences work.
Actually that's the way conferences work in all fields except computer science. In CS conferences play a more important role than journals; in most cases people judge the quality of a paper based more on the conference than the journal. Many conference papers never see a journal at all and many journal submissions are only slight variations of the conference proceedings version.
You really need to send something closer to a full paper to STOC if you hope to get accepted. You need to convince the committee that the results are new, important, correct and nontrivial. Most people submit a rough draft of a final paper, using the appendix if needed to put in their proofs.
Why do we keep the fiction of the extended abstract? Ethical and copyright rules prohibit us from publishing the same results in multiple places. We call the proceedings version an "extended abstract" so we can believe we don't violate these rules.
Non-theory conferences don't even pretend. The EC Conference, for example, solicits full papers though they do include the following note.
To accommodate the publishing traditions of different fields, authors may instead submit working papers that are under review or nearly ready for journal review. These submissions will be subject to review and considered for presentation at the conference but not for publication in the proceedings. These submissions need not conform to the conference paper format. Abstracts of accepted working papers will be included in the proceedings and must be coupled with a URL that points to the full paper and will be reliable for at least two years.