ICS 2010 Accepted Papers (with pdf files)

ICS 2010 accepted paper list is here. List with abstracts is here. Following is a list with links to pdf files. Please leave a comment if I missed any pdf files. If you haven't uploaded your accepted paper on your homepages/arXiv/ECCC please do so. As and when I find new files on the internet, I will update them here.

Update : Slides of the talks are available online.

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