Department of Computer Science and Engineering
Polytechnic Institute of NYU
A.B. Harvard University, 1984
Ph.D. University of California at Berkeley, 1989
Computational Learning Theory
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).
More complete list, with links: See
journal papers and book articles
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++))