Lisa Hellerstein

Research Areas

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

Selected Papers

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

• 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 Bernard Rosell, Soumya Ray, and David Page).
  icml05.ps

• On Compression-Based Text Classification.
  Proceedings of the 27th European Conference on Information Retrieval (ECIR), 2005 (with Yuval Marton and Ning Wu). (Abstract) (Full Paper at SpringerLink) (Errata)

• On the power of finite automata with both nondeterministic and probabilistic states.
  SIAM Journal on Computing 27(3): 739-762, 1998. (with Anne Condon, Samuel Pottle, and Avi 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