Skip to main content

Anna Gal


Anna Gal is a Professor of Computer Science at the University of Texas at Austin. She received her PhD in Computer Science at the University of Chicago. She was a postdoctoral fellow at the Institute for Advanced Study in Princeton, and at Princeton University. Her main research area is computational complexity theory. Her research interests include circuit complexity, communication complexity, fault tolerant computation and combinatorics. She is a recipient of an NSF CAREER Award and an Alfred P. Sloan Research Fellowship. She received the Machtey Award for Best Student Paper at the 1991 IEEE FOCS conference, and the EATCS Best Paper Award at Track A of ICALP 2003.


Research Areas:
Research Interests:
  • Computational complexity
  • Communication complexity
  • Coding theory
  • Algorithms
  • Combinatorics

Select Publications

A. Gal, K. A. Hansen, M. Koucky, P. Pudlak and E. Viola. 2013. “Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates”.

A. Gal and J. Ford. 2013. “Hadamard tensors and lower bounds on multiparty communication complexity”.

A. Gal and A. Mills. 2012. “Three query locally decodable codes with higher correctness require exponential length”.

A. Gal and P. Gopalan. 2010. “Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence”.

A. Gal and P.B. Miltersen. 2007. “The cell probe complexity of succinct data structures”.

Awards & Honors

  • 2001 - Alfred P. Sloan Research Fellowship
  • 1999 - NSF CAREER Award
  • 2003 - EATCS Best Paper Award, ICALP
  • 1991 - Machtey Award for Best Student Paper, IEEE FOCS

Contact Info

Anna Gal
(512) 471-9539
GDC 4.420