SIGACT FY'04 Annual Report

July 2003 - June 2004
Submitted by: Harold Gabow, SIGACT Chair

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 community 
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.

1. Awards that were given out:

Danny Lewin Best Student Paper Award for STOC 2004:
Prize shared by Scott Aaronson, "Lower bounds for local search by quantum arguments" and Jonathan Kelner, "Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus"

Best Student Paper Award for SODA 2004:

Chaitanya Swamy, "Correlation clustering: Maximizing agreements via semi definite programming"

STOC 04 Best Paper Awards:

Ran Raz, "Multi-linear formulas for permanent and determinant are of super-polynomial size" Sanjeev Arora, Satish Rao and Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning"

Kanellakis Theory and Practice Award (with ACM):
Gary Miller, Michael Rabin, Robert Solovay, Volker Strassen

Citation:

For the development of efficient randomized tests of primarily, enabling the practical realization of public key cryptography and demonstrating the power of randomized algorithms.

Godel Prize (with EATCS):

Maurice Herlihy and Nir Shavit for "The Topological Structure of Asynchronous Computability" Journal of the ACM, Volume 46, Issue 6 (1999), and Michael Saks and Fotios Zaharoglou for "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge" SIAM Journal on Computing, Volume 29, Number 5 (2000).

Citation:

The two papers recognized by the 2004 Godel Prize offer one of the most important breakthroughs in the theory of distributed computing.

The problem attacked is the complete understanding of asynchronous wait-free deterministic computation in the basic shared memory model. These papers demonstrate that one can avoid the inherent difficulty of analyzing a dynamic model, transforming it into a static one by associating computational tasks with simplicial complexes and translating the question of existence of a wait-free protocol into (distinct but related) topological questions about the complexes. This reformulation allows the introduction of powerful topological invariants, such as homologies, to show the impossibility of numerous tasks, including set-agreement and renaming.

The discovery of the topological nature of distributed computing provides a new perspective on the area and represents one of the most striking examples, possibly in all of applied mathematics, of the use of topological structures to quantify natural computational phenomena.

Eugene L. Lawler Award for Humanitarian Contributions within Computer Science and Informatics (with ACM):

Patrick Ball

Citation:

For his leadership in the creation of open source software, Analyzer and Martus, that enables human rights groups to securely collect, safeguard, organize, disseminate, and conduct statistical analysis of human rights abuses. Martus and Analyzer have been used by NGO's in Guatemala, Sierra Leone, Ghana, the Philippines, Sri Lanka and the United States. Dr. Ball demonstrates a vision of technology used in the service of humanity.

SIGACT Distinguished Service Award:

Rocky Ross

Citation:

The 2004 SIGACT Distinguished Service Prize is awarded to Rockford J. Ross for his long-standing service to the theoretical computer science community. His tenure in charge of the Education Forum at SIGACT News has exceeded all expectations in length and breadth, and has out-lasted at least three Editors. Rocky has been known by all who have worked with him for his alacrity and tireless reliability. He has consistently chosen subjects of interest to a broad computer science audience. His contributions have been impeccably prepared, and infused with wit, insight, wonder and the texture of his own unique character. It is oft overheard that Rocky's column is the first one to be read with each new issue. In fact his ever-colorful by-line from the wilderness of Montana has become a well-loved hallmark of SIGACT News.

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

STOC 04 had a large number of papers in the emerging areas of quantum computation and algorithmic game theory/economics. There were a smaller number of papers in new areas such as data mining, analysis of data streams, and property testing. Below are *very* brief summaries of such papers.

Internet Routing

"On the performance of greedy algorithms in packet buffering" by S. Albers and M. Schmidt Analyzes the simplest strategy for transmitting packets and avoiding packet loss.

"Adaptive routing with end-to-end feedback: distributed learning and geometric approaches" by B. Awerbuch and R.D. Kleinberg Gives algorithms to route traffic to achieve short delays, without knowing the current traffic pattern. (Instead, the algorithm receives limited feedback about the delays of the messages it sends.)

"Know thy neighbor's neighbor: the power of look ahead in randomized P2P networks" by G.S. Manku, M. Naor, U. Wieder The greedy routing strategy is suboptimal in many network topologies. Looking 2 hops ahead gives optimal routing algorithms.

"The zero-one principle for switching networks" by Y. Azar and Y. Richter A principle of classic switching theory extends to quality of service routing. Several algorithms with improved routing quality are designed using this principle.

Quantum Computation

"Graph entropy and quantum sorting problems" by A.C.-C. Yao Shows quantum computers are subject to the same limitations as classic computers on the problem of sorting numbers.

"Multilinear formulas and skepticism of quantum computing" by S. Aaronson Introduces a classification of quantum states, to help decide if there are states needed for quantum algorithms (e.g., Shor's factoring algorithm) that can or cannot be physically achieved.

"Exponential separation of quantum and classical one-way communication complexity" by Z. Bar-Yossef, T.S. Jayram, I. Kerenidis Exhibits a communication problem that can be solved exponentially more efficiently by quantum communication than by ordinary communication.

"Lower bounds for local search by quantum arguments" by S. Aaronson Establishes lower bounds on finding local minima, for quantum computation; the bounds then extend to similar bounds for classic computation.

"Quantum and classical query complexities of local search are polynomially related" by M. Santha and M. Szegedy Establishes the relationship between deterministic, randomized and quantum local search, introduced in the previous paper of Aaronson.

"The quantum adiabatic optimization algorithm and local minima" by B.W. Reichardt Gives a natural problem on which this popular quantum algorithm affords no advantage over brute force computation.

Economics and Game Theory

"Auction algorithms for market equilibrium" by R. Garg and S. Kapoor Gives improved method for computing the fair prices corresponding to an initial distribution of goods, assuming linear utility functions.

"The spending constraint model for market equilibrium: Algorithmic, existence and uniqueness results" by N.R. Devanur and V.V. Vazirani Gives a new model for market equilibria, allowing nonlinear utility functions yet still allowing efficient computation of equilibria.

"The complexity of pure Nash equilibria" by A. Fabrikant, C. Papadimitriou, K.Talwar In games modeling congestion of network traffic, computing a pure (nonrandomized) Nash equilibrium point is provably difficult (PLS-complete) in general but can be done in polynomial time when all players have the same source and destination.

"Computing Nash equilibria for scheduling on restricted parallel links" by M. Gairing, T. Lucking, M. Mavronicolas and B. Monien Gives an algorithm to modify a given assignment of traffic into one with the same maximum delay, but that is a Nash equilibrium, i.e., selfish users will choose it.

Data Streams

"Algorithms for dynamic geometric problems over data streams" by P. Indyk Shows how to estimate the solution to geometric problems such as minimum spanning tree when the data is presented in a stream that far exceeds the memory capacity.

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

SIGACT instituted a new budgeting policy of providing $1000 honoraria to the invited speakers at STOC. The three invited talks (Quantum Algorithms, A. Ambainis; Network Games, E. Tardos; Depth through Breadth, A. Wigderson) help all members of the community stay abreast of recent developments in other sub areas.

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

STOC 04 initiated a reduced registration fee for postdoctoral students. This was in response to feedback that the conference was too expensive for many postdocs. The program was sponsored by NEC Laboratories of America. In addition we continued the (recently started) STOC Developing Country Travel Awards and STOC Student Travel Awards, providing financial support to conference attendees who are from nontraditional countries and who are students, respectively.

The SIGACT digital scanning project continues to be in progress. The DVD will contain the entire past proceedings of the main theory conferences: STOC, FOCS, Complexity, LICS, and SODA. It will be distributed free to SIGACT members.

In response to the increase in submission numbers to STOC and SODA, the PCs of both conferences were enlarged. The STOC PC has changed to a hybrid of electronic and physical meetings. In previous years we had abandoned the physical PC meeting because of economies afforded by web-based deliberations. We are now supplementing the web-based system with a short physical meeting. This recognizes the value of face-to-face discussions and concerted group decision making. The physical meetings are also valuable learning experiences for the PC members. The conference budget for STOC has offered the increasing amounts of financial support for the physical meeting. We will continue this trend even more in STOC 05.

We continue to experiment with PC software. STOC 04 used Microsoft's CMT system, and the committee supplemented it with a number of more intelligent supporting programs. STOC 05 will use the traditional SIGACT submission software; however but it is being enhanced by Christian Scheideler to be more user friendly (allowing attachments, and perhaps PDF files).

A new technical column, Online Algorithms, was added to SIGACT News. It is written by Marek Chrobak of University of California at Riverside. It began with the December 2003 issue. Riccardo Pucella, currently at Cornell University, will be taking over editorship of the Logic Column. A new Awards section is being added to SIGACT News.

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:

The increase in submission numbers to theory conferences continues to be an issue. The community is producing a wealth of high quality work, and we must ensure that our program committees have the human and technological resources to process submissions in a fair and knowledgeable fashion. Actions already taken are listed above. We continue to monitor this issue. The issue that dominated the STOC 04 Business Meeting was the future of the STOC Best Paper Special Issue. The main question is which journal should host this issue. Many members of the community are dissatisfied with the exorbitant pricing policies of the current publisher. In response to a vote at the STOC Business Meeting, the STOC 04 Special Issue will appear in SIAM Journal on Computing. The Executive Committee is working on a policy for future special issues, taking feedback from the community into account.