REU Site: Combinatorics, Algorithms, and AI applied to Real Problems (CAAR)

This program will recruit 10 to 20 undergraduates per year to come to the University of Maryland at College Park where they will work for 10 weeks on team research projects with expert mentors. The goal of these projects is to take theoretical results and make progress towards using them in practice. To illustrate our approach, we list four real examples of topics studied in this project and describe how they serve the national interest.

(1) Making programs run faster (e.g., by making them parallel so they can be run using multiple computers or cores). This will benefit all sciences as more and more work in science relies on fast computation. Note that the most recent Nobel prize in Chemistry went to work that used computation in a major way.

(2) Making computer more secure (e.g., by studying secure cryptography and efficient communication schemes). Advancing secure communication is important for both the Military and Financial sectors.

(3) Getting Artificial Intelligence (AI) to make less errors. AI now plays a critical role in healthcare, e.g., in disease diagnosis, selecting treatment, clinical lab testing, drug discovery, and many other tasks. Many such applications are hampered by the fact that AI can make errors and harm people as a result. Practical research on AI aimed at reducing mistakes is important for the health and prosperity of our nation.

(4) Make quantum computers practical. Sometime in the future practical quantum computing may be a reality. We need to both hasten this advance and know how to take advantage of it. Two important applications are simulating quantum mechanics (which will help science) and cryptography (which is important for security).

This program will give undergraduate students a unique opportunity to do research. This is especially important for students who normally do not have that opportunity, in particular, students from non-research-focused schools and from underrepresented groups. There will be a special effort to recruit such students.

This effort will increase the number of researchers which will help science and technology progress faster. This program will give students an idea of what graduate school is like in two ways: (1) their research projects are scaled down versions of Ph.D. theses; and

(2) there will be interaction with other students in Research Experience for Undergraduates (REU) programs, current graduate students, and faculty.

The students will be offered a variety of research projects, and will also be given a strong voice in the creation of their own projects. We list sample projects below:

(1) Parallel Computing: If one computer or core can solve a problem in time T then perhaps p computers (cores) can solve that problem in T/p time. In this project students will study how to design practical and efficient algorithms that can be run on real-world parallel computers and obtain large speedups.

(2) Cryptography and Security: Most current cryptosystems are based on factoring (or other problems in number theory) being hard. Since factoring might become easy due to quantum computers becoming realistic, there has been much work on designing alternative cryptosystems. This project will code up these alternatives to test if they are easy to use, efficient, and secure.

(3) Question-Answering Systems (AI): There are many AI programs that will, given a question, try to answer it. If the question is given as text, they often do very well. If the question is given as an image (e.g., "is this a dog?") then they often do poorly. This project will discern which questions they do badly on and strive to make the system better.

(4) Quantum Error Correction: If Alice sends a string of (classical) bits over a noisy line then she can use error-correction techniques that will detect and correct errors. One obstacle to real quantum computers is the lack of good error-correction for qubits. This project will study known quantum error correction techniques and extend them.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.