List of Accepted Papers

A list of the papers with abstracts may be found here.

In order of submission. (39 papers)

• Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature? [PDF]
  Benny Applebaum, Yuval Ishai and Eyal Kushilevitz
  
  
• Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol [PDF]
  Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan Kelner, Avinatan Hassidim and Peter Shor
  
  
• Analytical Tools for Natural Algorithms [PDF]
  Bernard Chazelle
  
  
• A New Approach to Strongly Polynomial Linear Programming [PDF]
  Mihály Bárász and Santosh Vempala
  
  
• Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract) [PDF]
  Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge
  
  
• Pan-Private Streaming Algorithms [PDF]
  Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum and Sergey Yekhanin
  
  
• Robustly Leveraging Collusion in Combinatorial Auctions [PDF]
  Jing Chen, Silvio Micali and Paul Valiant
  
  
• Robust Perfect Revenue From Perfectly Informed Players [PDF]
  Jing Chen, Avinatan Hassidim and Silvio Micali
  
  
• Playing Games without Observing Payoffs [PDF]
  Michal Feldman, Adam Kalai and Moshe Tennenholtz
  
  
• Adversarial Leakage in Games [PDF]
  Noga Alon, Yuval Emek, Michal Feldman and Moshe Tennenholtz
  
  
• Game Theory with Costly Computation: Formulation and Application to Protocol Security [PDF]
  Joseph Y. Halpern and Rafael Pass
  
  
• Bounding Rationality by Discounting Time [PDF]
  Lance Fortnow and Rahul Santhanam
  
  
• Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities [PDF]
  Vijay V. Vazirani and Mihalis Yannakakis
  
  
• Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions [PDF]
  Brendan Lucier
  
  
• A New Look at Selfish Routing [PDF]
  Christos Papadimitriou and Gregory Valiant
  
  
• Local Algorithms for Finding Interesting Individuals in Large Networks [PDF]
  Mickey Brautbar and Michael Kearns
  
  
• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior [PDF]
  Maria-Florina Balcan and Avrim Blum and Yishay Mansour
  
  
• Reaching Consensus on Social Networks [PDF]
  Elchanan Mossel and Grant Schoenebeck
  
  
• Robustness of the Learning with Errors Assumption [PDF]
  Shafi Goldwasser, Yael Kalai, Chris Peikert and Vinod Vaikuntanathan
  
  
• Distribution-Specific Agnostic Boosting [PDF]
  Vitaly Feldman
  
  
• Space-Efficient Estimation of Robust Statistics and Distribution Testing [PDF]
  Steve Chien, Katrina Ligett and Andrew McGregor
  
  
• Cryptographic Complexity Classes and Computational Intractability Assumptions [PDF]
  Hemanta K. Maji, Manoj Prabhakaran and Mike Rosulek
  
  
• Hard Instances for Satisfiability and Quasi-one-way Functions [PDF]
  Andrej Bogdanov, Kunal Talwar and Andrew Wan
  
  
• On the Construction of One-Way Functions from Average Case Hardness [PDF]
  Noam Livne
  
  
• Proof-Carrying Data and Hearsay Arguments from Signature Cards [PDF]
  Alessandro Chiesa and Eran Tromer
  
  
• Are Stable Instances Easy? [PDF]
  Yonatan Bilu and Nathan Linial
  
  
• A New Approximation Technique for Resource-Allocation Problems [PDF]
  Barna Saha and Aravind Srinivasan
  
  
• Global Alignment of Molecular Sequences via Ancestral State Reconstruction [PDF]
  Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch
  
  
• Effectively Polynomial Simulations [PDF]
  Toniann Pitassi and Rahul Santhanam
  
  
• Circuit Lower Bounds, Help Functions, and the Remote Point Problem [PDF]
  V. Arvind and Srikanth Srinivasan
  
  
• Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction [PDF]
  Ariel Gabizon and Avinatan Hassidim
  
  
• Symmetric LDPC Codes and Local Testing [PDF]
  Tali Kaufman and Avi Wigderson
  
  
• Weight Distribution and List-Decoding Size of Reed-Muller Codes [PDF]
  Tali Kaufman, Shachar Lovett and Ely Porat
  
  
• Non-Malleable Codes [PDF]
  Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs
  
  
• Interactive Proofs For Quantum Computations [PDF]
  Dorit Aharonov, Michael Ben-Or and Elad Eban
  
  
• On the Power of a Unique Quantum Witness [PDF]
  Rahul Jain, Iordanis Kerenidis,Greg Kuperberg, Miklos Santha, Or Sattath and Shengyu Zhang
  
  
• Bounds on the Quantum Satisfiability Threshold [PDF]
  Sergey Bravyi, Cristopher Moore and Alexander Russell
  
  
• Memory Consistency Conditions for Self-Assembly Programming [PDF]
  Aaron Sterling
  
  
• Cache Replacement Policies for Multicore Processors [PDF]
  Avinatan Hassidim