-
-
panni@cs.utexas.edu
Phone: 512-471-9539
Office Location
GDC 4.420
Postal Address
2317 SPEEDWAY
AUSTIN, TX 78712-
Ph.D., University of Chicago (1995)
Research Interests
Dr. Gal's research interests are in computational complexity, lower bounds for complexity of Boolean functions, communication complexity, fault tolerance, randomness and computation, algorithms and combinatorics.
-
Selected Publications:
Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence, with P. Gopalan, SIAM Journal on Computing Vol. 39, No. 8, pp. 3463-3479, 2010.
The cell probe complexity of succinct data structures, with P.B. Miltersen, Special Issue of selected papers from ICALP 2003, (received EATCS Best Paper Award) Theoretical Computer Science, vol. 379, 2007, pp. 405 - 417.
Hadamard tensors and lower bounds on multiparty communication complexity, with Jeff Ford, Proceedings of ICALP 2005, pp. 1163 - 1175.
Omega(log N) lower bounds on the amount of randomness in 2-private computation, with Adi Rosen, SIAM Journal on Computing , Vol. 34, No. 4, 2005, pp. 946-959.
A characterization of span program size and improved lower bounds for monotone span programs, Computational Complexity, Vol. 10, No. 4, 2001, pp. 277-296.
-
- Alfred P. Sloan Research Fellowship, 2001
- NSF CAREER Award,1999
- EATCS Best Paper Award at Track A of ICALP, 2003
- Machtey Award (Best Student Paper) at the 32nd IEEE
- Symposium on Foundations of Computer Science (FOCS), 1991
-
