ITCS '16- Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
Full Citation in the ACM Digital Library
SESSION: Session 1
Can Almost Everybody be Almost Happy?
Yakov Babichenko
Christos Papadimitriou
Aviad Rubinstein
Mechanisms With Costly Knowledge
Atalay M. Ileri
Silvio Micali
On the Computational Complexity of Optimal Simple Mechanisms
Aviad Rubinstein
SESSION: Session 2
Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry
Joseph M. Landsberg
Nicolas Ressayre
On Hardness of Approximating the Parameterized Clique Problem
Subhash Khot
Igor Shinkar
The Complexity of DNF of Parities
Gil Cohen
Igor Shinkar
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions
Parikshit Gopalan
Noam Nisan
Rocco A. Servedio
Kunal Talwar
Avi Wigderson
SESSION: Session 3
Local Algorithms for Block Models with Side Information
Elchanan Mossel
Jiaming Xu
Distribution Design
Amos Beimel
Ariel Gabizon
Yuval Ishai
Eyal Kushilevitz
Sampling Correctors
Clement L. Canonne
Themis Gouleakis
Ronitt Rubinfeld
On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]
Roei Tell
SESSION: Session 4
Strategic Classification
Moritz Hardt
Nimrod Megiddo
Christos Papadimitriou
Mary Wootters
A PAC Approach to Application-Specific Algorithm Selection
Rishi Gupta
Tim Roughgarden
An Axiomatic Approach to Community Detection
Christian Borgs
Jennifer Chayes
Adrian Marple
Shang-Hua Teng
SESSION: Session 5
Obfuscating Conjunctions under Entropic Ring LWE
Zvika Brakerski
Vinod Vaikuntanathan
Hoeteck Wee
Daniel Wichs
Secure Multiparty Computation with General Interaction Patterns
Shai Halevi
Yuval Ishai
Abhishek Jain
Eyal Kushilevitz
Tal Rabin
Fully Succinct Garbled RAM
Ran Canetti
Justin Holmgren
Cryptography for Parallel RAM from Indistinguishability Obfuscation
Yu-Chi Chen
Sherman S.M. Chow
Kai-Min Chung
Russell W.F. Lai
Wei-Kai Lin
Hong-Sheng Zhou
SESSION: Session 6
Timeability of Extensive-Form Games
Sune K. Jakobsen
Troels B. Sørensen
Vincent Conitzer
Auction Revenue in the General Spiteful-Utility Model
Jing Chen
Silvio Micali
How to Incentivize Data-Driven Collaboration Among Competing Parties
Pablo Daniel Azar
Shafi Goldwasser
Sunoo Park
From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology
Christos Papadimitriou
Georgios Piliouras
SESSION: Session 7
Rational Proofs with Multiple Provers
Jing Chen
Samuel McCauley
Shikha Singh
Lower Bounds: From Circuits to QBF Proof Systems
Olaf Beyersdorff
Ilario Bonacina
Chew Leroy
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
Marco L. Carmosino
Jiawei Gao
Russell Impagliazzo
Ivan Mihajlin
Ramamohan Paturi
Stefan Schneider
The Space "Just Above" BQP
Scott Aaronson
Adam Bouland
Joseph Fitzsimons
Mitchell Lee
SESSION: Session 8
Coordination Complexity: Small Information Coordinating Large Populations
Rachel Cummings
Katrina Ligett
Jaikumar Radhakrishnan
Aaron Roth
Zhiwei Steven Wu
On a Natural Dynamics for Linear Programming
Damian Straszak
Nisheeth K. Vishnoi
On the Space Complexity of Linear Programming with Preprocessing
Yael Tauman Kalai
Ran Raz
Oded Regev
SESSION: Session 9
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means
Pranjal Awasthi
Moses Charikar
Ravishankar Krishnaswamy
Ali Kemal Sinop
On Sketching Quadratic Forms
Alexandr Andoni
Jiecao Chen
Robert Krauthgamer
Bo Qin
David P. Woodruff
Qin Zhang
Energy-Efficient Algorithms
Erik D. Demaine
Jayson Lynch
Geronimo J. Mirano
Nirvan Tyagi
SESSION: Session 10
How To Bootstrap Anonymous Communication
Sune K. Jakobsen
Claudio Orlandi
Time-Lock Puzzles from Randomized Encodings
Nir Bitansky
Shafi Goldwasser
Abhishek Jain
Omer Paneth
Vinod Vaikuntanathan
Brent Waters
Is There an Oblivious RAM Lower Bound?
Elette Boyle
Moni Naor
Simultaneous Private Learning of Multiple Concepts
Mark Bun
Kobbi Nissim
Uri Stemmer
SESSION: Session 11
Information Complexity Density and Simulation of Protocols
Himanshu Tyagi
Shaileshh Venkatakrishnan
Pramod Viswanath
Shun Watanabe
Satisfiability on Mixed Instances
Ruiwen Chen
Rahul Santhanam
On the Computational Complexity of Limit Cycles in Dynamical Systems
Christos H. Papadimitriou
Nisheeth K. Vishnoi
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds
Alexander Golovnev
Alexander S. Kulikov