APPROX/RANDOM 2020 August 17-19, 2020, Virtual Conference

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



Jarosław Byrka and Raghu Meka (Eds.)
ISBN 978-3-95977-164-1, LIPICS Vol. 176 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 34 MB)
Search Publication Server


Authors
  • Agarwal, Ishan
  • Aggarwal, Divesh
  • Ahn, Kwangjun
  • Alon, Noga
  • Ameli, Afrouz Jabal
  • Anari, Nima
  • Andoni, Alexandr
  • Assadi, Sepehr
  • Bakshi, Ainesh
  • Bandyapadhyay, Sayan
  • Beideman, Calvin
  • Ben-David, Shalev
  • Ben Yamin, Lior
  • Bhangale, Amey
  • Bhattacharya, Anup
  • Bhrushundi, Abhishek
  • Blais, Eric
  • Bläser, Markus
  • Bommireddi, Abhinav
  • Boyd, Sylvia
  • Bshouty, Nader H.
  • Bubeck, Sébastien
  • Burns, Collin
  • Byrka, Jarosław
  • Canonne, Clément L.
  • Chakrabarti, Amit
  • Chakraborty, Diptarka
  • Chakraborty, Sourav
  • Chalermsook, Parinya
  • Chan, Chun-Hsiang
  • Chandrasekaran, Karthekeyan
  • Chepurko, Nadiia
  • Cheriyan, Joseph
  • Chlamtáč, Eden
  • Chubarian, Karine
  • Chuzhoy, Julia
  • Chybowska-Sokół, Joanna
  • Cummings, Robert
  • Czumaj, Artur
  • Das, Syamantak
  • Doron, Dean
  • Dreier, Jan
  • Fan, Bohan
  • Fichtenberger, Hendrik
  • Fomin, Fedor V.
  • Gálvez, Waldo
  • Gamlath, Buddhima
  • Garg, Sumegha
  • Ghosh, Arijit
  • Ghosh, Prantar
  • Golan, Shay
  • Golovach, Petr A.
  • Göös, Mika
  • Grandoni, Fabrizio
  • Greenhill, Catherine
  • Grinberg, Vadim
  • Grout, Logan
  • Gunda, Spoorthy
  • Guo, Siyao
  • Guo, Xiangyu
  • Guo, Zeyu
  • Gupta, Varun
  • Gurjar, Rohit
  • Guruswami, Venkatesan
  • Gutowski, Grzegorz
  • Hallgren, Sean
  • Harsha, Prahladh
  • Hatami, Pooya
  • Hirahara, Shuichi
  • Huang, Chien-Chung
  • Huang, Neng
  • Ibrahimpur, Sharat
  • Ihara, Diego
  • Jain, Lavina
  • Jain, Pallavi
  • Jansen, Klaus
  • Junosza-Szaniawski, Konstanty
  • Katzelnick, Dor
  • Kaufman, Tali
  • Khan, Arindam
  • Kociumaka, Tomasz
  • Kolman, Petr
  • Kopelowitz, Tsvi
  • Kopparty, Swastik
  • Kortsarz, Guy
  • Kothari, Pravesh K.
  • Kothari, Robin
  • Krishnaswamy, Ravishankar
  • Kuinke, Philipp
  • Kulkarni, Janardhan
  • Kumar, Mrinal
  • Kumar, Nikhil
  • Kumar, Rajendra
  • Laekhanukit, Bundit
  • Lee, Eunou
  • Levi, Reut
  • Li, Jing
  • Li, Ray
  • Li, Shi
  • Li, Yi
  • Lokshtanov, Daniel
  • Lund, Ben
  • Mahabadi, Sepideh
  • Mans, Bernard
  • Medina, Moti
  • Megow, Nicole
  • Meka, Raghu
  • Mikos, Patryk
  • Miracle, Sarah
  • Mishra, Gopinath
  • Mohammadi, Neshat
  • Mosheiff, Jonathan
  • Nölke, Lukas
  • Obremski, Maciej
  • Opršal, Jakub
  • Pandey, Anurag
  • Panolan, Fahad
  • Paraashar, Manaswi
  • Parekh, Ojas
  • Peng, Pan
  • Phillips, Jeff M.
  • Pittu, Madhusudhan Reddy
  • Polak, Adam
  • Porat, Ely
  • Potechin, Aaron
  • Potukuchi, Aditya
  • Pourmiri, Ali
  • Price, Eric
  • Rabani, Yuval
  • Rashtchian, Cyrus
  • Rau, Malin
  • Raz, Ran
  • Regev, Oded
  • Resch, Nicolas
  • Ribeiro, João
  • Ron, Dana
  • Rosin, Asaf
  • Rossmanith, Peter
  • Sandeep, Sai
  • Saranurak, Thatchaphol
  • Sarpatwar, Kanthi
  • Saurabh, Saket
  • Scarlett, Jonathan
  • Schieber, Baruch
  • Schwartz, Roy
  • Sgherzi, Francesco
  • Shachnai, Hadas
  • Shaltiel, Ronen
  • Sharakanski, Ella
  • Sharoni, Yotam
  • Sidiropoulos, Anastasios
  • Silas, Shashwat
  • Simonov, Kirill
  • Sohler, Christian
  • Starikovskaya, Tatiana
  • Stephens-Davidowitz, Noah
  • Streib, Amanda Pascoe
  • Streib, Noah
  • Svagerka, Michal
  • Szigeti, Zoltán
  • Tai, Wai Ming
  • Tale, Prafullkumar
  • Tang, Yi
  • Ta-Shma, Amnon
  • Tell, Roei
  • Thaler, Justin
  • Thiery, Theophile
  • Tran, Linh
  • Uznański, Przemysław
  • Valizadeh, Mina
  • Vaz, Daniel
  • Vuong, Thuy-Duong
  • Vu, Van
  • Wang, Lu
  • Ward, Justin
  • Watanabe, Osamu
  • Watson, Thomas
  • Wei, Alexander
  • Wei, Hao-Ting
  • Wimmer, Karl
  • Woodruff, David P.
  • Wootters, Mary
  • Xian, Jiayi
  • Xu, Chao
  • Zhang, Yuhao
  • Zhu, Hanlin

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Byrka, Jarosław ; Meka, Raghu

    Abstract | Document (373 KB) | BibTeX

    Extractor Lower Bounds, Revisited
    Authors: Aggarwal, Divesh ; Guo, Siyao ; Obremski, Maciej ; Ribeiro, João ; Stephens-Davidowitz, Noah

    Abstract | Document (556 KB) | BibTeX

    A Simpler Strong Refutation of Random k-XOR
    Authors: Ahn, Kwangjun

    Abstract | Document (552 KB) | BibTeX

    Iterated Decomposition of Biased Permutations via New Bounds on the Spectral Gap of Markov Chains
    Authors: Miracle, Sarah ; Streib, Amanda Pascoe ; Streib, Noah

    Abstract | Document (565 KB) | BibTeX

    Improved Explicit Hitting-Sets for ROABPs
    Authors: Guo, Zeyu ; Gurjar, Rohit

    Abstract | Document (590 KB) | BibTeX

    Almost Optimal Testers for Concise Representations
    Authors: Bshouty, Nader H.

    Abstract | Document (606 KB) | BibTeX

    Palette Sparsification Beyond (Δ+1) Vertex Coloring
    Authors: Alon, Noga ; Assadi, Sepehr

    Abstract | Document (678 KB) | BibTeX

    On Hitting-Set Generators for Polynomials That Vanish Rarely
    Authors: Doron, Dean ; Ta-Shma, Amnon ; Tell, Roei

    Abstract | Document (744 KB) | BibTeX

    Polynomial Identity Testing for Low Degree Polynomials with Optimal Randomness
    Authors: Bläser, Markus ; Pandey, Anurag

    Abstract | Document (536 KB) | BibTeX

    Bounds for List-Decoding and List-Recovery of Random Linear Codes
    Authors: Guruswami, Venkatesan ; Li, Ray ; Mosheiff, Jonathan ; Resch, Nicolas ; Silas, Shashwat ; Wootters, Mary

    Abstract | Document (586 KB) | BibTeX

    Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?
    Authors: Shaltiel, Ronen

    Abstract | Document (663 KB) | BibTeX

    Balanced Allocation on Dynamic Hypergraphs
    Authors: Greenhill, Catherine ; Mans, Bernard ; Pourmiri, Ali

    Abstract | Document (599 KB) | BibTeX

    The GaussianSketch for Almost Relative Error Kernel Distance
    Authors: Phillips, Jeff M. ; Tai, Wai Ming

    Abstract | Document (674 KB) | BibTeX

    A Fast Binary Splitting Approach to Non-Adaptive Group Testing
    Authors: Price, Eric ; Scarlett, Jonathan

    Abstract | Document (594 KB) | BibTeX

    Maximum Shallow Clique Minors in Preferential Attachment Graphs Have Polylogarithmic Size
    Authors: Dreier, Jan ; Kuinke, Philipp ; Rossmanith, Peter

    Abstract | Document (493 KB) | BibTeX

    On Nonadaptive Security Reductions of Hitting Set Generators
    Authors: Hirahara, Shuichi ; Watanabe, Osamu

    Abstract | Document (495 KB) | BibTeX

    Testable Properties in General Graphs and Random Order Streaming
    Authors: Czumaj, Artur ; Fichtenberger, Hendrik ; Peng, Pan ; Sohler, Christian

    Abstract | Document (596 KB) | BibTeX

    Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs
    Authors: Beideman, Calvin ; Chandrasekaran, Karthekeyan ; Xu, Chao

    Abstract | Document (639 KB) | BibTeX

    On Testing and Robust Characterizations of Convexity
    Authors: Blais, Eric ; Bommireddi, Abhinav

    Abstract | Document (506 KB) | BibTeX

    Distributed Testing of Graph Isomorphism in the CONGEST Model
    Authors: Levi, Reut ; Medina, Moti

    Abstract | Document (699 KB) | BibTeX

    Reaching a Consensus on Random Networks: The Power of Few
    Authors: Tran, Linh ; Vu, Van

    Abstract | Document (527 KB) | BibTeX

    Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG
    Authors: Garg, Sumegha ; Kothari, Pravesh K. ; Raz, Ran

    Abstract | Document (604 KB) | BibTeX

    Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
    Authors: Chakrabarti, Amit ; Ghosh, Prantar ; Thaler, Justin

    Abstract | Document (663 KB) | BibTeX

    Disjointness Through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond
    Authors: Bhattacharya, Anup ; Chakraborty, Sourav ; Ghosh, Arijit ; Mishra, Gopinath ; Paraashar, Manaswi

    Abstract | Document (613 KB) | BibTeX

    Testing Data Binnings
    Authors: Canonne, Clément L. ; Wimmer, Karl

    Abstract | Document (624 KB) | BibTeX

    Chernoff Bound for High-Dimensional Expanders
    Authors: Kaufman, Tali ; Sharakanski, Ella

    Abstract | Document (545 KB) | BibTeX

    Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
    Authors: Rashtchian, Cyrus ; Woodruff, David P. ; Zhu, Hanlin

    Abstract | Document (598 KB) | BibTeX

    Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
    Authors: Ron, Dana ; Rosin, Asaf

    Abstract | Document (606 KB) | BibTeX

    When Is Amplification Necessary for Composition in Randomized Query Complexity?
    Authors: Ben-David, Shalev ; Göös, Mika ; Kothari, Robin ; Watson, Thomas

    Abstract | Document (624 KB) | BibTeX

    On Multilinear Forms: Bias, Correlation, and Tensor Rank
    Authors: Bhrushundi, Abhishek ; Harsha, Prahladh ; Hatami, Pooya ; Kopparty, Swastik ; Kumar, Mrinal

    Abstract | Document (561 KB) | BibTeX

    On the List Recoverability of Randomly Punctured Codes
    Authors: Lund, Ben ; Potukuchi, Aditya

    Abstract | Document (449 KB) | BibTeX

    On Perturbation Resilience of Non-Uniform k-Center
    Authors: Bandyapadhyay, Sayan

    Abstract | Document (635 KB) | BibTeX

    Low-Rank Binary Matrix Approximation in Column-Sum Norm
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Panolan, Fahad ; Simonov, Kirill

    Abstract | Document (699 KB) | BibTeX

    Pinning down the Strong Wilber 1 Bound for Binary Search Trees
    Authors: Chalermsook, Parinya ; Chuzhoy, Julia ; Saranurak, Thatchaphol

    Abstract | Document (732 KB) | BibTeX

    Revisiting Alphabet Reduction in Dinur’s PCP
    Authors: Guruswami, Venkatesan ; Opršal, Jakub ; Sandeep, Sai

    Abstract | Document (487 KB) | BibTeX

    L_p Pattern Matching in a Stream
    Authors: Starikovskaya, Tatiana ; Svagerka, Michal ; Uznański, Przemysław

    Abstract | Document (651 KB) | BibTeX

    Computing Bi-Lipschitz Outlier Embeddings into the Line
    Authors: Chubarian, Karine ; Sidiropoulos, Anastasios

    Abstract | Document (625 KB) | BibTeX

    Online Minimum Cost Matching with Recourse on the Line
    Authors: Megow, Nicole ; Nölke, Lukas

    Abstract | Document (514 KB) | BibTeX

    Hardness of Approximation of (Multi-)LCS over Small Alphabet
    Authors: Bhangale, Amey ; Chakraborty, Diptarka ; Kumar, Rajendra

    Abstract | Document (532 KB) | BibTeX

    On Approximating Degree-Bounded Network Design Problems
    Authors: Guo, Xiangyu ; Kortsarz, Guy ; Laekhanukit, Bundit ; Li, Shi ; Vaz, Daniel ; Xian, Jiayi

    Abstract | Document (631 KB) | BibTeX

    Permutation Strikes Back: The Power of Recourse in Online Metric Matching
    Authors: Gupta, Varun ; Krishnaswamy, Ravishankar ; Sandeep, Sai

    Abstract | Document (594 KB) | BibTeX

    How to Cut a Ball Without Separating: Improved Approximations for Length Bounded Cut
    Authors: Chlamtáč, Eden ; Kolman, Petr

    Abstract | Document (1,412 KB) | BibTeX

    On the Facility Location Problem in Online and Dynamic Models
    Authors: Guo, Xiangyu ; Kulkarni, Janardhan ; Li, Shi ; Xian, Jiayi

    Abstract | Document (598 KB) | BibTeX

    Nearly Optimal Embeddings of Flat Tori
    Authors: Agarwal, Ishan ; Regev, Oded ; Tang, Yi

    Abstract | Document (494 KB) | BibTeX

    A Tight (3/2+ε) Approximation for Skewed Strip Packing
    Authors: Gálvez, Waldo ; Grandoni, Fabrizio ; Ameli, Afrouz Jabal ; Jansen, Klaus ; Khan, Arindam ; Rau, Malin

    Abstract | Document (580 KB) | BibTeX

    Learning Lines with Ordinal Constraints
    Authors: Fan, Bohan ; Ihara, Diego ; Mohammadi, Neshat ; Sgherzi, Francesco ; Sidiropoulos, Anastasios ; Valizadeh, Mina

    Abstract | Document (483 KB) | BibTeX

    Improved Circular k-Mismatch Sketches
    Authors: Golan, Shay ; Kociumaka, Tomasz ; Kopelowitz, Tsvi ; Porat, Ely ; Uznański, Przemysław

    Abstract | Document (653 KB) | BibTeX

    On Guillotine Separability of Squares and Rectangles
    Authors: Khan, Arindam ; Pittu, Madhusudhan Reddy

    Abstract | Document (546 KB) | BibTeX

    Maximizing Throughput in Flow Shop Real-Time Scheduling
    Authors: Ben Yamin, Lior ; Li, Jing ; Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas

    Abstract | Document (572 KB) | BibTeX

    Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains
    Authors: Katzelnick, Dor ; Schwartz, Roy

    Abstract | Document (604 KB) | BibTeX

    Streaming Complexity of SVMs
    Authors: Andoni, Alexandr ; Burns, Collin ; Li, Yi ; Mahabadi, Sepideh ; Woodruff, David P.

    Abstract | Document (577 KB) | BibTeX

    On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
    Authors: Gunda, Spoorthy ; Jain, Pallavi ; Lokshtanov, Daniel ; Saurabh, Saket ; Tale, Prafullkumar

    Abstract | Document (735 KB) | BibTeX

    Online Coloring of Short Intervals
    Authors: Chybowska-Sokół, Joanna ; Gutowski, Grzegorz ; Junosza-Szaniawski, Konstanty ; Mikos, Patryk ; Polak, Adam

    Abstract | Document (663 KB) | BibTeX

    Approximating Requirement Cut via a Configuration LP
    Authors: Schwartz, Roy ; Sharoni, Yotam

    Abstract | Document (584 KB) | BibTeX

    Parametrized Metrical Task Systems
    Authors: Bubeck, Sébastien ; Rabani, Yuval

    Abstract | Document (427 KB) | BibTeX

    A Constant Factor Approximation for Capacitated Min-Max Tree Cover
    Authors: Das, Syamantak ; Jain, Lavina ; Kumar, Nikhil

    Abstract | Document (471 KB) | BibTeX

    An Extension of Plücker Relations with Applications to Subdeterminant Maximization
    Authors: Anari, Nima ; Vuong, Thuy-Duong

    Abstract | Document (494 KB) | BibTeX

    Approximating Star Cover Problems
    Authors: Gamlath, Buddhima ; Grinberg, Vadim

    Abstract | Document (622 KB) | BibTeX

    On the Approximability of Presidential Type Predicates
    Authors: Huang, Neng ; Potechin, Aaron

    Abstract | Document (527 KB) | BibTeX

    An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem
    Authors: Hallgren, Sean ; Lee, Eunou ; Parekh, Ojas

    Abstract | Document (460 KB) | BibTeX

    Better and Simpler Learning-Augmented Online Caching
    Authors: Wei, Alexander

    Abstract | Document (541 KB) | BibTeX

    A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
    Authors: Boyd, Sylvia ; Cheriyan, Joseph ; Cummings, Robert ; Grout, Logan ; Ibrahimpur, Sharat ; Szigeti, Zoltán ; Wang, Lu

    Abstract | Document (504 KB) | BibTeX

    Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints
    Authors: Huang, Chien-Chung ; Thiery, Theophile ; Ward, Justin

    Abstract | Document (589 KB) | BibTeX

    Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
    Authors: Chan, Chun-Hsiang ; Laekhanukit, Bundit ; Wei, Hao-Ting ; Zhang, Yuhao

    Abstract | Document (600 KB) | BibTeX

    Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
    Authors: Bakshi, Ainesh ; Chepurko, Nadiia ; Woodruff, David P.

    Abstract | Document (719 KB) | BibTeX

      




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