default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID7th ITCS 2016: Cambridge, MA, USA
- Madhu Sudan:
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016. ACM 2016, ISBN 978-1-4503-4057-1
Session 1
- Yakov Babichenko, Christos H. Papadimitriou, Aviad Rubinstein:
Can Almost Everybody be Almost Happy? 1-9 - Atalay Mert Ileri
, Silvio Micali:
Mechanisms With Costly Knowledge. 11-19 - Aviad Rubinstein:
On the Computational Complexity of Optimal Simple Mechanisms. 21-28
Session 2
- Joseph M. Landsberg, Nicolas Ressayre:
Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry. 29-35 - Subhash Khot, Igor Shinkar:
On Hardness of Approximating the Parameterized Clique Problem. 37-45 - Gil Cohen, Igor Shinkar:
The Complexity of DNF of Parities. 47-58 - Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson:
Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. 59-70
Session 3
- Elchanan Mossel, Jiaming Xu:
Local Algorithms for Block Models with Side Information. 71-80 - Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz:
Distribution Design. 81-92 - Clément L. Canonne, Themis Gouleakis, Ronitt Rubinfeld:
Sampling Correctors. 93-102 - Roei Tell:
On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]. 103-110
Session 4
- Moritz Hardt, Nimrod Megiddo, Christos H. Papadimitriou, Mary Wootters:
Strategic Classification. 111-122 - Rishi Gupta, Tim Roughgarden:
A PAC Approach to Application-Specific Algorithm Selection. 123-134 - Christian Borgs, Jennifer T. Chayes, Adrian Marple, Shang-Hua Teng:
An Axiomatic Approach to Community Detection. 135-146
Session 5
- Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs:
Obfuscating Conjunctions under Entropic Ring LWE. 147-156 - Shai Halevi, Yuval Ishai, Abhishek Jain, Eyal Kushilevitz, Tal Rabin:
Secure Multiparty Computation with General Interaction Patterns. 157-168 - Ran Canetti, Justin Holmgren:
Fully Succinct Garbled RAM. 169-178 - Yu-Chi Chen, Sherman S. M. Chow, Kai-Min Chung, Russell W. F. Lai, Wei-Kai Lin, Hong-Sheng Zhou:
Cryptography for Parallel RAM from Indistinguishability Obfuscation. 179-190
Session 6
- Sune K. Jakobsen, Troels Bjerre Sørensen, Vincent Conitzer:
Timeability of Extensive-Form Games. 191-199 - Jing Chen, Silvio Micali:
Auction Revenue in the General Spiteful-Utility Model. 201-211 - Pablo Daniel Azar, Shafi Goldwasser, Sunoo Park:
How to Incentivize Data-Driven Collaboration Among Competing Parties. 213-225 - Christos H. Papadimitriou, Georgios Piliouras:
From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology. 227-235
Session 7
- Jing Chen, Samuel McCauley, Shikha Singh:
Rational Proofs with Multiple Provers. 237-248 - Olaf Beyersdorff, Ilario Bonacina, Leroy Chew:
Lower Bounds: From Circuits to QBF Proof Systems. 249-260 - Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider:
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. 261-270 - Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The Space "Just Above" BQP. 271-280
Session 8
- Rachel Cummings, Katrina Ligett, Jaikumar Radhakrishnan, Aaron Roth, Zhiwei Steven Wu:
Coordination Complexity: Small Information Coordinating Large Populations. 281-290 - Damian Straszak, Nisheeth K. Vishnoi:
On a Natural Dynamics for Linear Programming. 291 - Yael Tauman Kalai, Ran Raz, Oded Regev:
On the Space Complexity of Linear Programming with Preprocessing. 293-300
Session 9
- Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, Ali Kemal Sinop:
Spectral Embedding of k-Cliques, Graph Partitioning and k-Means. 301-310 - Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. 311-319 - Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi:
Energy-Efficient Algorithms. 321-332
Session 10
- Sune K. Jakobsen, Claudio Orlandi:
How To Bootstrap Anonymous Communication. 333-344 - Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, Brent Waters:
Time-Lock Puzzles from Randomized Encodings. 345-356 - Elette Boyle, Moni Naor:
Is There an Oblivious RAM Lower Bound? 357-368 - Mark Bun, Kobbi Nissim, Uri Stemmer:
Simultaneous Private Learning of Multiple Concepts. 369-380
Session 11
- Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath, Shun Watanabe:
Information Complexity Density and Simulation of Protocols. 381-391 - Ruiwen Chen, Rahul Santhanam:
Satisfiability on Mixed Instances. 393-402 - Christos H. Papadimitriou, Nisheeth K. Vishnoi:
On the Computational Complexity of Limit Cycles in Dynamical Systems. 403 - Alexander Golovnev, Alexander S. Kulikov:
Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds. 405-411
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-10 18:41 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
