Appendix D
SIGACCESS FY’09 Annual Report
July 2008 - June 2009
Submitted by: Vicki L. Hanson, Past Chair and Andrew Sears, Chair
SIGACCESS continues to expand its membership and activities to meet member needs. This report highlights SIGACCESS Awards as well and the SIG's conference, publication, and other activities.
Awards
ACM Student Research Competition (SRC)
First Place in this competition was awarded to Xu Liu. ASSETS'08 SRC winners competed in the ACM-wide SRC. Across all ACM SIGs and conferences participating, Xu was awarded first place in the Graduate Student Category for his paper "Mobile Currency Reader for People with Visual Impairments." He was invited to the ACM Awards ceremony in San Diego in June where the award was announced. For more information, see http://www.acm.org/src/
This is a tremendous honor for Xu. In addition, SIGACCESS is pleased that this is the second time in the past few years that the ASSETS SRC has produced the ACM 1st Place Winner. The previous recipient of this prize was Eugene Borodin in 2007.
ACM SIGACCESS AWARD for Outstanding Contributions to Computing and Accessibility
Two years ago the ACM SIGACCESS Award for Outstanding Contributions to Computing and Accessibility was created. The award, given every other year, recognizes 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 or those who have made a notable impact through a significant innovation. The inaugural award was presented in 2008 to Jim Thatcher. Nominations to begin the 2010 award process will be announced shortly.
2008 SIGACCESS Best Paper Award
Feng, J., Lazar, J., Kumin, L., and Ozok, A. 2008. Computer usage by young individuals with down syndrome: an exploratory study. In Proceedings of the 10th international ACM SIGACCESS Conference on Computers and Accessibility (Halifax, Nova Scotia, Canada, October 13 - 15, 2008). Assets '08. ACM, New York, NY, 35-42. DOI= http://doi.acm.org/10.1145/1414471.1414480
2008 SIGACCESS Best Student Paper Award
Borodin, Y., Bigham, J. P., Raman, R., and Ramakrishnan, I. V. 2008. What's new?: making web page updates accessible. In Proceedings of the 10th international ACM SIGACCESS Conference on Computers and Accessibility (Halifax, Nova Scotia, Canada, October 13 - 15, 2008). Assets '08. ACM, New York, NY, 145-152. DOI= http://doi.acm.org/10.1145/1414471.1414499
ASSETS Conference
ASSEST'08 was held in Halifax, Nova Scotia, Canada. This was the first time ASSETS has been held outside the US since 2002. Conference attendance was excellent, exceeding attendance projections. Particularly notable was that the conference continues to expand areas of research, with a number of cognitive issues represented in this year's papers. This broadening of research interests attests to the growing importance of considering the needs of a diverse population.
For the fifth year, the conference featured an NSF-sponsored Doctoral Consortium (see http://www.sigaccess.org/news/2009/03/january-2009-sigaccess-newsletter-now.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 third Microsoft Student Research Competition (SRC) event. The SRC allows students from diverse ACM areas to present their work and get recognized for achievement. Award winners were:
1st Prize: Keith Trnka, University of Delaware, for 'Adapting word prediction to subject matter without topic-labeled data'
2nd Prize: Xu Liu, University of Maryland, for 'A Camera Phone Based Currency Reader for the Visually Impaired'
3rd Prize: Mohammed Hoque, MIT, for 'Analysis of Speech Properties of Neurotypicals and Individuals Diagnosed with Autism and Down Syndrome'
The SIGACCESS Business Meeting held at ASSETS updated attendees on SIG activities and discussed ideas for new activities. Key issues included accessibility of publications in the ACM Digital Library. Specifically, it was considered important to work with ACM to ensure that ASSETS Proceedings are accessible.
Publications
The inaugural issue of the ACM Transactions on Accessible Computing (TACCESS) appeared in May, 2008. Since May, four additional issues have been published. See http://portal.acm.org/toc.cfm?id=J1156&type=periodical&coll=ACM&dl=ACM&CFID=43106710&CFTOKEN=53985827 for details. TACCESS is 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 Sri Kurniawan, Editor-in-Chief, see http://www.sigaccess.org/community/newsletter/.
Also available on the SIGACCESS website is the monthly 'left field' column (see http://www.sigaccess.org/community/left_field/) by Yeliz Yesilada. The goal of Left Field is to bring to the attention of members publications from the ACM Digital Library that are of interest, but published in venues typically outside the reading of SIGACCESS members.
In Cooperation Conferences
SIGACCESS provided financial support for the International Cross Disciplinary Workshop on Web Accessibility 2009 (W4A) at the WWW Conference in Madrid this past April (see http://www.w4a.info/2009/).
SIGACCESS Website
The SIGACCESS website recently received a new look. This accessible site was created and is maintained by the new SIGACCESS webmaster, Darren Lunn of the University of Manchester.
In Memoriam
We note the passing on April 11 of our friend and colleague Noelle Carbonell. Those of you who knew her personally know of her great humanity, keen intellect, and dedication to high quality work. As Secretary-Treasurer of SIGACCESS these past three years she was a staunch advocate for people with disabilities and was a strong advocate for international cooperation on research in this area. We will greatly miss her energy and passion.
SIGACT FY’09 Annual Report
July 2008 - June 2009
Submitted by: Richard E. Ladner, Past Chair
1. Awards
§ 2009 Gödel Prize: For “Entropy waves, the zig-zag graph product and new constant degree expanders,” Omer Reingold, Salil Vadhan and Avi Wigderson, Annals of Mathematics, Vol 155, (2002), 157-187 and “Undirected connectivity in Log-Space,” Omer Reingold, Journal of ACM, Vol 55 (4) (2007).
§ Knuth Prize: Volker Strassen for his seminal and influential contributions to efficient algorithms. The Knuth Prize is given jointly by SIGACT and IEEE TCMFCS.
§ Paris Kanellakis Theory and Practice Award: Corinna Cortes and Vladimir Vapnik for their development of Support vector machines. This award is an ACM award sponsored in part by SIGACT.
§ Edsger W. Dijkstra Prize in Distributed Computing: Baruch Awerbuch and David Peleg for their paper “Sparse partitions” in the Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990). The Dijkstra Prize is given jointly by SIGACT and SIGOPS.
§ SIGACT Distinguished Service Award: To be awarded in 2010.
§ Best Papers Award at STOC 2009: Chris Peikert for “Public-key cryptosystems from the worst-case shortest vector problem” and Robin Moser for “A constructive proof of the Lovász local lemma.”
§ SIGACT Danny Lewin Best Student Paper Award at STOC 2009: Robin Moser for “A constructive proof of the Lovász local lemma.”
2. Significant papers on new areas published in proceedings
This second was prepared with help from Michael Mitzenmacher, Claire Mathieu, and Boaz Patt-Shamir, program chairs of STOC 2009, SODA 2009, PODC 2008, respectively.
STOC 2009
The ACM Symposium on Theory of Computing (STOC 2009) covers much of computer science theory.
Chris Peikert’s best paper at STOC 2009 represents a major advance in cryptography. In 1997 Ajtai published a breakthrough result: one-way functions based on the assumption that approximations for the shortest vector problem (SVP) in an integer lattice are intractable (for any lattice). One-way functions are the most basic building block in cryptography, as they yield commitment protocols and digital signatures. However, they do not yield full public-key encryption schemes. Thus, an obvious question emerged: base a public-key encryption scheme on the difficulty of approximating the size of the shortest vector. A year later Ajtai-Dwork in 1998 did base a public-key encryption scheme the worst case unique-SVP approximation problem. The unique-SVP problem is a special case of the general SVP problem and it was clear that this is a first result on the way to the general case. Can you build a public key cryptosystem based on the worst case difficulty of SVP? This has been open since 1998. Peikert finally resolves this question. His technique utilizes a clever reduction from the worst case of case SVP to learning with errors. Additionally, his stronger proof is simpler and more direct than previous works.
Robin Moser’s Best Paper and Best Student Paper at STOC 2009 represents a new and constructive way to find satisfying instances of complex satisfiable formulas. The Lovasz Local Lemma (LLL) provides a tool for showing the probability a set of events happens, even when there are non-trivial dependencies among the events. As an example, the LLL implies that any k-CNF formula in which each clause shares variables with at most 2k-2 other clauses is satisfiable. However, the proof is nonconstructive. This paper shows how to give an efficient algorithm that constructs the solution for such a problem. The proposed algorithm uses a drastically different approach from previous similar attempts and is extremely simple. The algorithm starts with a random assignment and tries to satisfy any violated clauses using local changes. If this procedure takes too long the algorithm simply chooses a new random assignment and starts again. The paper is elegant, both in terms of its algorithm and analysis. It promises to increase the applicability and the utility of the LLL throughout the fields of probability and randomized algorithms.
SODA 2009
SODA is a major conference that focuses on algorithms and combinatorics.
Bernard Chazelle’s Best Paper at SODA 2009, “Natural Algorithms,” analyzes the convergence of flocking algorithms. A flocking model consists of a set of entities that adapt their behavior depending on other entities in their neighborhood. In a discrete time version, the behavior is adapted in the next time step. Flocking comes down to the behavior that an entity will adapt its velocity by taking the velocities of entities nearby into account (basically, by averaging). This paper uses techniques from the analysis of algorithms to analyze convergence of models for flocking. The neighborhood of an entity (bird) is defined as the other birds within unit distance. For one recent model, the Cucker-Smale flocking model, convergence time is proved, with an upper bound on the number of time steps that is some tower-of-twos in the input size. A lower bound on convergence time is also given, again with a (much shorter) tower-of-twos. This analysis is from a point of view that control theorists have not looked at, when analyzing models of coordinated motion. It is a very fresh and welcome view of this style of algorithm.
Gabriel Nivasch’s Best Student Paper at SODA 2009, “Improved Bounds and New Techniques for Davenport-Schinzel Sequences and Their Generalizations”
Davenport-Schinzel sequences are fundamental to the analysis of a variety of geometric algorithms and their outputs: Davenport-Schinzel sequences appear in bounds for the complexity of lower envelopes of line segments, of the graphs of simple functions, of single faces of arrangements, of geometric partitions in higher dimensions, of transversals. An (n,s) Davenport-Schinzel sequence is a sequence of symbols (alphabet size n) that has no subsequences isomorphic to ababa... (length s+2). What is the maximum length of an (n,s) Davenport-Schinzel sequence? Although the paper is technical, it simplifies or improves all previous upper and lower bounds, comes up with a simplified construction, and obtains in several cases very nice definitive results (exact asymptotics for Davenport-Schinzel sequences of order 3, correct exponent for growth of Davenport-Schinzel sequences for even s). The best part of the results is their comparative simplicity. It will be a landmark for the experts on the topic.
PODC 2008
PODC is a major conference that focuses on the theory of distributed computing.
Armando Castañeda and Sergio Rajsbaum’s Best Student Paper Award for PODC 2008 “New Combinatorial Topology Upper and Lower Bounds for Renaming” reexamines the well known renaming problem. This paper throws surprising light on the central problem of Renaming. Specifically, it is shown that contrary to previous belief, there are some special values of n such that wait-free renaming of n processors into [1,...,k] names is possible for k < 2n-1. The paper goes on to characterize the precise set of numbers n for which renaming n processors into [1,...,k] names requires k ≥ 2n-1. Thus, using combinatorial topology analysis, the paper extends our understanding of the foundations of asynchronous distributed systems.
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 (41st STOC), Symposium on Principles of Distributed Computing (27th PODC), Symposium on Computational Geometry (25th SOCG), Symposium on Parallel Algorithms and Architectures (21st SPAA), and Symposium on Discrete Algorithms (19th SODA). SIGACT also supports several conferences in-cooperation including Symposium on Principles of Database Systems (PODS), Symposium on Foundations of Computer Science (FOCS), Symposium on Principles of Programming Languages (POPL).
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 to 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.
A new Ad Hoc Committee on STOC has been formed chaired by Shafi Goldwasser and Richard Ladner with the goal of finding alternatives to ensure that STOC continues to welcome interesting, path breaking submissions, regardless of whether or not they are mathematically hard. More generally, the committee's charge is to explore alternatives that allow SIGACT to continue to publish contributions that introduce new topics, approaches, frameworks, and techniques to our field, without creating a new conference. A report from the Committee will be given to the SIGACT Executive Committee for possible action.