2007 sigact report
Download 22.75 Kb.
|
2007 SIGACT REPORT Richard E. Ladner, SIGACT Chair August 1 , 2007 1. Awards
2. Significant papers on new areas published in proceedings This section was prepared with the help of Uri Feige, Hal Gabow, and Roger Wattenhofer. STOC 2007 The ACM Symposium on Theory of Computing (STOC 2007) covers much of computer science theory. Two award winning papers stood out at the conference. ``Towards 3-Query Locally Decodable Codes of Subexponential Length" by Sergey Yekhanin. This paper shared best paper award, and also received the best student paper award. Yekhanin’s paperchanges the perception of what researchers believe is doable. It introduces a new approach to constructing Locally Decodable Codes (LDC) and Private Information Retrieval (PIR) schemes. This method leads to constructions with dramatically improved parameters compared to previously known constructions, better than what many researchers in the field thought was possible. We shall give a few more details on the result for LDCs. A 3-query LDC encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit xi of the message by querying only three bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. Previous constructions required N to be exponential in n1/2. The new approach offers a family of constructions with progressively better parameters, based on Mersenne primes p=2t-1. In the new constructions, it suffices that N is exponential in n, where depends on the value of p. Based on the largest known Mersenne prime, can be taken as small as 10-7. Under the conjecture that there are infinitely many Mersenne primes, can tend to 0 as n grows. The results for PIRs offer improvements of a similar flavor in communication complexity. ================= ``Faster Integer Multiplication" by Martin Fürer. This paper shared best paper award. This paper returns to an old and basic computational problem, and provides the first improvement in several decades. Integer multiplication is one of the most basic arithmetic operations. The natural multiplication algorithm takes O(n2) time. It has long been known that fast Fourier transform (FFT) can be used in order to obtain multiplication algorithms that are asymptotically much more efficient. Using this approach, Schönhage and Strassen designed a multiplication algorithm with a running time of O(n log n loglog n). This is almost best possible (under certain natural models of computation), except for the loglog n term. Despite the fact that multiplication is such a basic problem and that the multiplication algorithm appeared in textbooks already 30 years ago, there has been essentially no progress in closing this remaining loglog n gap. The current paper achieves such progress, replacing the loglog n term by 2O(log* n). The new algorithm offers new insights about how FFT can be used. SODA 2007 The ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) covers many topics in discrete algorithms and mathematics. A number of papers stood out at the conference. “Deterministic pivoting algorithms for constrained ranking and clustering problems” by Anke van Zuylen and Rajneesh Hegde and Kamal Jain and David P.Williamson. “Aggregation of Partial Rankings, p-Ratings and Top-m lists” by Nir Ailon. These first two papers attacked the problem of how to combine rankings s from independent sources to produce the best overall ranking. For exmple, how does a committee rank competing proposals? How to order a set of stocks that have been rated by Moody and other rating agencies? How a meta-search engine orders the hits provided by various search engines? This area has attracted research at a number of recent conferences, and these two paper obtain the very best results. ================= “Island Hopping and Path Colouring with applications to WDM Network Design” by Andrew McGregor and Bruce Shepherd WDM (wavelength division multiplexed) networks transmit information using lightbeams through optical fibers. These networks are being deployed, starting in the last 20 years. Multiplexing allows different wavelengths to be transmitted on the same fiber, eg current systems use up to 160 different wavelengths. This paper improves previous strategies for designing such networks. ================= “Model-driven Optimization using Adaptive Probes” by Sudipto Guha and Kamesh Munagala. Suppose a network of sensors is deployed in a forest, and we need to find the maximum temperature. Each sensor has reported an estimated temperature, but these estimates need to be made more accurate, at the expense of dedicating sensors to refining their estimates. How can we get the most reliable estimate, when we can only afford to dedicate a small number of the sensors? ================= “Sandpile transience on the grid is polynomially bounded” by Laszlo Babai and Igor Gorodezky. The Abelian Sandpile Model has been proposed by statistical physicists to model diffusion processes and other dynamic systems. Grains of sand are dropped onto cells, And when a cell has as many grains as it has neighboring cells, its grains move to the neighbors, by giving 1 grain to each neighbor. But 1 special cell digests every grain it gets, never returning them. This paper contributes to the argument for the realism of this model, by showing that the system quickly settles into its long term behavior, without wasting too much time passing through "transient" states. ================= “Speed scaling for weighted flow time” by Nikhil Bansal, Kirk Pruhs and Cliff Stein. “Energy efficient online deadline scheduling” by Chan, Chan, Lam, Lee, Mak and Wong. Modern computer architectures and operating systems try to utilize power in the best possible way. They can change processing speed to prolong battery life (slower speed uses far less power). These 2 papers give strategies for managing power that are provably good: ========================= “Line-of-Sight Networks” by Alan Frieze and Jon Kleinberg and R. Ravi and Warren Debany
In line-of-sight position can communicate. It shows that many of the desirable properties for establishing global communication that hold in the traditional model can also be achieved in the new, more realistic model. ================= “Minimizing Movement”, Erik D. Demaine and MohammadTaghi Hajiaghayi and Hamid Mahini and Amin Sayedi and Shayan Oveisgharan and Morteza Zadimoghaddam
3. Significant programs that provided a springboard for further technical efforts SIGACT sponsored or co-sponsored a number of important conferences including the Symposium on Theory of Computation (39th STOC), Symposium on Principles of Distributed Computing (25th PODC), Symposium on Computational Geometry (23rd SOCG), and Symposium on Parallel Algorithms and Architectures (19th SPAA). SIGACT also supports several conferences in-cooperation including Symposium on Principles of Database Systems (PODS), Symposium on Discrete Algorithms (SODA), Symposium on Foundations of Computer Science (FOCS), Symposium on Principles of Programming Languages (POPL). SIGACT has endorsed a proposal to start the ACM Transactions on Computation Theory which will complement the ACM Transactions on Algorithms and the ACM Transactions on Computational Logic to provide coverage of almost all of theoretical computer science. The new journal is now going through the approval process. SIGACT sponsored its first Undergraduate Student Research Competition at STOC 2007. 4. Innovative programs which provide service to our technical community The Committee for the Advancement of Theoretical Computer Science sponsored by SIGACT has been very active this past year. The committee meets by conference call every two weeks and has developed and executed action plans increase the visibility of theoretical computer science and to increase the funding base for theory of computation at the NSF. As an example the committee spearheaded the effort to hold two workshops on the Computational Worldview and the Sciences at Princeton and Cal Tech. These workshops brought together top people in theoretical computer science and various sciences to discuss how the computational view of science can change the nature of these sciences proceed. This effort inspired in part the new NSF program Cyber-Enabled Discovery and Innovation (CDI). SIGACT, with the help of ACM headquarters, produced two press releases for the Gödel and Knuth Prizes. This effort is intended to make our research more accessible to the general public. SIGACT continues to support student attendance at SODA, FOCS, and STOC by funding Student Best Paper Awards, travel, lunches, and reduced registration fees. This helps ensure that the maximum number of students can attend these conferences. 5. Summary of key issues that the membership of the SIGACT will have to deal with in the next 2-3 years As was mentioned over the past few years, the key issue for our community is funding for research. The Committee for the Advancement of Theoretical Computer Science (CATCS) is tackling this problem directly. Related to the funding issue is the image of theoretical computer science within computer science, the science community as a whole, and the public. Articulating the importance of theoretical computer science research is essential so that these outside communities understand and appreciate what we are all about. The expanded role of the CATCS includes working on this problem. There is also concern about the academic job market which is affected by the lack of growth in computer science majors. After five years of decline in enrollment there seems to be a slight upturn this year. The rising costs of proceedings and journals and the move toward electronic publication is of concern. University libraries are cancelling subscriptions to some journals completely and are moving toward electronic, non-paper, access to save money. SIGACT’s efforts to expand the ACM journal offerings in competition with for-profit journals is helping attack this problem. Download 22.75 Kb. Share with your friends:
|