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.