Lisa Hellerstein

  • Professor & Interim Chair for the Department of CSE



Research Interests: Computational learning theory, Machine learning, Algorithms, Complexity theory, Discrete mathematics

  • A.B. Harvard University, 1984
  • Ph.D. University of California at Berkeley, 1989

  • The Stochastic Score Classification Problem.
    Proceedings of the 26th Annual European Symposium on Algorithms (ESA), 2018 (with D. Gkenosis, N. Grammel, and D. Kletenik)
  • Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.
    Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014 (with A. Deshpande and D. Kletenik).
  • Tight bounds on proper equivalence query learning of DNF.
    Proceedings of the 25th Conference on Learning Theory (COLT), 2012 (with D. Kletenik, L. Sellie and R.A. Servedio).
  • Algorithms for distributional and adversarial pipelined filter ordering problems.
    ACM Transactions on Algorithms, 5(2):1--34, 2009 (with A. Condon, A. Deshpande, and N. Wu).
  • Minimizing disjunctive normal form formulas and AC0 circuits given a truth table. SIAM Journal on Computing, 38(1):63--84, 2008 (with E. Allender, P. McCabe, T. Pitassi, M. E. Saks).
  • On the power of finite automata with both nondeterministic and probabilistic states.
    SIAM Journal on Computing 27(3): 739-762, 1998. (with A. Condon, S. Pottle, and A. Wigderson).
  • How many queries are needed to learn. JACM 43(5):840-862, 1996 (with K. Pillaipakkamnatt, D.Wilkins, and V. Raghavan).
  • Coding techniques for handling failures in large disk arrays.
    Algorithmica, 12:182-208, 1994 (with G. Gibson, R.M. Karp, R.H. Katz, and D.A. Patterson).
  • More complete list, with links: See journal papers and book articles and conference papers.

Current Projects, Research Labs, and Groups