Anna Gál

Professor
Office: 
GDC 4.420
Phone: 
(512) 471-9539
Email: 
panni [at] cs [dot] utexas [dot] edu
Research: 

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.

UTCS Research Areas: 
Selected Awards & Honors: 
  • 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
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.
Professional Activities: 
  • Associate Editor, ACM Transactions on Computation Theory.
  • Member of the Scientific Board of the Electronic Colloquium on Computational Complexity (ECCC).
  • Member of the Conference Steering Committee for the IEEE Conference on Computational Complexity (3-year elected term: 2004-2007).
  • Guest Editor of the Journal Theoretical Computer Science for the Special Issue of ICALP 2006. 
  • Guest Editor of the Journal Computational Complexity for the Special Issue of the 2005 IEEE Conference on Computational Complexity. 
  • Program committee member of the following conferences:
  • IEEE Conference on Computational Complexity (CCC 2009, 2005, 2001) 
  • International Colloquium on Automata, Languages and Programming (ICALP 2009, 2006) 
  • Randomization and Computation (RANDOM  2010, 2008) 
  • International Symposium on Theoretical Aspects of Computer Science (STACS 2008) 
  • Frontiers of Algorithms Workshop (FAW 2007) 
  • International Computing and Combinatorics Conference (COCOON 2003) 
  • IEEE Symposium on Foundations of Computer Sciences (FOCS 2002)