UT Algorithms and Computational Theory Group

Research Themes

The algorithms and computational theory (ACT) group focuses on the theoretical foundations of computer science. The current research interests of faculty in the group include algorithm design, complexity theory, parallel and distributed computation, graph theory, randomized computation, computational learning theory, probabilistic methods and combinatorics. A major focus of the group is on the design and analysis of provably efficient algorithms for solving fundamental computational problems, where efficiency can be measured in terms of different resources such as time, space, number of processors, and number of random bits. We also have strong connections to application areas of theoretical CS such as data mining and computational biology.

Faculty

Algorithms and Complexity

Scott Aaronson -- Quantum computing, computational complexity.
Anna Gal (panni"at"cs.utexas.edu) --- Computational complexity, lower bounds, fault tolerant computing, randomness and computation, algorithms, combinatorics.
Adam Klivans (klivans"at"cs.utexas.edu) --- Learning Theory, computational complexity, pseudorandomness, limit theorems.
Dana Moshkovitz -- Probabilistically checkable proofs (PCPs), pseudorandomness, coding theory, algorithms.
Greg Plaxton (plaxton"at"cs.utexas.edu) --- Algorithm design and analysis, algorithmic game theory.
Eric Price (ecprice"at"cs.utexas.edu) -- Algorithms.
Vijaya Ramachandran (vlr"at"cs.utexas.edu) --- Algorithm design and analysis, parallel computation, machine models, graph theory, graph algorithms and data structures.
Brent Waters --- cryptography.
David Zuckerman (diz"at"cs.utexas.edu) --- Randomness and computation, pseudorandomness, computational complexity, coding theory, distributed computing, cryptography.

Data Mining and Machine Learning

Inderjit Dhillon, machine learning/data mining, numerical linear algebra.
Pradeep Ravikumar, statistics, machine learning.

Computational Biology and Bioinformatics

Chandra Bajaj, computational biology, visualization.
Bill Press, computational biology.

Formal Methods

Recently Graduated Students and Postdocs

We have had great success in placing our students and postdocs in academia and research labs. We list a few recent examples here:

Allison Lewko, now at Columbia.
Xin Li, now at Johns Hopkins University.
Raghu Meka, now at Microsoft Research.
Sasha Sherstov, now at UCLA.
Anup Rao, now at U. Washington.
Rezaul Alam Chowdhury, now at Stony Brook U.
Parikshit Gopalan, now at Microsoft Research.
Seth Pettie, now at U. Michigan.

Student Awards

We are proud of the prestigious awards our students have won at major TCS conferences:

Sasha Sherstov, Best Student Paper Award (Machtey Prize) at FOCS 2009.
Sasha Sherstov, Best Student Paper Award at Complexity 2008.
Sasha Sherstov, Best Student Paper Award at Complexity 2007.
Anup Rao, Best Student Paper Award (Danny Lewin Prize) at STOC 2006.
Sasha Sherstov, Best Student Paper Award at COLT 2006.
Vladimir Trifonov, Best Student Paper Award (Danny Lewin Prize) at STOC 2005.
Seth Pettie, Best Student Paper Award at ICALP 2002.
Seth Pettie, Best Paper Award at ICALP 2000.
Pierre Kelsen, Best Student Paper Award at STOC 1992.

Seminar Series

The ACT Seminar usually meets on Fridays at 11, and features research talks, problem solving sessions, and discussion of recent theory research results.

Click here for the ACT seminar calendar.

The `algorithms' Mailing List

The algorithms mailing list is an electronic mailing list on which ACT seminars are announced. If you are part of the UT community can add yourself to this mailing list by sending an e-mail message to udb"at"cs.utexas.edu; please describe your UT affiliation along with your request to be added to the algorithms mailing list. You can remove your name from this mailing list at any time by sending a message requesting removal to udb"at"cs.utexas.edu.