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


Benny said...

Our paper (Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?) is available in my home page

Thanks for collecting the pdfs.


Shiva Kintali said...

Thanks Benny. I added a link to your paper.

Noam said...

Here is a link to my paper ("On the Construction of One-Way Functions from Average-Case Hardness"):

Noam Livne

Shiva Kintali said...

Thanks Noam. I added a link to your paper.

Anonymous said...

Better be the head of a dog than the tail of a lion.