Dear Author: Enclosed please find the guidelines and pertinent information for submission of your paper(s). Please note: It is of particular importance that you leave sufficient space in the lower left corner of the first column on the first page for ACM to fill in the copyright information. There is a 10-page maximum on your paper. If you wish to have additional pages, you may have up to 2 additional pages at a cost of $250 per page. Please make your check payable to STOC'99 and send it with your copyright form and paper to Susan Welby (address below). Please submit camera-ready copy (produced on a high-resolution output device) of your manuscript on 8 1/2" x 11" paper following the proceedings format appended below. Proceedings templates to create camera-ready copy are available in Word, WordPerfect, FrameMaker and LaTex. These templates are located at: http://www.acm.org/sigs/pubs/proceed/template.html. Please also submit an electronic copy to stoc99@sigact.acm.org. This version should be identical to the hardcopy version. The enclosed ACM copyright form must be signed and returned with your paper. I caution you that ACM will not publish any paper that is not accompanied by a signed copyright form. In those cases where there is more than one author per paper, the first-named (assumed senior) author only must sign. The full ACM Copyright policy, revised as of November 15, 1995, is available via http://www.acm.org/pubs/copyright_policy.html. Please federal express or mail your paper and signed copyright form so that it is received by Susan Welby by February 12, 1999. The paper and signed copyright form should be sent to: Susan Welby Lab for Computer Science MIT 545 Tech Square Cambridge Mass 02139 Telephone #617-253-5876 Fax #617-258-5429 Email address: susan@theory.lcs.mit.edu Please let me know if I can be of further assistance. Sincerely, Tom Leighton Program Chair, STOC'99 ACM Proceedings Specifications Title: Centered 18 pt, Bold, Helvetica Author, ACM Fellow: Centered 12 pt, Helvetica Affiliation: Centered 10 pt, Helvetica Email: Centered 12 pt, Helvetica Abstract: Flush Left 12 pt, Bold, Times Roman Section (heading 1): Flush Left 12 pt, Bold, Times Roman, numbered- ex: 1 Subsection (heading 2) Flush Left 12 pt, Bold, Times Roman, numbered- ex 1.2 Subsubsection (heading 3): Flush Left 11 pt, Italics, Times Roman, numbered- ex 1.2.3 Subsubsubsection (heading 4):Flush Left 11 pt, Italics, Times Roman, numbered- ex 1.2.3.4 Subsubsubsubsection (heading 5): Flush Left 11 pt, Italics, Times Roman, numbered- ex 1.2.3.4.5 Text: 2 column, justified, size of type 9 pt. space between lines 10 pt Text Font: Times Roman Column width: 3.33" (8.45 cm) 2 column gutter: .33"(.83 cm) Top Margin: 1" (2.54 cm) Right Margin: From edge .75" (1.9 cm) Left Margin: From edge .75" (1.9 cm) Bottom Margin: 1" (2.54 cm) Copyright space on 1st page: lower left column 1.5" (3.81 cm) Paragraph indentation: None, flush left, line space between paragraphs Footnote/Citation: 9 pt, Times Roman Bibliography/Reference: 10 pt. Use the standard CACM format for references, i.e., a numbered list at the end of the article, ordered alphabetically by first author, and referenced by number in brackets [2]. Reference number in brackets positioned as a negative indent. Text aligned .25" (.63 cm) in from margin. Subsequent pages: For pages other than the first, start at the top margin and continue in double-column format. Tables/Figures/Images: Placed in text as close to reference as possible. May extend across both columns to a maximum width of 7" (17.78 cm). Captions: 9 pt, bold, Times Roman, numbered (ex. "Table 1." or "Figure 2."), and centered beneath each table, figure or image. ACM COPYRIGHT FORM http://www.acm.org/pubs/copyright_form.html. Title of Work: Author(s): Publication or Conference Name and Date: A. TRANSFER OF COPYRIGHT AGREEMENT Copyright to the above work (including without limitation, the right to publish the work in whole or in part in any and all forms of media, now or hereafter known) is hereby transferred to the ACM (for U.S. Government work, to the extent transferrable*) effective as of the date of this agreement on the understanding that the work has been accepted for publication by ACM. However, each of the Authors retain the following rights: 1 All other proprietary rights except copyright (and the publication rights transferred to ACM), such as patent rights. 2 The right to reuse, without fee, in future works of the Author's own provided that the ACM citation and Copyright notice are included. 3 The right to post a personal copy on non-ACM servers for limited noncommercial distributions, provided that the ACM Copyright notice is attached to the personal copy and that the server prominently displays a general policy notice (see sample of Server Notice in Revised ACM Interim Copyright Policy, version 2, section 5.3) about the use of copyright works it contains. 4 Employers who originally own copyright may distribute copies of works of their employees within the employer's organization. This Form must be signed by the Author or, in the case of a "work made for hire," by the employer and must be received by ACM, Inc. --See Box C-- before processing of the manuscript for publication can be completed. Authors should understand that consistent with ACM's policy of encouraging dissemination of information each published paper will appear with the following notice: "Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee." Signature_______________________ Print Name_______________________ Title, if not Author_____________________ Date________________________ B. *DECLARATION FOR U.S. GOV'T WORK This certifies that the above author(s) wrote the paper (a) as part of work as U.S. government employees or, (b) as other noncopyrightable work. Signature________________________________ Agency__________________________________ Title, if not Author__________________________ Date Signed______________________________ C. WHERE TO RETURN THIS FORM For Proceedings papers, please return the signed form in hardcopy to the Conference Program Chair. ACM revised 7/97 TO: Authors Submitting Papers for Publication by ACM FROM: ACM Director of Publications SUBJECT: ACM Copyright Procedures Thank you for submitting a paper for publication by ACM, Inc. ACM's publications are read throughout the world, and we must deal with requests for reprinting, republishing, redistributing, digitizing, posting to servers, translating, anthologizing, and other actions. It is the policy of ACM to own the copyrights on its technical publications to protect the interests of ACM, its Authors and their employers, and at the same time to facilitate the appropriate reuse of this material by others. United States Copyright Law requires that the transfer of copyright of each contribution from the Author to ACM be confirmed in writing. It is necessary that Authors sign either Part A or Part B of the ACM Copyright Form and return it with the manuscript to the address on the Form (see Revised ACM Interim Copyright Policy, sections 2.1, 4.1, 4.2). If you are employed and you prepared your paper as part of your job, the rights to your paper may initially rest with your employer. In that case, when you sign the ACM Copyright Transfer Form, we assume you are authorized to do so by your employer. If not, it should be signed by someone so authorized. For jointly authored papers, an original signature is required from one (assumed senior) Author only. However, we assume all Authors have been advised and have consented to the terms of this Form. Authors who are U.S. government employees and/or whose papers are not copyrightable as part of certain Government contract work, are not required to sign Part A, but all co-authors outside the Government contract are. Part B of the Form is to be used instead of Part A only if any or all Authors are U.S. Government employees and they prepared the paper as part of their job, or the work is an uncopyrightable product of a Government contract. ACM Authors have all the rights scientific authors have historically enjoyed, including the right to present orally the submitted or similar material in any form; the right to reuse in future works of the Author's own with notice and credit to ACM; the right to republish in any form of media with notice and credit to ACM, in works published by the employer or for the employer's internal business purposes; the right to reproduce and distribute for peer review in reasonable quantities (see Revised ACM Interim Copyright Policy, sections 3, 5.3); and all proprietary rights other than copyright. Although it is not part of ACM's policy to grant Authors or their organizations the sole right to approve permissions for republishing by third parties, ACM always seeks the approval of its Authors, for jointly authored papers the first-named (assumed senior) Author only, in weighing such requests. This is done as a matter of professional courtesy.