Lisa Hellerstein

  • Professor & Interim Chair for the Department of Computer Science and Engineering

Computer Science and Engineering

Connect

Lisa Hellerstein headshot

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

Research Centers, Labs, and Groups