2012-2013 Papers

This page contains some papers produced during the academic year of 2012-2013.

Theoretical Computer Science

  • J. Chen and A. Zinger. The Robustness of Extortion in Iterated Prisoner's Dilemma. Under review at Journal of Economic Theory, 2013.
  • M. Braverman, J. Chen and S. Kannan. Optimal Waiting Times and Assignments in Healthcare Provision. 2013.
  • H. Huang, N. Linial, H. Naves, Y. Peled, B. Sudakov. On the 3-local profiles of graphs, preprint.
  • H. Huang, N. Linial, H.Naves, Y. Peled, B. Sudakov. On the densities of cliques and independent sets in graphs, preprint.
  • H. Huang. On the maximum induced density of directed stars and related problems, preprint.
  • G. Kol and R. Raz. Interactive Channel Capacity. STOC 2013.
  • Y. Kalai, R. Raz and R. Rothblum. Delegation for Bounded Space. STOC 2013.
  • A. Bhattacharyya, E. Fischer, H. Hatami, P. Hatami and S. Lovett. Every locally characterized affine-invariant property is testable. ECCC 2012.
  • C. Even-Zohar and S. Lovett. The Freiman-Ruzsa Theorem in Finite Fields. ECCC 2012.
  • M. Mendel and A. Naor. Nonlinear spectral calculus and super-expanders. Publications mathmatiques de l'IHS, 2013.
  • J. R. Lee, M. Mendel and M. Moharrami. A node-capacitated Okamura-Seymour theorem. Proceedings of the Symposium on Theory of Computing. STOC 2013.
  • M. Mendel and A. Naor. Spectral calculus and Lipschitz exten-sion for barycentric metric spaces. Submitted, 2013.
  • A. Moitra, R. O'Donnell. Pareto Optimal Solutions for Smoothed Analysts. 2013.
  • N. Alon, A. Moitra, B. Sudakov. Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications.
  • S. Arora, R. Ge, A. Moitra, S. Sachdeva. Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. arXiv:1206.5349v2, 2012.
  • M. Hardt and A. Moitra. Can We Reconcile Robustness and Efficiency in Unsupervised Learning?. arXiv:1211.1041v2, 2012.
  • S. Arora, R. Ge, Y. Halpern, D. Mimno, A. Moitra, D. Sontag, Y. Wu, M. Zhu. Practical Algorithm for Topic Modeling with Provable Guarantees. arXiv:1212.4777v1, 2012.
  • A. Moitra and M. Saks. A Polynomial Time Algorithm for Lossy Population Recovery. arXiv:1302.1515v1, 2012.
  • A. Moitra. A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. ECCC 2012.
  • M. Braverman and A. Moitra. An Information Complexity Approach to Extended Formulations. ECCC 2012.
  • J. Nelson and H. Nguyen. Sparsity Lower Bounds for Dimensionality Reducing Maps. arXiv: 1211.0995v1, 2012.
  • J. Nelson, E. Price and M. Wootters. New constructions of RIP matrices with fast multiplication and fewer rows. arXiv:1211.0986v1, 2012.
  • A. Drucker. Nondeterministic Direct Product Reducations and the Success Probability of SAT Solvers. May 16th, 2013 [Preliminary version]