Lisa Hellerstein

Research Interests: Computational learning theory Machine learning Algorithms Complexity theory Discrete mathematics

Harvard University 1984
Bachelor of Arts, Applied Mathematics/Computer Science

University of California at Berkeley 1989
Doctor of Philosophy, Computer Science

CONFERENCE PAPERS AND JOURNAL ARTICLES

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

Current Projects, Research Labs, and Groups