![[*]](http://www.cs.duke.edu/icons/latex2html/icons.gif/foot_motif.gif){kind=icon}
Jeffrey S. Vitter
SIGACT Chair
March 1998
This report is also available with better formatting in postscript format .
The primary mission of ACM SIGACT (Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory) is to foster and promote the discovery and dissemination of high quality research in the domain of theoretical computer science. The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, complexity theory, parallel computation, distributed computation, information theory, cryptography, program semantics and verification, machine learning, computational biology, VLSI, computational geometry, computational number theory and algebra, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
SIGACT actively sponsors numerous symposia, workshops, and awards (often in cooperation with other SIGs and Societies) as well as a quarterly newsletter.
During the past year, SIGACT has initiated procedures for electronic program committee meetings for its flagship conference STOC (ACM Symposium on Theory of Computing). The electronic submission server is now installed and running without problems on SIGACT's home machine, sigact.acm.org. The procedures are now being disseminated to other conferences and societies. We have also installed software for electronic management of program committee meetings. The software gathers scores and comments and produces web pages with organized rankings and comments on papers.
SIGACT awarded two prizes in 1997, both endowed by SIGACT, and contributed endowment to a third. We awarded the second Donald E. Knuth Prize for Outstanding Contributions to the Foundations of Computer Science in October 1997 to Les Valiant for his far-reaching contributions to the study of computational complexity, parallel computation, and learning theory. The Prize includes $5,000 plus a $1,000 travel fund. We awarded the first SIGACT Distinguished Service Award at STOC in May 1997 to David Johnson for his substantial service as former SIGACT Chair, conference organizer, and numerous other roles. The Award includes a $1,000 prize and $500 for travel. SIGACT has also contributed to the endowment for the Paris Kanellakis Theory and Practice Award, which was awarded for the first time last year; the recipients were Len Adelman, Whit Diffie, Martin Hellman, Ralph Merkle, Ron Rivest, and Adi Shamir for their pioneering work on public-key cryptography, which is central to modern computer security.
SIGACT continues to be a major supporter of the FCRC meetings and of the ACM electronic publishing initiatives. SIGACT is the sponsor of the first two International Conferences on Computational Molecular Biology conferences (RECOMB); the first was held in January 1997 and the second will take place in March 1998. SIGACT began co-sponsorship in 1996 of the annual Workshop on I/O in Parallel And Distributed Systems (IOPADS).
The committee on Long-Range Planning completed its final report, ``Contributions of Theoretical Computer Science.''
SIGACT awards or co-sponsors the following awards:
 Award |
Most recent recipients |
| Gödel Prize |
Joel Halpern and Yoram Moses |
| Knuth Prize | Les Valiant |
| Kanellakis Award | Adelman, Diffie, Hellman, Merkle, Rivest, & Shamir |
| Distinguished Service Award | David Johnson |
| STOC Best Student Paper | Luca Trevisan |
One of SIGACT's primary roles and successes is its sponsorship of symposia. During 1997 SIGACT was affiliated with 11 conferences, and it will be involved in three additional conferences in 1998. It was full sponsor of the following two conferences in 1997:
The publications of the conferences sponsored by SIGACT are published by the ACM. SIGACT also maintains an active web page at http://www.acm.org/sigact/ with links to several items of interest. The SIGACT newsletter, SIGACT News, is published four times per year. In 1997 the four issues comprised a total of 340 pages:
March 1997 (Vol. 28, No. 1, Whole Number 102, 54pp.),
June 1997 (Vol. 28 No. 2, Whole Number 103, 88pp.),
September 1997 (Vol. 28 No. 3, Whole Number 104, 102pp.),
December 1997 (Vol. 24 No. 4, Whole Number 105, 96pp).
Included were a variety of interesting columns and regular features:
3 Computational Geometry Columns,
1 Cryptology Column,
4 Computational Complexity Columns,
1 Logic Column,
1 Database Theory Column,
1 Parallel Algorithms Column,
1 Book Review Column (containing reviews of 3 books),
4 Reprints from Computing Reviews Columns,
3 NSF Reports,
3 Technical Report Columns,
4 Educational Forum Columns,
1 Open Problems Column, and
4 Theory Calendars.
In addition, SIGACT News also published
4 Conference Reports,
17 Calls for Papers and Participation,
1 Conference Program,
1 Obituary, and
10 articles.
SIGACT News regularly prints research news columns in several areas of theoretical computer science. It also publishes book reviews and curricula and outlines of CS courses as they are taught at various universities. SIGACT sponsors deeply discounted registration fees for students at most of its conferences. The SIGACT student lunch program allows students to eat for free alongside full-paying registrants at most meetings.
SIGACT collaborates extensively with IEEE Computer Society, EATCS, SIAM, and other SIGs and organizations. Several examples of conferences that are co-sponsored with other groups are included above. SIGACT co-sponsors the Knuth Prize with the IEEE TCMFC. SIGACT looks forward to future collaboration with other SIGs and societies and is particularly enthusiastic about its involvement in the federated meetings.
SIGACT works closely with overseas organizations such as EATCS, the European Association for Theoretical Computer Science. SIGACT and EATCS jointly sponsor the Gödel Prize. Several foreign countries have local SIGACT chapters, and SIGACT routinely sponsors or cooperates with conferences that are held overseas. SIGACT also sponsors a proceedings donation program for researchers in underdeveloped countries.
SIGACT has benefited greatly from the substantial efforts and wisdom of its many volunteers, including its officers, conference chairs, steering committees, program committees, local arrangement committees, newsletter staff, theory net (email) coordinator, awards chair, electronic publications board, as well as many others. The SIGACT membership is highly active and involved in SIGACT and the field of research that it represents.
Our extended Executive Committee currently consists of the following volunteers:
Jeff Vitter, Chair,
Faith Fich, Vice-Chair,
Hal Gabow, Secretary/Treasurer,
David Karger, Member-at-Large and Chair of Electronic Publications Committee,
Prabhakar Raghavan, Member-at-Large,
Alok Aggarwal, Conference site coordinator and IEEE TCMFC chair and liaison,
Ian Parberry, SIGACT News editor,
Doug Ierardi, TheoryNet coordinator,
David Johnson, Awards Chair,
Tom Leighton, previous SIGACT Chair,
Josep Diaz, EATCS president and liaison.
Carl Smith served as chair of the Long-Range Policy Committee, which issued its final report in 1997.
Our many other volunteers span the range from graduate students and new PhDs to very senior and well-known computer scientists. For example, two of our committee members are Turing Award winners: Juris Hartmanis of the Gödel Prize Committee and Dick Karp (chair) of the Distinguished Service Award Committee.
| Fiscal Year |
Reg | Assoc | Stud | Non-ACM | Total | Reten | Subscriptions |
| '94 |
1376 | 112 | 298 | 79 | 1865 | 69% | 184 |
| '95 | 1475 | 88 | 341 | 55 | 1959 | 69% | 195 |
| '96 | 1264 | 100 | 244 | 204 | 1812 | 67% | 179 |
| '97 | 1191 | 105 | 218 | 140 | 1654 | 70% | 171 |
| '98 (to Dec '97) | 1173 | 101 | 210 | 134 | 1618 | 71% | 176 |
The fund balance in December 1997 was 277% of the required fund balance. SIGACT continues its strong financial performance because of successful conferences, member plus packages, and single copy proceedings sales.
| Fund Balance | FY '94 | FY '95 | FY '96 | FY '97 | FY '98 |
|---|---|---|---|---|---|
| (12/97) | |||||
| Actual Balance | $186,194 | $295,217 | $397,823 | $313,027 | $330,969 |
| Required Balance | n/a | $125,880 | $68,337 | $142,075 | $119,639 |
In FY '97 $150,000 was transferred from the SIGACT fund to an endowment for awards (see below). SIGACT has continued its recent policy of reducing the contingency line item on its conference budgets in order to reduce surpluses and registration costs. The strong net revenue for SIGACT and successful conferences are illustrated in the next two tables.
| Yearly Finances | FY '94 | FY '95 | FY '96 | FY '97 |
|---|---|---|---|---|
| Revenue | 407,434 | 434,739 | 309,155 | 397,153 |
| Expenses | 307,438 | 325,716 | 206,549 | 481,949 |
| Net Increase (Loss) | 99,996 | 109,023 | 102,606 | (84,796) |
| Conferences | FY '94 | FY '95 | FY '96 | FY '97 |
| Revenue | 214,624 | 267,474 | 148,339 | 231,113 |
| Expenses | 184,233 | 237,318 | 116,458 | 232,257 |
| Surplus (Loss) | 30,391 | 30,156 | 31,881 | (1,144) |
The following seven corporations are the current SIGACT institutional sponsors. Each sponsor contributes $1,000 per year.
SIGACT contributed $150,000 for award endowments in FY '97:
| Revenue | |
|---|---|
| Dues Income (less 2% collection) | 25,602 |
| Member Plus Package | 30,416 |
| Non-Mmbr. Subscriptions | 6,006 |
| Newsletter Package Subscription | 4,207 |
| Proceedings Package Subscription | 16,256 |
| Single Copy Sales | 24 |
| Proceedings Sales | 48,200 |
| Airmail Service | 880 |
| Other Income | 5,000 |
| Interest Income | 11,100 |
| Conferences | 245,609 |
| Total Revenue | 393,300 |
| Expenses | |
| Publications: | |
| Production/Printing | 50,125 |
| Distribution/Postage | 16,388 |
| Storage & Obsolescense | 1,278 |
| Data Processing, Labels | 536 |
| Order Processing | 4,900 |
| Total Publication Expenses | 73,227 |
| Officer Services | |
|---|---|
| Travel/Subsistence | 7,500 |
| Postage | 1,125 |
| Minor Printing | 1,125 |
| Total Officer Services | 9,750 |
| Grants | 16,000 |
| Awards | 10,000 |
| Miscellaneous Expenses | 16,500 |
| SIG Board Allocation | 2,791 |
| SIG Support Allocation | 51,643 |
| Transfer Support to Conf. | 22,275 |
| Conferences | 240,738 |
| Total Expenses | 398,374 |
| Net Surplus (Deficit) | (5,074) |
| SIG Fund Beginning Balance | 317,272 |
| SIG Fund Ending Balance | 312,198 |
| Required Fund Balance | 127,017 |
SIGACT is fulfilling its commitments well: The newsletter is frequent, informative, and timely, the many conferences it supports contain current research of the highest quality, and items of immediate interest are routinely posted on the internet. SIGACT is doing well financially and has experienced only a modest decrease in membership during the past few years.
The primary concern of the SIGACT membership is the recent decline in academic job opportunities for its graduate students. The decline in job opportunities is the result of the field reaching middle age (there are many young faculty and few retirements), the rapid increase in the number of PhD-producing faculty during the past few years, and the contraction of giants such as IBM, Bellcore, and DEC.
In response, the SIGACT community is working together with funding agencies and industry to adapt to the changing job market. It is likely that SIGACT will pay even more attention to related applied fields and that its students will be increasingly encouraged to prepare for applied and/or non-academic positions upon graduation. At the same time SIGACT continues to highlight the accomplishments of its community and to advocate for the strategic importance of theoretical computer science. The current year is certainly more promising in terms of job opportunities for students in theoretical computer science; the situation may be turning around.