Professor, Department of Computer Science and Engineering, NYU Tandon School of Engineering
A.B. Harvard University
Ph.D. University of California at Berkeley
Faculty member in the Theoretical Computer Science Group at NYU
Research Areas
- Algorithms
- Computational Learning Theory
- Machine Learning
- Complexity Theory
- Discrete Mathematics
Selected Papers
- Quickly Determining Who Won an Election.
Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS), 2024 (with N. Liu and K. Schewior) - 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 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014 (with A. Deshpande and D. Kletenik). - 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).
- 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, see Google Scholar page or DBLP page
Projects
- Minimum Cost Strategies for Sequential Search and Evaluation
- Towards Robust Uncertain Data Management
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