Source: https://people.eecs.berkeley.edu/~vazirani/
Timestamp: 2019-04-22 00:05:20+00:00

Document:
The duality gap for two-team zero-sum games with L. Schulman, ITCS 2017.
A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians with Z. Landau, T. Vidick, arXiv:1307.5143 [quant-ph], 2013. ITCS 2014. Nature Physics 11, 566-569 (2015).
Local tests of global entanglement and a counterexample to the generalized area law with D. Aharonov, A. Harrow, Z. Landau, D. Nagaj, M. Szegedy, FOCS 2014.
Algorithms, Games, and Evolution with E. Chastain, A. Livnat, C. Papadimitriou, PNAS vol. 111, no. 29, 10620-10623, 2014.
How ``Quantum" is the D-Wave Machine? with S. Shin, Smith, J. Smolin, arXiv:1401.7087 [quant-ph], 2014.
Fully device independent quantum key distribution with T. Vidick, ITCS 2014. Phys. Rev. Lett. 113, 140501, 2014.
Classical command of quantum systems with B. Reichardt, F. Unger, ITCS 2013. Nature 496, 456 - 460 (25 April 2013).
An area law and sub-exponential algorithm for 1D systems with I. Arad, A. Kitaev, Z. Landau, arXiv:1301.1162 [quant-ph], 2012.
Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics with D. Aharonov, Philosophy of Science anthology "Computability: Godel, Turing, Church, and beyond", Editors: Copeland, Posy, Shagrir, MIT press, 2012.
An improved 1D area law for frustration-free systems. with I.Arad, Z.Landau, Phys. Rev. B 85, 195145 (2012).
Certifiable Quantum Dice: or, true random number generation secure against quantum adversaries. with T. Vidick, Proceedings of the ACM Symposium on the Theory of Computing (2012).
The 1D Area Law and the Complexity of Quantum States: A combinatorial approach. with D.Aharonov, I.Arad, Z.Landau, Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011).
The detectability lemma and its applications to Quantum Hamiltonian complexity. with D.Aharonov, I.Arad, Z.Landau, New J. Phys. 13 (2011).
Certifiable Quantum Dice. with T. Vidick, Philosophical Transactions of the Royal Society, A 2012, 370, 3432-3448.
The detectability lemma and quantum gap amplification. with D.Aharonov, I.Arad, Z.Landau, Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 417-426 (2009).
Expander Flows, Geometric Embeddings and Graph Partitioning. with S. Arora, S. Rao, Journal of ACM, 56(2), 2009.
Geometry, Flows and Graph Partitioning Algorithms. with S. Arora, S. Rao, Commun. ACM, 51(10):96-105, 2008.
Graph partitioning using single commodity flows. with R. Khandekar, S. Rao, Proceedings of Symposium on the Theory of Computing, 2006.
AdWords and the Generalized Bipartite Matching Problem. with A. Mehta, A. Saberi, V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 2005. Journal of ACM, 54(5), 2007.
Expander Flows, Geometric Embeddings and Graph Partitioning. with S. Arora, S. Rao, Proceedings of Symposium on the Theory of Computing, 2004.
Quantum Mechanical Algorithms for the Non-Abelian Hidden Subgroup Problem. with M. Grigni, L. Schulman, M. Vazirani, Proceedings of Symposium on the Theory of Computing, 2001; Combinatorica, Volume 24, Number 1, pp 137-154, January 2004.
Limits on Quantum Adiabatic Optimization. with W. van Dam, manuscript.
Dense Quantum Coding and Quantum Finite Automata. with A. Ambainis, A. Nayak, A. Ta-Shma, Proceedings of Symposium on the Theory of Computing, 1999; Journal of the ACM, Volume 49, Issue 4, 2002.
How Powerful is Adiabatic Quantum Computation. with W. van Dam, M. Mosca, Proceedings of Symposium on the Foundations of Computer Science, 2001.
Quantum Walks on Graphs. with D. Aharonov, A. Ambainis, J. Kempe, Proceedings of Symposium on the Theory of Computing, 1999.
Computing with Highly Mixed States. with A. Ambainis, L. Schulman, Proceedings of Symposium on the Theory of Computing, 2000. Journal of the ACM Volume 53, Issue 3 (May 2006), Pages: 507 - 531.
Quantum Bit Escrow. with D. Aharonov, A. Ta-Shma, A. Yao, Proceedings of Symposium on the Theory of Computing, 2000.
Molecular Scale Heat Engines and Scalable Quantum Computation. with L. Schulman, Proceedings of Symposium on the Theory of Computing, 1999.
The Quantum Communication Complexity of Sampling. with A. Ambainis, L. Schulman, A. Ta-Shma, A. Wigderson, Proceedings of Symposium on the Foundations of Computer Science, 1998. Siam J. Comput., Vol. 32, No. 6, pp. 1570-1585, 2003.
On the Power of Quantum Computation. Philosophical Transactions of the Royal Society London A (1998) 356, 1759-1768.
Go With the Winners Algorithms. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1994.
On syntactic versus computational views of approximability. with S. Khanna, R. Motwani, M. Sudan, Proceedings of Symposium on the Foundations of Computer Science, 1994. SIAM Journal on Computing, 28(1): 164-191, February 1999.
Simple and Efficient Leader Election in the Full Information Model. with R. Ostrowsky, S. Rajagopalan, Proceedings of Symposium on the Theory of Computing, 1994.
Simulating Quadratic Dynamical Systems is PSPACE-hard. with S. Arora, Y. Rabani, Proceedings of Symposium on the Theory of Computing, 1994.
Quantum Complexity Theory. with E. Bernstein, Proceedings of Symposium on the Theory of Computing, 1993. Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.
Strengths and Weaknesses of Quantum Computation. with C. Bennett, E. Bernstein, G. Brassard, Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.
A Mildly Exponential Algorithm for Approximating the Permanent. with M. Jerrum, Proceedings of Symposium on the Foundations of Computer Science, 1992. invited paper, special issue of Algorithmica 16 (1996), 392-401.
Choosing a Reliable Hypothesis. with W. Evans, S. Rajagopalan, Proceedings of the Symposium on Computational Learning Theory}, 1993.
A Markovian Extension of Valiant's Learning Model. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1990. Information and Computation, Vol. 117, No. 2, pp~181-186, 1995.
Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability. with S. Arora, R. Impagliazzo; early draft.
An Optimal Online Bipartite Matching Algorithm. with R. Karp, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1990.
Matching is as Easy as Matrix Inversion. with K. Mulmuley, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1987. Combinatorica, Vol. 7, No. 1, 1987.
Efficiency Considerations in Using Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1987.
Random Polynomial Time is Equal to Semi-Random Polynomial Time. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1985.
Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1985. Combinatorica, Vol. 7, No. 4, 1987.
Generating Quasi-Random Sequences from Semi-Random Sources. with M. Santha, Proceedings of Symposium on the Foundations of Computer Science, 1984, Journal Comput. Sys. Sci., Vol. 33, No. 1, 1986.
Efficient and Secure Pseudo-Random Number Generation. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1984.
Trapdoor Pseudo-Random Number Generators, with Applications to Protocol Design. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1983.
2011 Thomas Vidick (Postdoctoral fellow, MIT).

References: V. 
 V. 
 V. 
 V. 
 V. 
 V.