ITCS 2016 : List of Accepted Papers

  1. Sampling Correctors. Clément Canonne (Columbia University); Themis Gouleakis (MIT); Ronitt Rubinfeld (MIT & Tel Aviv)
  2. Strategic Classification. Moritz Hardt (Google Research); Nimrod Megiddo (IBM Almaden); Christos Papadimitriou (Berkeley); Mary Wootters (CMU)
  3. Can Almost Everybody be Almost Happy?\\ PCP for PPAD and the Inapproximability of Nash. Yakov Babichenko (Technion); Christos Papadimitriou (UC Berkeley); Aviad Rubinstein (UC Berkeley)
  4. On Being Far from Far and on Dual Problems in Property Testing. Roei Tell (Weizmann)
  5. On Hardness of Approximating the Parameterized Clique Problem. Subhash Khot (NYU); Igor Shinkar (NYU)
  6. The Complexity of DNF of Parities. Gil Cohen (Caltech); Igor Shinkar (NYU)
  7. Permanent v. Determinant: An exponential lower bound assuming symmetry. J.M. Landsberg (Texas A&M); Nicolas Ressayre (University of Lyon I)
  8. On the Computational Complexity of Optimal Simple Mechanisms. Aviad Rubinstein (UC Berkeley)
  9. Timeability of Extensive-Form Games. Sune K. Jakobsen (Queen Mary U.; London); Troels B. Sørensen (IT-University of Copenhagen); Vincent Conitzer (Duke University)
  10. Smooth Boolean functions are easy: efficient algorithms for low sensitivity functions. Parikshit Gopalan (Microsoft Research); Noam Nisan (Hebrew U. & Microsoft Research); Rocco Servedio (Columbia); Kunal Talwar (Google Research); Avi Wigderson (IAS)
  11. The space "just above" BQP. Scott Aaronson (MIT); Adam Bouland (MIT); Joseph Fitzsimons (Singapore U. Tech. and Design & National U. Singapore); Mitchell Lee (MIT)
  12. Lower bounds: from circuits to QBF proof systems. Olaf Beyersdorff (University of Leeds); Ilario Bonacina (Sapienza University Rome); Leroy Chew (University of Leeds)
  13. Auction Revenue in the General Spiteful-Utility Model. Jing Chen (Stony Brook); Silvio Micali (MIT)
  14. Mechanisms With Costly Knowledge. Atalay M. Ileri (MIT); Silvio Micali (MIT)
  15. How to Bootstrap Anonymous Communication. Sune K. Jakobsen (Queen Mary U., London); Claudio Orlandi (Aarhus U.)
  16. Rational Proofs with Multiple Provers. Jing Chen (Stony Brook); Samuel McCauley (Stony Brook); Shikha Singh (Stony Brook)
  17. Time-Lock Puzzles from Randomized Encodings. Nir Bitansky (MIT); Shafi Goldwasser (MIT & Weizmann); Abhishek Jain (Johns Hopkins); Omer Paneth (Boston U.); Vinod Vaikuntanathan (MIT)
  18. Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility. Marco L. Carmosino (UCSD); Jiawei Gao (UCSD); Russell Impagliazzo (UCSD); Ivan Mikhailin (UCSD); Ramamohan Paturi (UCSD); Stefan Schneider (UCSD)
  19. Simultaneous Private Learning of Multiple Concepts. Mark Bun (Harvard University); Kobbi Nissim (Ben-Gurion & Harvard); Uri Stemmer (Ben-Gurion University)
  20. An Axiomatic Approach to Community Detection. Christian Borgs (Microsoft Research); Jennifer Chayes (Microsoft Research); Adrian Marple (Stanford); Shang-Hua Teng (USC)
  21. Local Algorithms for Block Models with Side Information. Elchanan Mossel (U. Penn & Berkeley); Jiaming Xu (U. Penn)
  22. On the Space Complexity of Linear Programming with Preprocessing. Yael Tauman Kalai (Microsoft Research); Ran Raz (Weizmann & IAS); Oded Regev (NYU)
  23. Spectral Embedding of k-Cliques; Graph Partitioning and k-Means. Pranjal Awasthi (Princeton); Moses Charikar (Princeton); Ravishankar Krishnaswamy (Microsoft Research); Ali Kemal Sinop (UC Berkeley)
  24. On the Computational Complexity of Limit Cycles in Dynamical Systems. Christos H. Papadimitriou (Berkeley); Nisheeth K. Vishnoi (EPFL)
  25. On Sketching Quadratic Forms. Alexandr Andoni (Columbia); Jiecao Chen (Indiana U. Bloomington); Robert Krauthgamer (Weizmann); Bo Qin (HKUST); David P. Woodruff (IBM Almaden); Qin Zhang (Indiana U. Bloomington)
  26. Information Complexity Density and Simulation of Protocols. Himanshu Tyagi (IISc.); Shaileshh Venkatakrishnan (UIUC); Pramod Viswanath (UIUC); Shun Watanabe (Tokyo U. Agriculture & Tech.)
  27. Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds. Alexander Golovnev (NYU); Alexander S. Kulikov (Steklov Institute; St. Petersburg)
  28. Energy-Efficient Algorithms. Erik D. Demaine (MIT); Geronimo J. Mirano (MIT); Jayson Lynch (MIT); Nirvan Tyagi (MIT)
  29. From Nash equilibria to chain recurrent sets: Solution concepts and topology. Christos H. Papadimitriou (Berkeley); Georgios Piliouras (Singapore U. Tech. & Design)
  30. How to Incentivize Data-Driven Collaboration Among Competing Parties. Pablo Daniel Azar (MIT); Shafi Goldwasser (MIT & Weizmann); Sunoo Park (MIT)
  31. Distribution Design. Amos Beimel (Ben Gurion); Ariel Gabizon (Technion); Yuval Ishai (Technion & UCLA); Eyal Kushilevitz (Technion)
  32. Secure Multiparty Computation with General Interaction Patterns. Shai Halevi (IBM Research); Yuval Ishai (Technion); Abhishek Jain (Johns Hopkins); Eyal Kushilevitz (Technion); Tal Rabin (IBM Research)
  33. Is There an Oblivious RAM Lower Bound? Elette Boyle (IDC Herzliya); Moni Naor (Weizmann)
  34. On a Natural Dynamics for Linear Programming. Damian Straszak (EPFL); Nisheeth K. Vishnoi (EPFL)
  35. Obfuscating Conjunctions under Entropic Ring LWE. Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT); Hoeteck Wee (ENS); Daniel Wichs (Northeastern)
  36. Fully Succinct Garbled RAM. Ran Canetti (Boston U. & Tel Aviv); Justin Holmgren (MIT)
  37. A PAC Approach to Application-Specific Algorithm Selection. Rishi Gupta (Stanford); Tim Roughgarden (Stanford)
  38. Coordination Complexity: Small Information Coordinating Large Populations. Rachel Cummings (Caltech); Katrina Ligett (Caltech); Jaikumar Radhakrishnan (TIFR); Aaron Roth (U. Penn.); Zhiwei Steven Wu (U. Penn)
  39. Satisfiability on Mixed Instances. Ruiwen Chen (U. Edinburgh); Rahul Santhanam (U. Edinburgh)
  40. Cryptography for Parallel RAM from Indistinguishability Obfuscation. Yu-Chi Chen (Academia Sinica); Sherman S.M. Chow (Chinese University of Hong Kong); Kai-Min Chung (Academia Sinica); Russell W.F. Lai (Chinese University of Hong Kong); Wei-Kai Lin (Academia Sinica)