List of Accepted Papers

The following is a preliminary list of the papers accepted to ICS2010.  A list of the papers with abstracts may be found here.

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