

Umesh Vazirani
Professor
Research Areas
Research Centers
Teaching Schedule
(Spring 2015)
Selected Publications
 R. Khandekar, S. Rao, and U. Vazirani, "Graph partitioning using single commodity flows," in Proc. 38th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 2006, pp. 385390.
 A. Mehta, A. Saberin, U. Vazirani, and V. Vazirani, "AdWords and generalized online matching," in Proc. 46th Annual IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2005, pp. 264273.
 J. Vala, A. V. Thapliyal, S. Myrgren, U. Vazirani, D. S. Weiss, and K. B. Whaley, "Perfect pattern formation of neutral atoms in an addressable optical lattice," Physical Review A (Atomic, Molecular, and Optical Physics), vol. 71, no. 3, pp. 32324113, March 2005.
 S. Arora, S. Rao, and U. Vazirani, "Expander flows, geometric embeddings and graph partitioning," in Proc. 36th Annual ACM Symp. on Theory of Computing, New York, NY: ACM Press, 2004, pp. 222231.
 M. Grigni, L. J. Schulman, M. Vazirani, and U. Vazirani, "Quantum mechanical algorithms for the nonabelian hidden subgroup problem," Combinatorica, vol. 24, no. 1, pp. 137154, Jan. 2004.
 W. van Dam, M. Mosca, and U. Vazirani, "How powerful is adiabatic quantum computation?," in Proc. 42nd IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society Press, 2001, pp. 279287.
 U. Vazirani, "On the power of quantum computation," Physical Transactionsof the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 356, no. 1743, pp. 17591768, Aug. 1998.
 S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, "On syntactic versus computational views of approximability," SIAM J. on Computing, vol. 28, no. 1, pp. 164191, Feb. 1998.
 E. Bernstein and U. Vazirani, "Quantum complexity theory," SIAM J. on Computing, vol. 26, no. 5, pp. 14111473, Oct. 1997.
 C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, "Strengths and weaknesses of quantum computing," SIAM J. on Computing, vol. 26, no. 5, pp. 15101523, Oct. 1997.
 R. M. Karp, U. Vazirani, and V. V. Vazirani, "An optimal algorithm for online bipartite matching," in Proc. 22nd Annual ACM Symp. on Theory of Computing, H. Ortiz, Ed., New York, NY: ACM Press, 1990, pp. 352358.
 K. Mulmuley, U. Vazirani, and V. V. Vazirani, "Matching is as easy as matrix inversion," in Proc. 19th Annual ACM Conf. on Theory of Computing, A. V. Aho, Ed., New York, NY: ACM Press, 1987, pp. 345354.
 M. Santha and U. Vazirani, "Generating quasirandom sequences from semirandom sources," J. Computer and System Sciences, vol. 33, no. 1, pp. 7587, Aug. 1986.
 U. Vazirani and V. V. Vazirani, "Random polynomial time is equal to slightlyrandom polynomial time," in Proc. 26th Annual IEEE Symp. on Foundations of Computer Science, Washington, DC: IEEE Computer Society Press, 1985, pp. 417428.



