APPROX/RANDOM 2018 August 20-22, 2018 - Princeton, NJ, USA

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



Eric Blais and Klaus Jansen and José D. P. Rolim and David Steurer (Eds.)
ISBN 978-3-95977-085-9, LIPICS Vol. 116 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 31 MB)
Search Publication Server


Authors
  • Agrawal, Akanksha
  • Babai, László
  • Bandyapadhyay, Sayan
  • Becker, Amariah
  • Beigi, Salman
  • Belovs, Aleksandrs
  • Bhaskara, Aditya
  • Black, Timothy J. F.
  • Blais, Eric
  • Blanca, Antonio
  • Blasiok, Jaroslaw
  • Bogdanov, Andrej
  • Borodin, Allan
  • Braverman, Mark
  • Braverman, Vladimir
  • Bun, Mark
  • Carboni Oliveira, Igor
  • Carstens, Corrie Jacobien
  • Chalermsook, Parinya
  • Chekuri, Chandra
  • Cheng, Kuan
  • Chen, Zongchen
  • Chlamtác, Eden
  • C. S., Karthik
  • Das, Syamantak
  • Dikstein, Yotam
  • Dinur, Irit
  • D. P. Rolim, José
  • Eden, Talya
  • Etesami, Omid
  • Even, Guy
  • Filmus, Yuval
  • Galanis, Andreas
  • Ganor, Anat
  • Goldberg, Leslie Ann
  • Gracar, Peter
  • Grigorescu, Elena
  • Guo, Siyao
  • Gupta, Shalmoli
  • Guruswami, Venkatesan
  • Harsha, Prahladh
  • Haviv, Ishay
  • Hon, Wing-Kai
  • Horn, Paul
  • Hoza, William M.
  • Huang, Zhiyi
  • Iliopoulos, Fotis
  • Jansen, Klaus
  • Johansson, Tony
  • Kabanets, Valentine
  • Kang, Ning
  • Karavasilis, Christodoulos
  • Kaufman, Tali
  • Kleer, Pieter
  • Klivans, Adam R.
  • Koroth, Sajin
  • Ko, Young Kun
  • Krishnan, Aditya
  • Kulkarni, Janardhan
  • Kumar, Akash
  • Kumar, Neeraj
  • Kumar, Srivatsan
  • Laekhanukit, Bundit
  • Lang, Harry
  • Leshkowitz, Maya
  • Levi, Amit
  • Liao, Chung-Shou
  • Li, Ray
  • Li, Shi
  • Liu, Tianyu
  • Li, Xin
  • Li, Yi
  • Lokshtanov, Daniel
  • Lovett, Shachar
  • Lu, Zhenjian
  • Manurangsi, Pasin
  • Meir, Or
  • Misra, Pranabendu
  • Mohanty, Sidhanth
  • Nakar, Yonatan
  • Nakos, Vasileios
  • Narayanan, Shyam
  • O'Donnell, Ryan
  • Oppenheim, Izhar
  • Pankratov, Denis
  • Reddy, Goonwanth
  • Ron, Dana
  • Rosenbaum, Will
  • Sadakane, Kunihiko
  • Santhanam, Rahul
  • Santiago, Richard
  • Sarpatwar, Kanthi
  • Saurabh, Saket
  • Schieber, Baruch
  • Servedio, Rocco A.
  • Shachnai, Hadas
  • Shepherd, F. Bruce
  • Sra, Suvrit
  • Stauffer, Alexandre
  • Stefankovic, Daniel
  • Steurer, David
  • Sudan, Madhu
  • Suri, Subhash
  • Swernofsky, Joseph
  • Tang, Zhihao Gavin
  • Tan, Li-Yang
  • Thaler, Justin
  • Trevisan, Luca
  • Varadarajan, Kasturi
  • Vardi, Shai
  • Vaz, Daniel
  • Vaze, Rahul
  • Viderman, Michael
  • Vigoda, Eric
  • Vishnoi, Nisheeth K.
  • Wei, Hao-Ting
  • Wiese, Andreas
  • Wimmer, Karl
  • Woodruff, David P.
  • Wootters, Mary
  • Wuu, Angela
  • Wu, Xiaowei
  • Xing, Chaoping
  • Yang, Kuan
  • Yildiz, Ozan
  • Yoshida, Yuichi
  • Yuan, Chen
  • Zehavi, Meirav
  • Zhang, Jiapeng
  • Zhang, Yuhao
  • Zhao, Yu
  • Zhou, Samson

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Blais, Eric ; Jansen, Klaus ; D. P. Rolim, José ; Steurer, David

    Abstract | Document (358 KB) | BibTeX

    Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems
    Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (522 KB) | BibTeX

    Improved Approximation Bounds for the Minimum Constraint Removal Problem
    Authors: Bandyapadhyay, Sayan ; Kumar, Neeraj ; Suri, Subhash ; Varadarajan, Kasturi

    Abstract | Document (830 KB) | BibTeX

    A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
    Authors: Becker, Amariah

    Abstract | Document (676 KB) | BibTeX

    Low Rank Approximation in the Presence of Outliers
    Authors: Bhaskara, Aditya ; Kumar, Srivatsan

    Abstract | Document (513 KB) | BibTeX

    Greedy Bipartite Matching in Random Type Poisson Arrival Model
    Authors: Borodin, Allan ; Karavasilis, Christodoulos ; Pankratov, Denis

    Abstract | Document (673 KB) | BibTeX

    Semi-Direct Sum Theorem and Nearest Neighbor under l_infty
    Authors: Braverman, Mark ; Ko, Young Kun

    Abstract | Document (509 KB) | BibTeX

    Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
    Authors: Braverman, Vladimir ; Grigorescu, Elena ; Lang, Harry ; Woodruff, David P. ; Zhou, Samson

    Abstract | Document (645 KB) | BibTeX

    Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
    Authors: Chalermsook, Parinya ; Das, Syamantak ; Even, Guy ; Laekhanukit, Bundit ; Vaz, Daniel

    Abstract | Document (552 KB) | BibTeX

    Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations
    Authors: Chekuri, Chandra ; Gupta, Shalmoli

    Abstract | Document (823 KB) | BibTeX

    Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
    Authors: Chlamtác, Eden ; Manurangsi, Pasin

    Abstract | Document (570 KB) | BibTeX

    Lower Bounds for Approximating Graph Parameters via Communication Complexity
    Authors: Eden, Talya ; Rosenbaum, Will

    Abstract | Document (560 KB) | BibTeX

    Communication Complexity of Correlated Equilibrium with Small Support
    Authors: Ganor, Anat ; C. S., Karthik

    Abstract | Document (529 KB) | BibTeX

    On Minrank and the Lovász Theta Function
    Authors: Haviv, Ishay

    Abstract | Document (366 KB) | BibTeX

    Online Makespan Minimization: The Power of Restart
    Authors: Huang, Zhiyi ; Kang, Ning ; Tang, Zhihao Gavin ; Wu, Xiaowei ; Zhang, Yuhao

    Abstract | Document (571 KB) | BibTeX

    On Sketching the q to p Norms
    Authors: Krishnan, Aditya ; Mohanty, Sidhanth ; Woodruff, David P.

    Abstract | Document (621 KB) | BibTeX

    Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models
    Authors: Kulkarni, Janardhan ; Li, Shi

    Abstract | Document (520 KB) | BibTeX

    Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
    Authors: Levi, Amit ; Yoshida, Yuichi

    Abstract | Document (525 KB) | BibTeX

    Deterministic Heavy Hitters with Sublinear Query Time
    Authors: Li, Yi ; Nakos, Vasileios

    Abstract | Document (546 KB) | BibTeX

    On Low-Risk Heavy Hitters and Sparse Recovery Schemes
    Authors: Li, Yi ; Nakos, Vasileios ; Woodruff, David P.

    Abstract | Document (569 KB) | BibTeX

    Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
    Authors: Manurangsi, Pasin ; Trevisan, Luca

    Abstract | Document (558 KB) | BibTeX

    Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers
    Authors: Narayanan, Shyam

    Abstract | Document (476 KB) | BibTeX

    Robust Online Speed Scaling With Deadline Uncertainty
    Authors: Reddy, Goonwanth ; Vaze, Rahul

    Abstract | Document (517 KB) | BibTeX

    Multi-Agent Submodular Optimization
    Authors: Santiago, Richard ; Shepherd, F. Bruce

    Abstract | Document (588 KB) | BibTeX

    Generalized Assignment of Time-Sensitive Item Groups
    Authors: Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas

    Abstract | Document (508 KB) | BibTeX

    On Geodesically Convex Formulations for the Brascamp-Lieb Constant
    Authors: Sra, Suvrit ; Vishnoi, Nisheeth K. ; Yildiz, Ozan

    Abstract | Document (425 KB) | BibTeX

    Tensor Rank is Hard to Approximate
    Authors: Swernofsky, Joseph

    Abstract | Document (425 KB) | BibTeX

    An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
    Authors: Wei, Hao-Ting ; Hon, Wing-Kai ; Horn, Paul ; Liao, Chung-Shou ; Sadakane, Kunihiko

    Abstract | Document (513 KB) | BibTeX

    Fixed-Parameter Approximation Schemes for Weighted Flowtime
    Authors: Wiese, Andreas

    Abstract | Document (504 KB) | BibTeX

    List-Decoding Homomorphism Codes with Arbitrary Codomains
    Authors: Babai, László ; Black, Timothy J. F. ; Wuu, Angela

    Abstract | Document (570 KB) | BibTeX

    Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources
    Authors: Beigi, Salman ; Bogdanov, Andrej ; Etesami, Omid ; Guo, Siyao

    Abstract | Document (446 KB) | BibTeX

    Adaptive Lower Bound for Testing Monotonicity on the Line
    Authors: Belovs, Aleksandrs

    Abstract | Document (387 KB) | BibTeX

    Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
    Authors: Blanca, Antonio ; Chen, Zongchen ; Vigoda, Eric

    Abstract | Document (429 KB) | BibTeX

    Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
    Authors: Blanca, Antonio ; Galanis, Andreas ; Goldberg, Leslie Ann ; Stefankovic, Daniel ; Vigoda, Eric ; Yang, Kuan

    Abstract | Document (505 KB) | BibTeX

    Polar Codes with Exponentially Small Error at Finite Block Length
    Authors: Blasiok, Jaroslaw ; Guruswami, Venkatesan ; Sudan, Madhu

    Abstract | Document (518 KB) | BibTeX

    Approximate Degree and the Complexity of Depth Three Circuits
    Authors: Bun, Mark ; Thaler, Justin

    Abstract | Document (617 KB) | BibTeX

    Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence
    Authors: Carstens, Corrie Jacobien ; Kleer, Pieter

    Abstract | Document (487 KB) | BibTeX

    Randomness Extraction in AC0 and with Small Locality
    Authors: Cheng, Kuan ; Li, Xin

    Abstract | Document (586 KB) | BibTeX

    Boolean Function Analysis on High-Dimensional Expanders
    Authors: Dikstein, Yotam ; Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh

    Abstract | Document (510 KB) | BibTeX

    Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents
    Authors: Gracar, Peter ; Stauffer, Alexandre

    Abstract | Document (1,510 KB) | BibTeX

    Flipping out with Many Flips: Hardness of Testing k-Monotonicity
    Authors: Grigorescu, Elena ; Kumar, Akash ; Wimmer, Karl

    Abstract | Document (549 KB) | BibTeX

    How Long Can Optimal Locally Repairable Codes Be?
    Authors: Guruswami, Venkatesan ; Xing, Chaoping ; Yuan, Chen

    Abstract | Document (495 KB) | BibTeX

    On Minrank and Forbidden Subgraphs
    Authors: Haviv, Ishay

    Abstract | Document (421 KB) | BibTeX

    Preserving Randomness for Adaptive Algorithms
    Authors: Hoza, William M. ; Klivans, Adam R.

    Abstract | Document (612 KB) | BibTeX

    Commutative Algorithms Approximate the LLL-distribution
    Authors: Iliopoulos, Fotis

    Abstract | Document (537 KB) | BibTeX

    The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree
    Authors: Johansson, Tony

    Abstract | Document (505 KB) | BibTeX

    Satisfiability and Derandomization for Small Polynomial Threshold Circuits
    Authors: Kabanets, Valentine ; Lu, Zhenjian

    Abstract | Document (556 KB) | BibTeX

    High Order Random Walks: Beyond Spectral Gap
    Authors: Kaufman, Tali ; Oppenheim, Izhar

    Abstract | Document (454 KB) | BibTeX

    Improved Composition Theorems for Functions and Relations
    Authors: Koroth, Sajin ; Meir, Or

    Abstract | Document (563 KB) | BibTeX

    Round Complexity Versus Randomness Complexity in Interactive Proofs
    Authors: Leshkowitz, Maya

    Abstract | Document (492 KB) | BibTeX

    Improved List-Decodability of Random Linear Binary Codes
    Authors: Li, Ray ; Wootters, Mary

    Abstract | Document (530 KB) | BibTeX

    Sunflowers and Quasi-Sunflowers from Randomness Extractors
    Authors: Li, Xin ; Lovett, Shachar ; Zhang, Jiapeng

    Abstract | Document (473 KB) | BibTeX

    Torpid Mixing of Markov Chains for the Six-vertex Model on Z^2
    Authors: Liu, Tianyu

    Abstract | Document (4,290 KB) | BibTeX

    On the Testability of Graph Partition Properties
    Authors: Nakar, Yonatan ; Ron, Dana

    Abstract | Document (513 KB) | BibTeX

    On Closeness to k-Wise Uniformity
    Authors: O'Donnell, Ryan ; Zhao, Yu

    Abstract | Document (520 KB) | BibTeX

    Pseudo-Derandomizing Learning and Approximation
    Authors: Carboni Oliveira, Igor ; Santhanam, Rahul

    Abstract | Document (519 KB) | BibTeX

    Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits
    Authors: Servedio, Rocco A. ; Tan, Li-Yang

    Abstract | Document (687 KB) | BibTeX

    Randomly Coloring Graphs of Logarithmically Bounded Pathwidth
    Authors: Vardi, Shai

    Abstract | Document (516 KB) | BibTeX

    Explicit Strong LTCs with Inverse Poly-Log Rate and Constant Soundness
    Authors: Viderman, Michael

    Abstract | Document (469 KB) | BibTeX

      




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