ITCS 2016 : List of Accepted Papers
-
Sampling Correctors.
Clément Canonne (Columbia University); Themis Gouleakis (MIT); Ronitt Rubinfeld (MIT & Tel Aviv)
-
Strategic Classification.
Moritz Hardt (Google Research); Nimrod Megiddo (IBM Almaden); Christos Papadimitriou (Berkeley); Mary Wootters (CMU)
-
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)
-
On Being Far from Far and on Dual Problems in Property Testing.
Roei Tell (Weizmann)
-
On Hardness of Approximating the Parameterized Clique Problem.
Subhash Khot (NYU); Igor Shinkar (NYU)
-
The Complexity of DNF of Parities.
Gil Cohen (Caltech); Igor Shinkar (NYU)
-
Permanent v. Determinant: An exponential lower bound assuming symmetry.
J.M. Landsberg (Texas A&M); Nicolas Ressayre (University of Lyon I)
-
On the Computational Complexity of Optimal Simple Mechanisms.
Aviad Rubinstein (UC Berkeley)
-
Timeability of Extensive-Form Games.
Sune K. Jakobsen (Queen Mary U.; London); Troels B. Sørensen (IT-University of Copenhagen); Vincent Conitzer (Duke University)
-
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)
-
The space "just above" BQP.
Scott Aaronson (MIT); Adam Bouland (MIT); Joseph Fitzsimons (Singapore U. Tech. and Design & National U. Singapore); Mitchell Lee (MIT)
-
Lower bounds: from circuits to QBF proof systems.
Olaf Beyersdorff (University of Leeds); Ilario Bonacina (Sapienza University Rome); Leroy Chew (University of Leeds)
-
Auction Revenue in the General Spiteful-Utility Model.
Jing Chen (Stony Brook); Silvio Micali (MIT)
-
Mechanisms With Costly Knowledge.
Atalay M. Ileri (MIT); Silvio Micali (MIT)
-
How to Bootstrap Anonymous Communication.
Sune K. Jakobsen (Queen Mary U., London); Claudio Orlandi (Aarhus U.)
-
Rational Proofs with Multiple Provers.
Jing Chen (Stony Brook); Samuel McCauley (Stony Brook); Shikha Singh (Stony Brook)
-
Time-Lock Puzzles from Randomized Encodings.
Nir Bitansky (MIT); Shafi Goldwasser (MIT & Weizmann); Abhishek Jain (Johns Hopkins); Omer Paneth (Boston U.); Vinod Vaikuntanathan (MIT)
-
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)
-
Simultaneous Private Learning of Multiple Concepts.
Mark Bun (Harvard University); Kobbi Nissim (Ben-Gurion & Harvard); Uri Stemmer (Ben-Gurion University)
-
An Axiomatic Approach to Community Detection.
Christian Borgs (Microsoft Research); Jennifer Chayes (Microsoft Research); Adrian Marple (Stanford); Shang-Hua Teng (USC)
-
Local Algorithms for Block Models with Side Information.
Elchanan Mossel (U. Penn & Berkeley); Jiaming Xu (U. Penn)
-
On the Space Complexity of Linear Programming with Preprocessing.
Yael Tauman Kalai (Microsoft Research); Ran Raz (Weizmann & IAS); Oded Regev (NYU)
-
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)
-
On the Computational Complexity of Limit Cycles in Dynamical Systems.
Christos H. Papadimitriou (Berkeley); Nisheeth K. Vishnoi (EPFL)
-
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)
-
Information Complexity Density and Simulation of Protocols.
Himanshu Tyagi (IISc.); Shaileshh Venkatakrishnan (UIUC); Pramod Viswanath (UIUC); Shun Watanabe (Tokyo U. Agriculture & Tech.)
-
Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.
Alexander Golovnev (NYU); Alexander S. Kulikov (Steklov Institute; St. Petersburg)
-
Energy-Efficient Algorithms.
Erik D. Demaine (MIT); Geronimo J. Mirano (MIT); Jayson Lynch (MIT); Nirvan Tyagi (MIT)
-
From Nash equilibria to chain recurrent sets: Solution concepts and topology.
Christos H. Papadimitriou (Berkeley); Georgios Piliouras (Singapore U. Tech. & Design)
-
How to Incentivize Data-Driven Collaboration Among Competing Parties.
Pablo Daniel Azar (MIT); Shafi Goldwasser (MIT & Weizmann); Sunoo Park (MIT)
-
Distribution Design.
Amos Beimel (Ben Gurion); Ariel Gabizon (Technion); Yuval Ishai (Technion & UCLA); Eyal Kushilevitz (Technion)
-
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)
-
Is There an Oblivious RAM Lower Bound?
Elette Boyle (IDC Herzliya); Moni Naor (Weizmann)
-
On a Natural Dynamics for Linear Programming.
Damian Straszak (EPFL); Nisheeth K. Vishnoi (EPFL)
-
Obfuscating Conjunctions under Entropic Ring LWE.
Zvika Brakerski (Weizmann); Vinod Vaikuntanathan (MIT); Hoeteck Wee (ENS); Daniel Wichs (Northeastern)
-
Fully Succinct Garbled RAM.
Ran Canetti (Boston U. & Tel Aviv); Justin Holmgren (MIT)
-
A PAC Approach to Application-Specific Algorithm Selection.
Rishi Gupta (Stanford); Tim Roughgarden (Stanford)
-
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)
-
Satisfiability on Mixed Instances.
Ruiwen Chen (U. Edinburgh); Rahul Santhanam (U. Edinburgh)
-
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)