Curriculum Vitae Info

Academic History

Education:
- BA, 1979, Theatre, Computer Science (double major), University of Iowa
- Ph.D., 1985, Information and Computer Science, Georgia Institute of Technology (Advisor: Kim N. King)
Students
- Harsha Tirumala
  - Thesis: Meta Complexity: Connections to One-Way Functions and Zero Knowledge Protocols , 2023.
- Erick Chastain
  - Thesis: The Multiplicative Weights Update Method for Evolutionary Biology , 2017.
- Luke Friedman
  - Thesis: Some Applications of Randomness in Computational Complexity , 2013.
- Fengming Wang
  - Thesis: On Circuit Complexity Classes and Iterated Matrix Multiplication, 2011.
- Sambuddha Roy
  - Thesis: Complexity Theoretic Aspects of Planar Restrictions and Obliviousness, 2006.
- Detlef Ronneburger
  - Thesis: Kolmogorov Complexity and Derandomization, 2004.
- Samir Datta
  - Thesis: Bounded Depth Arithmetic Circuits, 2004.
- Michal Koucký
  - Thesis: On Traversal Sequences, Exploration Sequences, and Completeness of Kolmogorov Random Strings , 2003.
- Martin Strauss
  - Thesis: Measure in Feasible Complexity Classes, 1995.
- Vivek Gore
  - Thesis: Lower Bounds for Uniform Constant Depth Circuits, 1993.
Employment
- Distinguished Professor Emeritus, Dept. of Computer Science, Rutgers University (2023-present)
- Distinguished Professor, Dept. of Computer Science, Rutgers University (2008-2023)
  - Department Chair (2006-2009)
  - Director, Graduate Program in Computer Science (2006, and 1999-2003).
  - Member of DIMACS (1989-2023)
  - Member of Graduate Faculty of Rutgers Mathematics Department (1993-2023)
- Professor, Dept. of Computer Science, Rutgers University (1997-2008)
- Associate Professor, Dept. of Computer Science, Rutgers University (1991-1997)
- Assistant Professor, Dept. of Computer Science, Rutgers University (1985-1991)
Visiting Positions
- 2023: Simons Institute Program on Meta-complexity
- 2018: Simons Institute Program on Lower Bounds in Computational Complexity
- 2015: Santa Fe Institute
- 2015: University of California, San Diego
- 2011: Tsinghua University Beijing, China
- 2010: University of South Africa, Pretoria (Fulbright Fellowship)
- 2009: University of Cape Town, South Africa (Fulbright Fellowship)
- 2004: Macquarie University, Sydney, Australia
- 2004: Victoria University, Wellington, New Zealand
- 2003: Tokyo Institute of Technology, Japan
- 1997: Universität Tübingen
- 1997: The Institute of Mathematical Sciences, Chennai, India
- 1992-3: Princeton University
- 1989: Universität Würzburg
Honors
- Eric Allender Day at the Simons Institute, February 13, 2023. (See the photo.)
- DIMACS Workshop on E+M=C^2 (Eric Allender and Mike Saks are 60), January 26-27, 2017.
- Best paper award, 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)
- Fulbright Research Fellowship, 2009-2010
- Fellow of the ACM
- ACM Distinguished Scientist
Selected Invited Lectures
- 16th International Conference on Computability, Complexity and Randomness (CCR 2023) (Presentation available on-line.)
- Richard M. Karp Distinguished Lecture Series, Simons Institute for the Theory of Computing, Berkeley, 2023. (Presentation available on-line.)
- International Conference on Language and Automata Theory and Applications (LATA 2020/2021), (Presentation available on-line.)
- Computational Complexity Conference (CCC 2021), (Presentation available on-line.)
- Aspects of Computation, Institute for Mathematical Sciences, National University of Singapore, 2017. (Mini-course available on-line.)
- ImmermanFest, 2014, Vienna, Austria. (Presentation available on-line.)
- China Theory Week 2012, August 13-17, 2012, Aarhus, Denmark. (Presentation available on-line.)
- Computability in Europe (CiE 2012), June 18-23, 2012, Cambridge, England. (Presentation available on-line.)
- Distinguished Lecture, University at Buffalo, November 11, 2010. (Presentation available on-line.)
- Computability in Europe (CiE 2010), June 30-July 5, 2010, Ponta Delgada, Azores, Portugal. (Presentation available on-line.)
- New Zealand Mathematics Research Institute Summer Workshop (NZMRI 2009), January 4-9, Napier, New Zealand.
- 10th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2008), July 16-18, 2008, Charlottetown, Prince Edward Island. (Presentation available on-line.)
- 3rd International Computer Science Symposium in Russia (CSR 2008) June 7-12, 2008, Moscow, Russia. (Presentation available on-line.)
- Computing: The Australasian Theory Symposium (CATS 2008), January 22-25, 2008, Wollongong, Australia. (Presentation available on-line.)
- Computability in Europe (CiE 2007), Special session on Complexity of Algorithms and Proofs June 18-23, 2007, Siena.
- Conference on Computability, Complexity, and Randomness, January 10-13, 2007, Buenos Aires.
- Symposium on Computational Complexity, Honoring Dr. Richard M. Karp, April 28, 2004, Philadelphia. (Presentation available on-line.)
- 10th Workshop on Logic, Language, Information and Computation (WoLLIC'2003), Ouro Preto, Brazil, July 27-August 1, 2003.
- Foundations of Computational Mathematics (FoCM 2002), semi-plenary speaker, Workshop on Complexity, Minneapolis, August 5-14, 2002.
- 21st annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'01), Bangalore, India, December 13, 2001.
- Summer Workshop on Computability, Complexity, and Computational Algebra, organized by the New Zealand Mathematical Research Institute, Kaikoura, New Zealand, January 7-14, 2000.
- 17th International Conference of the Chilean Computer Science Society (SCCC '97), Viña del Mar, Chile, November 11, 1997.
- 16th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'96), Hyderabad, India, December 18, 1996. (Presentation available on-line.)
- 8th International Conference on Fundamentals of Computation Theory (FCT'90), Gosen, Germany, September 11, 1990.
- SIGAL International Symposium on Algorithms, Tokyo, Japan, August 16, 1990.
Professional Activities
- Treasurer, SIGACT Executive Committee, 2018-2021.
- Member of the Editorial Board: ACM Transactions on Computation Theory (ToCT) (2007-2021) [Editor-in-Chief (2010-2017)]
- Member of the Editorial Board: Computability (The Journal of the Association Computability in Europe) (2011-2023)
- Associate Editor-in-Chief: Chicago Journal of Theoretical Computer Science (2010-2023) [Editor since 1994; Consulting Editor 1998-2010]
- Member, Advisory Panel, Springer/CiE book series ``Theory and Applications of Computability'' (2009-2017).
- Member, Advisory Board, Birkhäuser book series ``Progress in Computer Science and Applied Logic'' (2013-2017).
- Member of the Editorial Board: Computational Complexity (2006-2016)
- Member, Panel of Judges, Turing Centenary Research Fellowships and Scholarships, 2012.
- Member of Steering Committee, IEEE Structure in Complexity Theory Conference / IEEE Conference on Computational Complexity (2013-2016, 2006-2009 and 1994-2001); Chair 1997-2000.
- Scientific Board: Electronic Colloquium on Computational Complexity (1995-2021).
- Member, Chief Editorial Committee, DIMACS/AMS Book Series (2004-2023).
- NSERC Computer Science Evaluation Group (2012-2015).
- Guest Editor, Special Issue of Computational Complexity on the 2004 IEEE Conference on Computational Complexity.
- Editor, Computational Complexity Column, Bulletin of the European Association for Theoretical Computer Science (1997-2000).
- Co-organizer, DIMACS Special Year on Logic and Algorithms (1995-1996).
- Chair, program committee, 10th annual IEEE Structure in Complexity Theory Conference (1995).
- Program Committee Membership
- Workshop Co-organizer:
  - DIMACS Workshop on Meta-Complexity, Barriers, and Derandomization (2022).
  - Clay Mathematics Institute Complexity Theory Workshop, Oxford University (2018).
  - Clay Mathematics Institute workshop on New Insights into Computational Intractability, Oxford University (2013).
  - DIMACS-DIMATIA workshop: Algebraic Methods and Arithmetic Circuits (1999).
  - DIMACS workshop: Special Year on Logic and Algorithms -- One Year Later (1997).
  - Workshop on Structure and Complexity Theory, Schloss Dagstuhl, Germany (1996).
  - DIMACS Workshop on Structural Complexity and Cryptography (1990).
Research Support
- NSF Grant, 2019--2023.
- NSF Grant, 2019--2022.
- NSF Grant, 2015--2020.
- NSF Grant, 2015--2017.
- NSF Grant, 2011--2015.
- NSF Expeditions Grant, 2008--2014. This grant supported the Center on Computational Intractability.
- NSF Grant, 2008--2011.
- NSF Collaborative Research Grant, 2007--2010. See also the partner awards at Berkeley, Chicago, Connecticut, Dartmouth, Florida, Iowa State, Notre Dame, North Texas, Penn State, and Wyoming. The total award is $559,094. A web site describing the project can be found here.
- NSF Grant, 2005--2008.
- NSF Grant, 2001--2004.
- NSF Grant, 1998--2001.
- Deutsche Forschungsgemeinschaft Grant TU 7/117-1, 1997.
- NSF Grant, 1995--1998.
- NSF Grant, 1992--1995.
- NSF Grant, 1990--1992.
- NSF Research Initiation Grant, 1988--1990.
Other NSF Support
- DIMACS/Simons Collaboration on Lower Bounds in Complexity Theory. 2018--2022. (Co-PI)
- DIMACS REU in Algorithms from Foundations to Applications, 2019--2023. (Co-PI)
- NSF Grant to support student participation at the Clay Mathematics Institute Complexity Theory Workshop, Oxford University (2018).
Publications
Miscellaneous
- A nice comment from a former undergraduate. (See page 6.)
- And another.
- Mentions in Quanta Magazine: