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?

Mechanisms With Costly Knowledge

On the Computational Complexity of Optimal Simple Mechanisms

SESSION: Session 2

Permanent v. Determinant: An Exponential Lower Bound Assuming Symmetry

On Hardness of Approximating the Parameterized Clique Problem

The Complexity of DNF of Parities

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions

SESSION: Session 3

Local Algorithms for Block Models with Side Information

Distribution Design

Sampling Correctors

On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

SESSION: Session 4

Strategic Classification

A PAC Approach to Application-Specific Algorithm Selection

An Axiomatic Approach to Community Detection

SESSION: Session 5

Obfuscating Conjunctions under Entropic Ring LWE

Secure Multiparty Computation with General Interaction Patterns

Fully Succinct Garbled RAM

Cryptography for Parallel RAM from Indistinguishability Obfuscation

SESSION: Session 6

Timeability of Extensive-Form Games

Auction Revenue in the General Spiteful-Utility Model

How to Incentivize Data-Driven Collaboration Among Competing Parties

From Nash Equilibria to Chain Recurrent Sets: Solution Concepts and Topology

SESSION: Session 7

Rational Proofs with Multiple Provers

Lower Bounds: From Circuits to QBF Proof Systems

Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

The Space "Just Above" BQP

SESSION: Session 8

Coordination Complexity: Small Information Coordinating Large Populations

On a Natural Dynamics for Linear Programming

On the Space Complexity of Linear Programming with Preprocessing

SESSION: Session 9

Spectral Embedding of k-Cliques, Graph Partitioning and k-Means

On Sketching Quadratic Forms

Energy-Efficient Algorithms

SESSION: Session 10

How To Bootstrap Anonymous Communication

Time-Lock Puzzles from Randomized Encodings

Is There an Oblivious RAM Lower Bound?

Simultaneous Private Learning of Multiple Concepts

SESSION: Session 11

Information Complexity Density and Simulation of Protocols

Satisfiability on Mixed Instances

On the Computational Complexity of Limit Cycles in Dynamical Systems

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds