2007-2008 Papers

This page contains links to some papers produced during the academic year of 2007-2008.

Theoretical Computer Science

• Venkatesan Guruswami.  Artin Automorphisms, cyclotomic function fields, and folded list-decodable codes.  Manuscript, 2008.
• Venkatesan Guruswami, Rajsekar Manokaran and Prasad Raghavendra.  Beating the random ordering is hard: Inapproximability of Maximum Acyclic Subgraph.  In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, October 2008.
• Venkatesan Guruswami, James Lee and Avi Wigderson.  Euclidean sections of sublinear randomness and error-correcting codes.
• Venkatesan Guruswami and Prasad Raghavendra.   Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness.  APPROX 2008 and ECCC Report TR08-08.
• Venkatesan Guruswami and Atri Rudra.  Soft decoding, dual BCH codes, and better list-decodable  varepsilon-biased codes.  In Proceedings of the 23rd IEEE Conference on Computational Complexity,  pp. 163-174, June 2008.
• Parikshit Gopalan and Venkatesan Guruswami.  Hardness amplification within NP against deterministic algorithms.  In Proceedings of the 23rd IEEE Conference on Computational Complexity, pp. 19-30, June 2008.
• Venkatesan Guruswami, James Lee and Alexander Razborov.  Almost Euclidean sections of $ell N^1$ via expander codes.  SODA 2008.
• Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang.  Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs.  ECCC Report TR07-113; submitted to Combinatorica, 2007.
• Venkatesan Guruswami and Widad Machmouchi.  Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction.  In Proceedings of the 2008 IEEE International Symposium on Information Theory, June 2008.
•  Anup Rao.  Parallel Repetition in Projection Games and a Concentration Bound.  STOC 08,  SICOMP Special Issue for STOC 08.
• Guy Kindler, Ryan O'Donnell, Anup Rao and Avi Wigderson.  Spherical Cubes and Rounding in High Dimensions. FOCS 08.
• Boaz Barak, Moritz Hardt, Ishay Haviv,  Anup Rao,  Oded Regev and David Steurer.  Rounding Parallel Repetitions of Unique Games.  FOCS 08.
• Yael Tauman Kalai, Xin Li,  Anup Rao and David Zuckerman.  Network Extractor Protocols.  FOCS 08.
•  Alexander A. Razborov and Alexander A. Sherstov.  The Sign-Rank of AC^0.  2008
• Cynthia Dwork and Sergey Yekhanin.  New efficient attacks on statistical disclosure control mechanisms.  Proceedings of the 28th International Cryptology Conference (CRYPTO), pp. 469-480, 2008.
• Swastik Kopparty and Sergey Yekhanin.  Detecting rational points on hypersurfaces over finite fields.  Proceedings of the 23rd IEEE Computational Complexity Conference (CCC), pp. 311-320, 2008.
• Kiran S. Kedlaya and Sergey Yekhanin.  Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers.  Proceedings of the 23rd IEEE Computational Complexity Conference, pp. 175-186, 2008.  Accepted to SIAM Journal of Computing, 2008.
• Sergey Yekhanin.  Towards 3-query locally decodable codes of subexponential length.  Journal of the ACM, vol. 55, issue 1, pp. 1-16, 2008.
•  Noga Alon, Lech Drewnowski and Tomasz Luczak.  Stable Kneser Hypergraphs and Ideals in N with the Nikodym Property.  Proceedings of the Amer. Math. Soc. 137 (2009), 467-471.
• Noga Alon, Jaroslaw Grytczuk, Michal Lason and Mateusz Michalek.  Splitting necklaces and measurable colorings of the real line.  Proceedings of the Amer. Math. Soc., to appear.
• Noga Alon and Uri Stav.  What is the Furthest Graph from a Hereditary Property?  Random Structures and Algorithms 33 (2008), 87-104.
• Noga Alon and Shmuel Friedland.  The Maximum Number of Perfect Matchings in Graphs with a Given Degree Sequence.  The Electronic J. Combinatorics 15 (2008), N13.
• Noga Alon, Boris Bukh and Benny Sudakov.  Discrete Kakeya-type problems and small bases.  Israel J. Math, to appear.
• Noga Alon, Ido Ben-Eliezer and Michael Krivelevich.  Small sample spaces cannot fool low degree polynomials.  RANDOM 2008, to appear.
• Noga Alon, Avinatan Hasidim, Eyal Lubetzky, Uri Stav and Amit Weinstein.  Broadcasting with side information.  Proceedings of the 49th IEEE FOCS (2008), to appear.
• Xi Chen, Xiaoming Sun and Shang-Hua Teng.  Quantum Separation of Local Search and Fixed Point Computation.  Proceedings of the 14th Annual International Computing and Combinatorics Conference, pp. 169-178, 2008.  
• Jin-Yi Cai, Xi Chen and Dong Li.  A Quadratic Lower Bound for the Permanent and Determinant Problem over any Characteristic \ne 2.  Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 491-498, 2008.
• Kevin P. Costello and Van Vu, On the Rank of Random Sparse Matrices.  Submitted.
• Kevin P. Costello and Van Vu.  Concentration of Determinant-based Permanent Estimators for Strictly Positive Matrices.  Submitted.
  
• Jacob Fox and Benny Sudakov.  Ramsey-Type Problem for an Almost Monochromatic K4.  To appear.
• David Conlon, Jacob Fox and Benny Sudakov.  Ramsey numbers of sparse hypergraphs.  To appear.
• Noga Alon, Michael Krivelevich and Benny Sudakov.  Large Nearly Regular Induced Subgraphs.  SIAM J. Discrete Math, vol. 22, no. 4 (2008), pp. 1325-1337.
• Jozsef Solymosi and Van Vu.  "Sum-product estimates for well-conditioned matrices."  The Bulletin of the London Mathematical Society.  Accepted.
• Jozsef Solymosi.  "Spectral bounds on incidences."  Additive Combinatorics. Eds. Javier Cilleruelo, Marc Noy and Oriol Serra.  Advanced Courses of CRM.  Birkhauser, 2009.  Accepted.
• Jozsef Solymosi.  "Incidences and the Spectra of Graphs."  Building Bridges between Mathematics and Computer Science, vol. 19.  Eds. Martin Groetschel and Gyula Katona.  Series: Bolyai Society Mathematical Studies.  Springer, 2008. pp. 499-513.