Lisa   Hellerstein

Lisa Hellerstein


Computer Science and Engineering

Journal Articles

  • 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).
  • Flow algorithms for two pipelined filter ordering problems. Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS), 2006 (with Anne Condon, Amol Deshpande, and Ning Wu). Extended version to appear in ACM Transactions on Algorithms.
  • Why skewing works: Learning difficult Boolean functions with greedy tree learners. Proceedings of the 22nd International Conference on Machine Learning (ICML), 2005 (with B. Rosell, S. Ray, and D. Page).
  • On compression-based text classification. Proceedings of the 27th European Conference on Information Retrieval (ECIR), 2005 (with Y. Marton and N. Wu).
  • 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 publications: see my website.


University of California at Berkeley, Class of 1989

Doctor of Philosophy, Computer Science

Harvard University, Class of 1984

Bachelor of Arts, Applied Mathematics/Computer Science

Research Interests

Computational learning theory
Machine learning
Complexity theory
Discrete mathematics