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