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.

• Are Stable Instances Easy? [pdf]
  Yonatan Bilu and Nathan Linial
  
  
• On the Construction of One-Way Functions from Average Case Hardness
  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
  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
  Steve Chien; Katrina Ligett; Andrew McGregor
  
  
• Hard instances for satsifiability and quasi-one-way functions
  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
  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
  Vijay V. Vazirani and Mihalis Yannakakis
  
  
• Breaking and making quantum money
  Scott Aaronson, Edward Farhi, David Gosset, Jonathan Kelner, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor
  
  
• Non-Malleable Codes
  Stefan Dziembowski and Krzysztof Pietrzak and Daniel Wichs
  
  
• Bounding Rationality by Discounting Time
  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
  Shafi Goldwasser, Yael Kalai, Chris Peikert, Vinod Vaikuntanathan
  
  
• Local Algorithms for Finding Interesting Individuals in Large Networks
  Mickey Brautbar and Michael Kearns
  
  
• Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?
  Benny Applebaum and Yuval Ishai and Eyal Kushilevitz
  
  
• A New Approximation Technique for Resource-Allocation Problems
  Barna Saha, Aravind Srinivasan
  
  
• Analytical Tools for Natural Algorithms
  Bernard Chazelle
  
  
• Effectively Polynomial Simulations [pptx]
  Toniann Pitassi and Rahul Santhanam
  
  
• Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior
  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
  Hemanta K. Maji (1), Manoj Prabhakaran (1), Mike Rosulek (2)
  
  
• Cache Replacement Policies for Multicore Processors [pdf]
  Avinatan Hassidim
  
  
• Pan-Private Streaming Algorithms
  Cynthia Dwork Moni Naor Toni Pitassi Guy Rothblum Sergey Yekhanin
  
  
• Reaching Consensus on Social Networks
  Elchanan Mossel and Grant Schoenebeck
  
  
• Proof-Carrying Data and Hearsay from Signature Cards
  Alessandro Chiesa, Eran Tromer
  
  
• Global Alignment of Molecular Sequences via Ancestral State Reconstruction
  Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim, Sebastien Roch

SODA 2010 accepted papers

SODA 2010 accepted papers list is here.
Here is a list with abstracts.

FOCS 2009 Accepted Papers (with pdf files)

FOCS 2009 accepted paper list is here. List with abstracts is here. Following is a list with links to pdf files. Leave a comment if I missed any pdf files. If you haven't uploaded your accepted paper on your homepages please do so.

• Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions [pdf]
  Zeev Nutov.

• Randomized Self-Assembly for Exact Shapes [pdf]
  David Doty.

• Symmetry and approximability of submodular maximization problems [pdf]
  Jan Vondrak.

• Fully Dynamic $(2 + \eps)$ Approximate All-Pairs Shortest Paths with $O(\log \log n)$ Query and Close to Linear Update Time
  Aaron Bernstein.

• Bounded Independence Fools Halfspaces [pdf]
  Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola.

• A Parallel Repetition Theorem for Any Interactive Argument [pdf]
  Iftach Haitner.

• Two-message quantum interactive proofs are in PSPACE [arXiv]
  Rahul Jain, Sarvagya Upadhyay and John Watrous.

• Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers [pdf]
  Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan.

• Optimal Long Code Test with One Free Bit [ps]
  Nikhil Bansal and Subhash Khot.

• Combinatorial PCPs with efficient verifiers [pdf] [summary]
  Or Meir.

• A $(\log n)^{\Omega(1)}$ integrality gap for the Sparsest Cut SDP [arXiv]
  Jeff Cheeger, Bruce Kleiner and Assaf Naor.

• Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
  Ben Reichardt. [arXiv]
  

• Multiparty Communication Complexity and Threshold Circuit Complexity of AC^0
  Dang-Trinh Huynh-Ngoc and Paul Beame. [pdf]
  

• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP [pdf]
  Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi and Howard Karloff.

• Delaunay Triangulations in O(sort(n)) and Other Transdichotomous and Hereditary Algorithms in Computational Geometry [pdf] [summary]
  Kevin Buchin and Wolfgang Mulzer.

• Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
  Saugata Basu and Thierry Zell. [arXiv]

• Learning Decision Trees From Random Examples: a Smoothed Analysis [pdf]
  Adam Kalai, Shang-Hua Teng and Alex Samorodnitsky.

• A Complete Characterization of Statistical Query Learning with Applications to Evolvability [pdf]
  Vitaly Feldman.

• Optimal quantum strong coin flipping [arXiv]
  André Chailloux and Iordanis Kerenidis.

• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size [pdf]
  Ankur Moitra.

• Submodular Function Minimization under Covering Constraints [ps.gz]
  Satoru Iwata and Kiyohito Nagano.

• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design [arXiv]
  Julia Chuzhoy and Sanjeev Khanna.

• Blackbox Polynomial Identity Testing for Depth 3 Circuits [ECCC]
  Neeraj Kayal and Shubhangi Saraf.

• The Complexity of Rationalizing Network Formation [pdf]
  Shankar Kalyanaraman and Christopher Umans.

• Exact And Approximate Pattern Matching In The Streaming Model
  Ely Porat and Benny Porat.

• A new probability using typical moments and concentration results [arXiv]
  Ravindran Kannan.

• Orthogonal Range Reporting in Three and Higher Dimensions [pdf]
  Peyman Afshani, Lars Arge and Kasper Dalgaard Larsen.

• Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks [arXiv]
  Yossi Azar, Benjamin Birnbaum, L. Elisa Celis, Nikhil R. Devanur and Yuval Peres.

• SDP Integrality Gaps with Local $\ell_1$-Embeddability [pdf]
  Subhash Khot and Rishi Saket.

• On the Power of Randomization in Algorithmic Mechanism Design [pdf]
  Shahar Dobzinski and Shaddin Dughmi.

• Constraint Satisfaction Problems of Bounded Width [pdf] [slides]
  Libor Barto and Marcin Kozik.

• On Allocating Goods to Maximize Fairness [arXiv]
  Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.
  

• Regularity Lemmas and Combinatorial Algorithms [summary] [pdf]
  Nikhil Bansal and Ryan Williams.

• One bit encryption is complete
  Steven Myers and abhi shelat.

• Composition of low-error 2-query PCPs using decodable PCPs [ECCC]
  Irit Dinur and Prahladh Harsha.

• Smoothed Analysis of Multiobjective Optimization [pdf]
  Heiko Roeglin and Shang-Hua Teng.

• k-Means has Polynomial Smoothed Complexity [arXiv]
  David Arthur, Bodo Manthey and Heiko Roeglin.

• Reducibility Among Fractional Stability Problems [pdf]
  Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.

• Online Stochastic Matching: Beating 1-1/e [pdf]
  Jon Feldman, Aranyak Mehta, Vahab Mirrokni and S. Muthukrishnan.

• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems [arXiv]
  Sandy Irani and Daniel Gottesman.

• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities [arXiv]
  Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng.

• Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy [pdf]
  Yi Deng, Vipul Goyal and Amit Sahai.

• Space-Efficient Framework for Top-k String Retrieval Problems [pdf]
  Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter.

• (Meta) Kernelization [pdf]
  Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos.

• Choice-memory tradeoff in allocations [arXiv]
  Noga Alon, Ori Gurel-Gurevich and Eyal Lubetzky.

• The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection
  Eyal Kushilevitz and Enav Weinreb.

• Convergence to Equilibrium in Local Interaction Games [pdf]
  Andrea Montanari and Amin Saberi.

• Instance-Optimal Geometric Algorithms [ps]
  Peyman Afshani, Jeremy Barbay and Timothy M. Chan.

• Planarity allowing few error vertices in linear time [pdf]
  Ken-ichi Kawarabayashi.

• Constructing Small-Bias Sets from Algebraic-Geometric Codes [pdf]
  Avraham Ben-Aroya and Amnon Ta-Shma.

• Oblivious Routing for the L_p-norm [pdf]
  Matthias Englert and Harald Räcke.

• The Intersection of Two Halfspaces Has High Threshold Degree
  Alexander Sherstov.

• Distance Oracles for Sparse Graphs [html] [pdf]
  Christian Sommer, Elad Verbin and Wei Yu.

• Universal Blind Quantum Computation [arXiv]
  Anne Broadbent, Joseph Fitzsimons and Elham Kashefi.

• Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization [arXiv]
  Tanmoy Chakraborty, Zhiyi Huang and Sanjeev Khanna.

• Decomposing Coverings and the Planar Sensor Cover Problem [pdf]
  Matt Gibson and Kasturi Varadarajan.

• Extracting Correlations
  Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.

• The Data Stream Space Complexity of Cascaded Norms
  T.S. Jayram and David Woodruff.

• Faster generation of random spanning trees [pdf]
  Jonathan Kelner and Aleksander Madry.

• Integrality gaps for Strong SDP Relaxations of Unique Games [pdf]
  Prasad Raghavendra and David Steurer.

• How to Round Any CSP [pdf]
  Prasad Raghavendra and David Steurer.

• KKL, Kruskal-Katona, and monotone nets [pdf]
  Ryan O'Donnell and Karl Wimmer.

• Higher eigenvalues of graphs [pdf]
  Jonathan Kelner, James Lee, Gregory Price and Shanghua Teng.

• Efficient sketches for Earth-Mover Distance, with applications [pdf]
  Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.

• Agnostic Learning of Monomials by Halfspaces is Hard
  Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra and Yi Wu.

• An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk [arXiv]
  Ashish Goel and Ian Post.

• Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions [pdf]
  Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang.

• Local Graph Partitions for Approximation and Testing [html]
  Avinatan Hassidim, Jonathan Kelner, Huy Nguyen and Krzysztof Onak.

• Linear systems over composite moduli [pdf]
  Arkadev Chattopadhyay and Avi Wigderson.

• Models for the compressible Web [pdf]
  Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi and Prabhakar Raghavan.

• Breaking the Multicommodity Flow Barrier for O(sqrt(log n))-approximations to Sparsest Cut [arXiv]
  Jonah Sherman.

• A Probabilistic Inequality with Applications to Threshold Direct Product Theorems [ECCC]
  Falk Unger.

• 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness [summary]
  Yael Tauman Kalai, Xin Li and Anup Rao.

---------------------------------------------------------------------------------------

FOCS notification

I just received an email that the following paper is accepted to FOCS 2009. You can find a pdf of its full version here.

• Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng
  Reducibility Among Fractional Stability Problems

Since we had electronic proceedings at STOC'09, I am hoping that FOCS'09 continues this tradition. If so, it makes sense to remove the upper bound on the number of pages for the camera-ready version. I cannot imagine converting these 50 page results into a 10 page paper.

Barriers Everywhere

Two upcoming workshops :

1. DIMACS Tutorial on Limits of Approximation Algorithms: PCPs and Unique Games
2. Program for Barriers in Computational Complexity Workshop

It would be great if the talks at (1) are recorded. Video talks are great resource for the community, since not everybody can afford (money/time) to attend all these great workshops. Talks at Intractability Center are are always recorded, which is great !!

PPAD-complete problems on wikipedia

As requested by many of the readers of my blog, I added a wikipedia entry for PPAD-complete problems. It is called List of PPAD-complete problems. I added only the contents. I will try to add more content when I get time. Please feel free to edit and make it as informative (with definitions of problems, references, open problems etc) as possible.

Hamilton Paths Puzzle

Prove the following :

• Let G be an undirected graph and G' its complement. Let h(G) be the number of Hamilton paths of G, then h(G) + h(G') is even.

Update : Assume that the number of vertices of G is at least 5.

2009 Fulkerson Prize

It seems 2009 Fulkerson Prize is awarded to the following paper.

• Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas : The Strong Perfect Graph Theorem, Annals of Mathematics Vol. 164 (2006), 51 -- 229 [pdf]

This is the fourth time for Paul Seymour, third time for Neil Robertson and second time for Robin Thomas. The list of past winners is here and here.