ITCS 2014 Accepted Papers

David Gamarnik and Madhu Sudan. Limits of local algorithms over sparse random graphs
Yossi Azar, Uriel Feige, Michal Feldman and Moshe Tennenholtz. Sequential Decision Making with Vector Outcomes
Tali Kaufman and Alexander Lubotzky. High Dimensional Expanders and Property Testing
Elad Haramaty and Madhu Sudan. Deterministic Compression with Uncertain Priors
Kazuo Iwama and Yuichi Yoshida. Parameterized Testability
Nader Bshouty. Testers and their Applications
Uriel Feige and Moshe Tennenholtz. Invitation games and the price of stability
Amir Shpilka, Avishay Tal and Ben Lee Volk. On the Structure of Boolean Functions with Small Spectral Norm
Fernando Brandao, Aram Harrow, James Lee and Yuval Peres. Adversarial hypothesis testing and a quantum Stein's Lemma for restricted measurements
Ran Gelles, Amit Sahai and Akshay Wadia. Private Interactive Communication Across an Adversarial Channel
Venkatesan Guruswami and Euiwoong Lee. Complexity of approximating CSP with Balance / Hard Constraints
Sayan Bhattacharya, Sungjin Im, Janardhan Kulkarni and Kamesh Munagala. Coordination Mechanisms from (almost) all Scheduling Policies
Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman and Andrew Wan. Faster Private Release of Marginals on Small Databases
Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff. Direct Sum Fails for Zero Error Average Communication
Karthekeyan Chandrasekaran and Santosh Vempala. Integer Feasibility of Random Polytopes
Mark Braverman, Jing Chen and Sampath Kannan. Optimal Provision-After-Wait in Healthcare
Mark Braverman and Kanika Pasricha. The computational hardness of pricing compound options
Pavel Hrubes and Avi Wigderson. Non-commutative arithmetic circuits with division
Manor Mendel and Assaf Naor. Expanders with respect to Hadamard spaces and random graphs
Elaine Angelino and Varun Kanade. Attribute-Efficient Evolvability of Sparse Linear Functions
Zeph Landau, Umesh Vazirani and Thomas Vidick. A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Umesh Vazirani and Thomas Vidick. Fully device independent quantum key distribution
Eldar Fischer, Oded Lachish and Yonatan Goldhirsh. Partial tests, universal tests and decomposability
Jonathan Berry, Luke Fostvedt, Daniel Nordman, Cynthia Phillips, C. Seshadhri and Alyson Wilson. Why do simple algorithms for triangle enumeration work in the real world?
Cristopher Moore and Leonard Schulman. Tree Codes and a Conjecture on Exponential Sums
Mohammad Mahmoody, Hemanta Maji and Manoj Prabhakaran. Limits of Random Oracles in Secure Computation
Yuval Rabani, Leonard Schulman and Chaitanya Swamy. Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
Rishi Gupta, Tim Roughgarden and C. Seshadhri. Decompositions of Triangle-Dense Graphs
Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs and Michele Scquizzato. Energy-Efficient Circuit Design
Yuichi Yoshida and Yuan Zhou. Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems
Zvika Brakerski and Guy Rothblum. Black-Box Obfuscation for d-CNFs
Laszlo Babai. On the Automorphism Groups of Strongly Regular Graphs
Mahdi Cheraghchi and Venkatesan Guruswami. Capacity of Non-Malleable Codes
Parikshit Gopalan, Salil Vadhan and Yuan Zhou. Locally Testable Codes and Cayley Graphs
Yi-Kai Liu. Building one-time memories from isolated qubits
Michael Kearns, Mallesh Pai, Aaron Roth and Jonathan Ullman. Mechanism Design in Large Games: Incentives and Privacy
David Xiao, Kobbi Nissim and Salil Vadhan. Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals
Joseph Y. Halpern, Rafael Pass and Lior Seeman. The Truth Behind the Myth of the Folk Theorem
Joshua Brody, Dominik Scheder, Sune Jakobsen and Peter Winkler. Cryptogenography
Afonso S. Bandeira, Moses Charikar, Amit Singer and Andy Zhu. Multireference Alignment using Semidefinite Programming
Eric Miles. Iterated group products and leakage resilience against NC^1
Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath and Alon Rosen. Candidate weak pseudorandom functions in AC0 o MOD2
Siyao Guo, Pavel Hubacek, Alon Rosen and Margarita Vald. Rational Arguments: Single Round Delegation with Sublinear Verification
Zvika Brakerski and Vinod Vaikuntanathan. Lattice-Based FHE as Secure as PKE
Andrew Wan, John Wright and Chenggang Wu. Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture
Deeparnab Chakrabarty and Chaitanya Swamy. Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences
Erez Druk and Yuval Ishai. Linear-Time Encodable Codes Meeting the Gilbert-Varshamov Bound and Their Cryptographic Applications
Ho-Lin Chen, David Doty and David Soloveichik. Rate-independent computation in mass-action chemical reaction networks