2004-2005 papers

This page contains links to some papers produced during the academic year of 2004-2005. It is our intention to regularly update this page, so if you know of any new links/references please let us know. Also, this year turned out to be even more interdisciplinary than usual, and many papers are hard to classify within "complexity", "algorithms" or "combinatorial" categories. Thus, unlike previous years, we even do not attempt such a classification. We still try, however, to identify a few topics on which the communication between the program's residents was particularly intense. All other papers are listed alphabetically.

Derandomization, Pseudo-Randomness and Applications

TCS/DM Methods in Statistical Mechanics

  • D. Galvin, Slow Mixing of Local Dynamics for 3-Colourings on Regular Bipartite Graphs
  • D. Galvin, Bounding the Partition Function of Spin Systems, Electronic Journal of Combinatorics, 13(1): R72, 2006
  • D. Galvin, P. Tetali, Slow Mixing of Glauber Dynamics for the Hard-Core Model on Regular Bipartite Graphs, Random Structures and Algorithms, 28: 427-443, 2006
  • F. Martinelli, A. Sinclair, D. Weitz, Fast Mixing for Independent Sets, Colorings and Other Model on Trees, Random Structures and Algorithms, 31: 134-172, 2007
  • D. Weitz, Combinatorial Criteria for Uniqueness of Gibbs Measures, Random Structures and Algorithms, 27(4): 445-475, 2005
  • D. Weitz, Counting down the tree

Grothendieck-Type Inequalities

  • N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic Forms on Graphs, Inventiones Mathematicae, 163: 499-522, 2006
  • S. Arora, E. Berger, E. Hazan, G. Kindler, S. Safra, On Non-Approximability for Quadratic Programs, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 206-215

Other papers

  • S. Aaronson, Oracles Are Subtle But Not Malicious, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, 2006, pages 261-273
  • S. Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, 36(1): 30-52, 2005
  • S. Aaronson, Quantum Computing, Postselection, and Probabilistic Polynomial-Time, Proceedings of the Royal Society A, 461(2063): 3473-3482, 2005
  • S. Aaronson, The Complexity of Agreement, Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pages 634-643
  • R. Aharoni, E. Berger, Menger's Theorem for Infinite Graphs
  • R. Aharoni, E. Berger, The Intersection of a Matroid and a Simplicial Complex, Transactions of the American Mathematical Society, 358(11): 4895-4917, 2006
  • M. Alekhnovich, S. Arora, I. Tourlakis, Towards Strong Nonapproximability Results in the Lovasz-Schrijver Hierarchy, Proceedings of the 37th Annual ACM Symposium on the Theory of Computing, 2005, pages 294-303
  • M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi, Toward a Model for Backtracking and Dynamic Programming, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, 2005, pages 308-322
  • M. Alekhnovich, S. Khot, G. Kindler, N. Vishnoi, Hardness of Approximating the Closest Vector Problem with Pre-Processing, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 216-225
  • M. Alekhnovich, S. Khot, T. Pitassi, Inapproximability of Fixed Parameter Problems
  • N. Alon, Ranking Tournaments, SIAM J. on Discrete Mathematics, 20: 137-142, 2006
  • N. Alon, B. Bollobas, A. Gyarfas, J. Lehel, A. Scott, Maximum Directed Cuts in Acyclic Digraphs, Journal of Graph Theory, 55: 1-13, 2007
  • N. Alon, E. Fisher, I. Newman, Testing of Bipartite Graph Properties, SIAM Journal on Computing, 37: 959-976, 2007
  • N. Alon, M. Krivelevich, J. Spencer, T. Szabo, Discrepancy Games, The Electronic Journal of Combinatorics, 12:R51, 2005
  • N. Alon, M. Krivelevich, B. Sudakov, Embedding Nearly-Spanning Bounded Degree Trees, Combinatorica, 27: 629-644, 2007
  • N. Alon, I. Newman, A. Shen, G. Tardos, N. Vereshchagin, Partitioning Multi-Dimensional Sets in a Small Number of Uniform Parts, European Journal of Combinatorics, 28:134-144, 2007
  • N. Alon, R. Radoicic, B. Sudakov, J. Vondrak, A Ramsey-Type Result for the Hypercube, Journal of Graph Theory, 53: 196-208, 2006
  • N. Alon, A. Shapira, A Characterization of the (natural) Graph Properties Testable with One-Sided Error, , SIAM Journal on Computing, 37: 1703-1727, 2008
  • N. Alon, A. Shapira, B. Sudakov, Additive Approximation for Edge-Deletion Problems, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 419-428
  • B. Barak, R. Canetti, J. Lindell, R. Pass, T. Rabin, Secure Computation Without Authentication, Proceedings of the 25th Annual International Cryptology Conference (CRYPTO 2005), pages 361-377
  • B. Barak, S. Halevi, A Model and an Architecture for Pseudo-Random Generation and Applications to /dev/random, Proceedings of the 12th ACM Conference on Computing and Communication Security, 2005, pages 203-212
  • B. Barak, A. Sahai, How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 543-552
  • P. Beame, T. Pitassi, N. Segerlind, A. Wigderson, A Strong Direct Product Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness, Computational Complexity, 15(4): 391-432, 2006
  • E. Berger, R. Ziv, A Note on the Cover Number and Independence Number in Hypergraphs
  • F. Bonomo, M. Chudnovsky, G. Duran, Partial Characterizations of Clique-Perfect Graphs I: Subclasses of Claw-Free Graphs, Discrete Applied Mathematics, 156(7): 1058-1082, 2008
  • F. Bonomo, M. Chudnovsky, G. Duran, Partial Characterizations of Clique-Perfect Graphs II: Diamond-Free and Helly Circular-Arc Graphs
  • M. Chudnovsky, W. Cunningham, J. Geelen, An Algorithm for Packing Non-Zero A-paths in Group-Labeled Graphs
  • M. Chudnovsky, Alexandra Ovetsky, Coloring Quasi-Line Graphs, Journal of Graph Theory, 54(1): 41-50, 2007
  • N. Goyal, G. Kindler, M. Saks, Lower Bounds for the Noisy Broadcast Problem, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 40-49
  • A. Razborov, On the Minimal Density of Triangles in Graphs
  • A. Wigderson, D. Xiao, A Randomness-Efficient Sampler for Matrix-Valued Functions and Applications, Proceedings of the 46th Symposium on Foundations of Computer Science, 2005, pages 397-406