Andris AMBAINIS

Andris AMBAINIS
Professor
Faculty of Physics and Mathematics
University of Latvia
Raina bulv. 19, Riga, LV 1586
Latvia

Phone:+371 67034517
Fax: +371 67820153
E-mail: ambainis@lanet.lv, andris.ambainis@lu.lv

Born: January 18, 1975, Daugavpils, Latvia

Research Interests

Quantum computing, quantum communication, quantum cryptography, foundations of quantum mechanics (quantum nonlocality), theoretical computer science (algorithms and complexity).

Education

Ph.D. , University of California, Berkeley, 2001
Dr.Sc.Comp., University of Latvia, 1997
Master in Computer Science, University of Latvia, 1997
Bachelor in Computer Science (with distinction), University of Latvia, 1996

Experience

Professor, University of Latvia, 2009-
Assistant Professor, Department of Combinatorics and Optimization, University of Waterloo, 2004 - 2007
Researcher, University of California, Berkeley, 2003-2004
Associate Professor, University of Latvia, 2003-2009
Assistant Professsor, University of Latvia, 2002-2003
Researcher, Institute for Advanced Study, Princeton, 2001-2002
Researcher-Intern at IBM Research, Summer 2000.
Researcher-Intern at Microsoft Research, Summer 1999.
Research Assistant at Laboratory of Artificial Intelligence, Institute of Mathematics and Computer Science, University of Latvia, 1992-1997.
Programmer, "SWH Informativas Sistemas", Riga, Latvia, 1994-1996.

Awards and Scholarships

Full Member, Latvian Academy of Sciences, 2007
Sloan Fellowship, 2007.
Corresponding Member, Latvian Academy of Sciences, 2003
Neyman Dissertation Prize, Mathematics Department, UC Berkeley, 2002.
Microsoft Graduate Fellowship, 2000-2002 .
Ramamurthy Award, EECS Department, UC Berkeley, 2000, 2001
Best student paper award at STOC'2000
Berkeley Fellowship for Graduate Studies (fellowship to the best entering graduate student in department), 1997-2000
Awards for best Master's thesis from "SWH Izglitibai, Zinatnei un Kulturai" and University of Latvia, 1997
Charles Babbage Award (Award to the best computer science student of University of Latvia), 1996
An award for best Bachelor's thesis from "SWH Izglitibai, Zinatnei un Kulturai" program of Latvia Education Foundation, 1996
Young Scientist Award from Academia Europeana, 1996
CRA (Computing Research Association) special recognition in CRA Undergraduate Student Award competition, 1995
Fellowship "SWH Izglitibai, Zinatnei un Kulturai" from Latvia Education Foundation, 1994-1996
Charles Babbage Award (Award to the best computer science student of University of Latvia), 1994
1st prize in International Mathematical Olympiad in 1991 (Sigtuna, Sweden) and 2nd prize in 1992 (Moscow, Russia) .

Service

Program Committee Member:

13th Conference on Fundamentals of Computation Theory (FCT), Riga, August 2001
36th ACM Symposium on Theory of Computation (STOC), Chicago, June 2004
4th ERATO Conference on Quantum Information Science (EQIS), Tokyo, September 2004
20th IEEE Conference on Computational Complexity, Prague, July 2006
International Workshop on Randomization and Computation (RANDOM), Barcelona, Spain, August 2006.
ACM Symposium on Theory of Computation(STOC), San Diego, CA, USA, June 2007.
3rd Symposium on Stochastic Algorithms, Foundations and Applications (SAGA), Switzerland, September 2007
11th Workshop on Quantum Information Processing (QIP), Deli, India, December 2007.
26^th International Symposium on Theoretical Aspects of Computer Science, Freiburg, Germany, February 2009.
41^st ACM Symposium on Theory of Computation (STOC), Beteshda, USA, May 2009.
6^th Central European Quantum Information Processing Workshop, Czech Republic, June2009.
Asia Conference on Quantum Information Science (AQIS), Nanjing, China, August 2009.

Proposal evaluator for:

National Science Foundation (USA), 2003, 2009,
US-Israel Binational Science Foundation, 2004.
Israel Science Foundation, 2005.
NWO(Netherlands Organisation for Scientific Research), 2005.
Czech Science Foundation, 2006.
NSERC (Natural Sciences and Engineering Research Council of Canada), 2008.

Editor for scientific journals:

Theory of Computing, 2004-

Algorithmica, 2005-

Reviewer:

Computer Science Journals: Journal of ACM, SIAM Journal on Computing, Journal of Computer and Systems Sciences, Algorithmica, Theoretical Computer Science, Information and Computation, Information Processing Letters, Computational Complexity, International Journal on Foundations of Computer Science, Random Structures and Algorithms.
Physics Journals: Physical Review Letters, Physical Review A, Journal of Statistical Physics, Journal of Quantum Information Processing.
Conferences: ACM Symposium on Theory of Computing (STOC), IEEE Conference on Foundations of Computer Science (FOCS), IEEE Conference on Computational Complexity (CCC), SIAM Conference on Discrete Algorithms (SODA), Symposium on Theoretical Aspects of Computer Science (STACS), International Colloquium on Automata, Languages and Programming (ICALP), Workshop on Mathematical Foundations of Computer Science (MFCS), International Workshop on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), International Symposium on Algorithms and Computation (ISAAC), International Workshop on Randomisation and Approximation Techniques in Computer Science (RANDOM), ERATO Conference on Quantum Information Science (EQIS), International Workshop on Algorithmic Learning Theory (ALT), Latin American Theoretical Informatics Workshop (LATIN).

Publications

A total of 100 publications (35 journal papers, 59 papers in refereed conference proceedings, 2 encyclopedia articles, 4 teaching materials). The most important publications are listed below:

A. Ambainis, A. Childs, B. Reichardt, R. Spalek, S. Zhang, Any AND-OR formula of size N can be evaluated in time O(N^{1/2+epsilon}) on a quantum computer. SIAM Journal on Computing, accepted for publication.
A.Ambainis, R.Spalek, R. de Wolf. A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs. Algorithmica, 55:422-461, 2009.
A. Ambainis. Probabilistic PFIN-type learning: general properties. Journal of Computer and System Sciences (special issue in memory of Carl H. Smith), 74:457-489, 2008.
A.Ambainis. Quantum walk algorithm for element distinctness. - SIAM Journal on Computing, 2007, vol. 37, pp. 210-239.
A.Ambainis.Polynominal degree vs. quantum query complexity. – Journal of Computer & System Sciences, 2006, vol. 72, pp. 220-238.
A.Ambainis, L.Schulman, U.Vazirani. Quantum computing with highly mixed states. – Journal of the ACM, 2006, vol. 53, pp. 507-531.
A. Ambainis. A new protocol and lower bounds for quantum coin flipping . - Journal of Computer and System Sciences, 2004, vol.68, pp.398-416.
A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, A. Wigderson. Quantum communication complexity of sampling. - SIAM Journal on Computing, 2003, vol.32(6), pp.1570-1585.
T. Brun, H. Carteret, A. Ambainis. Classical to quantum transition for random walks. - Physical Review Letters, 91:130602 (4 pp.), September 2003.
A. Ambainis. Dense quantum coding and quantum finite automata. - Journal of the ACM, 49(4):496-511, July 2002.
A. Ambainis, J. Watrous. Two-way finite automata with quantum and classical states. - Theoretical Computer Science, 287(2):299-311, July 2002.
A. Ambainis. "Quantum lower bounds by quantum arguments". - Journal of Computer and System Sciences, 64(4):750-767, June 2002.
A. Ambainis, S. Bloch, D. Schweizer. Delayed binary search, or playing twenty questions with a procrastinator. - Algorithmica, 32(4):641-650, April 2002.
A. Ambainis, K. Apsitis, R. Freivalds, W. Gasarch, C.H. Smith. Hierarchies of probabilistic and team FIN-learning. - Theoretical Computer Science, 261(1): 91-117, June 2001.
A. Ambainis. Communication complexity in 3-computer model. - Algorithmica, 16:298-301, 1996.
A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, J. Watrous. One dimensional quantum walks.- Proceedings of ACM Symposium on Theory of Computation (STOC), pp. 37-49, Heraklion, Greece, July 2001.
D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani. Quantum walks on graphs.- Proceedings of ACM Symposium on Theory of Computation (STOC), pp. 50-59, Heraklion, Greece, July 2001.
A. Ambainis, M. Mosca, A. Tapp, R. de Wolf. Private quantum channels. - Proceedings of IEEE Conference on Foundations of Computer Science(FOCS), November 2000.
A. Ambainis, R. Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalisations.- Proceedings of IEEE Conference on Foundations of Computer Science(FOCS), pp. 332-341, Palo Alto, CA, October 1998.
A. Ambainis, R. Desper, M. Farach, S. Kannan. Nearly tight bounds on the learnability of evolution. - Proceedings of IEEE Conference on Foundations of Computer Science(FOCS), pp. 524-533, Miami, FL, October 1997.
A. Ambainis. Upper bound on the communication complexity of private information retrieval. - Proceedings of International Conference on Automata, Languages and Programming (ICALP), pp. 233-237, Bologna, Italy, July 1997.

Research Projects

Marie Curie International Reintegration Grant, EU 7^th framework program, 2008-now.
Creating a new research group in quantum computing and theory of computing, University of Latvia research grant, 2007-now.
Research in quantum algorithms, quantum complexity theory and quantum cryptography, Discovery Grant, Natural Sciences and Engineering Research Council of Canada (NSERC), 2005 – 2007.
Quantum Information Processing, Canadian Institute for Advanced Research (CIAR) 2004 - 2007.
IQC University Professorship, University of Waterloo, 2004 – 2007.

Last update 8.10.2009