Appendix D
SIGACCESS Annual Report
July 2007 - June 2008
Submitted by: Vicki L. Hanson, Chair
SIGACCESS continues to expand its membership and activities to meet member needs. This report highlights a new ACM SIGACCESS Award as well and the SIG’s conference and publication activities. Membership continues to do well, with people from 29 different countries belonging to SIGACCESS.
ACM SIGACCESS AWARD for Outstanding Contributions to Computing and Accessibility
SIGACCESS is delighted to announce the creation this year of the ACM SIGACCESS AWARD for Outstanding Contributions to Computing and Accessibility. The award, to be given every other year, recognizing individuals who have made significant and lasting contributions to the development of computing technologies that improve the accessibility of media and services to people with disabilities. Outstanding contributions through research, practice, or advocacy are recognized. The award recognizes members of the community for long-term accomplishments orthose who have made a notable impact througha significant innovation.
Through a nomination process this past spring, Jim Thatcher was selected as the first recipient for his pioneering work on screen readers and his continuing accessibility efforts. He will be presented with the award at the ASSETS’08 conference in Halifax this coming October.
We thank the nominating committee, Enrico Pontelli (Chair), Peter Gregor, and Helen Petrie, for their work on this inaugural award.
ASSETS Conference Updates
ASSEST’07 was held in Tempe, Arizona. Notably, conference attendees were warmly welcomed by the Arizona State University School of Computing and Informatics which hosted an evening of technology demonstrations at the university.
Two ACM Best Paper Awards were presented at the conference:
SIGACCESS Best Paper Award: Matt Huenerfauth, Liming Zhao, Erdan Gu and Jan Allbeck , The City University of New York and the University of Pennsylvania. “Evaluating American Sign Language Generation Through the Participation of Native ASL Signers”
SIGACCESS Best Student Paper Award: Karyn Moffatt and Joanna McGrenere, University of British Columbia. “Slipping and drifting: Using older users to uncover pen-based target acquisition difficulties”
For the fourth year, the conference featured an NSF sponsored Doctoral Consortium (see http://www.sigaccess.org/newsletter/sept07.php ). This consortium allowed advanced doctoral students to present their dissertation topics and receive feedback during formative stages of their work.
The conference also hosted its second Microsoft Student Research Competition (SRC) event. The SRC allows students from diverse ACM areas to present their work and get recognized for achievement. First Place at the ASSETS SRC was awarded to Jun Gong (Northeastern University); Second Place was awarded to Darren Lunn (The University of Manchester). Darren Lunn went on to compete in the ACM Student Research Competition (SRC) Grand Finals.
Finally, a SIGACCESS Business Meeting was held at ASSETS. Attendees were updated on SIG activities and discussed ideas for new activities.
Publications
The ACM Transactions on Accessible Computing (TACCESS) launched its inaugural issue in May, 2008, see http://portal.acm.org/browse_dl.cfm?linked=1&part=transaction&idx=J1156&coll=ACM&dl=ACM&CFID=75242761&CFTOKEN=83567117 TACCESSis a quarterly journal that publishes refereed articles addressing issues of computing as it impacts the lives of people with disabilities. It provides a technical forum for disseminating innovative research related to computing technologies and their use by people with disabilities. This journal is available online to SIGACCESS members.
The SIGACCESS newsletter continues with its regular online publications with its new Editor-in-Chief, Sri Kurniawan see http://www.acm.org/sigaccess/newsletter/.
Also available on the SIGACCESS website is the monthly ‘left field’ column (see http://www.acm.org/sigaccess/leftfield/) by Yeliz Yesilada. The goal of Left Field is to bring to the attention of members publications for the ACM Digital Library that are of interest, but published in venues typically outside the reading of SIGACCESS members.
Finally, a Special Issue of ACM Transactions on Computer-Human Interaction on “Computers and Accessibility” was published in September, 2007.
Developing students
A key focus for SIGACCESS is developing new researchers. The SIG has taken many steps to address this goal. In addition to the student events at ASSETS, the SIG undertook the following initiatives this past year:
The SIGACCESS website maintains repository of information about Ph.D. and Master’s theses related to assistive technologies, computer access, and the application of computing and information technology in solving relevant disability problems, see http://www.acm.org/sigaccess/phd/index.php This site can be used not only to learn about this work (sometimes in advance of its publication), but also as a resource for locating universities and faculty active in the area. Students wishing to publish their work can find an online submission form on the website.
SIGACESS participated in cooperation with the SIGCSE’08 conference. This conference on Computer Science Education had a focus on inclusive education, see http://www.cs.duke.edu/sigcse08/.
Other Activities
SIGACCESS, under the leadership of Clayton Lewis, continued to work on accessibility policy issues this year.
SIGACCESS continues to partner with National Alliance for Access to Computing Careers (AccessComputing) for the purpose of increasing the representation of people with disabilities in a wide range of computing careers,including those in computer science, information systems, software development,computer engineering, systems management and maintenance, and teaching. More information about AccessComputing can be found at http://www.acm.org/sigaccess/newsletter/june06/june06_01.php and http://www.washington.edu/accesscomputing/
SIGACCESS provided financial support for the International Cross Disciplinary Workshop on Web Accessibility 2008 (W4A) at the WWW Conference in Beijing this past May (see http://www.w4a.info/2008/ ). The workshop had the theme ‘One World, One Web: Surfers become Designers?”
SIGACT FY’08 Annual Report
July 2007 - June 2008
Submitted by: Richard E. Ladner, SIGACT Chair
1. Awards
§ Gödel Prize: Dan Spielman and Shang-Hua Teng for their paper “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time” which appeared in the Journal of the ACM (JACM), 51(3), May 2004. The result was first presented at STOC 2001. The Gödel Prize is awarded jointly by SIGACT and EATCS.
§ Knuth Prize: Awarded in Fall 2008.
§ Paris Kanellakis Theory and Practice Award: Bruno Buchberger for his role in developing the theory of Groebner Bases into a highly effective tool in computer algebra, widely used in symbolic computation systems. This award is an ACM award sponsored in part by SIGACT.
§ Edsger W. Dijkstra Prize in Distributed Computing: Cynthia Dwork, Nancy Lynch, and the late Larry Stockmeyer for the paper “Consensus in the presence of partial synchrony” which appeared in the Journal of the ACM, Vol. 35, No. 2, April, 1988. A preliminary version appeared in PODC 1984. The Dijkstra Prize is given jointly by SIGACT and SIGOPS.
§ SIGACT Distinguished Service Award: Dick Karp for many years of outstanding service to the theoretical computer science community.
§ Best Paper Award at STOC 2008: “Optimal Hierarchical Decompositions for Congestion Minimization in Networks” by Harald Räcke and “Algorithms and Inapproximability Results for Every CSP?” by Prasad Raghavendra.
§ SIGACT Danny Lewin Best Student Paper Award at STOC 2008: “Algorithms and Inapproximability Results for Every CSP?” by Prasad Raghavendra.
2. Significant papers on new areas published in proceedings
STOC 2008
The ACM Symposium on Theory of Computing (STOC 2008) covers much of computer science theory. Two award winning papers stood out at the conference. There was a great program highlighted by the best papers “Optimal Hierarchical Decompositions for Congestion Minimization in Networks” by Harald Räcke and “Algorithms and Inapproximability Results for Every CSP?” by Prasad Raghavendra. The Danny Lewin Best Student Paper Award was also given to Prasad for the same work. Program Chair Cynthia Dwork provided these summaries.
“Optimal Algorithms and Inapproximability Results for Every CSP?”
By Prasad Raghavendra
This remarkable paper, winner of the Danny Lewin Best Student Paper Award and co-winner of the Best Paper Award, makes precise the connection between the limitations of semidefinite programming (SDP) and the Unique Games Conjecture (UGC), proving that if UGC is true, then for every constraint satisfaction problem (CSP) the best approximation ratio is given by a certain simple SDP. The result holds both for maximization and minimization problems over arbitrary finite domains. The connection is then exploited to obtain a generic polynomial-time algorithm for all constraint satisfaction problems (CSPs). Assuming the Unique Games Conjecture, this algorithm achieves the optimal approximation ratio for every CSP. Unconditional results are obtained for 2-CSPs.
“Optimal Hierarchical Decompositions for Congestion Minimization in Networks”
By Harald Räcke
This co-winner of the Best Paper Award studies hierarchical graph decompositions, which play an important role in the design of approximation and online algorithms for graph problems. A hierarchical decomposition of a graph is a recursive partitioning of the node set into smaller and smaller pieces until at the lowest level of the hierarchy individual pieces only contain single vertices. Such a decomposition is naturally associated with a tree network that reflects this partitioning process and in which the leaf nodes correspond to nodes of the original graph. These types of decompositions have become a major tool for the development of approximation and online algorithms for graph problems, as they allow to approximate arbitrary undirected graphs by tree networks. These decompositions approximate point-to-point distances in the original graph. Problems can be solved on the tree and the solutions converted to solutions on the original graphs, while paying only an f = log n factor in the performance guarantee. A different type of decomposition aims at constructing a tree that does not approximate point-to-point distance, but instead approximates the cut structure of the graph in the sense that for any multicommodity flow problem in the original graph, the optimum solution of the corresponding flow problem in a decomposition tree can be converted to a solution in the original graph with a congestion that is only a factor f’ larger. The best known value for f’ was O(log2 n loglog n). The new paper constructs cut-based decompositions that reduce f’ to log n, which is asymptotically optimal. The main applications of the new decomposition are an optimal O(log n)-competitive algorithm for oblivious routing in general undirected graphs, and an O(log n)-approximation for Minimum Bisection.
SODA08
“Tight Lower Bounds for Selection in Randomly Ordered Streams” by Amit Chakrabarti and Sudipto Guha and T. S. Jayram and Mihai Patrascu
In this paper the authors provide a matching lower bound to settle a long standing conjecture by Munro and Paterson (1978) on the number of passes needed in the streaming model for computing medians in the random order model. They show that any polylog(n) space algorithm requires Ω(log log n) passes, where n denotes the length of the stream. The hardness of the problem and the structure of the proof comes from partitioning the input into p+1 parts of decreasing size and setting up a p+1 player communication game accordingly. They then show that there is a sequence of p+1 subproblems that any algorithm needs to solve (pointer chasing) and that with the limited communication dictated by the space budget no player receives enough information to make much progress with its subproblem until its turn comes (round elimination).
“Adaptive Local Ratio” by Julian Mestre
This was the best student paper at SODA 2008. This paper studies the local ratio/primal-dual techniques, two important techniques for approximation algorithm design. Mestre introduces an adaptive approach and apply his technique to design an improved approximation algorithm for the following data migration problem. A (multi-)graph is given in which the vertices correspond to disks and the (directed) edges to data items that need to be transferred from one disk to another. Each disk (vertex) can only transfer one item at any given time and each transfer takes one unit of time. Thus, any feasible solution to the data transfer problem is a legal edge coloring of the (undirected) graph. The objective is to minimizing the sum of the completion times of the vertices. There are known 3-approximation algorithms for the problem which are based on the primal-dual method, or, alternatively, on local ratio. The crucial step in a local ratio algorithm is the decomposition of the weight function w into a positive linear combination of weight functions, such as c1w1 + ...+ ckwk. In this particular application, w is decomposed into w1 + w2. Usually, w1 is a “simple” function which has the property that any minimal solution obtained recursively for w2 is also a good approximation for w1. The latter decomposition is the creative step in devising a local ratio algorithm. In the primal-dual language this step corresponds to choosing a constraint or a set of constraints. The author takes the local ratio method one step further and suggests “automizing” the decomposition step by solving a linear program at each step and finding an optimal decomposition. In primal-dual lingo this would mean generating new constraints as the algorithm proceeds. The author proves that the linear program generates a decomposition which yields an improved approximation factor of 1 + φ(golden ratio) for the data migration problem. The analysis of the linear program is non-trivial and very elegant.
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 (40th STOC), Symposium on Principles of Distributed Computing (26th PODC), Symposium on Computational Geometry (24th SOCG), and Symposium on Parallel Algorithms and Architectures (20th 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 helped launch the new ACM Transactions on Computation Theory.
SIGACT successfully nominated Shafi Goldwasser for the Athena Lecturer.
4. Innovative programs which provide service to our technical community
The Committee for the Advancement of Theoretical Computer Science (CATCS) 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. The Committee has helped advise the NSF CISE Assistant Director on several matters including recruiting for positions within CISE and restructuring the organization.
CATCS with funding from the Computing Community Consortium held the Visions for Theoretical Computer Science Workshop which consolidates theoretical research agendas into compact visions that are accessible to people outside of our field.