default search action
20th RANDOM / 19th APPROX 2016: Paris, France
- Klaus Jansen, Claire Mathieu, José D. P. Rolim, Chris Umans:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France. LIPIcs 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-018-7 - Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors. 0:i-0:xvi
- Arturs Backurs, Anastasios Sidiropoulos:
Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces. 1:1-1:15 - Amitabh Basu
, Michael Dinitz
Computing Approximate PSD Factorizations. 2:1-2:12 - Ivan Bliznets
Hardness of Approximation for H-Free Edge Modification Problems. 3:1-3:17 - Moses Charikar
On Approximating Target Set Selection. 4:1-4:16 - Lin Chen
Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources. 5:1-5:12 - Eden Chlamtác, Michael Dinitz
The Densest k-Subhypergraph Problem. 6:1-6:19 - Michael B. Cohen
Online Row Sampling. 7:1-7:18 - Uriel Feige, Michal Feldman, Inbal Talgam-Cohen:
Oblivious Rounding and the Integrality Gap. 8:1-8:23 - Nir Halman:
A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy. 9:1-9:11 - Sungjin Im, Janardhan Kulkarni, Benjamin Moseley, Kamesh Munagala:
A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints. 10:1-10:15 - Samir Khuller, Sheng Yang:
Revisiting Connected Dominating Sets: An Optimal Local Algorithm? 11:1-11:12 - Anthony Kim
Online Energy Storage Management: an Algorithmic Approach. 12:1-12:23 - Guy Kortsarz, Zeev Nutov:
LP-Relaxations for Tree Augmentation. 13:1-13:16 - Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, Justin Ward:
A Bi-Criteria Approximation Algorithm for k-Means. 14:1-14:20 - Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
Near-Optimal UGC-hardness of Approximating Max k-CSP_R. 15:1-15:28 - Dániel Marx, Ario Salmasi, Anastasios Sidiropoulos:
Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs. 16:1-16:54 - Andrew McGregor, Sofya Vorotnikova:
Planar Matching in Streams Revisited. 17:1-17:12 - Sharath Raghvendra:
A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching. 18:1-18:16 - Noah Stephens-Davidowitz:
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One. 19:1-19:18 - Ridwan Syed, Madhur Tulsiani:
Proving Weak Approximability Without Algorithms. 20:1-20:15 - Jasine Babu, Areej Khoury, Ilan Newman:
Every Property of Outerplanar Graphs is Testable. 21:1-21:19 - Victor Bapst, Amin Coja-Oghlan:
The Condensation Phase Transition in the Regular k-SAT Model. 22:1-22:18 - Arnab Bhattacharyya, Abhishek Bhowmick, Chetan Gupta:
On Higher-Order Fourier Analysis over Non-Prime Fields. 23:1-23:29 - Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded Independence vs. Moduli. 24:1-24:9 - Vladimir Braverman, Alan Roytman, Gregory Vorsanger:
Approximating Subadditive Hadamard Functions on Implicit Matrices. 25:1-25:19 - Guillaume Chapuy, Guillem Perarnau
Local Convergence and Stability of Tight Bridge-Addable Graph Classes. 26:1-26:11 - Amin Coja-Oghlan, Will Perkins
Belief Propagation on Replica Symmetric Random Factor Graph Models. 27:1-27:15 - Daniel Dadush, Shashwat Garg, Shachar Lovett
Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem. 28:1-28:12 - Esther Ezra, Shachar Lovett:
On the Beck-Fiala Conjecture for Random Set Systems. 29:1-29:10 - Bernd Gärtner, Antonis Thomas:
The Niceness of Unique Sink Orientations. 30:1-30:14 - Heng Guo, Pinyan Lu
Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. 31:1-31:26 - Prahladh Harsha
On Polynomial Approximations to AC^0. 32:1-32:14 - Pooya Hatami:
On the Structure of Quintic Polynomials. 33:1-33:18 - Jan Hazla, Thomas Holenstein, Elchanan Mossel:
Lower Bounds on Same-Set Inner Product in Correlated Spaces. 34:1-34:11 - Carlos Hoppen
Estimating Parameters Associated with Monotone Properties. 35:1-35:13 - Varun Kanade
Stable Matching with Evolving Preferences. 36:1-36:13 - Subhash Khot, Igor Shinkar:
An ~O(n) Queries Adaptive Tester for Unateness. 37:1-37:7 - Reut Levi, Dana Ron
A Local Algorithm for Constructing Spanners in Minor-Free Graphs. 38:1-38:15 - Yi Li
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. 39:1-39:11 - Dhruv Medarametla, Aaron Potechin
Bounds on the Norms of Uniform Low Degree Graph Matrices. 40:1-40:26 - Ryuhei Mori
Lower Bounds for CSP Refutation by SDP Hierarchies. 41:1-41:30 - Dana Moshkovitz, Govind Ramnarayan, Henry Yuen:
A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian. 42:3-42:29 - Cyril Nicaud:
Fast Synchronization of Random Automata. 43:1-43:12 - Anup Rao, Makrand Sinha:
A Direct-Sum Theorem for Read-Once Branching Programs. 44:1-44:15 - Ronen Shaltiel, Jad Silbak:
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. 45:1-45:38 - Renjie Song, Yitong Yin, Jinman Zhao:
Counting Hypergraph Matchings up to Uniqueness Threshold. 46:1-46:29 - Yitong Yin, Chihao Zhang:
Sampling in Potts Model on Sparse Random Graphs. 47:1-47:22
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-13 21:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: