Monday, November 02, 2009

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