2001-2002 papers

This page contains links to some papers produced during the academic year of 2001-2002.

Complexity and Algorithms

Quantum Computations

• A. Ambainis, A New Protocol and Lower Bounds for Quantum Coin Flipping, Journal of Computer and System Sciences, 68:398-416, 2004
• A. Ambainis, H. Buhrman, Y. Dodis, H. Roehrig, Multiparty Quantum Coin Flipping, Proceedings of the 19th IEEE Conference on Computational Complexity, 2004
• A. Ambainis, A. Smith, K. Yang, Extracting Quantum Entanglement (general entanglement purification protocols), Proceedings of the 17th IEEE Conference on Computational Complexity, 2002, pages 103-112
• A. Ambainis, Quantum Query Algorithms and Lower Bounds: a Survey, Proceedings of FOTFS III, Trends on Logic, 23: 15-32, 2004
• A. Ambainis, Lower Bound for a Class of Weak Quantum Coin Flipping Protocols
• T. Brun, H. Carteret, A. Ambainis, Quantum Random Walks with Decoherent Coins, Physical Review A, 67, 032304, 2003
• T. Brun, H. Carteret, A. Ambainis, Quantum Walks Driven by Many Coins, Physical Review A, 67, 052317, 2003
• T. Brun, H. Carteret, A. Ambainis, The Quantum to Classical Transition for Random Walks, Physical Review Letters, 51, 130602, 2003
• A. Razborov, Quantum Communication Complexity of Symmetric Predicates, Izvestiya: mathematics, 67(1): 145-159, 2003
• O. Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, 33(3): 738-760, 2004

Explicit Constructions of Expanders

• N. Alon, M. Capalbo, Explicit Unique-Neighbor Expanders, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pages 73-79
• N. Alon, M. Capalbo, Smaller Explicit Superconcentrators, Internet Mathematics, 1:151-163, 2004
• M. Capalbo, Explicit Constant Degree Unique-Neighbor Expanders
• M. Capalbo, O. Reingold, S. Vadhan, A. Wigderson, Randomness Conductors and Constant-Degree Expansion Beyond the Degree/2 Barrier, Proceedings of the 34th Symposium on the Theory of Computing, 2002, pages 659-668
• R. Meshulam, A. Wigderson, Expanders in Group Algebras, Combinatorica, 24(4): 659--680, 2004