Lisa Hellerstein

Professor, Department of Computer Science and Engineering, Polytechnic Institute of NYU
A.B. Harvard University, 1984
Ph.D. University of California at Berkeley, 1989

Research Areas

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).
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 complete list, with links: See journal papers and book articles and conference papers.

"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


Dept. of Computer and Information Science Polytechnic University Six MetroTech Center Brooklyn, NY 11201-3840		Phone: (718)260-3689 Fax: (718) 260-3609 Email address: hstein At duke.poly.edu