Wanted: Undergrads
Funding for four undergrad summer projects (listed below)
Contact: Professor Aram Harrow aram@cs.washington.edu
1. Compressed sensing of tensors
2. Web infrastructures for open science
3. Quantum gate compiling
4. Hard instances of group and graph isomorphism
Here is a little more information about each project.
-------------------------------------------------------
1. Compressed sensing of tensors
Tensors are generalizations of matrices that can be thought of as arrays with more than two indices. Unfortunately, they lack many of the mathematical properties of matrices, such as eigenvalues and eigenvectors, that make them amenable to fast algorithms, such as Gaussian elimination. Nevertheless, they appear in many practical problems of data analysis, as well as open problems in complexity
theory. Thus, finding fast algorithms to perform calculations on
tensors is a major open problem in algorithmic research.
This project will focus on one specific problem, which is recovering a tensor from a small number of measurements (also known as compressed sensing). Previously, compressed sensing has been widely used for vector and matrix data. For example, it was a key component of the recent winning solution to the Netflix prize. However, performing compressed sensing of tensors presents a number of new challenges.
This research project involves developing and implementing algorithms for compressed sensing of tensors, and then testing them on both synthetic and real data.
Requirements:
The project has both programming and math components. The programming will involve large-scale matrix calculations, but the mathematical side will probably be more challenging. The math required will be linear algebra. Having taken a course in convex optimization would be a plus, but is not necessary.
----------------------------------------------------------
2. Web infrastructures for open science
Even though the internet was originally designed to revolutionize scientific communication, scientific publishing remains dominated by the centuries-old journal model. We are looking for a web developer to help disrupt this model by creating and maintaining web tools to facilitate new forms of scientific communication. Specifically, we want to develop a website that would add various social features to arxiv.org (which is the dominant preprint server used in physics, math, computer science and other fields). Some examples of what this site would allow are:
1. Public discussion of papers on arxiv.org, ranging from facebook-style "likes" to stackexchange-style comment threads.
2. Hosting "overlay journals," which would perform the traditional peer review of existing journals, but would leave the papers hosted on arxiv.org. In this way, they could function without requiring copyright transfer or any subscription charges.
3. Hosting "journal clubs" and other discussion fora that are centered around existing research groups, or topical areas.
These are not meant to be exhaustive, and we are open to discussing new ideas in this space as well.
This project will involve deploying a live website that will be used by an active community of scientists.
Minimum Requirements:
Web development experience is required, preferably for sites with an active user base. Ability to work independently. Courses in HCI or web programming are a plus, but are not required.
-----------------------------------------------------
3. Quantum gate compiling
The goal of quantum computing is to exploit quantum physics to create new types of computers that are qualitatively different from any previous model of computation. As with conventional computers, quantum computers will require a method of 'compiling' high-level commands into elementary logic gates. However, these gates are no longer operations such as NAND and OR, but instead are described by matrices. The compiling problem is to find a short string of the known gates that can be multiplied together to approximate a target gate.
The goal of this project is to implement and to attempt to improve various compiling proposals due to Kitaev, Shen and Vyalyi (KSV).
Implementation will involve learning the math behind the KSV compiling techniques and coding them in a language such as C, python or matlab.
The next goal of the project is to extend the KSV compiler to account for realistic features of (proposed) quantum architectures, such as the requirement that gates act on qubits (quantum bits) that are spatially adjacent. Another more speculative goal is to improve the performance of the compiler in the setting of gates that act on many qubits.
Minimum Requirements:
Programming ability and mathematical maturity are required. The main area of mathematics involved will be linear algebra, although only basic linear algebra concepts will be used (albeit in a sophisticated way).
---------------------------------------------------------
4. Hard instances of group and graph isomorphism
Given two graphs G and H, is it possible to relabel the vertices in G so that it equals H? Similarly, given two groups, when are they equivalent up to a relabeling of their elements? These problems are known as *isomorphism problems* and their computational complexity is an open problem, as they are neither known to be in P, nor to be NP-complete. On the one hand, no polynomial-time algorithms are known for them, despite decades of study. On the other hand, there is evidence that they are not NP-complete, and group isomorphism can be solved in nearly polynomial time, while no examples of graph isomorphism are known that can defeat all known algorithms. (On the other hand, these existing graph-isomorphism algorithms have not been proven to work in all cases.)
The goal of this project is to search for hard instances of the group isomorphism problem by exhaustively checking all groups up to a certain order. Next, by translating group isomorphism problems into graph isomorphism problems, this project would seek to construct hard instances of graph isomorphism. The project will therefore involve programming and also some group theory. Depending on how the code performs on a single core, it may be necessary to parallelize the code or port it to run on a cluster. The results should be publishable if the project is successful.
Additional technical details are available at http://www.cs.washington.edu/homes/aram/misc/search-iso.pdf
Minimum requirements:
Programming knowledge and mathematical maturity. You must be willing to learn basic group theory, but do NOT need to already have taken a class in it.
