APPROX/RANDOM 2016 September 7-9, 2016 - Paris, France

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



Klaus Jansen and Claire Mathieu and José D. P. Rolim and Chris Umans (Eds.)
ISBN 978-3-95977-018-7, LIPICS Vol. 60 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 25 MB)
Search Publication Server

Authors
  • Babu, Jasine
  • Backurs, Arturs
  • Bapst, Victor
  • Basu, Amitabh
  • Bhattacharyya, Arnab
  • Bhowmick, Abhishek
  • Bliznets, Ivan
  • Boppana, Ravi
  • Braverman, Vladimir
  • Chapuy, Guillaume
  • Charikar, Moses
  • Chen, Lin
  • Chlamtac, Eden
  • Cohen, Michael B.
  • Coja-Oghlan, Amin
  • Cygan, Marek
  • Dadush, Daniel
  • Dinitz, Michael
  • Ezra, Esther
  • Feige, Uriel
  • Feldman, Michal
  • Garg, Shashwat
  • Guo, Heng
  • Gupta, Chetan
  • Gärtner, Bernd
  • Halman, Nir
  • Harsha, Prahladh
  • Hatami, Pooya
  • Hazla, Jan
  • Holenstein, Thomas
  • Hoppen, Carlos
  • Håstad, Johan
  • Im, Sungjin
  • Jansen, Klaus
  • Kanade, Varun
  • Khot, Subhash
  • Khoury, Areej
  • Khuller, Samir
  • Kim, Anthony
  • Kohayakawa, Yoshiharu
  • Komosa, Pawel
  • Konrad, Christian
  • Kortsarz, Guy
  • Kulkarni, Janardhan
  • Lang, Richard
  • Lee, Chin Ho
  • Lefmann, Hanno
  • Leonardos, Nikos
  • Levi, Reut
  • Li, Xin
  • Li, Yi
  • Liaghat, Vahid
  • Lovett, Shachar
  • Lu, Pinyan
  • Magniez, Frédéric
  • Makarychev, Konstantin
  • Makarychev, Yury
  • Manurangsi, Pasin
  • Marx, Dániel
  • Mathieu, Claire
  • McGregor, Andrew
  • Medarametla, Dhruv
  • Mori, Ryuhei
  • Moseley, Benjamin
  • Moshkovitz, Dana
  • Mossel, Elchanan
  • Munagala, Kamesh
  • Musco, Cameron
  • Naamad, Yonatan
  • Nakkiran, Preetum
  • Newman, Ilan
  • Nicaud, Cyril
  • Nikolov, Aleksandar
  • Nutov, Zeev
  • Pachocki, Jakub
  • Perarnau, Guillem
  • Perkins, Will
  • Pilipczuk, Michal
  • Potechin, Aaron
  • Qin, Junjie
  • Rabanca, George
  • Raghvendra, Sharath
  • Ramnarayan, Govind
  • Rao, Anup
  • Rolim, José D. P.
  • Ron, Dana
  • Roytman, Alan
  • Rubinfeld, Ronitt
  • Saberi, Amin
  • Salmasi, Ario
  • Shaltiel, Ronen
  • Shinkar, Igor
  • Sidiropoulos, Anastasios
  • Silbak, Jad
  • Sinha, Makrand
  • Song, Renjie
  • Srinivasan, Srikanth
  • Stagni, Henrique
  • Stephens-Davidowitz, Noah
  • Sviridenko, Maxim
  • Syed, Ridwan
  • Talgam-Cohen, Inbal
  • Thomas, Antonis
  • Trevisan, Luca
  • Tulsiani, Madhur
  • Umans, Chris
  • Viola, Emanuele
  • Vorotnikova, Sofya
  • Vorsanger, Gregory
  • Ward, Justin
  • Wirth, Anthony
  • Witmer, David
  • Woodruff, David P.
  • Yang, Sheng
  • Ye, Deshi
  • Yin, Yitong
  • Yuen, Henry
  • Zhang, Chihao
  • Zhang, Guochuan
  • Zhao, Jinman
    		•

    		  
    Front Matter, Table of Contents, Preface, Program Committees, External Reviewers, List of Authors
    Authors: Jansen, Klaus ; Mathieu, Claire ; Rolim, José D. P. ; Umans, Chris

    Abstract | Document (358 KB) | BibTeX

    Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional l_p Spaces
    Authors: Backurs, Arturs ; Sidiropoulos, Anastasios

    Abstract | Document (496 KB) | BibTeX

    Computing Approximate PSD Factorizations
    Authors: Basu, Amitabh ; Dinitz, Michael ; Li, Xin

    Abstract | Document (488 KB) | BibTeX

    Hardness of Approximation for H-Free Edge Modification Problems
    Authors: Bliznets, Ivan ; Cygan, Marek ; Komosa, Pawel ; Pilipczuk, Michal

    Abstract | Document (577 KB) | BibTeX

    On Approximating Target Set Selection
    Authors: Charikar, Moses ; Naamad, Yonatan ; Wirth, Anthony

    Abstract | Document (624 KB) | BibTeX

    Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources
    Authors: Chen, Lin ; Ye, Deshi ; Zhang, Guochuan

    Abstract | Document (424 KB) | BibTeX

    The Densest k-Subhypergraph Problem
    Authors: Chlamtac, Eden ; Dinitz, Michael ; Konrad, Christian ; Kortsarz, Guy ; Rabanca, George

    Abstract | Document (617 KB) | BibTeX

    Online Row Sampling
    Authors: Cohen, Michael B. ; Musco, Cameron ; Pachocki, Jakub

    Abstract | Document (543 KB) | BibTeX

    Oblivious Rounding and the Integrality Gap
    Authors: Feige, Uriel ; Feldman, Michal ; Talgam-Cohen, Inbal

    Abstract | Document (546 KB) | BibTeX

    A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy
    Authors: Halman, Nir

    Abstract | Document (523 KB) | BibTeX

    A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints
    Authors: Im, Sungjin ; Kulkarni, Janardhan ; Moseley, Benjamin ; Munagala, Kamesh

    Abstract | Document (524 KB) | BibTeX

    Revisiting Connected Dominating Sets: An Optimal Local Algorithm?
    Authors: Khuller, Samir ; Yang, Sheng

    Abstract | Document (466 KB) | BibTeX

    Online Energy Storage Management: an Algorithmic Approach
    Authors: Kim, Anthony ; Liaghat, Vahid ; Qin, Junjie ; Saberi, Amin

    Abstract | Document (633 KB) | BibTeX

    LP-Relaxations for Tree Augmentation
    Authors: Kortsarz, Guy ; Nutov, Zeev

    Abstract | Document (1,106 KB) | BibTeX

    A Bi-Criteria Approximation Algorithm for k-Means
    Authors: Makarychev, Konstantin ; Makarychev, Yury ; Sviridenko, Maxim ; Ward, Justin

    Abstract | Document (564 KB) | BibTeX

    Near-Optimal UGC-hardness of Approximating Max k-CSP_R
    Authors: Manurangsi, Pasin ; Nakkiran, Preetum ; Trevisan, Luca

    Abstract | Document (646 KB) | BibTeX

    Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs
    Authors: Marx, Dániel ; Salmasi, Ario ; Sidiropoulos, Anastasios

    Abstract | Document (1,046 KB) | BibTeX

    Planar Matching in Streams Revisited
    Authors: McGregor, Andrew ; Vorotnikova, Sofya

    Abstract | Document (555 KB) | BibTeX

    A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching
    Authors: Raghvendra, Sharath

    Abstract | Document (473 KB) | BibTeX

    Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
    Authors: Stephens-Davidowitz, Noah

    Abstract | Document (553 KB) | BibTeX

    Proving Weak Approximability Without Algorithms
    Authors: Syed, Ridwan ; Tulsiani, Madhur

    Abstract | Document (553 KB) | BibTeX

    Every Property of Outerplanar Graphs is Testable
    Authors: Babu, Jasine ; Khoury, Areej ; Newman, Ilan

    Abstract | Document (568 KB) | BibTeX

    The Condensation Phase Transition in the Regular k-SAT Model
    Authors: Bapst, Victor ; Coja-Oghlan, Amin

    Abstract | Document (639 KB) | BibTeX

    On Higher-Order Fourier Analysis over Non-Prime Fields
    Authors: Bhattacharyya, Arnab ; Bhowmick, Abhishek ; Gupta, Chetan

    Abstract | Document (652 KB) | BibTeX

    Bounded Independence vs. Moduli
    Authors: Boppana, Ravi ; Håstad, Johan ; Lee, Chin Ho ; Viola, Emanuele

    Abstract | Document (478 KB) | BibTeX

    Approximating Subadditive Hadamard Functions on Implicit Matrices
    Authors: Braverman, Vladimir ; Roytman, Alan ; Vorsanger, Gregory

    Abstract | Document (580 KB) | BibTeX

    Local Convergence and Stability of Tight Bridge-Addable Graph Classes
    Authors: Chapuy, Guillaume ; Perarnau, Guillem

    Abstract | Document (466 KB) | BibTeX

    Belief Propagation on Replica Symmetric Random Factor Graph Models
    Authors: Coja-Oghlan, Amin ; Perkins, Will

    Abstract | Document (521 KB) | BibTeX

    Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem
    Authors: Dadush, Daniel ; Garg, Shashwat ; Lovett, Shachar ; Nikolov, Aleksandar

    Abstract | Document (486 KB) | BibTeX

    On the Beck-Fiala Conjecture for Random Set Systems
    Authors: Ezra, Esther ; Lovett, Shachar

    Abstract | Document (459 KB) | BibTeX

    The Niceness of Unique Sink Orientations
    Authors: Gärtner, Bernd ; Thomas, Antonis

    Abstract | Document (597 KB) | BibTeX

    Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
    Authors: Guo, Heng ; Lu, Pinyan

    Abstract | Document (645 KB) | BibTeX

    On Polynomial Approximations to AC^0
    Authors: Harsha, Prahladh ; Srinivasan, Srikanth

    Abstract | Document (570 KB) | BibTeX

    On the Structure of Quintic Polynomials
    Authors: Hatami, Pooya

    Abstract | Document (512 KB) | BibTeX

    Lower Bounds on Same-Set Inner Product in Correlated Spaces
    Authors: Hazla, Jan ; Holenstein, Thomas ; Mossel, Elchanan

    Abstract | Document (506 KB) | BibTeX

    Estimating Parameters Associated with Monotone Properties
    Authors: Hoppen, Carlos ; Kohayakawa, Yoshiharu ; Lang, Richard ; Lefmann, Hanno ; Stagni, Henrique

    Abstract | Document (618 KB) | BibTeX

    Stable Matching with Evolving Preferences
    Authors: Kanade, Varun ; Leonardos, Nikos ; Magniez, Frédéric

    Abstract | Document (508 KB) | BibTeX

    An ~O(n) Queries Adaptive Tester for Unateness
    Authors: Khot, Subhash ; Shinkar, Igor

    Abstract | Document (489 KB) | BibTeX

    A Local Algorithm for Constructing Spanners in Minor-Free Graphs
    Authors: Levi, Reut ; Ron, Dana ; Rubinfeld, Ronitt

    Abstract | Document (585 KB) | BibTeX

    Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
    Authors: Li, Yi ; Woodruff, David P.

    Abstract | Document (498 KB) | BibTeX

    Bounds on the Norms of Uniform Low Degree Graph Matrices
    Authors: Medarametla, Dhruv ; Potechin, Aaron

    Abstract | Document (646 KB) | BibTeX

    Lower Bounds for CSP Refutation by SDP Hierarchies
    Authors: Mori, Ryuhei ; Witmer, David

    Abstract | Document (643 KB) | BibTeX

    A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian
    Authors: Moshkovitz, Dana ; Ramnarayan, Govind ; Yuen, Henry

    Abstract | Document (685 KB) | BibTeX

    Fast Synchronization of Random Automata
    Authors: Nicaud, Cyril

    Abstract | Document (566 KB) | BibTeX

    A Direct-Sum Theorem for Read-Once Branching Programs
    Authors: Rao, Anup ; Sinha, Makrand

    Abstract | Document (512 KB) | BibTeX

    Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels
    Authors: Shaltiel, Ronen ; Silbak, Jad

    Abstract | Document (726 KB) | BibTeX

    Counting Hypergraph Matchings up to Uniqueness Threshold
    Authors: Song, Renjie ; Yin, Yitong ; Zhao, Jinman

    Abstract | Document (1,915 KB) | BibTeX

    Sampling in Potts Model on Sparse Random Graphs
    Authors: Yin, Yitong ; Zhang, Chihao

    Abstract | Document (609 KB) | BibTeX

    		  



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