2003-2004 papers

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