Lisa Hellerstein
Professor, Department of Computer Science and Engineering, NYU Tandon School of Engineering
A.B. Harvard University, 1984
Ph.D. University of California at Berkeley, 1989
Research Areas
 Algorithms
 Computational Learning Theory
 Machine Learning
 Complexity Theory
 Discrete Mathematics
Selected Papers

The Stochastic Score Classification Problem.
Proceedings of the 26th Annual European Symposium on Algorithms (ESA), 2018
(with D. Gkenosis, N. Grammel, and D. Kletenik)

Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover.
Proceedings of the 25th ACMSIAM Symposium on Discrete Algorithms (SODA), 2014
(with A. Deshpande and D. Kletenik).

Tight bounds on proper equivalence query learning of DNF.
Proceedings of the 25th Conference on Learning Theory (COLT), 2012 (with D. Kletenik, L. Sellie and R.A. Servedio).

Algorithms for distributional and adversarial pipelined filter ordering problems.
ACM Transactions on Algorithms, 5(2):134, 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):6384, 2008
(with E. Allender, P. McCabe, T. Pitassi, M. E. Saks).
 On the power of finite automata with both
nondeterministic and probabilistic states.
SIAM Journal on Computing 27(3): 739762, 1998.
(with A. Condon, S. Pottle, and A. Wigderson).
 How many queries are needed to learn. JACM 43(5):840862, 1996 (with K. Pillaipakkamnatt, D.Wilkins, and V. Raghavan).
 Coding techniques for handling failures in large disk arrays.
Algorithmica, 12:182208, 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.
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++))
Projects
Address
Dept. of Computer Science and Engineering
NYU Tandon School of Engineering
370 Jay St.
Brooklyn, NY 11201
Email address:
lisa.hellerstein At nyu.edu