*This page contains links to some papers produced during the academic year of 2003-2004.*

## Derandomization and Pseudo-Randomness

- B. Barak, R. Impagliazzo, A. Wigderson, Extracting Randomness from Few Independent Sources,
*SIAM Journal on Computing*, 36(4): 1095-1118, 2006 - E. Rozenman, A. Shalev, A. Wigderson, Iterative construction of Cayley expander graphs,
*Theory of Computing*, 2: 91-120, 2006 - A. Shpilka, A. Wigderson, Derandomizing Homomorphism Testing in General Groups,
*SIAM Journal on Computing*, 36(4): 1215-1230, 2006 - See also Small Pseudo-Random Families of Matrices... in the section
*Quantum Computations*below

## Proof Complexity (and applications)

- M. Alekhnovich, Lower Bounds for k-DNF Resolution on Random 3-CNFs, Proceedings of the
*37th Annual ACM Symposium on Theory of Computing, 2005*, pages 251-256 - M. Alekhnovich, M. Braverman, V. Feldman, A. Klivans, T. Pitassi, Learnability and Automatizability, Proceedings of the
*45th Symposium on Foundations of Computer Science, 2004*, pages 621-630 - M. Alekhnovich, E. Hirsch, D. Itsykson, Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas,
*Journal of Automated Reasoning*, 35(1-3):51-72, 2005 - J. Krajicek, Structured Pigeonhole Principle, Search Problems and Hard Tautologies,
*Journal of Symbolic Logic*, 70(2): 619-630, 2005 - N. Segerlind, An Exponential Separation between Res(k) and Res(k+1) for k<= \epsilon\log n,
*Information Processing Letters*, 93(4): 185-190, 2005

## Quantum Computations

- A. Ambainis, Quantum Search Algorithms,
*SIGACT News*, 35(2): 22-35, 2004 - A. Ambainis, Quantum Walk Algorithm for Element Distinctness,
*SIAM Journal on Computing*, 37(1): 210-239, 2007 - A. Ambainis, J. Kempe, A.Rivosh, Coins Make Quantum Walks Faster, Proceedings of the
*16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005*, pages 1099-1108 - A. Ambainis, A. Smith, Small Pseudo-Random Families of Matrices: Derandomizing Approximate Quantum Encryption, Proceedings of the
*8th International Workshop on Randomization and Computation, 2004*, pages 249-260 - A. Razborov, An Upper Bound on the Threshold Quantum Decoherence Rate,
*Quantum Information and Computation*, 4(3): 222-228, 2004

## Other papers in Complexity, Cryptography and Algorithms

- B. Barak, R. Canetti, J. B. Nielsen, R. Pass, Universally Composable Protocols with Relaxed Set-Up Assumptions, Proceedings of the
*45th Symposium on Foundations of Computer Science, 2004*, pages 186-195 - I. Dinur, E. Friedgut, G. Kindler, R. O'Donnell, On the Fourier Tails of Bounded Functions over the Discrete Cube, Proceedings of the
*38th Symposium on Theory of Computing, 2006*, pages 437-446 - C. Dwork, M. Naor, O. Reingold, Immunizing Encryption Schemes from Decryption Errors, Proceedings of
*EUROCRYPT 2004*, pages 342-360 - S. Khot, Hardness of Approximating the Shortest Vector Problem in Lattices,
*Journal of the ACM*, 52(5): 789-808, 2005 - S. Khot, Ruling out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique,
*SIAM Journal on Computing*, 36(4): 1025-1071, 2006 - S. Khot, G. Kindler, E. Mossel, R. O'Donnell, Optimal Inapproximability Results for MAX-CUT and other Two-variable CSPs,
*SIAM Journal on Computing*, 37(1): 319-357, 2007 - V. Lifschitz, A. Razborov, Why Are There So Many Loop Formulas?,
*ACM Transactions on Computational Logic*, 7(2): 261-268, 2006 - D. Micciancio, N. Segerlind, Using Hypergraph Homomorphisms to Guess Three Secrets
- E. Mossel, R. O'Donnell, O. Regev, J. Steif, B. Sudakov, Non-interactive Correlation Distillation, Inhomogeneous Markov Chains, and the Reverse Bonami-Beckner Inequality,
*Israel Journal of Mathematics*, 154: 299-336, 2006 - R. O'Donnell, R. Servedio, On Decision Trees, Influences, and Learning Monotone Decision Trees
- A. Razborov, Guessing More Secrets via List Decoding,
*Internet Mathematics*, 2(1): 21-30, 2005 - O. Reingold, L. Trevisan, S. Vadhan, Notions of Reducibility between Cryptographic Primitives, Proceedings of the
*Theory of Cryptography Conference 2004*, pages 1-20 - T. Sang, F. Bacchus, P. Beame, H. Kautz, T. Pitassi, Combined Component Caching and Clause Learning for Effective Model Counting, Proceedings of the
*7th International Conference on Theory and Applications of Satisfiability Testing, 2004*

## Combinatorics

- M. Chudnovsky, Berge Trigraphs,
*Journal of Graph Theory*, 53: 1-55, 2006 - M. Chudnovsky, P. Seymour, The Roots of the Stable Set Polynomial of a Clawfree Graph,
*Journal of Combinatorial Theory, Ser. B*, 97:350-357, 2007 - M. Chudnovsky, P. Seymour, Clawfree Graphs I -- Clique Cutsets
- M. Chudnovsky, P. Seymour, Clawfree Graphs II -- Circular Interval Graphs
- M. Chudnovsky, P. Seymour, Clawfree Graphs III -- Sparse Decomposition
- M. Chudnovsky, P. Seymour, The Structure of Clawfree Graphs,
*Surveys in Combinatorics, London Math. Soc. Lecture Note Series Vol. 327*, 2005