*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 - 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, 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