This page contains links to some papers produced during the academic year of 2001-2002. It is our intention to regularly update this page, so if you know of any new links/references please let us know.

    I have tried to identify below a few topics on which the communication between the program's residents was particularly intense. All other papers are listed alphabetically.

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

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

I. Dinur, V. Guruswami, S. Khot, Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon), Electronic Colloquium on Computational Complexity, Report TR02-027

I. Dinur, O. Regev, C. Smyth, The Hardness of 3-Uniform Hypergraph Coloring, Combinatorica, 25(5): 519-535, 2005

M. Alekhnovich, A. Razborov, Satisfiability, Branch-Width and Tseitin Tautologies, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pages 593-603

N. Alon, R. Beigel, S. Kasif, S. Rudich, B. Sudakov, Learning a Hidden Matching, SIAM Journal on Computing, 33: 487-501, 2004

Z. Bar-Yossef, O. Reingold, R. Shaltiel, L. Trevisan, Streaming Computation of Combinatorial Objects, Proceedings of the 17th IEEE Conference on Computational Complexity, 2002, pages 165-174

R. Beigel, H. Buhrman, P. Fejer, L. Fortnow, P. Grabowski, L. Longpre, , A. Muchnik, F. Stephan, L. Torenvliet, Enumerations of the Kolmogorov function, Journal of Symbolic Logic, 71(2):501-528, 2006

R. Beigel, L. Fortnow, A. Pavan, Membership Comparable and p-Selective Sets, Technical Note 2002-006N, NEC Research Institute, 2002

R. Beigel, L. Fortnow, F. Stephan, Infinitely Often Autoreducible Sets, SIAM Journal on Computing, 36(3): 595-608, 2006

I. Dinur, K. Nissim, Revealing information while preserving privacy, Proceedings of the 22nd Symposium on Principles of Database Systems, 2003, pages 202-210

E. Friedgut, J. Kahn, A. Wigderson, Computing Graph Properties by Randomized Subcube Partitions, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2002), pages 105-113

Y. Gertner, T. Malkin, O. Reingold, On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, pages 126-135

O. Goldreich, A. Wigderson, Derandomization that is Rarely Wrong from Short Advice that is Typically Good, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2002), pages 209-223

S. Kasif, Z. Weng, R. Beigel, C. DeLisi, A Computational Framework for Optimal Masking in the Synthesis of Oligonucleotide Microarrays, Nucleic Acids Research, 30(20): 106, 2002

A. Razborov, Resolution Lower Bounds for Perfect Matching Principles, Journal of Computer and System Sciences, 69(1): 3-27, 2004

O. Regev, Priority Algorithms for Makespan Minimization in the Subset Model, Information Processing Letters, 84(3): 153-157, 2002

N. Alon, J. Balogh, P. Keevash, B. Sudakov, The number of edge colorings with no monochromatic cliques, Journal of the London Math. Society, 70(2): 273-288, 2004

N. Alon, B. Bollobas, M. Krivelevich, B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, Journal of Combinatorial Theory, ser. B, 88: 329-346, 2003

N. Alon, M. Krivelevich, B. Sudakov, Turan numbers of bipartite graphs and related Ramsey-type questions, Combinatorics, Probability and Computing, 12: 477-494, 2003

N. Alon, M. Krivelevich, B. Sudakov, Induced subgraphs of prescribed size, Journal of Graph Theory, 43: 239-251, 2003

N. Alon, P. Pudlak, Equilateral sets in $l^n_p$, Geometric and Functional Analysis, 13: 467-482, 2003

N. Alon, V. Rodl, Sharp bounds for some multicolor Ramsey numbers, Combinatorica, 25: 125-141, 2005

B. Gelbord, R. Meshulam, Spaces of singular matrices and matroid parity, European Journal of Combinatorics, 23(2): 389-397, 2002

P. Keevash, B. Sudakov, Local density in graphs with forbidden subgraphs, Combinatorics, Probability and Computing, 12:139-153, 2003

J.H. Kim, B. Sudakov, V. Vu, On the asymmetry of random graphs and random regular graphs, Random Structures and Algorithms, 21:216-224, 2002

A. Kostochka, B. Sudakov, On Ramsey numbers of sparse graphs, Combinatorics, Probability and Computing, 12: 627-641, 2003

B. Reed, B. Sudakov, List coloring when the chromatic number is close to the order of the graph, Combinatorica, 25: 117-123, 2005