2008-2009 Papers

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

Theoretical Computer Science

• A. Akavia.  Finding significant Fourier transform coefficients deterministicaly and locally.  Electronic Colloquium on Computational Complexity (ECCC), 15(102), 2008.
• A. Akavia.  Solving hidden number problem with one bit oracle and advice.   Proceedings of the 29th Annual International Cryptology Conference, Santa Barbara, CA, August 16-20, 2009.
• A. Akavia, Shafi Goldwasser and Vinod Vaikuntanathan.  Simultaneous hardcore bits and cryptography against memory attacks.  In Omer Reingold, ed., TCC, volume 5444 of Lecture Notes in Computer Science, pp. 474-495.  Springer, 2009.
• A. Akavia and Ramarathnam Venkatesan.  Perturbation codes.  In 46th Annual Allerton Conference, September 23-26, 2008, University of Illinois at Urbana-Champaign.
• N. Alon and E. Lubetzky.  Uniformly cross intersecting families, Combinatorica 29 (2009), pp. 389-431.
• N. Alon and N. Wormald.  High degree graphs contain large star factors.  "Fete of Combinatorics," Bolyai Soc. Math. Studies, 20 (G. Katona, A. Schrijver and T. Szony , eds.), Spring 2010, pp. 9-21.
• N. Alon and U. Feige.  On the power of two, three and four probes.  Proceedings of the 20th Annual ACM-SIAM SODA (2009), pp. 346-354.
• N. Alon and P. Edelman.  The inverse Banzhaf problem. Social Choice and Welfare,34 (2010), no. 3, pp. 371-377.
• N. Alon and S. Gutner.  Balanced Hashing, Color Coding and Approximate Counting. Proceedings IWPEC 2009,  J. Chen and F. V. Fomin, eds.), LNCS 5917 (2009), pp. 1-16.
• N. Alon.  Economical elimination of cycles in the torus. Combinatorics, Probability and Computing 18 (2009): 619-627.
  
• N. Alon, A. Granville and A. Ubis.  The number of sumsets in a finite field.  Bull. London Math. Soc.  To appear.
• N. Alon, R. Panigrahy and S. Yekhanin.  Deterministic approximation algorithms for the nearest codeword problem.  RANDOM-APPROX 2009, pp. 339-351.
• N. Alon, D. Lokshtanov and S. Saurabh.  fast FAST.  Proceedings of ICALP 2009: 49-58.
• A. Chattopadhyay and A. Wigderson.  Linear systems over composite moduli.  Proceedings of FOCS 2009, pp. 43-62.
• B. Barak, M. Braverman, X. Chen and A. Rao.  Direct sums in randomized communication complexity.  ECCC Report TR09-044, 2009.
• J-Y. Cai, X. Chen and P. Lu.  Graph homomorphisms with complex values: A dichotomy theorem.  arXiv:0903.4728, 2009.
• X. Chen, D. Dai, Y. Du and S-H. Teng.  Settling the complexity of Arrow-Debreu equilibria in markets with additively separable utilities.  arXiv:0904.0644, 2009.
• Z. Dvir, S. Kopparty, S. Saraf and M. Sudan.  Extensions to the method of multiplicities, with applications to kakeya sets and mergers.   Proceedings of FOCS 2009, pp. 181-190.
• Z. Dvir.  On the size of kakeya sets in finite fields.  J. Amer. Math. Soc., 22:1093-1097, 2009.
• Z. Dvir.  Extractors for varieties.  Proceedings of the IEEE Conference on Computational Complexity 2009.
• Z. Dvir and A. Wigderson.  Kakeya sets, new mergers and old extractors.  Proceedings of  FOCS 2008, pp. 625-633.
• Z. Dvir.  Recent progress on the kakeya problem.  Report, June 2009.
• P. Hrubes and A. Yehudayoff.  Arithmetic complexity in algebraic extensions.  Submitted.
• P. Hrubes and A. Yehudayoff.  Homogeneous formulas and symmetric polynomials.  arXiv:0707.2621v1, 2009..
• P. Hrubes and A. Yehudayoff.  Monotone separations for constant degree polynomials.  Inf. Process. Lett. 110(1):1-3 (2009).
• P. Hrubes.  Kreisel's conjecture with minimality principle.  Journal of Symbolic Logic 74(3):976j-988 (2009).
• P. Hrubes and I. Tzameret.  The proof complexity of polynomial identities.  Proceedings of IEEE Conference on Computational Complexity 2009, pp. 41-51.
• P. Hrubes, S. Jukna, A. Kulikov and P. Pudlak.  On convex complexity measures.  Submitted.
• C. Calabro, R. Impagliazzo, V. Kabanets and R. Paturi.  The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs.  J. Comput. Syst. Sci. 74(3):386-393 (2008).
• Y. Dodis, R. Impagliazzo, R. Jaiswal and V. Kabanets.  Security Amplification for Interactive Cryptographic Primitives.  TCC 2009: 128-145.
• R. Impagliazzo, R. Jaiswall and V. Kabanets.  Chernoff-Type Direct Product Theorems.  J. Cryptology 22(1): 75-92 (2009).
• R. Impagliazzo, V. Kabanets and A. Kolokolova.  An axiomatic approach to algebrization.  Proceedings of STOC 2009: 695-704.
• R. Impagliazzo, V. Kabanets and A. Wigderson.  New direct-product testers and 2-query PCPs.  Proceedings of STOC 2009: 131-140.
• G. Kun and M. Szegedy.  A new line of attack on the dichotomy conjecture.  Proceedings of STOC 2009: 725-734.
• D. Moshkovitz and R. Raz.  Two query PCP with sub-constant error.  Proceedings of FOCS 2008,  pp. 140-180.
• A. Rao.  Parallel Repetition in Projection Games and a Concentration Bound.  Proceedings of the 40th Annual ACM Symposium on Theory of Computering, 2008
• B. Barak, A. Rao, R. Raz, R. Rosen and R. Shaltiel.  A Strong Parallel Repetition Theorem for Free Projection Games.  Proceedings of RANDOM 2009, pp. 352-365
• B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev and D. Steurer.  Rounding Parallel Repetitions of Unique Games.  Proceedings of FOCS 2008.
• G. Kindler, R. O'Donnell, A. Rao and Avi Wigderson.  Spherical Cubes and Rounding in High Dimension.  Proceedings of FOCS 2008: 189-198.
• Y. Kalai, X. Li and A. Rao.  2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness.  Proceedings of FOCS 2009, pp. 617-626.
• A. Rao.  Extractors for Low-Weight Affine Sources.  Proceedings of IEEE Conference on Computational Complexity 2009, pp. 95-101..
• V. Vassilevska, R. Williams and R. Yuster.  All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time.  Theory of Computing 5(1):173-189 (2009).
• V. Vassilevska and R. Williams.  Finding, minimizing, and counting weighted subgraphs.  Proceedings of the 41st Annual ACM Symposium on Theory of Computing 2009, pp. 455-464.
• V. Vassilevska.  Fixing a tournament.  Submitted.
• L. Fortnow, R. Santhanam and R. Williams.  Fixed-Polynomial Size Circuit Bounds. To appear in Proceedings of CCC 2009.
• R. Williams.  Finding paths of length k in O* (2^k). time.  Information Processing Letters 109 (6):315-318, 2009.
• I. Koutis and R. Williams.  Limits and applications of group algebra for parameterized problems.  ICALP (1) 2009, pp. 653-664..
• S. Diehl, D. van Melkebeek and R. Williams.  An Improved Time-Space Lower Bound for Tautologies.  Proceedings of COCOON 2009, pp. 429-438, and to appear in Journal of Combinatorial Optimization.
• I. Benjamin, G. Kozma, A. Yadin and A. Yehudayoff.  Entropy of random walk range.  Submitted.