- 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.

- 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.

- On Allocating Goods to Maximize Fairness [arXiv]

Deeparnab Chakrabarty, Julia Chuzhoy and Sanjeev Khanna.

- 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.

- 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.

## 8 comments:

Hi, the two-page summary of my paper with Nikhil is up:

http://www.cs.cmu.edu/~ryanw/regularity-summary.pdf

Sorry that the full paper isn't up yet, but we still want to revise it one more time before posting a version.

Thanks Ryan. I added a link to your summary.

My paper with Wimmer is on my home page.

Thanks Ryan. I added a link to your pdf file.

Hi,

A slightly revised version of what I submitted to FOCS is here:

http://www.wisdom.weizmann.ac.il/~orm/

papers/efficient_pcps_overview.pdf

and the two-page summary is here:

http://www.wisdom.weizmann.ac.il/~orm/

papers/efficient_pcps_brief.pdf

Thanks :)

Or Meir

Thanks Or Meir. I added links to both.

Post a Comment