Algorithms and Theory Laboratory

Welcome to the Algorithms and Theory Laboratory. Algorithms and theory covers a huge range of topics: classical complexity-theoretic and foundational questions; practical algorithms within specific problem domains; creating general-purpose tools and techniques; making abstract models that help one see into the heart of a problem. Theoretical computer science teaches a set of methods, ideas, and viewpoints that help us abstract problems from their messy human, scientific, or technological context, solve the problem, and re-inject the solution back into practice. That is what we like to do. If there’s an over-arching theme for our work, it is to develop and apply theory in a way that is interesting and useful; it is characteristic for the theory folks at UCD that our aesthetic sensibilities are informed by relevance (as well as by the math and wanting to have some fun).

In the last decade or so we have grown considerably, from three faculty to eight, with the growth occurring in computational biology, cryptography, and scientific computing. The following are some areas of particular interest by faculty members in the group: bioinformatics, combinatorial algorithms and optimization, computational biology, computational geometry, cryptography, data structures, distributed algorithms, graph algorithms, mathematical modeling, mathematical software, matrix computations, network phenomena, numerical linear algebra, parallel algorithms, provable security, scientific computing, string matching, and theoretical aspects of visualization. See faculty members’ individual web sites to get a feel for what we do.

While work in algorithms and theory can often be done under a tree
as well or better than in a physical laboratory, we
*do* have a physical lab where many of our graduate students live.
It’s at 2235 Kemper Hall, phone +1 530 752 8819.

- Nina Amenta - computational geometry, computer graphics (pubs)
- Zhaojun Bai - scientific computing, numerical linear algebra (pubs) (book)
- David Doty - molecular computing, distributing computing, theory (pubs)
- Vladimir Filkov - computational biology (pubs)
- Matt Franklin - cryptography (pubs)
- Dan Gusfield - algorithms, computational biology, bioinformatics (pubs) (book) (oldbook)
- Patrice Koehl - computational biology (pubs) (research web site)
- Chip Martel - algorithms (pubs)
- Phillip Rogaway - cryptography (pubs)

- Fatemeh Abbasinejad (advisor is Nina)
- Dimitiri DeFigueiredo (2235 Kemper) (advisors are Felix and Karl)
- Yelena Frid (advisor is Dan)
- Davide Gae (advisor is Patrice) (Biophysics)
- Rob Gysel (advisor is Dan)
- Matthew Lietzke (advisor is Bai)
- Shengren Li (advisor is Nina)
- Paul Mach (advisor is Patrice) (GGAM)
- Victor Missirian (advisor is Vladimir)
- Lance Simons (advisor is Nina)
- Kristian Stevens (advisor is Dan)
- Kristin Tennessen (advisor is Patrice)
- Balaji Venkatachalam (2235 Kemper) (advisor is Dan)
- Eric Willgohs (advisor is Patrice) (BME)
- Haibin Zhang (advisor is Matt)

- Euisung Kang (working with Patrice)
- Xinwei Shi (working with Patrice)
- Eric di Luccio (working with Patrice)
- Fumei Lam (working with Dan)
- Jun Liu (working with Bai and Richard Scalettar)
- Niroshan Nadarajah (working with Vladimir)
- Soumen Roy (working with Vladimir and R D'Souza)

- Gergei Bana (postdoc 06-07, Matt/Phil) (Instituto Superior Técnico, Portugal)
- John Black (PhD 2000, Phil) (University of Colorado, Boulder)
- Wenbin Chen (postdoc 2004-2006, Bai) (Fudan University, China)
- Sunghee Choi (PhD 2003, UT Austin, Nina) (KAIST)
- Archie Cobbs (PhD 199?, UC Berkeley, Dan) (Awarix)
- Kelly Dun (MSc 2005, Vladimir) (SecuriMetrics)
- Ananya Das (PhD 2010, Chip) (Lake Forest College)
- Zhihong Ding (Dan) (Adobe)
- Oliver Eulenstein (postdoc 1998-99, Dan) (Iowa State University)
- David Fernandez-Baca (PhD 1986, Chip) (Iowa State University)
- Patricia Francis-Lyon (advisor is Patrice)
- Jeremy Frank (PhD 1997, Chip) (NASA Ames)
- Eiichiro Fujisaki (visitor 98-99, Phil) (NTT, Japan)
- Martin Gagne (PhD 2008, Matt) (University of Calgary)
- Abel Gezahegne (MSc 2005, Nina) (Google)
- Mark Gondree (PhD 2008, Matt) (Naval Postgraduate School)
- Saurabh Goyal (MSc 2003, Matt) (?)
- Shengyin Gu (advisors are Nina, Bernd, Patrice, and Inna Dubchak (LBL))
- Viet Tung Hoang (PhD 2013, Phil) (University of Florida)
- Paul Horton (PhD, UC Berkeley, Dan) (CBRC, Tokyo, Japan)
- John Kececioglu (postdoc 92-94, Dan) (University of Arizona)
- Ravi Kolluri (MSc 200?, UT Austin, Nina) (UCB grad student)
- Jim Knight (postdoc, Dan) (CuraGen Corp)
- Jin Hwan Ko (postdoc 05-07, Bai) (Konkuk University, Korea)
- Ted Krovetz (PhD 2000, Phil) (Sacramento State, USA)
- Roger Lee (postdoc 07-08, Bai) (National Tsinghua University, Taiwan)
- Yung-Ta Li (PhD 2008, Bai) (National TsingHua University, Taiwan)
- Ben-Shan Liao (PhD 2007, Bai) (Siemens, Los Angeles, California)
- Susan Margulies (PhD 2008, Chip, Jesus De Loera)
- Atsuko Miyaji (visitor 01-02, Matt/Phil) (JAIST, Japan)
- Payman Mohassel (PhD 2009, Matt) (University of Calgary)
- Dalit Naor (PhD 1991, Dan) (IBM Haifa)
- Van Nguyen (PhD 2006, Chip)
- Samir Pandurangi (MSc 2004, Vladimir) (LLNL)
- Christian Pedersen (visitor, 1998, Dan) (University of Aarhus, Denmark)
- Antonio Piccolboni (Postdoc 1998-99, Dan) (Affymetrix)
- R. Ravi (Postdoc ??-??, Dan) (Carnegie Mellon University)
- Tom Ristenpart (MSc 2005, Phil) (PhD 2010, Mihir Bellare) (University of Wisconsin, Madison)
- Zachary Saul (PhD 2008, Vladimir) (Retronyms)
- Nameeta Shah (PhD 2006, Vladimir and B. Hamann) (Swedish Neuroscience Institute)
- Tom Shrimpton (PhD 2004, Phil) (Portland State and University of Lugano)
- Yun Song (Postdoc, 2006-07, Dan) (UC Berkeley)
- Till Stegers (PhD 2010, Phil) (Google)
- John Steinberger (PhD 2008, Phil) (Tsinghua University)
- Paul Stelling (PhD 2005, Chip; postdoc ??-??, Dan) (?)
- Jens Stoye (postdoc 97-98, Dan) (Bielefeld University, Germany)
- Julie Thompson (CNRS, Strasbourg, France) (advisor is Patrice)
- Jenny Wang (MSc 2005, Bai)
- Lusheng Wang (postdoc ??-??, Dan) (City University of Hong Kong, China)
- Yu Wang (MS 2005, Vladimir and P. Devanbu)
- Yufeng Wu (PhD 2007, Dan) (U of Connecticut)
- Ichitaro Yamazaki (PhD 2008, Bai) (Lawrence Berkeley Laboratory)
- Nikolai Zarkevic (ost-doc 07-08, Bai) (Robert Bosch Research Center, Cambridge, MA)

Comments or updates for this
page should be directed to

rogaway@cs.ucdavis.edu