Portal - APPROX/RANDOM 2017

APPROX/RANDOM 2017	August 16-18, 2017 - Berkeley, CA, USA
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) Klaus Jansen and José D. P. Rolim and David Williamson and Santosh S. Vempala (Eds.)
ISBN 978-3-95977-044-6, LIPICS Vol. 81	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 27 MB)
Search Publication Server

Authors

Chandrasekaran, Karthekeyan

Frank-Fischer, S. Luna

Guruswami, Venkatesan

Kapetanopoulos, Tobias

Pashkovich, Kanstantsin

Salavatipour, Mohammad R.

Swartworth, William J.

Velusamy, Santhoshini

Frontmatter, Table of Contents, Preface, Organization, External Reviewers, List of Authors

Authors: Jansen, Klaus ; Rolim, José D. P. ; Williamson, David P. ; Vempala, Santosh S.

Abstract | Document (355 KB) | BibTeX

Min-Cost Bipartite Perfect Matching with Delays

Authors: Ashlagi, Itai ; Azar, Yossi ; Charikar, Moses ; Chiplunkar, Ashish ; Geri, Ofir ; Kaplan, Haim ; Makhijani, Rahul ; Wang, Yuyi ; Wattenhofer, Roger

Abstract | Document (556 KB) | BibTeX

Global and Fixed-Terminal Cuts in Digraphs

Authors: Bérczi, Kristóf ; Chandrasekaran, Karthekeyan ; Király, Tamás ; Lee, Euiwoong ; Xu, Chao

Abstract | Document (891 KB) | BibTeX

A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs

Authors: Borradaile, Glencora ; Zheng, Baigong

Abstract | Document (590 KB) | BibTeX

The Quest for Strong Inapproximability Results with Perfect Completeness

Authors: Brakensiek, Joshua ; Guruswami, Venkatesan

Abstract | Document (616 KB) | BibTeX

Scheduling Problems over Network of Machines

Authors: Friggstad, Zachary ; Golestanian, Arnoosh ; Khodamoradi, Kamyar ; Martin, Christopher ; Rahgoshay, Mirmahdi ; Rezapour, Mohsen ; Salavatipour, Mohammad R. ; Zhang, Yifeng

Abstract | Document (555 KB) | BibTeX

Approximating Incremental Combinatorial Optimization Problems

Authors: Goemans, Michel X. ; Unda, Francisco

Abstract | Document (508 KB) | BibTeX

Stochastic Unsplittable Flows

Authors: Gupta, Anupam ; Karandikar, Archit

Abstract | Document (600 KB) | BibTeX

Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph

Authors: Guruswami, Venkatesan ; Velingker, Ameya ; Velusamy, Santhoshini

Abstract | Document (554 KB) | BibTeX

Symmetric Interdiction for Matching Problems

Authors: Haney, Samuel ; Maggs, Bruce ; Maiti, Biswaroop ; Panigrahi, Debmalya ; Rajaraman, Rajmohan ; Sundaram, Ravi

Abstract | Document (709 KB) | BibTeX

A Lottery Model for Center-Type Problems with Outliers

Authors: Harris, David G. ; Pensyl, Thomas ; Srinivasan, Aravind ; Trinh, Khoa

Abstract | Document (916 KB) | BibTeX

Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

Authors: Huang, Chien-Chung ; Kakimura, Naonori ; Yoshida, Yuichi

Abstract | Document (548 KB) | BibTeX

Fractional Set Cover in the Streaming Model

Authors: Indyk, Piotr ; Mahabadi, Sepideh ; Rubinfeld, Ronitt ; Ullman, Jonathan ; Vakilian, Ali ; Yodpinyanee, Anak

Abstract | Document (741 KB) | BibTeX

Online Strip Packing with Polynomial Migration

Authors: Jansen, Klaus ; Klein, Kim-Manuel ; Kosche, Maria ; Ladewig, Leon

Abstract | Document (996 KB) | BibTeX

Density Independent Algorithms for Sparsifying k-Step Random Walks

Authors: Jindal, Gorav ; Kolev, Pavel ; Peng, Richard ; Sawlani, Saurabh

Abstract | Document (564 KB) | BibTeX

Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

Authors: Kale, Sagar ; Tirodkar, Sumedh

Abstract | Document (575 KB) | BibTeX

Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints

Authors: Kesselheim, Thomas ; Tönnis, Andreas

Abstract | Document (570 KB) | BibTeX

On the Integrality Gap of the Prize-Collecting Steiner Forest LP

Authors: Könemann, Jochen ; Olver, Neil ; Pashkovich, Kanstantsin ; Ravi, R. ; Swamy, Chaitanya ; Vygen, Jens

Abstract | Document (556 KB) | BibTeX

Approximating Unique Games Using Low Diameter Graph Decomposition

Authors: Levi Alev, Vedat ; Lau, Lap Chi

Abstract | Document (522 KB) | BibTeX

Greedy Minimization of Weakly Supermodular Set Functions

Authors: Liberty, Edo ; Sviridenko, Maxim

Abstract | Document (426 KB) | BibTeX

Renyi Entropy Estimation Revisited

Authors: Obremski, Maciej ; Skorski, Maciej

Abstract | Document (591 KB) | BibTeX

Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces

Authors: Rabani, Yuval ; Venkat, Rakesh

Abstract | Document (522 KB) | BibTeX

When Are Welfare Guarantees Robust?

Authors: Roughgarden, Tim ; Talgam-Cohen, Inbal ; Vondrák, Jan

Abstract | Document (846 KB) | BibTeX

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences

Authors: Acharyya, Rupam ; Stefankovic, Daniel

Abstract | Document (611 KB) | BibTeX

On the Expansion of Group-Based Lifts

Authors: Agarwal, Naman ; Chandrasekaran, Karthekeyan ; Kolla, Alexandra ; Madan, Vivek

Abstract | Document (513 KB) | BibTeX

Efficient Removal Lemmas for Matrices

Authors: Alon, Noga ; Ben-Eliezer, Omri

Abstract | Document (501 KB) | BibTeX

The String of Diamonds Is Tight for Rumor Spreading

Authors: Angel, Omer ; Mehrabian, Abbas ; Peres, Yuval

Abstract | Document (486 KB) | BibTeX

Sharper Bounds for Regularized Data Fitting

Authors: Avron, Haim ; Clarkson, Kenneth L. ; Woodruff, David P.

Abstract | Document (569 KB) | BibTeX

The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime

Authors: Banks, Jess ; Kleinberg, Robert ; Moore, Cristopher

Abstract | Document (545 KB) | BibTeX

Cutoff for a Stratified Random Walk on the Hypercube

Authors: Ben-Hamou, Anna ; Peres, Yuval

Abstract | Document (410 KB) | BibTeX

Lower Bounds for 2-Query LCCs over Large Alphabet

Authors: Bhattacharyya, Arnab ; Gopi, Sivakanth ; Tal, Avishay

Abstract | Document (576 KB) | BibTeX

Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere

Authors: Bhattiprolu, Vijay ; Guruswami, Venkatesan ; Lee, Euiwoong

Abstract | Document (673 KB) | BibTeX

Continuous Monitoring of l_p Norms in Data Streams

Authors: Blasiok, Jaroslaw ; Ding, Jian ; Nelson, Jelani

Abstract | Document (561 KB) | BibTeX

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques

Authors: Brakensiek, Joshua

Abstract | Document (684 KB) | BibTeX

Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings

Authors: Cannon, Sarah ; Levin, David A. ; Stauffer, Alexandre

Abstract | Document (2,231 KB) | BibTeX

Agnostic Learning from Tolerant Natural Proofs

Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

Abstract | Document (572 KB) | BibTeX

On the Complexity of Constrained Determinantal Point Processes

Authors: Celis, L. Elisa ; Deshpande, Amit ; Kathuria, Tarun ; Straszak, Damian ; Vishnoi, Nisheeth K.

Abstract | Document (577 KB) | BibTeX

Sample-Based High-Dimensional Convexity Testing

Authors: Chen, Xi ; Freilich, Adam ; Servedio, Rocco A. ; Sun, Timothy

Abstract | Document (754 KB) | BibTeX

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

Authors: Chen, Xi ; Servedio, Rocco A. ; Tan, Li-Yang ; Waingarten, Erik

Abstract | Document (683 KB) | BibTeX

On Axis-Parallel Tests for Tensor Product Codes

Authors: Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

Abstract | Document (543 KB) | BibTeX

Charting the Replica Symmetric Phase

Authors: Coja-Oghlan, Amin ; Efthymiou, Charilaos ; Jaafari, Nor ; Kang, Mihyun ; Kapetanopoulos, Tobias

Abstract | Document (629 KB) | BibTeX

Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers

Authors: Doron, Dean ; Le Gall, François ; Ta-Shma, Amnon

Abstract | Document (610 KB) | BibTeX

Streaming Periodicity with Mismatches

Authors: Ergün, Funda ; Grigorescu, Elena ; Sadeqi Azer, Erfan ; Zhou, Samson

Abstract | Document (614 KB) | BibTeX

Locality via Partially Lifted Codes

Authors: Frank-Fischer, S. Luna ; Guruswami, Venkatesan ; Wootters, Mary

Abstract | Document (576 KB) | BibTeX

Testing Hereditary Properties of Sequences

Authors: Freitag, Cody R. ; Price, Eric ; Swartworth, William J.

Abstract | Document (429 KB) | BibTeX

Traveling in Randomly Embedded Random Graphs

Authors: Frieze, Alan ; Pegden, Wesley

Abstract | Document (557 KB) | BibTeX

The Minrank of Random Graphs

Authors: Golovnev, Alexander ; Regev, Oded ; Weinstein, Omri

Abstract | Document (516 KB) | BibTeX

Efficiently Decodable Codes for the Binary Deletion Channel

Authors: Guruswami, Venkatesan ; Li, Ray

Abstract | Document (477 KB) | BibTeX

On Some Computations on Sparse Polynomials

Authors: Volkovich, Ilya

Abstract | Document (565 KB) | BibTeX

Communication Complexity of Statistical Distance

Authors: Watson, Thomas

Abstract | Document (529 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)