Anna Gal
Professor
Research
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