Lisa Hellerstein

Research Areas

• Computational Learning Theory
• Machine Learning
• Algorithms
• Complexity Theory
• Discrete Mathematics

Selected Papers

• 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).

• 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).
  icml05.ps

• On compression-based text classification.
  Proceedings of the 27th European Conference on Information Retrieval (ECIR), 2005 (with Y. Marton and N. Wu). (pdf file) (Errata)

• 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).
  npfa.ps

• How many queries are needed to learn. JACM 43(5):840-862, 1996 (with K. Pillaipakkamnatt, D.Wilkins, and V. Raghavan).
  queries.ps

• 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 --- Complete listing of journal papers and book articles and complete listing of conference papers.

Courses Taught

• CS2134 (Data Structures and Algorithms)
• CS6923 (Machine Learning)
• CS6753 (Theory of Computation)
• CS3414 (Design and Analysis of Algorithms)
• CS604 (Design and Analysis of Algorithms II)
• CS200 (Programming and Problem Solving (in C++))

Survey Talks

• "Learning Boolean Formulas with Queries," presented at the AMS Short Course on Statistical Learning Theory, Joint Mathematics Meetings (2007).
  AMSTalk.ppt
  
• "Learning DNF Formulas: A Selected Survey," presented at the Workshop on Logic and Learning, affiliated with the IEEE Symposium on Logic in Computer Science (LICS), 2001.
  lics.ps