Button to scroll to the top of the page.

Anna Gal

Department of Computer Science

Theoretical Computer Science


Phone: 512-471-9539

Office Location
GDC 4.420

Postal Address
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