# 2005-2006 papers

*This page contains links to some papers produced during the academic year of 2005-2006. Our outcome this year has very much benefited from the closest interaction with Lie Groups, Representations and Discrete Mathematics, and, on the other hand, the ``core complexity'' (whatever it is) component was less strong than usual. As a consequence, when I tried to classify the papers, virtually any pair of categories I was able to think of had a non-trivial intersection; perhaps, this is a general trend. Anyway, unlike*

- N. Alon, V. Asodi, Tracing Many Users With Almost No Rate Penalty,
*IEEE Transactions on Information Theory*, 53: 437-439, 2007 - N. Alon, E. Fischer, I. Newman, A. Shapira, A Combinatorial Characterization of the Testable Graph Properties: it's all about regularity, Proceedings of the
*38th Annual ACM Symposium on the Theory of Computing, 2006*, pages 251-260 - N. Alon, M. Capalbo, Sparse Universal Graphs for Bounded Degree Graphs,
*Random Structures and Algorithms*, 31: 123-133, 2007 - N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. Rodl, Measures of Pseudorandomness for Finite Sequences: typical values,
*Combinatorics, Probability and Computing*, 15(1-2): 1-29, 2006 - N. Alon, E. Lubetsky, Graph Powers, Delsarte, Hoffman, Ramsey and Shannon,
*SIAM Journal on Discrete Mathematics*, 21: 329-348, 2007 - N. Alon, E. Lubetsky, Uniformly Cross Intersecting Families
- 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 - N. Alon, S. Smorodinsky, Conflict-free Colorings of Shallow Discs, Proceedings of the
*22nd Annual Symposium on Computational Geometry*, 2006, pages 41-43 - N. Alon, U. Stav, What is the Furthest Graph from a Hereditary Property?
- N. Alon, B. Sudakov, H-free Graphs of Large Minimum Degree,
*Electronic Journal of Combinatorics*, 13: R19, 2006 - N. Alon, B. Sudakov, On Graphs with Subgraphs of Large Independence Numbers,
*Journal of Graph Theory*, 56: 149-157, 2007 - B. Barak, A. Rao, R. Shaltiel, A. Wigderson, 2-Source Dispersers for Sub-Polynomial Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction, Proceedings of the
*38th Annual ACM Symposium on the Theory of Computing*, 2006, pages 671-680 - A. Bogdanov, L. Trevisan, Average-Case Complexity,
*Foundations and Trends in Theoretical Computer Science*, 2(1), 2006 - A. Bogdanov, L. Trevisan, On Worst-Case to Average-Case Reductions for NP Problems,
*SIAM Journal on Computing*, 36(4): 1119-1159, 2006 - T. Bohman, A. Frieze, B. Sudakov, The Game Chromatic Number of Random Graphs,
*Random Structures and Algorithms*, 32: 223-235, 2008 - J. Bourgain, A. Gamburd,
**New Results on Expanders**,*Comptes Rendus Acad. Sci. Paris, Ser. I*, 342: 717-721, 2006 - J. Bourgain, A. Gamburd,
**On the Spectral Gap for Finitely-Generated Subgroups of SU(2)**,*Invent. Math.*, 171(1): 83--121, 2008 - J. Bourgain, A. Gamburd,
**Uniform expansion bounds for Cayley graphs of SL_2(F_p)** - J. Bourgain, A. Gamburd, P. Sarnak,
**Sieving and Expanders**,*Comptes Rendus Acad. Sci. Paris, Ser. I*, 343: 155-159, 2006 - B. Bukh, B. Sudakov, Induced Subgraphs of Ramsey Graphs with Many Distinct Degrees,
*Journal of Combinatorial Theory, Ser. B*, 97: 612-619, 2007 - I. Dinur, M. Sudan, A. Wigderson, Robust Local Testability of Tensor Products of LDPC Codes, Proceedings of the
*10th International Workshop on Randomization and Computation (RANDOM 2006)*, pages 304-315 - T. Gedlander, Y. Glasner, Countable Primitive Groups
- Y. Glasner, Strong Approximation on Random Towers of Graphs
- Y. Glasner, N. Monod, Amenable Actions, Free Products and a Fixed Point Property,
*Bull. London Math. Soc.*, 39(1): 138–150, 2007 - S. Hoory, N. Linial, A. Wigderson, Expander Graphs and their Applications,
- G. Kalai, R. Meshulam, Intersections of Leray Complexes and Regularity of Monomial Ideals,
*Journal of Combinatorial Theory Ser. A.*, 113: 1586-1592, 2006 - P. Keevash, P. Loh, B. Sudakov,Bounding the number of edges in permutation graphs,
*Electronic Journal of Combinatorics*, 13: R44, 2006 - R. Krauthgamer, J. Lee, Algorithms on Negatively Curved Spaces, Proceedings of the
*47th Symposium on Foundations of Computer Science*, 2006, pages 119-132 - J. Lee, Volume Distortion for Subsets of Euclidean Spaces, Proceedings of the
*22nd Annual Symposium on Computational Geometry*, 2006, pages 207-216 - J. Lee, A. Naor, L_p Metrics on the Heisenberg Group and the Goemans-Linial Conjecture, Proceedings of the
*47th Symposium on Foundations of Computer Science*, 2006, pages 99-108 - J. Lee, A. Naor, Y. Peres, Trees and Markov Convexity, Proceedings of the
*17th Annual ACM-SIAM Symposium on Discrete Algorithms*, 2006, pages 1028-1037 - P. Loh, B. Sudakov, On the Strong Chromatic Number of Random Graphs,
*Combinatorics, Probability and Computing*, 17: 271-286, 2008 - P. Loh, B. Sudakov, Independent Transversals in Locally Sparse Graphs,
*Journal of Combinatorial Theory, Ser. B*, 97: 904-918, 2007 - A. Lubotzky, R. Meshulam, A Moore Bound for Simplicial Complexes,
*Bull. London Math. Soc.*, 39: 353-358, 2007 - M. Luby, A. Wigderson, Pairwise Independence and Derandomization,
*Foundations and Trends in Theoretical Computer Science*, 1(4): 237-301, 2005 - R. Meshulam, N. Wallach, Homological Connectivity of Random k-dimensional Complexes
- A. Razborov, Flag Algebras,
*Journal of Symbolic Logic*, 72(4): 1239-1282, 2007 - A. Razborov, On the Minimal Density of Triangles in Graphs
- A. Razborov, S. Yekhanin, An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval,
*Theory of Computing*, 3: 221-238, 2007 - B. Sudakov, Ramsey Numbers and the Size of Graphs
- B. Sudakov, J. Verstraete, Cycle Lengths in Sparse Graphs
- B. Sudakov, V. Vu, Local Resilience of Graphs
- T. Tao, V. Vu, Inverse Littlewood-Offord Theorems and the Condition Number of Random Matrices
- A. Wigderson, P, NP and Mathematics - a Computational Complexity Perspective, Proceedings of the
*International Congress of Mathematicians 2006*, Vol. I, EMS Publishing House, Zurich, 2007, pages 665-712