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
  • Computing on the Dark Side; Celebrating the work of Leonid Levin (Presentation available on-line.)
  • 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
    • 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) .
    • 53rd ACM Symposium on Theory of Computing (STOC 2021).
    • 15th Annual International Computer Science Symposium in Russia (CSR 2020).
    • 50th ACM Symposium on Theory of Computing (STOC 2018).
    • 33rd Computational Complexity Conference (CCC 2018).
    • 13th Latin American Theoretical Informatics Symposium (LATIN 2018).
    • Computability in Europe (CiE 2018).
    • 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018).
    • 11th International Conference on Language and Automata Theory and Applications (LATA 2017)
    • 11th Annual International Computer Science Symposium in Russia (CSR 2016).
    • 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016).
    • 22nd Annual International Computing and Combinatorics Conference (COCOON 2016).
    • 10th Annual International Computer Science Symposium in Russia (CSR2015).
    • 21st Workshop on Logic, Language, Information and Computation (WoLLIC 2014).
    • 9th Annual International Computer Science Symposium in Russia (CSR2014).
    • 8th Conference on Computability, Complexity, and Randomness (CCR 2013).
    • 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2013).
    • 18th Annual International Computing and Combinatorics Conference (COCOON 2012).
    • 27th Annual IEEE Conference on Computational Complexity (CCC 2012).
    • 6th International Conference on Language and Automata Theory and Applications (LATA 2012)
    • 17th Annual International Computing and Combinatorics Conference (COCOON 2011).
    • 6th Conference on Computability, Complexity, and Randomness (CCR 2011).
    • 5th Conference on Computability, Complexity, and Randomness (CCR 2010).
    • Computing: The Australasian Theory Symposium (CATS 2009), one of the conferences that constitute Australasian Computer Science Week 2009, Wellington, New Zealand.
    • 14h Annual International Computing and Combinatorics Conference (COCOON 2008).
    • 39th ACM Symposium on Theory of Computing (STOC 2007).
    • 2nd Annual International Computer Science Symposium in Russia (CSR2007).
    • 12th Workshop on Logic, Language, Information and Computation (WoLLIC 2005).
    • 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2005).
    • 19th Annual IEEE Conference on Computational Complexity (CCC 2004).
    • 2nd Annual IFIP Conference on Theoretical Computer Science (TCS 2002).
    • 7th Annual International Computing and Combinatorics Conference (COCOON 2001).
    • 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1999).
    • XVII International Conference of the Chilean Computer Science Society (SCCC) (1997).
    • 15th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1995).
    • Annual IEEE Structure in Complexity Theory Conference (1989, 1993, 1995)
  • 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:
    • Researchers Identify Master Problem Underlying All Cryptography
    • Which Computational Universe Do We Live In?
    • Complexity Theory's 50-Year Journey to the Limits of Knowledge
    • Cryptography Tricks Make a Hard Problem a Little Easier