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
  • Acharyya, Rupam
  • Agarwal, Naman
  • Alon, Noga
  • Angel, Omer
  • Ashlagi, Itai
  • Avron, Haim
  • Azar, Yossi
  • Bérczi, Kristóf
  • Banks, Jess
  • Ben-Eliezer, Omri
  • Ben-Hamou, Anna
  • Bhattacharyya, Arnab
  • Bhattiprolu, Vijay
  • Blasiok, Jaroslaw
  • Borradaile, Glencora
  • Brakensiek, Joshua
  • Cannon, Sarah
  • Carmosino, Marco L.
  • Celis, L. Elisa
  • Chandrasekaran, Karthekeyan
  • Charikar, Moses
  • Chen, Xi
  • Chiesa, Alessandro
  • Chiplunkar, Ashish
  • Clarkson, Kenneth L.
  • Coja-Oghlan, Amin
  • Deshpande, Amit
  • Ding, Jian
  • Doron, Dean
  • Efthymiou, Charilaos
  • Ergün, Funda
  • Frank-Fischer, S. Luna
  • Freilich, Adam
  • Freitag, Cody R.
  • Frieze, Alan
  • Friggstad, Zachary
  • Geri, Ofir
  • Goemans, Michel X.
  • Golestanian, Arnoosh
  • Golovnev, Alexander
  • Gopi, Sivakanth
  • Grigorescu, Elena
  • Gupta, Anupam
  • Guruswami, Venkatesan
  • Haney, Samuel
  • Harris, David G.
  • Huang, Chien-Chung
  • Impagliazzo, Russell
  • Indyk, Piotr
  • Jaafari, Nor
  • Jansen, Klaus
  • Jindal, Gorav
  • Könemann, Jochen
  • Kabanets, Valentine
  • Kakimura, Naonori
  • Kale, Sagar
  • Kang, Mihyun
  • Kapetanopoulos, Tobias
  • Kaplan, Haim
  • Karandikar, Archit
  • Kathuria, Tarun
  • Kesselheim, Thomas
  • Khodamoradi, Kamyar
  • Király, Tamás
  • Klein, Kim-Manuel
  • Kleinberg, Robert
  • Kolev, Pavel
  • Kolla, Alexandra
  • Kolokolova, Antonina
  • Kosche, Maria
  • Ladewig, Leon
  • Lau, Lap Chi
  • Lee, Euiwoong
  • Le Gall, François
  • Levi Alev, Vedat
  • Levin, David A.
  • Li, Ray
  • Liberty, Edo
  • Madan, Vivek
  • Maggs, Bruce
  • Mahabadi, Sepideh
  • Maiti, Biswaroop
  • Makhijani, Rahul
  • Manohar, Peter
  • Martin, Christopher
  • Mehrabian, Abbas
  • Moore, Cristopher
  • Nelson, Jelani
  • Obremski, Maciej
  • Olver, Neil
  • Panigrahi, Debmalya
  • Pashkovich, Kanstantsin
  • Pegden, Wesley
  • Peng, Richard
  • Pensyl, Thomas
  • Peres, Yuval
  • Price, Eric
  • Rabani, Yuval
  • Rahgoshay, Mirmahdi
  • Rajaraman, Rajmohan
  • Ravi, R.
  • Regev, Oded
  • Rezapour, Mohsen
  • Rolim, José D. P.
  • Roughgarden, Tim
  • Rubinfeld, Ronitt
  • Sadeqi Azer, Erfan
  • Salavatipour, Mohammad R.
  • Sawlani, Saurabh
  • Servedio, Rocco A.
  • Shinkar, Igor
  • Skorski, Maciej
  • Srinivasan, Aravind
  • Stauffer, Alexandre
  • Stefankovic, Daniel
  • Straszak, Damian
  • Sun, Timothy
  • Sundaram, Ravi
  • Sviridenko, Maxim
  • Swamy, Chaitanya
  • Swartworth, William J.
  • Tönnis, Andreas
  • Ta-Shma, Amnon
  • Tal, Avishay
  • Talgam-Cohen, Inbal
  • Tan, Li-Yang
  • Tirodkar, Sumedh
  • Trinh, Khoa
  • Ullman, Jonathan
  • Unda, Francisco
  • Vakilian, Ali
  • Velingker, Ameya
  • Velusamy, Santhoshini
  • Vempala, Santosh S.
  • Venkat, Rakesh
  • Vishnoi, Nisheeth K.
  • Volkovich, Ilya
  • Vondrák, Jan
  • Vygen, Jens
  • Waingarten, Erik
  • Wang, Yuyi
  • Watson, Thomas
  • Wattenhofer, Roger
  • Weinstein, Omri
  • Williamson, David P.
  • Woodruff, David P.
  • Wootters, Mary
  • Xu, Chao
  • Yodpinyanee, Anak
  • Yoshida, Yuichi
  • Zhang, Yifeng
  • Zheng, Baigong
  • Zhou, Samson

  •   
    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 Published by LZI