Appendix D
SIGACCESS FY’11 Annual Report
July 2010 - June 2011
Submitted by: Andrew Sears, Chair
SIGACCESS continues to refine its activities to meet member needs. This report highlights SIGACCESS Awards as well as the SIG’s conference, publication, and other activities.
Awards
ACM Student Research Competition (SRC)
SIGACCESS continues to conduct this competition in conjunction with the ASSETS conference. For ASSETS 2010, the winners are:
Undergraduate category:
First Place: Samuel White, University of Rochester
"AudioWiz: Nearly Real-time Audio Transcriptions"
Second Place: Timothy Walsh, University of Delaware
"Utterance-Based Systems: Organization and Design of AAC Interfaces"
Third Place: Jason Behmer, University of Washington
"LocalEyes: Accessible GPS and Points of Interest"
Graduate category:
First Place: Shiri Azenkot, University of Washington
"GoBraille: Enhancing Independence and Safety for Blind and Deaf-Blind
Public Transit Riders"
Second Place: Kristen Shinohara, University of Washington
"Investigating Meaning in Uses of Assistive Devices: Implications of
Social and Professional Contexts"
Third Place: Kyle Montague, University of Dundee
"Accessible Indoor Navigation"
ACM Grand Finals:
Third Place, Undergraduate category: Timothy Walsh, University of Delaware
"Utterance-Based Systems: Organization and Design of AAC Interfaces"
ACM SIGACCESS AWARD for Outstanding Contributions to Computing and Accessibility
The inaugural ACM SIGACCESS AWARD for Outstanding Contributions to Computing and Accessibility was awarded in 2008. 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 2010 recipient was Dr. Albert Cook of the University of Alberta, Canada. He received the award, and delivered a keynote address, at ASSETS 2010, in Orlando, Florida.
SIGACCESS Best Paper AwardJennifer Mankoff, Gillian R. Hayes, and Devva Kasnitz. 2010. Disability studies as a source of critical inquiry for the field of assistive technology. In Proceedings of the 12th international ACM SIGACCESS conference on Computers and accessibility (ASSETS '10). ACM, New York, NY, USA, 3-10. DOI=10.1145/1878803.1878807 http://doi.acm.org/10.1145/1878803.1878807
SIGACCESS Best Student Paper Award
Anne Marie Piper, Nadir Weibel, and James D. Hollan. 2010. Introducing multimodal paper-digital interfaces for speech-language therapy. In Proceedings of the 12th international ACM SIGACCESS conference on Computers and accessibility (ASSETS '10). ACM, New York, NY, USA, 203-210. DOI=10.1145/1878803.1878840 http://doi.acm.org/10.1145/1878803.1878840
SIGACCESS Scholarship in Computers and Accessibility
The SIGACCESS Scholarship Award aims to provide support for participation in the ASSETS conference for individuals who would not otherwise be able to attend. Practitioners, researchers, members of advocacy groups, or individuals with disabilities are eligible to apply. Applicants must have a demonstrated interest in accessible computing. Awardees will have the opportunity to actively participate in the ASSETS conference and gain experience and knowledge from interacting with experts in the field. The scholarship award is in the amount of $2,000. SIGACCESS awards up to two scholarships per year, pending availability of funds. The first two scholarships were awarded to Makayla Miranda Lewis and Michelle Burton to attend ASSETS 2010.
Supporting ACM-W Scholarships
Beginning with ASSETS 2010, SIGACCESS now supports the ACM-W Scholarship program by providing a complimentary registration to ACM-W Scholarship recipients. For ASSETS 2010, SIGACCESS provided a complimentary registration for Renata Cristina Barros Madeo.
SIGACCESS Impact Award
SIGACCESS has proposed a new award that was approved by ACM in June. The intent of this award is to recognize one paper, every other year, which was published/presented at the annual ASSETS Conference at least ten years earlier and that is considered to have had a significant impact on the field. This award will be given in odd numbered years, alternating with the Outstanding Contribution award mentioned above, starting in 2011.
Significant Programs
ASSETS Conference
ASSETS’10 was held in Orlando, FL. Once again, conference attendance exceeded projections, with over 130 attendees. Submissions for the technical program were received from Brazil, Canada, Chile, China, Ecuador, Finland, Germany, India, Ireland, Italy, Japan, Malaysia, the Netherlands, New Zealand, Portugal, South Korea, Spain, Switzerland, Taiwan, Thailand, Tunisia, the United Kingdom, and the United States. The papers accepted for inclusion in the technical program addressed a broad range of issues including non-visual access, issues involved in evaluating accessibility, sign language, accessible education, supporting mobility and communication, and various other topics.
Once again, the conference featured an NSF sponsored Doctoral Consortium (see http://www.sigaccess.org/community/newsletter/january_2011/jan11_all.pdf). This consortium allowed doctoral students to present their dissertation topics and receive feedback during formative stages of their work. The conference also hosted a Microsoft Student Research Competition (SRC) event (see information about the winners of the competition above).
The SIGACCESS Business Meeting, held at ASSETS, updated attendees on SIG activities and discussed ideas for new activities. The idea of holding ASSETS in another country has been discussed for several years, leading to ASSETS 2011 being held in Dundee, Scotland. There was also continued discussion of supporting workshops or other smaller events that were more focused with regard to topic or geographical location.
ACM Transactions on Accessible Computing The inaugural issue of the ACM Transactions on Accessible Computing (TACCESS) appeared in May, 2008. Volume one included three issues, with volumes two and three both including the full set of four issues. The number of submissions continues to grow. 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.
The SIGACCESS newsletter continues with its regular online publications: see http://www.sigaccess.org/community/newsletter/. Jinjuan Feng (Towson University) has served as the Newsletter Editor since June, 2010.
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.
SIGACCESS Website
The SIGACCESS website was created and maintained by the SIGACCESS webmaster, Darren Lunn of the University of Manchester. Darren Lunn stepped down in February 2011 with Jeffrey Bigham (University of Rochester) assuming these responsibilities at that time. The SIGACCESS web site provides information about the SIG’s activities including awards and conferences as well as a repository of dissertations and theses, our newsletter, the “Left Field” column, writing guidelines, and other resources which may be of value to the community.
Innovative programs
SIGACCESS has developed several resources which are made available to the community at large via the SIGACCESS web site. The first is a set of writing guidelines which reflect current thinking on language for writing in the academic accessibility community. Certain words or phrases can (intentionally or unintentionally) reflect bias or negative, disparaging, or patronizing attitudes toward people with disabilities and in fact any identifiable group of people. Choosing language that is neutral, accurate, and represents the preference of the groups to which it refers can convey respect and integrity. The second resource is a guide for planning accessible conferences. This document contains information for organizers of academic conferences who wish to make their events as accessible as possible, so that people with disabilities can participate fully.
Key Issues
Moving forward, there are a number of issues that SIGACCESS must address including developing future leaders for the community and continuing our efforts to reach new audiences. The SIG is actively engaged in developing leaders, recruiting new members of the community to participate both in the conference organizing committee and in other SIG activities. To reach new audiences, and become a more international organization, the SIG has once again arranged for ASSETS to be held in Europe. Assuming this is successful, we anticipate holding ASSETS outside of the US more frequently. We also continue to explore the idea of organizing workshops in addition to the annual ASSETS conference. One workshop was co-located with ASSETS 2010 and was successful. This model is likely to be repeated for ASSETS 2011. Additional workshops, reaching new communities, will continue to be on the agenda in the future.
SIGACT FY’11 Annual Report
July 2010 - June 2011
Submitted by: Lance Fortnow, Chair
1. Awards
§ 2011 Gödel Prize: Johan T. Håstad for his paper: Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001.
o The prize is awarded jointly with the EATCS and this year was awarded at the STOC conference during FCRC.
§ 2011 Knuth Prize: Ravi Kannan for his work on algorithmic techniques that have fundamentally contributed to computational complexity, discrete mathematics, geometry, and operations research.
o The prize is awarded jointly with IEEE-CS TCMFCS and this year was awarded at the STOC conference during FCRC. Ravi Kannan presented his Knuth Prize lecture as an FCRC plenary lecture.
§ 2010 Paris Kanellakis Theory and Practice Award: Kurt Mehlhorn for contributions to algorithm engineering by creating the LEDA library for algorithmic problem solving". This award is an ACM award sponsored in part by SIGACT.
§ STOC 2011 Best Paper Award: ``Subexponential lower bounds for randomized pivoting rules for solving linear programs'' by Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick and ``Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs'' by Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng.
§ Danny Lewin Best Student Paper Award (STOC 2011): ``Analyzing Network Coding Gossip Made Easy'' by Bernhard Haeupler
§ SIGACT awarded approximately thirty student travel awards to allow these students to attend the 2011 STOC conference.
2. Significant papers on new areas published in proceedings
With help from PC Chairs Salil Vadhan (STOC), Dana Randall (SODA) and Pierre Fraigniaud (PODC). Prasad Raghavendra and Shuchi Chawla also helped with the SODA papers.
STOC 2011
The ACM Symposium on Theory of Computing (STOC 2011) is one of the flagship conferences for theoretical computer science, bringing together researchers from a variety of different subfields.
One of the Best Paper Awards at STOC went to the paper ``Subexponential lower bounds for randomized pivoting rules for solving linear programs'' by Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick. This paper concerns simplex algorithms, which are some of the most widely used algorithms for solving linear programs in practice. A simplex algorithm is obtained by iterating a pivoting rule, which determines how one selects among the neighboring improvements to a basic feasible solution to the linear program. While most deterministic pivoting rules have long been known to require an exponential number of iterations in the worst case, it was open whether randomized pivoting rules require a superpolynomial number of iterations. This paper provides the first such bounds, showing that two of the most natural and well-studied randomized pivoting rules require a subexponential number of iterations. Interestingly, the lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games.
The other Best Paper Award at STOC went to the paper ``Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs'' by Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. This paper introduces a new approach to two of the most fundamental and long-studied computational problems --- maximum flows and minimum cuts --- by reducing them to a sequence of electrical flow problems, each of which can be approximately solved in nearly linear time. Using this approach, the paper provides the fastest known algorithms for computing approximately maximum s-t flows and approximately minimum s-t cuts in capacitated, undirected graphs, the first improvements in roughly a decade.
The Best Student Paper Award at STOC went to the paper ``Analyzing Network Coding Gossip Made Easy'' by Bernhard Haeupler. This paper is about random linear network coding (RLNC), which is a widely studied technique for multicasting with a high rate of information dissemination. Haeupler's paper introduces a new analysis technique that drastically simplifies, extends and strengthens previous results on RLNC. It shows that, in most settings, RLNC completes with high probability in time O(k + T) where k is the number of messages to be distributed and T is the time it takes to disseminate one message. This is information-theoretically optimal, and means that RLNC achieves ``perfect pipelining''. The key to the new analysis is a simple but very counterintuitive measure of what a node ``knows'' at a given point in the protocol.
SODA 2010
SODA is a major conference that focuses on algorithms and combinatorics.
Best Paper: An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
Nir Ailon, Technion Israel Institute of Technology, Israel and Edo Liberty, Yahoo! Research, Israel
Several forms of data such as images, videos or text documents are often represented geometrically as high-dimensional vectors. Clearly, computational tasks on these high dimensional vectors can be carried out efficiently, if one can reduce the dimension of these high-dimensional representations while preserving the metric properties such as pairwise distances.
In a seminal work in early 1980s, Johnson and Lindenstrauss showed that random linear projections into a small dimensional space would suffice to preserve pairwise distances. This dimension reduction technique often referred to as simply ``JL transform" or ``random projections" has tremendous applications in algorithms. The complexity of this transformation has received much attention recently and computationally efficient versions of the JL transform have emerged starting with the work of Ailon and Chazelle in 2006. These fast JL mappings have found applications to both practical and theoretical algorithms for the approximate nearest neighbor search, regression, singular value decomposition, and other high-dimensional geometric problems.
This work exhibits the fastest, near-optimal algorithm for the JL-transform. To this end, the paper borrows technical machinery from the work on the compressed sensing problem by Rudelson and Vershaynin.
Best Student Paper (shared): An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter
Shay Solomon, Ben-Gurion University of the Negev, Israel
Given a set of points in a Euclidean space (real d-dimensional space), a spanner is a sparse graph on these points that encodes all the distance information of these points. More precisely, the Euclidean distance between any pair of points is approximately equal to the total Euclidean length of the shortest path between them in the graph. In a sense, Euclidean spanners are a sparse approximation to the complete graph with weights equal to the Euclidean distances between the points. Euclidean spanners have found applications in geometric approximation algorithms, network topology design geometric distance oracles and numerous other contexts.