Students with disabilities face a variety of challenges in computer science education including those related to inaccessible curriculum, instruction and tools. In addition, few computer science classes teach students to understand accessibility and design accessible technology. This BOF will bring together individuals who are interested in increasing the accessibility of computing education as well as those interested in teaching about accessibility. Participants will share strategies to help each other do a better job of addressing accessibility in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, teaching accessibility, and more will be shared.

Most software in the world is not accessible to people with disabilities, in part because most people who create software do not know how to make it accessible. Using the new free online book Teaching Accessible Computing, participants in this special session will learn how they can incorporate accessibility topics into their favorite CS courses, like introductory programming, data structures, or artificial intelligence courses. The editors of the book will lead the special session, and several authors of the book's 17 chapters will talk about their chapters and lead topic groups to go into more depth about how they incorporated accessibility into their CS courses. Participants will leave this session with increased enthusiasm and concrete resources to support teaching accessibility in their CS topic courses, establishing connections to the broader community of CS educators and researchers interested in teaching accessibility.

Disability culture celebrates the diversity disability brings.Its consideration of the positive aspects of the disability experience (community, solidarity, creativity) offers a contrast to many other framings of disability.Disability culture thus has the potential to deepen understandings of accessibility and inform approaches to the design and research of accessibility technologies.To explore this potential, we begin by presenting a preliminary synthesis of disability culture for the accessibility research community, based on works of disability studies scholars and activists.We highlight cultural processes of finding community and building solidarity, valuing disabled agency and knowledge, and rejecting ableist norms.To see how these cultural aspects might inform accessibility technology design, we studied accessibility technologies made by disabled people for disabled people -interviewing disabled innovators who had created and disseminated accessibility technologies.We asked these innovators to share their stories and reflect on goals and values they imbued in their innovations.We analyzed how cultural themes of belonging, knowledge, and creativity influenced their work.Our work highlights the potential of a cultural lens in aligning accessibility technology with disabled people's values as well as unearthing new directions for inquiry for the field.

A growing body of research investigates how to make captioning experiences more accessible and enjoyable to disabled people. However, prior work has focused largely on English captioning, neglecting the majority of people who are multilingual (i.e., understand or express themselves in more than one language). To address this gap, we conducted semi-structured interviews and diary logs with 13 participants who used multilingual captions for accessibility. Our findings highlight the linguistic and cultural dimensions of captioning, detailing how language features (scripts and orthography) and the inclusion/negation of cultural context shape the accessibility of captions. Despite lack of quality and availability, participants emphasized the importance of multilingual captioning to learn a new language, build community, and preserve cultural heritage. Moving toward a future where all ways of communicating are celebrated, we present ways to orient captioning research to a language justice agenda that decenters English and engages with varied levels of fluency.

Students with disabilities face a variety of challenges in computer science education including those related to stigma around disability, inaccessible curriculum, instruction and tools, disability disclosure, and a lack of mentors. In addition, few computer science classes teach students to understand accessibility and design accessible technology. This BOF will bring together individuals who are interested in increasing the representation of people with disabilities in computing and improving their success as well as those interested in teaching about accessibility. Participants will share strategies to help each other do a better job of addressing disability inclusion and accessibility in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, teaching accessibility, and more will be shared.

Little research has examined the aspects of PMs’ use among individuals who are blind or visually impaired (BVI) who face extra challenges while entering credentials, such as low typing rates, low typing accuracy, shoulder surfing attacks, and verification of the entered data. This paper explores how knowledgeable BVI individuals are of digital security threats; the status of accessibility in security software; awareness of PMs among BVI; and the factors that drive rejection or adoption of PMs. Our findings revealed that the self-reported knowledge of digital security threats is high; there are many accessibility shortcomings in various security software; and the awareness of PMs among BVI individuals is relatively high, although actual use is far less. About 1/4-th of the participants in the study who tried using PMs rejected them. We found that inaccessibility, cross-platform differences, and security concerns as the top rejection factors. By contrast, convenience, effort saving, and accuracy were the primary adoption factors.

Students with disabilities face a variety of challenges in computer science education including those related to stigma around disability, inaccessible curriculum, instruction and tools, disability disclosure, and a lack of mentors. In addition, few computer science classes teach students to understand accessibility and design accessible technology. This BOF will bring together individuals who are interested in increasing the representation of people with disabilities in computing and improving their success as well as those interested in teaching about accessibility. Participants will share strategies to help each other do a better job of addressing disability inclusion and accessibility in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, teaching accessibility, and more will be shared.

The introduction of block-based programming has gradually changed the landscape of programming education, particularly for school children. Block languages today, however, have serious technical barriers to students with disabilities. For example, block languages are generally not screen reader accessible, incompatible with braille, and contain serious problems for users with motor impairments. No student with a disability should ever be denied access to learning computer science and they do not have to be. To help rectify this, we present a new approach to the design of block languages called Quorum Blocks. Quorum Blocks uses a custom hardware accelerated graphical rendering pipeline that takes into account how screen readers and other devices work under the hood. We discuss these technical details and demonstrate that accessibility support can be fully achieved without meaningfully losing either the look of modern blocks or their visual output. We present the results from focus groups that highlight the barriers students faced with a variety of disabilities when using the first version of Quorum Blocks. We focus especially on challenges with low vision users, screen reader users, or those using no mouse and only one hand to type. Block languages built using either our techniques, or on top of our libraries, would become accessible out of the box.

Millions of Deaf and hard-of-hearing (DHH) people primarily use a sign language for communication, but there is a lack of adequate sign language interpreting to fill these communication needs. Development of automatic sign language translation (ASLT) systems could help translate between a sign language and spoken language in situations where human interpreters are unavailable, and recent advances in large multi-lingual language models may soon enable ASLT to become a reality. Despite the potential for ASLT, Deaf community perspectives on and requirements for such technologies are poorly understood. In this work, we conduct a survey of Deaf community perspectives in the U.S. on ASLT in order to inform the development of ASLT systems that meet user needs and minimize harms. Our results shed light on scenarios where DHH users in the U.S. might want to use ASLT, their performance expectations for ASLT in these scenarios, design preferences for ASLT interfaces, and the benefits and harms they see in the development of ASLT.

Speechreading is the art of using visual and contextual cues in the environment to support listening. Often used by d/Deaf and Hard-of-Hearing (d/DHH) individuals, it highlights nuances of rich communication. However, lived experiences of speechreaders are underdocumented in HCI literature, and the impact of online environments and interactions of captioning with speechreading has not been explored in depth. We bridge these gaps through a three-part study consisting of formative interviews, design probes, and design sessions with 12 d/DHH individuals who speechread. Our primary contribution is to understand the lived experience of speechreading in online communication, and thus to better understand the richness and variety of techniques d/DHH individuals use to provision access. We highlight technical, environmental and sociocultural factors that impact communication accessibility, explore the design space of speechreading supports and share considerations for the design future of speechreading technology.

Sign languages are used as a primary language by approximately 70 million D/deaf people world-wide. However, most communication technologies operate in spoken and written languages, creating inequities in access. To help tackle this problem, we release ASL Citizen, the first crowdsourced Isolated Sign Language Recognition (ISLR) dataset, collected with consent and containing 83,399 videos for 2,731 distinct signs filmed by 52 signers in a variety of environments. We propose that this dataset be used for sign language dictionary retrieval for American Sign Language (ASL), where a user demonstrates a sign to their webcam to retrieve matching signs from a dictionary. We show that training supervised machine learning classifiers with our dataset advances the state-of-the-art on metrics relevant for dictionary retrieval, achieving 63\% accuracy and a recall-at-10 of 91\%, evaluated entirely on videos of users who are not present in the training or validation sets.

Students with disabilities face a variety of challenges in computer science education including those related to stigma around disability, inaccessible tools and instruction, disability disclosure, and a lack of mentors. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, and more will be shared.

Audio description (AD), an additional narration track that conveys visual information in media, improves video accessibility for blind or low vision (BLV) viewers. Despite being the primary beneficiaries of AD, BLV audiences are limited in how they can contribute to the AD writing process due to technology inaccessibility and societal biases. In this poster, we (1) prototype and test AccessibleAD, an accessible AD writing system, (2) analyze what context and features are valued by BLV description writers, and (3) explore nonvisual involvement in AD creation. This work expands on existing literature regarding audio description and explores best practices for expanding access to AD writing.

Students with disabilities face a variety of challenges including those related to stigma around disability, inaccessible tools and instruction, disability disclosure, and a lack of mentors. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, and more will be shared.

Although the number of blind or low vision (BLV) software developers is the largest minority population of developers with physical disabilities, they are often marginalized in mainstream online programming communities. We studied how BLV developers engage with a BLV-specific programming community called Program-L, by exploring the help-seeking behaviors of novices. We analyzed 173 messages written by 20 novices over a 4-year period and identified the kinds of help they asked for and their justifications for requesting that help. We learned that self disclosure, practical assistance, and community dynamics were all critical activities to support four types of novices: community, domain, programming, and accessibility. The findings of our work give insight into what support can look like for online communities for marginalized software developers.

Students with disabilities face a variety of challenges including those related to stigma around disability, inaccessible tools and instruction, disability disclosure, and a lack of mentors. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, and more will be shared.

Computing students with disabilities face a variety of difficulties in computing education and careers including inaccessible technology, difficulty arranging accommodations, attitudinal barriers, and a lack of mentors. This panel of computing students and recent graduates with disabilities will describe their experiences both in and out of the classroom. The goal is to provide the audience with an opportunity to hear first-hand how their educational needs were met as non-traditional computing students. In addition to the panelists' short presentations, the moderator will facilitate a dialog between the members of the audience and the panelists.

This panel will provide practical advice on what and how to teach accessibility in a variety of settings. In this context, teaching accessibility means teaching about computer technologies that people with various disabilities can use and be productive with. At the undergraduate level it could mean teaching about how to design and build accessible web sites and applications. At the graduate level it could be teaching about building applications that can help people with disabilities with specific tasks. An entire course could focus on accessibility or it could be just part of an existing course. It is also important to learn about the diversity of consumers of technologies: what their abilities are and what access infrastructures they use every day. All the panelists have extensive experience in teaching accessibility. They will provide the audience of the panel deep insights into what they might do to teach accessibility in their own courses.

Approximately 10% of computer science and engineering majors have a disability. Students with disabilities face a variety of challenges including those related to stigma around disability, inaccessible tools and instruction, disability disclosure, and a lack of mentors. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources related to accessible tools and instruction, universal design of learning, opportunities for students, and more will be shared.

A digital calculator is one of the most frequently used touch screen applications. However, keypad-based character input in existing calculator applications requires precise, targeted key presses that are time-consuming and error-prone for many screen readers users. We introduce GestureCalc, a digital calculator that uses target-free gestures for arithmetic tasks. It allows eyes-free target-less input of digits and operations through taps and directional swipes with one to three fingers, guided by minimal audio feedback. We conducted a mixed methods longitudinal study with eight screen reader users and found that they entered characters with GestureCalc 40.5% faster on average than with a typical touch screen calculator. Participants made more mistakes but also corrected more errors with GestureCalc, resulting in 52.2% fewer erroneous calculations than the baseline. Over the three sessions in the study, participants were able to learn the GestureCalc gestures and efficiently perform short calculations. From our interviews after the second session, participants recognized the effort in learning a new gesture set, yet reported confidence in their ability to become fluent in practice.

Keypad-based character input in existing digital calculator applications on touch screen devices requires precise, targeted key presses that are time-consuming and error-prone for many screen reader users. We demonstrate GestureCalc, a digital calculator that uses target-free gestures for arithmetic tasks. It allows eyes-free target-less input of digits and operations through taps and directional swipes with one to three fingers, guided by minimal audio feedback. A study of the effectiveness of GestureCalc for screen reader users appears in a full paper by the authors at this conference.

The use of technology in educational settings is extremely common. For many visually impaired children, educational settings are the first place they are exposed to the assistive technology that they will need to access mainstream computing devices. Current laws provide support for students to receive training from Teachers of the Visually Impaired (TVIs) on these assistive devices. Therefore, TVIs play an important role in the selection and training of technology. Through our interviews with TVIs, we discovered the factors that impact which technologies they select, how they attempt to mitigate the stigma associated with certain technologies, and the challenges that students face in learning assistive technologies. Through this research, we identified three needs that future research on assistive technology should address: (1) increasing focus on built-in accessibility features, (2) providing support for independent learning and exploration, and (3) creating technologies that can support users with progressive vision loss.

As diversity efforts in computer science begin to recognize disabled programmers as an underrepresented group, we step back to chronicle the experiences of blind programmers in higher education. Through a survey and follow-up interviews with 10 blind programmers, we share reflections and barriers important for the computing education community to understand as we attempt to welcoming cultures for disabled programmers. Our findings illuminated a variety of barriers blind programmers faced in college and the impact that they had on their ability to succeed in the field. We found that barriers permeate all parts of these blind student's' education from accessing the materials and doing the homework to working with professors. These barriers increased feelings of the isolation, decreased motivation especially when tasks were inaccessible, and prevented them from learning all the concepts covered in their degree program.

Approximately 10% of computer science and engineering majors have a disability. Students with disabilities are more likely to drop out of the major than those without disabilities. At the K-12 level, many tools used to teach computing have limited accessibility to students with disabilities. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources, including those produced by AccessComputing and AccessCSforAll, will be shared.

Block-based programming environments such as Scratch are designed to make programming easier to learn for both children and adults. Unfortunately, these environments rely so heavily on visual features that they are inaccessible to people who are blind and use screen readers. To address this problem, we created Blocks4All, a block-based environment for the Apple iPad, which uses the touchscreen and VoiceOver, the built-in screen reader for iOS, to help make the environment accessible. Blocks4All differs from existing block-based environments in three main ways: (1) it uses select, select, drop instead of drag and drop to move blocks, (2) the blocks are placed on the bottom of the screen and are a fixed size so that they can easily be found by touch even without sight, and (3) it uses both audio and spatial cues to convey information about statements nested inside repeat loops and conditionals. In our presentation, we will show the features we developed and demonstrate how to write code that uses both conditional statements and repeat loops. We anticipate the demo will be useful both for instructors with students with visual impairments and developers of block-based environments. Handouts will be provided that describe Blocks4All and information about how to download a beta version.

The College Board's AP Computer Science Principles (CSP) content has become a major new course for introducing K-12 students to the discipline. The course was designed for many reasons, but one major goal was to broaden participation. While significant work has been completed toward equity by many research groups, we know of no systematic analysis of CSP content created by major vendors in relation to accessibility for students with disabilities, especially those who are blind or visually impaired. In this experience report, we discuss two major actions by our team to make CSP more accessible. First, with the help of accessibility experts and teachers, we modified the entire Code.org CSP course to make it accessible. Second, we conducted a one-week professional development workshop in the summer of 2018 for teachers of blind or visually impaired students in order to help them prepare to teach CSP or support those who do. We report here on lessons learned that are useful to teachers who have blind or visually impaired students in their classes, to AP CSP curriculum providers, and to the College Board.

Sign languages lack a standard written form, preventing millions of Deaf people from accessing text in their primary language. A major barrier to adoption is difficulty learning a system which represents complex 3D movements with stationary symbols. In this work, we leverage the animation capabilities of modern screens to create the first animated character system prototype for sign language, producing text that combines iconic symbols and movement. Using animation to represent sign movements can increase resemblance to the live language, making the character system easier to learn. We explore this idea through the lens of American Sign Language (ASL), presenting 1) a pilot study underscoring the potential value of an animated ASL character system, 2) a structured approach for designing animations for an existing ASL character system, and 3) a design probe workshop with ASL users eliciting guidelines for the animated character system design.

As conversational agents and digital assistants become increasingly pervasive, understanding their synthetic speech becomes increasingly important. Simultaneously, speech synthesis is becoming more sophisticated and manipulable, providing the opportunity to optimize speech rate to save users time. However, little is known about people's abilities to understand fast speech. In this work, we provide the first large-scale study on human listening rates. Run on LabintheWild, it used volunteer participants, was screen reader accessible, and measured listening rate by accuracy at answering questions spoken by a screen reader at various rates. Our results show that blind and low-vision people, who often rely on audio cues and access text aurally, generally have higher listening rates than sighted people. The findings also suggest a need to expand the range of rates available on personal devices. These results demonstrate the potential for users to learn to listen to faster rates, expanding the possibilities for human-conversational agent interaction.

Blocks-based programming environments are a popular tool to teach children to program, but they rely heavily on visual metaphors and are therefore not fully accessible for children with visual impairments. We evaluated existing blocks-based environments and identified five major accessibility barriers for visually impaired users. We explored techniques to overcome these barriers in an interview with a teacher of the visually impaired and formative studies on a touchscreen blocks-based environment with five children with visual impairments. We distill our findings on usable touchscreen interactions into guidelines for designers of blocks-based environments.

A panel of students with disabilities who are pursuing computing degrees will describe their experiences both in and out of the classroom. The goal of the panel is to provide the audience with an opportunity to hear first-hand how their educational needs were met as non-traditional computing students. In addition to the panelists' short presentations, the moderator will facilitate a dialog between the members of the audience and the panelists.

Approximately 10% of computer science and engineering majors have a disability. Students with disabilities are more likely to drop out of the major than those without disabilities. At the K-12 level, many tools used to teach computing have limited accessibility to students with disabilities. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies to help each other do a better job of including these students in our classes and research projects. Resources, including those produced by AccessComputing and AccessCSforAll, will be shared.

Industry demand for software developers with knowledge of accessibility has increased substantially in recent years. However, there is little knowledge about the prevalence of higher education teaching about accessibility or faculty's perceived barriers to teaching accessibility. To address this gap, we surveyed 14,176 computing and information science faculty in the United States. We received a representative sample of at least one response from 318 of the 352 institutions we surveyed, totaling 1,857 responses. We found that 175 institutions (50%) had at least one instructor teaching accessibility and that no fewer than 2.5% of faculty overall teach accessibility. Faculty that teach accessibility are twice as likely to be female, to have expertise in HCI and software engineering, and to know people with disabilities. The most critical barriers to teaching accessibility that faculty reported were the absence of clear and discipline-specific accessibility learning objectives and the lack of faculty knowledge about accessibility. Faculty desired resources that were specific to the areas of computing in which they teach rather than general accessibility resources and guidelines.

Blocks-based programming environments, such as Scratch and Blockly, are designed to make learning programming easier for young children. They are increasingly being used for both formal and informal curriculum, such as many of Code.org's hour of code projects. However, these block-based environments rely heavily on visual metaphors and interactions, making them inaccessible for blind children. We describe our initial design of a touchscreen-based blocks environment that is accessible for blind children.

No abstract available.

Approximately 10% of computer science and engineering majors have a disability of some kind. Students with disabilities are more likely to drop out of the major than those without disabilities. At the K-12 level, many tools used to teach computing are inaccessible to students with disabilities. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies and promising practices to help each other do a better job of including these students in our classes and research projects. Resources, including those produced by AccessComputing and AccessCSforAll (formally AccessCS10K) will be shared. Handouts and stickers will be given out.

Quorum is a relatively new programming language that was originally designed for students with disabilities. In recent years, as its adoption has increased worldwide in K-12 (largely in middle/high school) and at universities, it has expanded to be a powerful, commercial-grade, programming language that includes support for 3D gaming, music, and other fun and creative activities. While new features are designed for all, they maintain compatibility for people with disabilities, including a novel way for individuals who are blind to create 3D games. Finally, Quorum is the first language to use human-factors evidence from both field data and randomized controlled trials in its design. This approach provides the broader research community an organized way to influence the design of the language over time according to evidence based practices. We call this approach evidence-oriented programming. A laptop would help participants follow along with the session and handouts will be provided. Quorum can be found at https://www.quorumlanguage.com/.

Sounds provide informative signals about the world around us. In situations where non-auditory cues are inaccessible, it can be useful for deaf and hard-of-hearing people to be notified about sounds. Through a survey, we explored which sounds are of interest to deaf and hard-of-hearing people, and which means of notification are appropriate. Motivated by these findings, we designed a mobile phone app that alerts deaf and hard-of-hearing people to sounds they care about. The app uses training examples of personally relevant sounds recorded by the user to learn a model of those sounds. It then screens the incoming audio stream from the phone's microphone for those sounds. When it detects a sound, it alerts the user by vibrating and providing a pop-up notification. To evaluate the interface design independent of sound detection errors, we ran a Wizard-of-Oz user study, and found that the app design successfully facilitated deaf and hard-of-hearing users recording training examples. We also explored the viability of a basic machine learning algorithm for sound detection.

We take a qualitative approach to understanding deaf and hard of hearing (DHH) students' experiences with real-time captioning as an access technology in mainstream university classrooms. We consider both existing human-based captioning as well as new machine-based solutions that use automatic speech recognition (ASR). We employed a variety of qualitative research methods to gather data about students' captioning experiences including in-class observations, interviews, diary studies, and usability evaluations. We also conducted a co-design workshop with 8 stakeholders after our initial research findings. Our results show that accuracy and reliability of the technology are still the most important issues across captioning solutions. However, we additionally found that current captioning solutions tend to limit students' autonomy in the classroom and present a variety of user experience shortcomings, such as complex setups, poor feedback and limited control over caption presentation. Based on these findings, we propose design requirements and recommend features for real-time captioning in mainstream classrooms.

Since 1976, when California State University Northridge (CSUN) began its Annual International Technology and Persons with Disabilities Conference, there have been specialized conferences with an accessibility theme. The first ACM ASSETS Conference was held in 1994 when 22 papers were presented. The Rehabilitation Engineering and Assistive Technology Society of North America (RESNA) began its conference in 1979. The first biennial International Conference on Computers Helping People with Special Needs (under a different name) was held in 1988. Accessibility focused journals have existed since at least 1986. This history demonstrates that accessibility has grown into a separate field in research and practice. While this is true, more and more, accessibility has become mainstream.

How can the broader field of computer science research be harnessed to address challenges and opportunities in accessibility? This poster summarizes the findings of a workshop, sponsored by the Computing Community Consortium (USA), that brought together computer scientists, representatives of disability advocacy organizations, people from industry, and government employees to develop an agenda for strategic research. Members of the ASSETS community may find the reports useful in organizing collaborative projects with others in the computer science community.

Approximately 10% of computer science and engineering majors have a disability of some kind. Students with disabilities are more likely to drop out of the major than those without disabilities. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies and promising practices to help each other do a better job of including these students in our classes and research projects. Resources, including those produced by AccessComputing (uw.edu/accesscomputing) and AccessCS10K (uw.edu/accesscomputing/accesscs10k), will be shared.

People who are blind or low-vision may have a harder time participating in exercise due to inaccessibility or lack of experience. We employed Value Sensitive Design (VSD) to explore the potential of technology to enhance exercise for people who are blind or low-vision. We conducted 20 semi-structured interviews about exercise and technology with 10 people who are blind or low-vision and 10 people who facilitate fitness for people who are blind or low-vision. We also conducted a survey with 76 people to learn about outsider perceptions of hypothetical exercise with people who are blind or low-vision. Based on our interviews and survey, we found opportunities for technology development in four areas: 1) mainstream exercise classes, 2) exercise with sighted guides, 3) rigorous outdoors activity, and 4) navigation of exercise spaces. Design considerations should include when and how to deliver auditory or haptic information based on exercise and context, and whether it is acceptable to develop less mainstream technologies if they enhance mainstream exercise. The findings of this work seek to inform the design of accessible exercise technologies.

It can be difficult for a blind developer to understand and navigate through a large amount of code quickly, as they are unable to skim as easily as their sighted counterparts. To help blind developers overcome this problem, we present StructJumper, an Eclipse plugin that creates a hierarchical tree based on the nesting structure of a Java class. The programmer can use the TreeView to get an overview of the code structure of the class (including all the methods and control flow statements) and can quickly switch between the TreeView and the Text Editor to get an idea of where they are within the nested structure. To evaluate StructJumper, we had seven blind programmers complete three tasks with and without our tool. We found that the users thought they would use StructJumper and there was a trend that they were faster completing the tasks with StructJumper.

Students learning American Sign Language (ASL) have trouble searching for the meaning of unfamiliar signs. ASL signs can be differentiated by a small set of simple features including hand shape, orientation, location, and movement. In a feature-based ASL-to-English dictionary, users search for a sign by providing a query, which is a set of observed features. Because there is natural variability in the way signs are executed, and observations are error-prone, an approach other than exact matching of features is needed. We propose ASL-Search, an ASL-to-English dictionary entirely powered by its users. ASL-Search utilizes Latent Semantic Analysis (LSA) on a database of feature-based user queries to account for variability. To demonstrate ASL-Search's viability, we created ASL-Flash, a learning tool that presents online flashcards to ASL students and provides query data. Our simulations on this data serve as a proof of concept, demonstrating that our dictionary's performance improves with use and performs well for users with varied levels of ASL experience.

Approximately 10% of computer science and engineering majors have a disability of some kind. Students with disabilities are more likely to drop out of the major than those without disabilities. This BOF will bring together individuals who are interested in increasing the representation of students with disabilities in computing and improving their success. Participants will share strategies and promising practices to help each other do a better job of including these students in our classes and research projects. Resources, including those produced by AccessComputing (uw.edu/accesscomputing), will be shared.

This special session is for SIGCSE attendees who are interested in K-12 computing education, especially those who have or are planning to have a NSF CS 10K project. A major goal of CS 10K is broadening participation, which includes providing computing education to students with disabilities. This interactive session will introduce attendees to AccessCS10K, a project to help teachers include students with disabilities in their K-12 computing classes. Furthermore, attendees will have a hands-on experience with the Quorum language, a language designed for youth regardless of disability. It is expected that attendees to the special session will be better prepared to include a student with a disability in their computing classes or to help other teachers do the same.

Textbook figures are often converted into a tactile format for access by blind students. These figures are not truly accessible unless the text within the figures is also made accessible. A common solution to access text in a tactile image is to use embossed Braille. We have developed an alternative to Braille that uses QR codes for students who want tactile graphics, but prefer the text in figures be spoken, rather than in Braille. Tactile Graphics with a Voice (TGV) allows text within tactile graphics to be accessible by using a talking QR code reader app on a smartphone. To evaluate TGV, we performed a longitudinal study where ten blind and low vision participants were asked to complete tasks using three alternative picture taking guidance techniques: 1) no guidance, 2) verbal guidance, and 3) finger pointing guidance. Our results show that TGV is an effective way to access text in tactile graphics, especially for those blind users who are not fluent in Braille. In addition, guidance preferences varied with each of the guidance techniques being preferred by at least one participant.

Textbook images are converted into tactile graphics to be made accessible to blind and low vision students. The text labels on these graphics are an important part of the image and must be made accessible as well. The graphics usually have the labels embossed in Braille. However, there are some blind and low vision students who cannot read Braille and need to be able to access the labels in a different manner. We present Tactile Graphics with a Voice, a system that encodes the labels in QR codes, which can be read aloud using the application, TGV, we developed. TGV provides feedback to support the user in scanning the QR code and allows the user to select which QR code to scan when multiple are close together.

People who are blind or visually impaired face difficulties accessing a growing array of everyday appliances, needed to perform a variety of daily activities, because they are equipped with electronic displays. We are developing a "Display Reader" smartphone app, which uses computer vision to help a user acquire a usable image of a display, to address this problem. The current prototype analyzes video from the smartphone's camera, providing real-time feedback to guide the user until a satisfactory image is acquired, based on automatic estimates of image blur and glare. Formative studies were conducted with several blind and visually impaired participants, whose feedback is guiding the development of the user interface. The prototype software has been released as a Free and Open Source (FOSS) project.

There are many educational smartphone games for children, but few are accessible to blind children. We present BraillePlay, a suite of accessible games for smartphones that teach Braille character encodings to promote Braille literacy. The BraillePlay games are based on VBraille, a method for displaying Braille characters on a smartphone. BraillePlay includes four games of varying levels of difficulty: VBReader and VBWriter simulate Braille flashcards, and VBHangman and VBGhost incorporate Braille character identification and recall into word games. We evaluated BraillePlay with a longitudinal study in the wild with eight blind children. Through logged usage data and extensive interviews, we found that all but one participant were able to play the games independently and found them enjoyable. We also found evidence that some children learned Braille concepts. We distill implications for the design of games for blind children and discuss lessons learned.

Mobile sign language video communication has the potential to be more accessible and affordable if the current recommended video transmission standard of 25 frames per second at 100 kilobits per second (kbps) as prescribed in the International Telecommunication Standardization Sector (ITU-T) Q.26/16 were relaxed. To investigate sign language video intelligibility at lower settings, we conducted a laboratory study, where fluent ASL signers in pairs held real-time free-form conversations over an experimental smartphone app transmitting real-time video at 5 fps/25 kbps, 10 fps/50 kbps, 15 fps/75 kbps, and 30 fps/150 kbps, settings well below the ITU-T standard that save both bandwidth and battery life. The aim of the laboratory study was to investigate how fluent ASL signers adapt to the lower video transmission rates, and to identify a lower threshold at which intelligible real-time conversations could be held. We gathered both subjective and objective measures from participants and calculated battery life drain. As expected, reducing the frame rate/bit rate monotonically extended the battery life. We discovered all participants were successful in holding intelligible conversations across all frame rates/bit rates. Participants did perceive the lower quality of video transmitted at 5 fps/25 kbps and felt that they were signing more slowly to compensate; however, participants' rate of fingerspelling did not actually decrease. This and other findings support our recommendation that intelligible mobile sign language conversations can occur at frame rates as low as 10 fps/50 kbps while optimizing resource consumption, video intelligibility, and user preferences.

A panel of college students with disabilities who are computing majors or have taken multiple computing courses will describe their experiences both in and out of the classroom. The goal of the panel is to provide the audience with an opportunity to hear first-hand how their educational needs were met as non-traditional computing students. In addition to the panelists' short presentations, the moderator will facilitate a dialog between the members of the audience and the panelists.

We present VBGhost: an accessible, educational smartphone game for people who are blind or low vision. It is based on the word game Ghost, in which players take turns adding letters to a word fragment while attempting to not complete a word. VBGhost uses audio and haptic feedback to reinforce Braille concepts. Players enter letters in the game by using Braille dot patterns on a touchscreen interface. Players can raise or lower dots to create Braille characters using taps and audio feedback from the phone. When a "raised" dot is touched on the screen, the phone vibrates. In VBGhost, a player can either play against the computer or against another person. We demonstrate the potential for the development of fun, accessible and educational games.

Approximately 10% of computer science and engineering majors have a disability of some kind. Those with disabilities are more likely to drop out of the major than those without disabilities. This BOF will bring together those who are interested in improving the success of these students. Strategies will be shared among the participants of the BOF to help each other do a better job of including these students in our classes and research projects.

Eyes-free input usually relies on audio feedback that can be difficult to hear in noisy environments. We present DigiTaps, an eyes-free number entry method for touchscreen devices that requires little auditory attention. To enter a digit, users tap or swipe anywhere on the screen with one, two, or three fingers. The 10 digits are encoded by combinations of these gestures that relate to the digits' semantics. For example, the digit 2 is input with a 2-finger tap. We conducted a longitudinal evaluation with 16 people and found that DigiTaps with no audio feedback was faster but less accurate than with audio feedback after every input. Throughout the study, participants entered numbers with no audio feedback at an average rate of 0.87 characters per second, with an uncorrected error rate of 5.63%.

Blind mobile device users face security risks such as inaccessible authentication methods, and aural and visual eavesdropping. We interviewed 13 blind smartphone users and found that most participants were unaware of or not concerned about potential security threats. Not a single participant used optional authentication methods such as a password-protected screen lock. We addressed the high risk of unauthorized user access by developing PassChords, a non-visual authentication method for touch surfaces that is robust to aural and visual eavesdropping. A user enters a PassChord by tapping several times on a touch surface with one or more fingers. The set of fingers used in each tap defines the password. We give preliminary evidence that a four-tap PassChord has about the same entropy, a measure of password strength, as a four-digit personal identification number (PIN) used in the iPhone's Passcode Lock. We conducted a study with 16 blind participants that showed that PassChords were nearly three times as fast as iPhone's Passcode Lock with VoiceOver, suggesting that PassChords are a viable accessible authentication method for touch screens.

Enabling end-users of Augmentative and Alternative Communication (AAC) systems to add personalized video content at runtime holds promise for improving communication, but the requirements for such systems are as yet unclear. To explore this issue, we present Vid2Speech, a prototype AAC system for children with complex communication needs (CCN) that uses personalized video to enhance representations of action words. We describe three design goals that guided the integration of personalized video to enhance AAC in our early-stage prototype: 1) Providing social-temporal navigation; 2) Enhancing comprehension; and 3) Enabling customization in real time. Our system concept represents one approach to realizing these goals, however, we contribute the goals and the system as a starting point for future innovations in personalized video-based AAC.

A new non-visual method of numeric entry into a smartphone is designed, implemented, and tested. Users tap the smartphone screen with one to three fingers or swipe the screen in order to enter numbers. No buttons are used--only simple, easy-to-remember gestures. A preliminary valuation with sighted users compares the method to a standard accessible numeric keyboard with a VoiceOver-like screen reader interface for non-visual entry. We found that users entered numbers faster and with higher accuracy with our number entry method than with a VoiceOver-like interface, showing there is potential for use among blind people as well. The Tapulator, a complete calculator based on this non-visual numeric entry that uses simple gestures for arithmetic operations and other calculator actions is described.

Many wonderful enrichment programs have been created to introduce young people to computing, but with little attention to making them accessible to students with disabilities. In this workshop participants will learn from practitioners who have introduced computing and programming to young people with disabilities. They will also learn first-hand from students with disabilities about their needs in learning programming. There will be breakout sessions for participants to apply what they have learned to improve existing enrichment programs such as Alice, Arduino, Scratch, Kodu, App Inventor, Greenfoot, Lego Mindstorms, Processing, and Computer Science Unplugged.

Traditional user technology for communication, such as phones, computers, television, and radio, may not directly work for people who have sensory disabilities. Five classes of communication access technology are discussed: hearing enhancement technology, deaf technology, vision enhancement technology, blind technology, and deaf-blind technology. These technologies are discussed in the social context of the people who use the technology. Broad technical research challenges are delineated and new directions for exploration are discussed.

We explore using vibration on a smartphone to provide turn-by-turn walking instructions to people with visual impairments. We present two novel feedback methods called Wand and ScreenEdge and compare them to a third method called Pattern. We built a prototype and conducted a user study where 8 participants walked along a pre-programmed route using the 3 vibration feedback methods and no audio output. Participants interpreted the feedback with an average error rate of just 4 percent. Most preferred the Pattern method, where patterns of vibrations indicate different directions, or the ScreenEdge method, where areas of the screen correspond to directions and touching them may induce vibration.

People with disabilities have always overcome accessibility problems by enlisting people in their community to help. The Internet has broadened the available community and made it easier to get on-demand assistance remotely. In particular, the past few years have seen the development of technology in both research and industry that uses human power to overcome technical problems too difficult to solve automatically. In this paper, we frame recent developments in human computation in the historical context of accessibility, and outline a framework for discussing new advances in human-powered access technology. Specifically, we present a set of 13 design principles for human-powered access technology motivated both by historical context and current technological developments. We then demonstrate the utility of these principles by using them to compare several existing human-powered access technologies. The power of identifying the 13 principles is that they will inspire new ways of thinking about human-powered access technologies.

Video and image quality are often objectively measured using peak signal-to-noise ratio (PSNR), but for sign language video, human comprehension is most important. Yet the relationship of human comprehension to PSNR has not been studied. In this survey, we determine how well PSNR matches human comprehension of sign language video. We use very low bitrates (10-60 kbps) and two low spatial resolutions (192×144 and 320×240 pixels) which may be typical of video transmission on mobile phones using 3G networks. In a national online video-based user survey of 103 respondents, we found that respondents preferred the 320×240 spatial resolution transmitted at 20 kbps and higher; this does not match what PSNR results would predict. However, when comparing perceived ease/difficulty of comprehension, we found that responses did correlate well with measured PSNR. This suggests that PSNR may not be suitable for representing subjective video quality, but can be reliable as a measure for comprehensibility of American Sign Language (ASL) video. These findings are applied to our experimental mobile phone application, MobileASL, which enables real-time sign language communication for Deaf users at low bandwidths over the U.S. 3G cellular network.

Blind and deaf-blind people often rely on public transit for everyday mobility, but using transit can be challenging for them. We conducted semi-structured interviews with 13 blind and deaf-blind people to understand how they use public transit and what human values were important to them in this domain. Two key values were identified: independence and safety. We developed GoBraille, two related Braille-based applications that provide information about buses and bus stops while supporting the key values. GoBraille is built on MoBraille, a novel framework that enables a Braille display to benefit from many features in a smartphone without knowledge of proprietary, device-specific protocols. Finally, we conducted user studies with blind people to demonstrate that GoBraille enables people to travel more independently and safely. We also conducted co-design with a deaf-blind person, finding that a minimalist interface, with short input and output messages, was most effective for this population.

Despite growing awareness of the accessibility issues surrounding touch screen use by blind people, designers still face challenges when creating accessible touch screen interfaces. One major stumbling block is a lack of understanding about how blind people actually use touch screens. We conducted two user studies that compared how blind people and sighted people use touch screen gestures. First, we conducted a gesture elicitation study in which 10 blind and 10 sighted people invented gestures to perform common computing tasks on a tablet PC. We found that blind people have different gesture preferences than sighted people, including preferences for edge-based gestures and gestures that involve tapping virtual keys on a keyboard. Second, we conducted a performance study in which the same participants performed a set of reference gestures. We found significant differences in the speed, size, and shape of gestures performed by blind people versus those performed by sighted people. Our results suggest new design guidelines for accessible touch screen interfaces.

The goal of the MobileASL (American Sign Language) research project is to enable sign language communication over the U.S. cellular network, which is low bandwidth and lossy. Data loss can greatly impact the quality of compressed video because of temporal and spatial error propagation. We investigate techniques to minimize the effect of data loss for improving compressed video sign language conversations. As both computational power and bandwidth are limited on cellular devices, we must carefully allocate these resources. Specifically we focus on utilizing feedback to recover from data loss.

Many touch screens remain inaccessible to blind users, and those approaches to providing access that do exist offer minimal support for interacting with large touch screens or spatial data. In this paper, we introduce a set of three software-based access overlays intended to improve the accessibility of large touch screen interfaces, specifically interactive tabletops. Our access overlays are called edge projection, neighborhood browsing, and touch-and-speak. In a user study, 14 blind users compared access overlays to an implementation of Apple's VoiceOver screen reader. Our results show that two of our techniques were faster than VoiceOver, that participants correctly answered more questions about the screen's layout using our techniques, and that participants overwhelmingly preferred our techniques. We developed several applications demonstrating the use of access overlays, including an accessible map kiosk and an accessible board game.

This special issue includes the first set of articles addressing broadening participation in computing education. The articles span the stages of the pipeline, from introducing middle school children to computer science to retaining underrepresented groups at the university level. The preface presented here outlines the need for increasing the participation of underrepresented minorities, women, and people with disabilities in the development of technology. In addition, the preface summarizes the six articles included in this first (of two) issues on broadening participation.

This special issue includes the second set of articles addressing broadening participation in computing education. The articles span the stages of the pipeline, from introducing middle school children to computer science to retaining under-represented groups at the university level. The preface presented here outlines the need for increasing the participation of under-represented minorities, women, and people with disabilities in the development of technology. In addition, the preface summarizes the seven articles included in this second issue (of two) on broadening participation.

V-Braille is a novel way to haptically represent Braille characters on a standard mobile phone using the touch-screen and vibration. V-Braille may be suitable for deaf-blind people who rely primarily on their tactile sense. A preliminary study with deaf-blind Braille users found that, with minimal training, V-Braille can be used to read individual characters and sentences.

MobileASL is a video compression project for two-way, real-time video communication on cell phones, allowing Deaf people to communicate in the language most accessible to them, American Sign Language. Unfortunately, running MobileASL quickly depletes a full battery charge in a few hours. Previous work on MobileASL investigated a method called variable frame rate (VFR) to increase the battery duration. We expand on this previous work by creating two new power saving algorithms, variable spatial resolution (VSR), and the application of both VFR and VSR. These algorithms extend the battery life by altering the temporal and/or spatial resolutions of video transmitted on MobileASL. We found that implementing only VFR extended the battery life from 284 minutes to 307 minutes; implementing only VSR extended the battery life to 306 minutes, and implementing both VFR and VSR extended the battery life to 315 minutes. We evaluated all three algorithms by creating a linguistically accessible online survey to investigate Deaf people's perceptions of video quality when these algorithms were applied. In our survey results, we found that VFR produces perceived video choppiness and VSR produces perceived video blurriness; however, a surprising finding was that when both VFR and VSR are used together, they largely ameliorate the choppiness and blurriness perceived, i.e., they each improve the use of the other. This is a useful finding because using VFR and VSR together saves the most battery life.

American Sign Language (ASL) currently lacks agreed-upon signs for complex terms in scientific fields, causing deaf students to miss or misunderstand course material. Furthermore, the same term or concept may have multiple signs, resulting in inconsistent standards and strained collaboration. The ASL-STEM Forum is an online, collaborative, video forum for sharing ASL signs and discussing them. An initial user study of the Forum has shown its viability and revealed lessons in accommodating varying user types, from lurkers to advanced contributors, until critical mass is achieved.

Deaf and hard of hearing students must juggle their visual attention in current classroom settings. Managing many visual sources of information (instructor, interpreter or captions, slides or whiteboard, classmates, and personal notes) can be a challenge. ClassInFocus automatically notifies students of classroom changes, such as slide changes or new speakers, helping them employ more beneficial observing strategies. A user study of notification techniques shows that students who liked the notifications were more likely to visually utilize them to improve performance.

Mobile devices provide people with disabilities new opportunities to act independently in the world. However, these empowering devices have their own accessibility challenges. We present a formative study that examines how people with visual and motor disabilities select, adapt, and use mobile devices in their daily lives. We interviewed 20 participants with visual and motor disabilities and asked about their current use of mobile devices, including how they select them, how they use them while away from home, and how they adapt to accessibility challenges when on the go. Following the interviews, 19 participants completed a diary study in which they recorded their experiences using mobile devices for one week. Our results show that people with visual and motor disabilities use a variety of strategies to adapt inaccessible mobile devices and successfully use them to perform everyday tasks and navigate independently. We provide guidelines for more accessible and empowering mobile device design.

The H.264 encoder has input parameters that determine the bit rate and distortion of the compressed video and the encoding complexity. A set of encoder parameters is referred to as a parameter setting. We previously proposed two offline algorithms for choosing H.264 encoder parameter settings that have distortion-complexity performance close to the parameter settings obtained from an exhaustive search, but take significantly fewer encodings. However they generate only a few parameter settings. If there is no available parameter settings for a given encode time, the encoder will need to use a lower complexity parameter setting resulting in a decrease in peak-signal-to-noise-ratio (PSNR). In this paper, we propose two algorithms for finding additional parameter settings over our previous algorithm and show that they improve the PSNR by up to 0.71 dB and 0.43 dB, respectively. We test both our algorithms on Linux and PocketPC platforms.

Deaf and hard of hearing students are an underrepresented group in computing and face extra challenges in university-level computing courses. This paper describes a 9-week Summer Academy for Advancing Deaf and Hard of Hearing in Computing that jump-starts the academic careers of deaf and hard of hearing students and strengthens their interest in computing. Students take introductory computing and animation in a fun, supportive, accessible environment. We report on some of the problems students face and lessons we have learned about helping them overcome those problems. Through the academy, they meet other successful deaf and hard of hearing technology professionals, tour top computing companies, and display their own work to the local deaf and hard of hearing community. Students gain leadership, independent learning skills, and complete the program better prepared for a college major in computing.

We describe our system called MobileASL for real-time video communication on the current U.S. mobile phone network. The goal of MobileASL is to enable Deaf people to communicate with Sign Language over mobile phones by compressing and transmitting sign language video in real-time on an off-the-shelf mobile phone, which has a weak processor, uses limited bandwidth, and has little battery capacity. We develop several H.264-compliant algorithms to save system resources while maintaining ASL intelligibility by focusing on the important segments of the video. We employ a dynamic skin-based region-of-interest (ROI) that encodes the skin at higher quality at the expense of the rest of the video. We also automatically recognize periods of signing versus not signing and raise and lower the frame rate accordingly, a technique we call variable frame rate (VFR). We show that our variable frame rate technique results in a 47 % gain in battery life on the phone, corresponding to an extra 68 minutes of talk time. We also evaluate our system in a user study. Participants fluent in ASL engage in unconstrained conversations over mobile phones in a laboratory setting. We find that the ROI increases intelligibility and decreases guessing. VFR increases the need for signs to be repeated and the number of conversational breakdowns, but does not affect the users ’ perception of adopting the technology. These results show that our sign language sensitive algorithms can save considerable resources without sacrificing intelligibility. ACM Classification: H5.2 [Information interfaces and presentation]:Multimedia Information Systems–Video. K.4.2 [Computers and Society]: Social Issues–Assistive technologies for persons with disabilities. General terms:

Proper use of headings in web pages can make navigation more efficient for blind web users by indicating semantic divisions in the page. Unfortunately, many web pages do not use proper HTML markup (h1-h6 tags) to indicate headings, instead using visual styling to create headings, thus making the distinction between headings and other page text indistinguishable to blind users. In a user study in which sighted participants labeled headings on a set of web pages, participants did not often agree on which elements on the page should be labeled as headings, suggesting why headings are not used properly on the web today. To address this problem, we have created a system called HeadingHunter that predicts whether web page text semantically functions as a heading by examining visual features of the text as rendered in a web browser. Its performance in labeling headings compares favorably with both a manually-classified set of heading examples and the combined results of the sighted labelers in our study. The resulting system illustrates a general methodology of creating simple scripts operating over visual features that can be directly included in existing tools.

The goal of the MobileASL project is to increase accessibility by making the mobile telecommunications network available to the signing Deaf community. Video cell phones enable Deaf users to communicate in their native language, American Sign Language (ASL). However, encoding and transmission of real-time video over cell phones is a power-intensive task that can quickly drain the battery.

The web provides nearly ubiquitous access to information, but access for blind web users requires the use of expensive, specialized software programs called screen readers unlikely to be installed on most computers. WebAnywhere is a self-voicing, web-browsing web application that makes the web accessible for blind web users from most devices with web access. WebAnywhere requires no special permissions or additional software to be installed on the host machine, enabling it provide a self-voicing interface on almost any web-enabled device. WebAnywhere’s interface is written in Javascript, speech is retrieved from a remote server, and sounds are played using either Flash or existing embedded sound players. This paper describes the performance and security implications of the system’s unique design and how it has been engineered to provide usable access anywhere. Specifically, we present prefetching andcaching strategies developed to make the system responsive even on low-bandwidth connections and security considerations that replicate existing browser security policies.

Blind students are an underrepresented group in computer science. In this paper, we describe our experience preparing and leading the computer science track at the National Federation of the Blind Youth Slam. As part of this workshop, fifteen blind high school students created and personalized instant messaging chatbots, a project designed to be completely accessible to blind students. Chatbots enable students to infuse their own personalities into a socially-oriented program that incorporates ideas from artificial intelligence, natural language processing, and web services. We first outline the chatbots project and curriculum, which has wide appeal for all students, and then offer general design principles used to create it that can help ensure the accessibility of future projects. Students created their chatbots using a real programming language and were guided by both blind and sighted mentors. By programming from the start in a supportive environment, our students will gain the confidence to persevere in computer science in the future.

In this hands-on special session, attendees will learn about and use a Game of Life cellular automata framework (Java) to assist with outreach activities. Using the framework, students with no prior programming experience can create interesting behaviors within thirty minutes. The special session leaders have successfully used this approach for thirteen years in a one-week summer workshop for disabled high school students. The SIGCSE special session will include an introduction to the framework and keys to its success as an outreach activity, followed by participants solving, programming, and proposing specific problems. Attendees will be equipped to guide Game of Life outreach activities at their own outreach events.

People often use computers other than their own to access web content, but blind users are restricted to using computers equipped with expensive, special-purpose screen reading programs that they use to access the web. WebAnywhere is a web-based, self-voicing web application that enables blind web users to access the web from almost any computer that can produce sound without installing new software. WebAnywhere could serve as a convenient, low-cost solution for blind users on-the-go, for blind users unable to afford another screen reader and for web developers targeting accessible design. This paper describes the implementation of WebAnywhere, overviews an evaluation of it by blind web users, and summarizes a survey of public terminals that shows it can run on most public computers.

Cache-oblivious and cache-aware algorithms have been developed to minimize cache misses. Some of the newest processors have hardware prefetching where cache misses are avoided by predicting ahead of time what memory will be needed in the future and bringing that memory into the cache before it is used. It is shown that hardware prefetching permits the standard Floyd-Warshall algorithm for all-pairs shortest paths to outperform cache-oblivious and cache-aware algorithms. A simple improvement to the standard simple dynamic programming algorithm yields an algorithm that takes advantage of prefetching, and outperforms cache-oblivious and cache-aware algorithms. Finally, it is shown that variants of standard FFT algorithms exhibit good prefetching performance.

Web browsing is inefficient for blind web users because of persistent accessibility problems, but the extent of these problems and their practical effects from the perspective of the user has not been sufficiently examined. We conducted a study in situ to investigate the accessibility of the web as experienced by web users. This remote study used an advanced web proxy that leverages AJAX technology to record both the pages viewed and the actions taken by users on the web pages that they visited. Our study was conducted remotely over the period of one week, and our participants used the assistive technology and software to which they were already accustomed and had already configured according to preference. These advantages allowed us to aggregate observations of many users and to explore the practical effects on and coping strategies employed by our blind participants. Our study reflects web accessibility from the perspective of web users and describes quantitative differences in the browsing behavior of blind and sighted web users.

The MobileASL project aims to increase accessibility by enabling Deaf people to communicate over video cell phones in their native language, American Sign Language (ASL). Real-time video over cell phones can be a computationally intensive task that quickly drains the battery, rendering the cell phone useless. Properties of conversational sign language allow us to save power and bits: namely, lower frame rates are possible when one person is not signing due to turn-taking, and signing can potentially employ a lower frame rate than fingerspelling. We conduct a user study with native signers to examine the intelligibility of varying the frame rate based on activity in the video. We then describe several methods for automatically determining the activity of signing or not signing from the video stream in real-time. Our results show that varying the frame rate during turn-taking is a good way to save power without sacrificing intelligibility, and that automatic activity analysis is feasible.

We address the practical problem of automating the process of translating figures from mathematics, science, and engineering textbooks to a tactile form suitable for blind students. The Tactile Graphics Assistant (TGA) and accompanying workflow is described. Components of the TGA that identify text and replace it with Braille use machine learning, computational geometry, and optimization algorithms. We followed through with the ideas in our 2005 paper by creating a more detailed workflow, translating actual images, and analyzing the translation time. Our experience in translating more than 2,300 figures from 4 textbooks demonstrates that figures can be translated in ten minutes or less of human time on average. We describe our experience with training tactile graphics specialists to use the new TGA technology.

The H.264/ACV standard provides significant improvements in performance over earlier video coding standards at the cost of increased complexity. Our challenge is to determine H.264 parameter settings that have low complexity but still offer high video quality. In this paper, we propose two fast algorithms for finding the H.264 parameter settings that take about 1% and 8%, respectively, of the number of tests required by an exhaustive search. Both the fast algorithms result in a maximum decrease in peak-signal-to-noise ratio of less than 0.71 dB for different data sets and bitrates

Given is a sequence of n positive integers w 1 , w 2 ,…, w n that are associated with the items 1,2,… n , respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most w i slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/ w i . The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/ w i of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. Let H = ⌈Σ i ==1 n (1/ w i ) be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used H + O (ln H ) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most H + 1 bins. In the online setting, this article presents algorithms for both problems with H + O (√ H ) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least H +Ω(ln H ) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.

Most bit allocation algorithms for video are geared toward optimizing the average frame distortion. However, video sequences optimized this way may exhibit sudden changes in distortion, or "flicker," which can significantly affect the perceived quality of the sequence. An alternative approach is to minimize the maximum frame distortion, which aims to produce a constant-quality sequence, thus avoiding the flicker problem. In this work, we present a new algorithm for constant-quality video, called MultiStage. We first show how MultiStage works for an embedded bit plane coder, and we then demonstrate that it can be applied to traditional quantization-based coders, such as H.263 and H.264, in conjunction with a novel single-frame block-level rate-distortion optimization algorithm based on multiple-choice knapsack. We show that MultiStage achieves very good results, both in terms of maximum distortion and average distortion

Images without alternative text are a barrier to equal web access for blind users. To illustrate the problem, we conducted a series of studies that conclusively show that a large fraction of significant images have no alternative text. To ameliorate this problem, we introduce WebInSight, a system that automatically creates and inserts alternative text into web pages on-the-fly. To formulate alternative text for images, we present three labeling modules based on web context analysis, enhanced optical character recognition (OCR) and human labeling. The system caches alternative text in a local database and can add new labels seamlessly after a web page is downloaded, resulting in minimal impact to the browsing experience.

For Deaf people, access to the mobile telephone network in the United States is currently limited to text messaging, forcing communication in English as opposed to American Sign Language (ASL), the preferred language. Because ASL is a visual language, mobile video phones have the potential to give Deaf people access to real-time mobile communication in their preferred language. However, even today's best video compression techniques can not yield intelligible ASL at limited cell phone network bandwidths. Motivated by this constraint, we conducted one focus group and one user study with members of the Deaf Community to determine the intelligibility effects of video compression techniques that exploit the visual nature of sign language. Inspired by eyetracking results that show high resolution foveal vision is maintained around the face, we studied region-of-interest encodings (where the face is encoded at higher quality) as well as reduced frame rates (where fewer, better quality, frames are displayed every second). At all bit rates studied here, participants preferred moderate quality increases in the face region, sacrificing quality in other regions. They also preferred slightly lower frame rates because they yield better quality frames for a fixed bit rate. These results show promise for realtime access to the current cell phone network through signlanguage-specific encoding techniques.

Research Supported By National Science Foundation Grant Number Ccr-0104800. Richard Ladner was supported in part by the Boeing Professor-ship in Computer Science and Engineering. Contact Information: Professor Agnieszka Miguel, Department of Electrical & Computer Engineering Seattle University, 901 12th Avenue, P.O. Box 222000, Seattle, WA 98122-1090, (206)296-5965, [email protected]. ABSTRACT Algorithms for near-lossless compression of hyperspectral images are presented. They guarantee that the intensity of any pixel in the decompressed image(s) differs from its original value by no more than a user-specified quantity. To reduce the bit rate required to code images while providing significantly more compression than lossless algorithms, linear prediction between the bands is used. Each band is predicted by a previously transmitted band. The prediction is subtracted from the original band, and the residual is compressed with a bit plane coder which uses context-based adaptive binary arithmetic coding. To find the best prediction algorithm, the impact of various band orderings and optimization techniques on the compression ratios is studied.

Access to graphical images (bar charts, diagrams, line graphs, etc.) that are in a tactile form (representation through which content can be accessed by touch) is inadequate for students who are blind and take mathematics, science, and engineering courses. We describe our analysis of the current work practices of tactile graphics specialists who create tactile forms of graphical images. We propose automated means by which to improve the efficiency of current work practices.We describe the implementation of various components of this new automated process, which includes image classification, segmentation, simplification, and layout. We summarize our development of the tactile graphics assistant, which will enable tactile graphics specialists to be more efficient in creating tactile graphics both in batches and individually. We describe our unique team of researchers, practitioners, and student consultants who are blind, all of whom are needed to successfully develop this new way of translating tactile graphics.

We consider live continuous broadcast (such as radio or TV) to which users can join with time-shifting. They can join the broadcast at time t and receive the broadcast of time t - w for some offset parameter w ges 0. The simplest implementation that supports such a feature allocates a dedicated channel for each arrival time t and offset value w. Using such a technique, the server bandwidth quickly becomes a bottleneck. We adapt the stream merging technique to the time-shifting model, which allows us to greatly reduce the required server bandwidth. In addition to the application of distributing popular media, there are many other applications such as distance learning and large Internet events that could benefit from the use of time-shifting

Ringenburg et al. (2004) developed MultiStage, a bit-allocation algorithm for embedded video coders, that generates near-constant quality sequences. In this work, we show how the algorithm can be applied to quantization-based coders, and implement it for H.263. We also describe a novel approach for block-level bit allocation for H.263, cast as a variation on the multiple-choice knapsack problem, and show how to solve it efficiently with dynamic programming. Our results show that very stable quality can be achieved using relatively few coding iterations, with very little sacrifice in mean distortion.

For binary two-state Markov sources, we compute the bit-rate for context-independent Golomb coding, sequential coding, and interleaved coding. We also relate these coding methods to image compression work. Sequential coding is a context-dependent method that sequentially codes the source, choosing the order of the elementary Golomb code based on the last bit seen. Interleaved coding codes the even-numbered bits before the odd-numbered bits using elementary Golomb codes of several different orders. Of these methods, we show that no one method is best on all Markov sources.

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w1, l1),(w2, l 2),...,(wn, ln) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The processing length of job i is li slots (a slot is the processing time of one length unit). The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible parallel machines such that the gap (window) between two consecutive executions of the first slot of job i is at most wi slots. This problem arises in push broadcast systems in which data is transmitted on parallel channels.

We study the application of unequal loss protection (ULP) algorithms to motion-compensated video over lossy packet networks. In particular, we focus on streaming video applications over the Internet. The original ULP framework applies unequal amounts of forward error correction to embedded data to provide graceful degradation of quality in the presence of increasing packet loss. In this letter, we apply the ULP framework to baseline H.263, a video compression standard that targets low bit rates, by investigating reorderings of the bitstream to make it embedded. The reordering process allows a receiver to display quality video, even at the loss rates encountered in wireless transmissions and the current Internet.

This paper presents an algorithm for lossy compression of hyperspectral images for implementation on field programmable gate arrays (FPGA). To greatly reduce the bit rate required to code images, linear prediction is used between the bands to exploit the large amount of inter-band correlation. The prediction residual is compressed using the set partitioning in hierarchical trees algorithm. To reduce the complexity of the predictive encoder, this paper proposes a bit plane-synchronized closed loop predictor that does not require full decompression of a previous band at the encoder. The new technique achieves almost the same compression ratio as standard closed loop predictive coding and has a simpler on-board implementation.

We present three new bit allocation techniques, the multistage algorithm, the ratio algorithm, and the Pseudo I-frame method. The multistage and ratio algorithms are global interframe bit allocation algorithms for embedded video coders, which attempt to minimize the maximum distortion of any frame. The Pseudo I-frame method breaks a video into segments where bit allocation algorithms should be run, and segments where constant rate bit allocation will suffice. We present experiments, using the group testing for video coder (G. Shavit, et al., 2004), that compare our techniques to constant rate allocation and to a bit allocation algorithm due to Yang and Hemami (Y. Yang, et al., 1999).

Hong and Ladner (2001) used context-based group testing to implement bit-plane coding for image compression. We extend this technique to video coding, by replacing the quantization and entropy-coding stages, of an H.263 standard video coder, with bit-plane coding. We experiment with ways to improve baseline coder, including different classification schemes and cross-frame adaptive coding. Our results indicate that our new coder, GTV (group testing for video), significantly outperforms H.263 at medium to high bit-rates (300+kbps) on most sequences, while allowing very precise rate scalability.

We address the problem of designing optimal off-line algorithms that minimize the required bandwidth for media-on-demand systems that use stream merging. We concentrate on the case where clients can receive two media streams simultaneously and can buffer up to half of a full stream. We construct an O(nm) optimal algorithm for n arbitrary time arrivals of clients, where m is the average number of arrivals in an interval of a stream length. We then show how to adopt our algorithm to be optimal even if clients have a limited size buffer. The complexity remains the same. We also prove that using stream merging may reduce the required bandwidth by a factor of order $\rho L/\log(\rho L)$ compared to the simple batching solution where L is the length of a stream and $\rho\le 1$ is the density in time of all the n arrivals. On the other hand, we show that the bandwidth required when clients can receive an unbounded number of streams simultaneously is always at least 1/2 the bandwidth required when clients are limited to receiving at most two streams.

Summary form only given. The enhancements made to Sequitur for two more specific kinds of input are described, namely DNA strings and digitized music. Because of the natural orientation of the double helix DNA structure, DNA sequences bond to their reverse complements. Sequitur is enhanced to recognize reverse complements. These enhancements improved Sequitur's ability to compress and discover structure in DNA sequences. Several tables are given, which show a typical result for one human DNA sequence that is known to have some repetitive elements. Sequitur is enhanced to recognize three musical transformations: inversions, reversals, and transpositions.

The application of unequal loss protection (ULP) algorithms to motion-compensated video over lossy packet networks is studied. In particular, the focus is on streaming video applications over the Internet. The original ULP framework applies unequal amounts of forward error correction (FEC) to embedded data to provide graceful degradation of quality in the presence of increasing packet loss. The ULP framework is applied to baseline H.263, a non-embedded video compression standard, by investigating re-orderings of the bitstream. The re-ordering process makes the bitstream appear embedded, allowing a receiver to display high quality video even at the high loss rate encountered in wireless transmissions and the current Internet.

Many secure group communication systems rely on a group key, which is a secret shared among the members of the group. Secure messages are sent to the group by encrypting them with the group key. Because group membership is dynamic, it becomes necessary to change the group key in an efficient and secure fashion when members join or leave the group. We present a series of algorithms for solving this problem based on 2--3 trees, where each internal node has degree 2 or 3. The algorithms attempt to minimize the worst case communication cost of updating the group key and the auxiliary keys needed by the algorithms. The algorithms are analyzed for the worst case performance and evaluated empirically via simulations. We focus on the trade-off between the communication cost due to the structure of the tree and that due to the restructuring of the tree to maintain its structure.

We address the problem of designing efficient solutions for media-on-demand in systems that use stream merging. In a stream merging system, the receiving bandwidth of clients is larger than the playback bandwidth and clients can buffer parts of the transmission to be played back later. Intelligent use of these resources allows bandwidth usage to be reduced exponentially over traditional unicast delivery of popular media. We design an off-line algorithm that, in O(n) time, computes an optimal off-line stream merging solution for the case when the time horizon n is known ahead of time. In addition, we describe an on-line delay guaranteed solution that operates without knowledge of the time horizon size, and show that it performs asymptotically close to the optimal off-line algorithm. The on-line algorithm is simpler to implement than previously proposed on-line stream merging algorithms, and empirically performs well when the intensity of client arrivals is high.

The windows scheduling problem is defined by the positive integers n, h, and w 1 , ...,w n . There are n pages where the windoww i is associated with pagei , and h is the number of slotted channels available for broadcasting the pages. A schedule that solves the problem assigns pages to slots such that the gap between any two consecutive appearances of page i is at most w i slots. We investigate two optimization problems. (i) The optimal windows scheduling problem: given w 1 , ..., w n find a schedule in which h is minimized. (ii) The optimal harmonic windows scheduling problem: given h find a schedule for the windows w i = i in which n is maximized. The former is a formulation of the problem of minimizing the bandwidth in push systems that support guaranteed delay, and the latter is a formulation of the problem of minimizing the startup delay in media-on-demand systems. For the optimal windows scheduling problem we present an algorithm that constructs asymptotically close to optimal schedules, and for the optimal harmonic windows scheduling problem we show how to achieve the largest known n's for all values of h.

Summary form only given. Elementary Golomb codes have been widely used for compressing correlated binary sources. We study the theoretical bit-rate performance of two different Golomb coding methods on binary Markov sources: the sequential coding method, and the interleaved coding method. Although the theoretical bit-rate performance for these codes on on i.i.d. sources is known, to the best of our knowledge, theoretical performance results for elementary Golomb codes on correlated Markov sources have not been published.

This paper presents Group Testing for Wavelets (GTW), a novel embedded-wavelet-based image compression algorithm based on the concept of group testing. We explain how group testing is a generalization of the zerotree coding technique for wavelet-transformed images. We also show that Golomb coding is equivalent to Hwang's group testing algorithm. GTW is similar to SPIHT but replaces SPIHT's significance pass with a new group testing based method. Although no arithmetic coding is implemented, GTW performs competitively with SPIHT's arithmetic coding variant in terms of rate-distortion performance.

This paper introduces group testing for wavelet packets (GTWP), a novel embedded image compression algorithm based on wavelet packets and group testing. This algorithm extends the group testing for wavelets (GTW) algorithm to handle wavelet packets. Like its predecessor, GTWP obtains good compression performance without the use of arithmetic coding. It also shows that the group testing methodology is very flexible and can be applied in many different circumstances.

This paper presents the group testing for wavelets algorithm (GTM), which is a novel embedded wavelet-based image compression technique based on the concept of group testing. We explain how group testing is a generalization of the zerotree coding technique for wavelet-transformed images. We also show that Golomb coding is equivalent to Hwang's (Du and Hwang, 1993) group testing algorithm. GTW is similar to SPIHT (Said and Pearlman, 1996) but replaces SPIHT's sorting pass with a new group testing based method. Although no arithmetic coding is implemented, GTW performs competitively with SPIHT's arithmetic coding variant in terms of rate-distortion performance.

This paper describes an algorithm that achieves an approximately optimal assignment of forward error correction to progressive data within the unequal loss protection framework. It first finds the optimal assignment under convex hull and fractional bit allocation assumptions. It then relaxes those constraints to find an assignment that approximates the global optimum. The algorithm has a running time of O(hNlogN) where h is the number of points on the convex hull of the source's utility-cost curve and N is the number of packets transmitted.

We present the unequal loss protection (ULP) framework in which unequal amounts of forward error correction are applied to progressive data to provide graceful degradation of image quality as packet losses increase. We develop a simple algorithm that can find a good assignment within the ULP framework. We use the set partitioning in hierarchical trees coder in this work, but our algorithm can protect any progressive compression scheme. In addition, we promote the use of a PMF of expected channel conditions so that our system can work with almost any model or estimate of packet losses. We find that when optimizing for an exponential packet loss model with a mean loss rate of 20% and using a total rate of 0.2 bits per pixel on the Lenna image, good image quality can be obtained even when 40% of transmitted packets are lost.

Entropy-constrained vector quantization (ECVQ) offers substantially improved image quality over vector quantization (VQ) at the cost of additional encoding complexity. We extend results in the literature for fast nearest neighbor search of VQ to ECVQ. We use a new, easily computed distance that successfully eliminates most codewords from consideration.

We present an algorithm that assigns unequal amounts of forward error correction to progressive data so as to provide graceful degradation as packet losses increase. We use the SPIHT coder to compress images in this work, but our algorithm can protect any progressive compression scheme. The algorithm can also use almost any function as a model of packet loss conditions. We find that for an exponential packet loss model with a mean of 20% and a total rate of 0.2 bpp, good image quality can be obtained, even when 40% of transmitted packets are lost.

We present an approach to the generalized multiple description problem (V.K. Goyal et al., 1998) that is fundamentally different from previously published algorithms. Our approach uses explicit channel coding in the form of unequal loss protection to obtain a solution that incorporates many important properties: it can be used with any progressive source coder; it generates a balanced encoding with information equally dispersed among the descriptions; it adds a quantifiable amount of redundancy; it adapts that amount of redundancy to expected channel conditions; and it can optimize for different distortion measures. These properties allow the system to gradually improve image quality as the number of received descriptions increases. We compare our system to previously published results and show that forward error correction in multiple description coding can surpass them by a significant margin.

We propose a new maximum a posteriori (MAP) detector, without the need for explicit channel coding, to lessen the impact of communication channel errors on compressed image sources. The MAP detector exploits the spatial correlation in the compressed bitstream as well as the temporal memory in the channel to correct channel errors. We first present a technique for computing the residual redundancy inherent in a compressed grayscale image (compressed using VQ). The performance of the proposed MAP detector is compared to that of a memoryless MAP detector. We also investigate the dependence of the performance on memory characteristics of the Gilbert-Elliott channel as well as average channel error rate. Finally, we study the robustness of the proposed MAP detector's performance to estimation errors.

We propose a method for constructing a tiling between a pair of planar polygons. Our technique uses multiresolution: tilings of lower resolution polygons are used to construct a tiling for the full resolution polygons. The tilings are constructed using banded refinement, by restricted dynamic programming, in roughly linear time and space. By contrast, the optimal dynamic programming method requires quadratic time and space. In our empirical study of surface reconstruction of brain contours our algorithm exhibited significant speedup over the optimal dynamic program, yet nearly always found an optimal reconstruction. Our approach appears to be generalizable to other geometric problems solvable by dynamic programming, and flexible enough to be tuned for varying data set characteristics. 1 Introduction A typical subproblem of many surface reconstruction algorithms is the fitting of a surface to a set of parallel contours. This problem arises, for example, in medical visualization applic...

We consider the problem of sorting on a one-dimensional subbus array of processors, an architecture that communicates using a segmentable bus. The subbus broadcast operation makes possible a new class of parallel sorting algorithms whose complexity we analyze with the parallel insertion model. We give per-input lower bounds for sorting in the parallel insertion model and demonstrate sorting strategies that are optimal by matching those lower bounds. For each of our sorting strategies, we discuss the issues involved in implementing them on subbus machines. Finally, we empirically evaluate the performance of our sorting strategies by applying them to shearsort, a common two-dimensional mesh sorting algorithm. Our results suggest that for sorting the subbus broadcast capability gives at most a slight advantage over using only nearest neighbor communication.

We study image transmission on a lossy packet network in which the loss mechanism is modeled as buffer overflows. A simple error concealment strategy involving table lookups and a buffer allocation scheme with an optimally chosen virtual boundary for a 2 priority class system are described. Significant improvements are achieved by combining these two strategies.

Many variants of vector quantization offer substantially improved image quality at the cost of additional complexity in encoding. Algorithms for increased speed in nearest neighbor searches for full search VQ using the Euclidean distortion measure have been presented previously with excellent results. We extend these results to any variant of VQ such as entropy constrained vector quantization (ECVQ), and Bayes-risk VQ, which uses a Lagrangian distortion measure. Additionally we introduce a variation of the existing techniques which provides additional speedup for full search VQ using Euclidean distortion as well as for those VQs using modified distortion measures.

The time complexity of several fundamental problems on the sub-bus mesh parallel computer with p processors is investigated. The problems include computing the PARITY and MAJORITY of p bits, the SUM of p numbers of length $O(\log p)$, and the MINIMUM of p numbers. It is shown that in one dimension the time to compute any of these problems is $\Theta (\log p)$. In two dimensions the time to compute any of PARITY, MAJORITY, and SUM is $\Theta (\tfrac{{\log p}} {{\log \log p}})$. It was previously shown that the time to compute MINIMUM in two dimensions is $\Theta (\log \log p)$ [R. Miller et al., IEEE Trans. Comput., 42 (1993), pp. 678–692; L. Valiant, SIAM J. Comput., 4 (1975), pp. 348–355]

We describe a new way to organize a full-search vector quantization codebook so that images encoded with it can be sent progressively and have resilience to channel noise. The codebook organization guarantees that the most significant bits (MSBs) of the codeword index are most important to the overall image quality and are highly correlated. Simulations show that the effective channel error rates of the MSBs can be substantially lowered by implementing a maximum a posteriori (MAP) detector similar to one suggested by Phamdo and Farvardin (see IEEE Trans. Inform. Theory, vol.40, no.1, p.156-193, 1994). The performance of the scheme is close to that of pseudo-gray coding at lower bit error rates and outperforms it at higher error rates. No extra bits are used for channel error correction.

We consider the sequence transmission problem, that is, the problem of transmitting an infinite sequence of messages x 1 x 2 x 3 … over a channel that can both lose and reorder packets. We define performance measures, ideal transmission cost and recovery cost, for protocols that solve the sequence transmission problem. Ideal transmission cost measures the number of packets needed to deliver x n when the channel is behaving ideally and recovery cost measures how long it takes, in terms of number of messages delivered, for the ideal transmission cost to take hold once the channel begins behaving ideally. We also define lookahead, which measures the number of messages the sender can be ahead of the receiver in the protocol. We show that any protocol with constant recovery cost and lookahead requires linear ideal transmission cost. We describe a protocol, P lin , that has ideal transmission cost 2 n , recovery cost 1, and lookahead 0.

The calendar queue is an important implementation of a priority queue which is particularly useful in discrete event simulators. In this paper we present an analysis of the static calendar queue which maintains N active events. A step of the discrete event simulator removes and processes the event with the smallest associated time and inserts a new event whose associated time is the time of the removed event plus a random increment with mean /spl mu/. We demonstrate that for the infinite bucket calendar queue the optimal bucket width is approximately /spl delta//sub opt/=/spl radic/(2b/c)/spl mu//N where b is the time to process an empty bucket and c the incremental time to process a list element. With bucket width chosen to be /spl delta//sub opt/, the expected time to process an event is approximately minimized at the constant c+/spl radic/(2bc)+d, where d is the fixed time to process an event. We show that choosing the number of buckets to be O(N) yields a calendar queue with performance equal to or almost equal to the performance of the infinite bucket calendar queue.>

Examines how the performance of a memoryless vector quantizer changes as a function of its training set size. Specifically, the authors study how well the training set distortion predicts test distortion when the training set is a randomly drawn subset of blocks from the test or training image(s). Using the Vapnik-Chervonenkis (VC) dimension, the authors derive formal bounds for the difference of test and training distortion of vector quantizer codebooks. The authors then describe extensive empirical simulations that test these bounds for a variety of codebook sizes and vector dimensions, and give practical suggestions for determining the training set size necessary to achieve good generalization from a codebook. The authors conclude that, by using training sets comprising only a small fraction of the available data, one can produce results that are close to the results obtainable when all available data are used.>

The authors study codeword index assignment to allow for progressive image transmission of fixed rate full-search vector quantization (VQ). They develop three new methods of assigning indices to a vector quantization codebook and formulate these assignments as labels of nodes of a full-search progressive transmission tree. The tree is used to design intermediate codewords for the decoder so that full-search VQ has a successive approximation character. The binary representation for the path through the tree represents the progressive transmission code. The methods of designing the tree that they apply are the generalized Lloyd algorithm, minimum cost perfect matching from optimization theory, and a method of principal component partitioning. Their empirical results show that the final method gives intermediate signal-to-noise ratios (SNRs) that are close to those obtained with tree-structured vector quantization, yet they have higher final SNRs.

In this paper we present tight bounds on the efficiency of protocols that transmit messages through a communications channel that can lose and reorder packets and discuss new ways to measure the behavior of such protocols.

The classes of functions $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ that are analogous to the class $# P$ are defined. Functions in $# \textit{PSPACE}$ count the number of accepting computations of a nondeterministic polynomial space bounded Turing machine, and functions in $\natural \textit{PSPACE}$ count the number of accepting computations of nondeterministic polynomial space bounded Turing machines that on each computation path make at most a polynomial number of nondeterministic choices. In contrast to what is known about $# P$, exact characterizations of both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ are found. In particular, $# PSPACE = FSPACE$ (the class of functions computable in polynomial space) and $\natural PSPACE = FSPACE (poly)$ (the class of functions computable in polynomial space with output length bounded by a polynomial). Both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ can be characterized by counting problems related to alternating Turing machines. Both $# \textit{PSPACE}$ and $\natural \textit{PSPACE}$ have natural complete functions. It is an easy observation that $FP \subseteq # P \subseteq \natural \textit{PSPACE} $, where $FP$ is the class of functions computable in polynomial time. Relativization to oracles is considered, as are approximation techniques for obtaining a better understanding of whether either of the above inclusions is proper.

Article Free Access Share on Public Law 99-506, “Section 508” Electronic Equipment Accessibility for disabled workers Authors: R. E. Ladner Univ. of Washington, Washington, DC Univ. of Washington, Washington, DCView Profile , F. A. McDonough General Services Administration General Services AdministrationView Profile , W. Roth Center for Computing and Disability, SUNY Albany Center for Computing and Disability, SUNY AlbanyView Profile , L. A. Scadden Electronics Industries Foundation Electronics Industries FoundationView Profile , G. C. Vanderheiden Trace Research and Development Center Trace Research and Development CenterView Profile Authors Info & Claims CHI '88: Proceedings of the SIGCHI Conference on Human Factors in Computing SystemsMay 1988 Pages 219–222https://doi.org/10.1145/57167.57204Online:01 May 1988Publication History 5citation418DownloadsMetricsTotal Citations5Total Downloads418Last 12 Months13Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A user interface suitable for deaf-blind users is presented and justified. The interface is designed for small paperless Braille displays, large font visual displays, or other low-bandwidth displays. Some of the key properties of the interface are that it uses a hierarchical approach to structure both commands and data, has a small universal command set, and has pervasive editing capability. DBNet, a system employing the user interface, has been built and tested with deaf-blind users. DBNet will provide various communication services to the deaf-blind community including electronic news, mail, and bulletin boards.

New, improved algorithms are proposed for regulating access to a multiple-access channel, a common channel shared by many geographically distributed computing stations. A conflict of multiplicity n occurs when n stations transmit simultaneously to the channel. As a result, all stations receive feedback indicating whether n is 0, 1, or ≥2. If n = 1, the transmission succeeds; whereas if n ≥ 2, all the transmissions fail. Algorithms are presented and analyzed that allow the conflicting stations to compute a stochastic estimate n * of n , cooperatively, at small cost, as a function of the feedback elicited during its execution. An algorithm to resolve a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining one of our estimation algorithms with a tree algorithm (of Capetanakis, Hayes, and Tsybakov and Mikhailov) then leads to a hybrid algorithm for conflict resolution. Several efficient combinations are possible, the most efficient of which resolves conflicts about 20 percent faster on average than any of the comparable algorithms reported to date.

The classes of languages accepted by alternating pushdown automata, alternating stack automata, and alternating nonerasing stack automata, both with and without an auxiliary space bounded worktape, are characterized in terms of complexity classes defined by time bounded deterministic Turing machines. It is also shown that alternating 2-way finite state machines accept only regular languages.

A design of a data structure and efficient algorithms for concurrent manipulations of a dynamic search structure by independent user processes is presented in this paper. The algorithms include updating data, inserting new elements, and deleting elements. The algorithms support a high level of concurrency. Each of the operations listed above requires only constant amount of locking. In order to make the system even more efficient for the user processes, maintenance processes are introduced. The maintenance processes operate independently in the background to reorganize the data structure and “clean up” after the (more urgent) user processes. A proof of correctness of the algorithms is given and some experimental results and extensions are examined.

A conflict of multiplicity k occurs when k stations transmit simultaneously to a multiple access channel. As a result, all stations receive feedback indicating whether k is 0, 1, or is ≥ 2. If k = 1 the transmission succeeds, whereas if k ≥ 2 all the transmissions fail. In general, no a priori information about k is available. We present and analyze an algorithm that enables the conflicting stations to cooperatively compute a statistical estimate of k, at small cost, as a function of the feedback elicited during its execution. An algorithm to resolve a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining our estimation algorithm with a binary tree algorithm leads to a hybrid algorithm that resolves conflicts faster on average than any other reported to date.

In this paper we consider variations on the binary search algorithm when placed in the context of a multiprocessing environment. Several organizations are investigated covering the spectrum from total independence (or free competition for access to common resources) to cooperation as in SIMD architectures. It is assumed that the two main sources of overhead are memory interference and interprocessor synchronization. An organization combining interference-free access to memory by implicit synchronization and a small degree of cooperation yields the best results.

The prefix problem is to compute all the products x t o x2 .... o xk for i ~ k .~n, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has depth exactly [log:n] and size bounded by 4n An application yields fast, small Boolean ctrcmts to simulate fimte-state transducers.By simulating a sequentml adder, a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n Is obtained for n-bit binary addmon The size can be decreased significantly by permitting the depth to increase by an addmve constant KEY WORDS AND PHRASES automaton, binary addmon, clrcmt, combinational complexity, depth, fanout, parallehsm, size, transducer CR CATEGORIES 5.22, 5 25, 6 1, 6 32 X3 o X2.

There is a wide-spread belief among computer scientists that systems of communicating sequential processes are harder to analyze than purely sequential processes. The belief is largely based on the observation that the parallelism in such systems leads to a large number of possible interleavings of the actions of the different processes. We will show that other evidence supporting this belief is that the properties we are trying to analyze about these systems are themselves intrinsically complex. They are properties that make no sense when they are applied to purely sequential processes, or even parallel systems of sequential processes that have no ability to communicate with each other.

We introduce a fundamental propositional logical system for describing correctness, termination and equivalence of programs. We define a formal syntax and semantics for the propositional modal logic of programs and give several consequences of the definition. Principal conclusions are that deciding satisfiability requires time dn/log nfor some d > 1 and that satisfiability, even in an extended system, can be decided in nondeterministic time cnfor some c. We provide applications of the decision procedure to regular expressions, Ianov schemes, and classical systems of modal logic.

The computational complexity of the provability problem in systems of modal propositional logic is investigated. Every problem computable in polynomial space is $\log $ space reducible to the provability problem in any modal system between K and $S4$. In particular, the provability problem in K, T, and $S4$ are $\log $ space complete in polynomial space. The nonprovability problem in $S5$ is $\log $ space complete in nondeterministic polynomial time.

Two notions of polynomml time reduclbihty, denoted here by ~ T e and <.~P, were defined by Cook and Karp, respectively The abstract propertms of these two relatmns on the domain of computable sets are investigated.Both relations prove to be dense and to have minimal pairs.Further, there is a strictly ascending sequence with a minimal pair of upper bounds to the sequence.Our method of showing density ymlds the result that if P ~ NP then there are members of NP --P that are not polynomml complete KEY WORDS AND PHRASES polynomial time computation, Turing reduc~billty, many-one reducibility CR CATEGORIES 5 25

Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. We give definitions and comparisons for these reducibilities; we note, in particular, that all reducibilities of this type which do not have obvious implication relationships are in fact distinct in a strong sense. Proofs are by simultaneous diagonalization and encoding constructions.Work of Meyer and Stockmeyer [7] and Gill [2] then leads us to define nondeterministic versions of all of our reducibilities. Although many of the definitions degenerate, comparison of the remaining nondeterministic reducibilities among themselves and with the corresponding deterministic reducibilities yields some interesting relationships.

Several of the results that appear in [4] are stated to be true of polynominal time reducibility (≤p) but are not proved explicitly. We shall prove several of these results with the hope of shedding some light on the “determinism vs. nondeterminism” problem. The ideas behind these proofs already exist in [4] but appear here in a different setting. We shall spend most of our time on two theorems: (i) If φ <p Β then there exists an Α such that φ<p Α

A recursively enumerable (r.e.) set is mitotic if it is the disjoint union of two r.e. sets both of the same degree of unsolvability. A. H. Lachlan has shown in [3] that there exists a nonmitotic r.e. set. In this paper we make an initial investigation into the class of mitotic sets. The following results are proved, (i) An r.e. set is mitotic if and only if it is auto-reducible, (ii) There is a nonmitotic r.e. set of degree 0′, (iii) If d is an arbitrary non-recursive r.e. degree then there exists a nonmitotic r.e. set of degree ≤d. (iv) There exists a maximal set which is mitotic and a maximal set which is nonmitotic. Albert R. Meyer had independently proved (ii) and (iii) for nonautoreducible sets before (i) was known.