ITCS 2014 Accepted Papers
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
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
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
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 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
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 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
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
Erez Druk and Yuval Ishai. Linear-Time Encodable Codes Meeting the Gilbert-Varshamov Bound and Their Cryptographic Applications