SIGACT Annual Report July 2002 - June 2003

CONTENTS

1. Awards that were given out
2. Significant papers on new areas that were published in proceedings
3. Significant programs that provided a springboard for further technical efforts
4. Innovative programs which provide service to some part of your technical community; and
5. A very brief summary for the key issues that the membership of that SIG will have to deal with in the next 2-3 years.
6. Updates on volunteers

1. Awards that were given out

Knuth Prize (with IEEE TCMFC): Miklos Ajtai. Citation: For numerous ground-breaking contributions to Theoretical Computer Science.

Miki coauthored a landmark sorting network algorithm which exploited the power of expanders in an elegant way. He has developed fundamental tools for deriving circuit complexity and proof complexity lower bounds. He has derived superlinear time-space tradeoffs for branching programs. He has constructed a new class of suspected hard problems where the average case is provably as hard as the worst case. Many of Miki's other results are equally unique and spectacular. Miki is one of the most influential researchers in the theoretical community.

Danny Lewin Best Student Paper Award for STOC 2003: Thomas Hayes, for "Randomly coloring graphs of girth at least five"

Kanellakis Theory and Practice Award (with ACM): Peter Franaszek, for constrained channel coding. Citation: For contributions to the theory and practice of constrained channel coding, creating a revolution in the encoding of digital data for transmission and storage.

This award recognizes Peter Franaszek's seminal and sustained contributions to the theory and application of constrained channel codes for data recording and transmission. These codes enforce constraints on the sequence of signals in order to enable clock synchronization or ensure signal properties such as DC balance. Dr. Franaszek's theoretical work is at the core of several codes that are incorporated in ubiquitous industry standards. His contributions range from fundamental theory to detailed implementation at the physical link layer. He is the co-inventor of the 8B/10B code that is currently used in the Gigabit Ethernet and Infiniband standards, as well as in several standards for data transmission in storage networks including the Fiber Channel Standard, IBM's ESCON architecture and Hitachi's channel extender. His work has led to revolutionary advances in the recording density of digital media and the transmission bandwidth of digital communication systems.

Godel Prize (with EATCS): Yoav Freund and Robert Schapire for ``A Decision Theoretic Generalization of On-Line Learning and an Application to Boosting,'' Journal of Computer and System Sciences 55 (1997), pp. 119--139. Citation: This paper introduced AdaBoost, an adaptive algorithm to improve the accuracy of hypotheses in machine learning.

The algorithm demonstrated novel possibilities in analyzing data and is a permanent contribution to science even beyond computer science. Because of a combination of features, including its elegance, the simplicity of its implementation, its wide applicability, and its striking success in reducing errors in benchmark applications even while its theoretical assumptions are not known to hold, the algorithm set off an explosion of research in the fields of statistics, artificial intelligence, experimental machine learning, and data mining. The algorithm is now widely used in practice. The paper highlights the fact that theoretical computer science continues to be a fount of powerful and entirely novel ideas with significant and direct impact even in areas, such as data analysis, that have been studied extensively by other communities.

2. Significant papers on new areas that were published in proceedings

Research on problems inspired by the Internet continues. Issues include routing strategies for web traffic, strategies for pricing digital goods and services, and efficiently processing huge data sets. Below are some representative papers from STOC 03 on these areas.

"Management of multi-queue switches in QoS networks" by Azar and Richter

"Quality of service" routing -- ensuring faster routing for higher priority packets, or just ensuring that the fewest number of packets are lost -- becomes more crucial as traffic on the Internet increases. This paper gives a general technique to derive an algorithm for a routing switch with m queues from a (simpler) algorithm for 1 queue. Competitive analysis is used to guarantee the goodness of the algorithm, without any assumptions on distributions of packet arrivals etc.

"Pricing network edges for heterogeneous selfish agents" by Cole, Dodis, Roughgarden.

This paper studies the notion of taxing links in a network in order to ensure that traffic is routed in a globally efficient manner (when routing decisions are made individually by selfish users). It allows the population to be heterogeneous, i.e., a given latency can have a different perceived penalty for different users. The paper shows how to efficiently compute taxes, and gives mathematical conditions under which schemes with moderate tax rates exist.

"Optimal oblivious routing in polynomial time" by Azar, Cohen, Fiat, Kaplan and Racke.

Racke (in FOCS 02) gave a distributed algorithm for routing traffic through an undirected network in close to the optimal congestion ("close to" here means that the competitive ratio is polylogarithmic). Racke's result is surprising in that it is achieved without any knowledge of the current traffic in the network. This paper gives an efficient (polynomial time) algorithm to construct these routings. In fact the algorithm constructs optimal routings.

"Sublinear geometric algorithms" by Chazelle, Liu and Magen.

In the past several years papers have begun to investigate algorithms on massive data sets -- data sets so large that an algorithm cannot afford the time to examine them in entirety. This paper presents sublinear time algorithms for some fundamental problems in computational geomtetry, including intersection of 3 dimensional convex polyhedra and point location in 2 dimensional Delaunay triangulations and Voronoi diagrams.

3. Significant programs that provided a springboard for further technical efforts

STOC 03 was held at FCRC. Colleagues from different areas could be seen at STOC sessions, and vice versa. FCRC changes the quality of STOC, and the SIGACT EC strongly supports its continuation.

4. Innovative programs which provide service to some part of your technical community

STOC 03 initiated the STOC Developing Country Travel Awards. These are a new supplement to the ongoing program of STOC Student Travel Awards. The new awards are meant for faculty and researchers from developing countries, who are STOC authors or are otherwise contributing to the STOC conference. A maximum of $5,000 is to be awarded for each conference. Three awards were given this year.

A digital scanning project is budgeted and we are close to signing a contract. Back proceedings of IEEE FOCS conference and others will be scanned and distributed to SIGACT members on DVD, as well as made available on the web.

A review and improvement of PC software was begun this spring. The current software support for our program committees is widely used by the theory community at large, but is not as helpful as it could be. A committee is investigating the alternatives of paying for an upgrade to our own software or using a vendor's.

A new technical column on online algorithms, edited by Marek Chrobak, is being added to SIGACT News. This is an important area of algorithm design.

5 A very brief summary for the key issues that the membership of that SIG will have to deal with in the next 2-3 years.

Last year's report indicated financial difficulties with several conferences that seemed to signal an emerging trend. This year's conferences seem to be coming in as budgeted, so at least this year saw a pleasant change for the better.

The past two years have seen a tremendous increase in submission numbers to our conferences. This seems to be stretching our current PC structure to its limit. In response (to what we think will be a continuing trend) STOC is moving to a slightly larger PC, physical as well as electronic PC meeting, and the above-mentioned review of PC software.

6. Volunteer Updates.

The past 2 years have seen a number of changes in the SIGACT volunteer corps. In December 2002 Ian Parberry stepped down as Editor of SIGACT News, a position that he manned starting with the Summer 1991 issue. Ian created the digital version of SIGACT News, and added features such as the Quarterly Quote. Earlier in 2002 Ian stepped down as SIGACT webmaster. He created the website, which has many interesting and unique features ranging from useful bibliographies and guides for authors to the more whimsical theoretician's genealogy. Ian won the SIGACT Distinguished Service Prize in 1998 for these contributions.

Steve Tate also stepped down as SIGACT system administrator and manager of electronic conference support, a post he held since 1997. Steve oversaw the growth of our electronic conference submission system, which today is typically used by close to 20 conferences each year.

David Haglin is the new SIGACT News Editor. Wolfgang Bein is the new Information Director.