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

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] [ECCC] [arXiv]
  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 [ECCC] [arXiv]
  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 [pdf]
  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 [pdf]
  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] [pdf]
  Yael Tauman Kalai, Xin Li and Anup Rao.

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

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.

A Compendium of PPAD-complete problems

Motivated by my recent paper (joint work with Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng) and a suggestion of Noam Nisan, I created a compendium of PPAD-complete problems. Please let me know if you see any additions/corrections.

Dick Lipton's and Noam Nisan's Blogs

There are two new theory blogs.....

• Dick Lipton's Gödel’s Lost Letter and P=NP : This is an awesome blog. During my first semester at GeorgiaTech I took Dick's course on 'Open Problems in CS theory'. What an excellent course that was !! In every class, Dick proposed at least three open problems along with possible ways to attack them and required references. Since, it was my first semester at Gatech, some of these problems intimidated me. Nevertheless, I maintained a special notebook and scribbled each and every problem and references he mentioned, hoping to revisit them later. I am gald that all his open problems are being documented in his blog.
  

• Noam Nisan's Algorithmic game theory is very fresh. Just launcheded yesterday.

Complexity of Ken Ken Game

I came across this puzzle named Ken Ken. It is Sudoku-type puzzle with arithmetic constraints. Here is a complexity question :

• Is solving n x n Ken Ken puzzle NP-complete ?

NP-completeness results are known for similar games like Sudoku. Here is a paper on mathematics of Septoku. Here is David Eppstein's list of games with complexity results.

Free Algebraic Curves Book

William Fulton's Algebraic Curves book is available free online. What distinguishes it from other books is the excellent set of exercise problems.

Train Probability Puzzle

The probability of observing a train in 30 minutes on a track is 665/729. What is the probability of observing a train in 5 minutes ?

Hint : Shoot for an elegant solution.

Troyis Game

I came across this game called Troyis. Being a theoretician, whenever I come across a new game, the first question that comes to my mind is "What is its complexity ?". Here is the decision version of Troyis :

• TROYIS : Given an instance of Troyis, can you paint all the white cells in <= k clicks ?

Here is a puzzle : Prove (or disprove) that TROYIS is NP-complete.