- 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.
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. [pd! f]
- 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 Complet! e Characterization of Statistical Query Learning with Applicat! ions 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$-E! mbeddabi lity [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 Stochast! ic Matching: Beating 1-1/e [p df]
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
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
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 Multicommodit! y Flow Barrier for O(sqrt(log n))-approximations to Sparsest C! ut [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.
Graph Theory
No comments:
Post a Comment