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