RESEARCH

Over the past five years, I've worked in a number of different areas, including multimedia, auction theory, data compression, quantum computation, and computational geometry. I am currently deeply involved in the Mobile ASL project, working on activity recognition within American Sign Language. My advisors are Richard Ladner and Eve Riskin.
	Mobile ASL The goal of the Mobile ASL project is to compress sign language video so that deaf users can communicate via cell phone. While the deaf community has welcomed new technologies such as the Blackberry and other PDAs, it is cumbersome to use text messaging when compared to signing, since the speed of sign language is equivalent to speech. However, with current compression technology and low mobile phone bit rates, real-time video transmission is not possible. Our goal is to make cell phones accessible by supporting real-time compression and transmission of sign language video. Through user studies, we have discovered that deaf users can understand signs at very low frame rates. However, this is not true of finger spelling, which consists of small, specific motion. My goal is to distinguish between signing and finger spelling so we can adjust frame and bit rate to maximize efficiency while still remaining intelligible. We have verified the intelligibility of varying the frame rate and quantified the power savings on the phone. Our machine learning techniques have been successful at distinguishing, in real-time, signing frames from listening frames. See my publications.
	Multimedia Video-on-demand is a service in which a user interactively selects and downloads movies and other content. There are two main ways to implement video-on-demand from the server's perspective. The server could wait for requests and then react to them, perhaps by bundling requests together. However, this method requires a two-way communication channel between the server and client. Some servers, such as satellite TV, don't have two-way capabilities. The other choice is to proactively broadcast movies that are likely to be on demand. Since requests for movies follow a Zipf distribution, broadcast methods could serve the vast majority of on-demand needs. In Data Compression Conference 2006, I detailed our method for periodic broadcast of compressed variable bit rate movies. See my publications for more details.
	Auction Theory Auction theory is the study of problems at the intersection of game theory, economics, and computer science. Christos Papadimitriou essentially introduced the area with a paper describing how the internet has spawned new problems that may be answered using techniques from economics. In joint work with Atri Rudra, Ning Chen, Nikhil Bansal, Baruch Schieber, and Maxim Sviridenko, we looked at the problem of selling items to impatient bidders. Suppose an online music store wishes to sell unlimited copies of a song to a set of customers, and suppose each customer has a maximum price, an arrival time, and a departure time. If the store sets a price below a customer's maximum price while they are in the store, the customer will immediately buy the song. How can we set prices so as to maximize the store's revenue? We prove tight bounds on the competitiveness of deterministic online algorithms for this model. See my publications for further details.
	Data Compression For my qualifying project, I explored data compression of DNA. Sequitur is an elegant, linear-time online compression algorithm that also finds structure. I experimented with using Sequitur to compress DNA sequences. Follow the link below for more details, including my paper, my talk, and the datasets. This work was presented at the DIMACS Working Group on the Burrows-Wheeler Transform and is published as UW CSE Technical Report 2007-05-02: Grammar-based compression of DNA Sequences. Also in the field of data compression, I extended our group's work on MultiStage, a rate control algorithm, to H.264. See my publications for further details.
	Quantum computation In 1994, Peter Shor created a quantum algorithm that factored numbers in polynomial time, thus breaking RSA encryption (if we ever build a quantum computer). I am fascinated by the complexity issues at the intersection of quantum computation, cryptography, and the polynomial time hierarchy. What characterizes problems that can be solved quickly on a quantum computer? How does this affect the search for one-way functions and better cryptographic techniques? In spring 2003, I presented Sean Hallgren's quantum algorithm for Pell's Equation, which was the first-in-a-while quantum algorithm for a "practical" problem.
	Other work My final project in graphics was a frog animation. I also introduced a computational geometry problem to my fellow theory students that they discovered was NP-hard.

PUBLICATIONS

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.