This page contains links to some papers produced during the Special Year. They are roughly (in some cases somewhat artificially) classified by topic. It is our intention to regularly update  this page, so if you know of any new links/references please let us know. An extremely brief introduction to some of these subjects (with references to the literature), as well as equally brief annotations to some of them can be found at our topic page.
 
 

M. V. Alekhnovich, Mutilated Chessboard Problem is Exponentially Hard for Resolution, Theoretical Computer Science, 310(1-3): 513-525, 2004

M. V. Alekhnovich, A. A. Razborov, Resolution is Not Automatizable Unless W[P] is Tractable, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, pages 210-219

A. Atserias, N. Galesi, P. Pudlak, Monotone simulations of nonmonotone propositional proofs, Journal of Computer and System Sciences, 65: 626-638, 2002

E. Ben-Sasson, N. Galesi, Space Complexity of Random Formulae in Resolution, Random Structures and Algorithms, 23(1): 2003, 92-109

P. Pudlak, Parallel Strategies, Journal of Symbolic Logic, 68(4): 2003, 1242-1250

R. Raz, Resolution Lower Bounds for the Weak Pigeonhole Principle, Journal of the ACM, 51(2): 2004, 115-138

A. A. Razborov, Improved Resolution Lower Bounds for the Weak Pigeonhole Principle, Electronic Colloquium on Computational Complexity, Report TR01-055

N. Alon, A. Lubotzky, A. Wigderson, Semi-direct Product in Groups and Zig-Zag products in graphs: Connections and Applications, Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, 2001, pages 630-637

R. Impagliazzo, V. Kabanets, A. Wigderson, In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time, Journal of Computer and System Sciences, 65(4): 672-694, 2002

M. Naor, O. Reingold, Constructing Pseudo-Random Permutations with a Prescribed Structure, Journal of Cryptology, 5(2): 97-102, 2002

O. Reingold, R. Saltiel, A. Wigderson, Extracting Randomness via Repeated Condensing, SIAM Journal on Computing, 35(5): 1185-1209, 2006

O. Reingold, S. Vadhan, A. Wigderson, Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 2000, pages 3-13. A full version of a portion of this paper has appeared in Annals of Mathematics, 155(1): 157-187, 2002

W. Aiello, Y. Ishai, O. Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, Proceedings of the EUROCRYPT Conference, 2001, pages 119-135

L. Antunes, L. Fortnow, D. van Melkebeek, Computational Depth, Proceedings of the 16th IEEE Conference on Computational Complexity, 2001, pages 266-273

L. Babai, A. Gal, P. Kimmel, S. Lokam, Communication Complexity of Simultaneous Messages, SIAM Journal on Computing, 33(1): 137-166, 2003

J. Forster, M. Krause, S. Lokam, R. Mubarakzjanov, N. Schmitt, H. U. Simon, Relations between Communication Complexity, Linear Arrangements, and Computational Complexity, Proceedings of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science, 2001, pages 171-182

Y. Gertner, S. Kannan, T. Malkin, O. Reingold, The Relationship between Public Key Encryption and Oblivious Transfer, Proceedings of the 41st IEEE Symposium on Foundations of Computer Science, 2000, pages 325-335

O. Goldreich, S. Vadhan, A. Wigderson, On Interactive Proofs with a Laconic Prover, Journal of Computational Complexity, 2076: 334 (?), 2003

V. Guruswami, J. Hastad, M. Sudan, Hardness of approximate hypergraph coloring, SIAM Journal on Computing, 31(6): 1663-1686, 2002

V. Guruswami, J. Hastad, M. Sudan, D. Zuckerman, Combinatorial bounds for list decoding, IEEE Transactions on Information Theory, 48(5): 1021-1034, 2002

J. Hastad, A slight sharpening of LMN, Journal of Computer and System Sciences, 63(3): 498-508, 2001

J. Hastad, S. Khot, Query efficient PCPs with pefect completeness, Theory of Computing, 1: 119-149, 2005

J. Hastad, M. Naslund, Practical construction and analysis of pseudo-randomness primitives, Journal of Cryptology, 21(1): 1-26, 2008

J. Hastad, V. Srinivasan, On the advantage over a random assignment, Random Structures and Algorithms, 25(2): 117-149, 2004

J. Hastad, A. Wigderson, Simple analysis for linearity and PCP, Random Structures and Algorithms, 22(2): 139-160, 2003

M. Parnas, D. Ron, A. Samorodnitsky, Testing Basic Boolean Formulae, SIAM Journal on Discrete Mathematics, 16(1): 20-46, 2002

P. Sen, V. Srinivasan, Lower Bounds in the Quantum Cell Probe Model, Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP), 2001, pages 358-369

D. van Melkebeek, Time-Space Lower Bounds for Satisfiability, Bulletin of the European Association for Theoretical Computer Science, 73: 57-77, 2001
 
 

N. Alon, G. Kalai, J. Matousek, R. Meshulam, Transversal Numbers for Hypergraphs Arising in Geometry, Advances in Applied Mathematics, 29: 79-101, 2002

B. Bollobas, D. Gamarnik, O. Riordan, B. Sudakov, On the Value of a Random Minimum Length Steiner Tree, Combinatorica, 24(2): 187--207, 2004

K. Dikema, C. Yan, Moments of the Quasi-Nilpotent DT-Operator

B. Gelbord, R. Meshulam, Maximum Singular Spaces of Skew Symmetric Matrices

V. Grolmusz, B. Sudakov, On k-wise Set-Intersections and k-wise Hamming-Distances, Journal of Combinatorial Theory Ser. A, 99(1): 180-190, 2002

M. Krivelevich, B. Sudakov, The Largest Eigenvalue of Sparse Random Graphs, Combinatorics, Probability and Computing, 12: 61-72, 2003

M. Krivelevich, B. Sudakov, T. Szabo, Triangle Factors in Pseudo-random Graphs, Combinatorica, 24: 403-426, 2004

M. Krivelevich, B. Sudakov, V. Vu, N. Wormald, On the Probability of Independent Sets in Random Graphs, Random Structures and Algorithms, 22: 1-14, 2003

J. Kung, C. Yan, On the Expected Sum of Parking Functions, Annals of Combinatorics, 7(4): 481-493, 2003

J. Kung, C. Yan, Goncharov Polynomials and Parking Functions, J. Combin. Theory Ser. A, 102(1): 16-37, 2003

B. Reed, B. Sudakov, Asymptotically the list colouring constants are 1, Journal of Combinatorial Theory Ser. B, 86: 27-37, 2002

M. Scharlemann, A. Thompson, Unknotting Tunnels and Seifert Surfaces, Proc. London Math. Soc. (3), 87(2):523-544, 2003