APPROX/RANDOM 2021 August 16-18, 2021, University of Washington, Seattle, Washington, US (Virtual Conference)

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



Mary Wootters and Laura Sanità (Eds.)
ISBN 978-3-95977-207-5, LIPICS Vol. 207 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors
  • Albers, Susanne
  • Alrabiah, Omar
  • Ameli, Afrouz Jabal
  • Arutyunova, Anna
  • Assadi, Sepehr
  • Balogh, János
  • Banerjee, Sandip
  • Behnezhad, Soheil
  • Ben Yaacov, Inbar
  • Bhandari, Siddharth
  • Bhargava, Vishwas
  • Bhaskar, Umang
  • Bhattacharya, Anup
  • Bhawalkar, Kshipra
  • Bishnu, Arijit
  • Biswas, Amartya Shankha
  • Blanc, Guy
  • Blanca, Antonio
  • Borndörfer, Ralf
  • Borodin, Allan
  • Brakerski, Zvika
  • Bringmann, Karl
  • Brubach, Brian
  • Błasiok, Jarosław
  • Casel, Katrin
  • Cassis, Alejandro
  • Chakraborty, Sourav
  • Chekuri, Chandra
  • Chen, Zongchen
  • Cohen, Gil
  • Cohen, Ilan Reuven
  • Dani, Varsha
  • Deppert, Max A.
  • Doron, Dean
  • Eden, Talya
  • Epstein, Leah
  • Fairstein, Yaron
  • Fischer, Nick
  • Galanis, Andreas
  • Garg, Sumegha
  • Ghosh, Arijit
  • Ghosh, Sumanta
  • Girish, Uma
  • Goldberg, Leslie Ann
  • Golowich, Louis
  • Goyal, Dishant
  • Goyal, Vineet
  • Grammel, Nathaniel
  • Grandoni, Fabrizio
  • Grigorescu, Elena
  • Großwendt, Anna
  • Gupta, Anupam
  • Gupta, Diksha
  • Gurjar, Rohit
  • Guruswami, Venkatesan
  • Gálvez, Waldo
  • Göke, Alexander
  • Hanguir, Oussama
  • Harris, David G.
  • Harsha, Prahladh
  • Hayes, Thomas P.
  • Holmgren, Justin
  • Housni, Omar El
  • Hoza, William M.
  • Huang, Chien-Chung
  • Iliopoulos, Fotis
  • Issac, Davis
  • Ivanov, Peter
  • Jaiswal, Ragesh
  • Jansen, Klaus
  • Jayaram, Rajesh
  • Jin, Yaonan
  • Jowhari, Hossein
  • Kallaugher, John
  • Karingula, Sankeerth Rao
  • Khan, Arindam
  • Khodamoradi, Kamyar
  • Kim, Eun Jung
  • Koenemann, Jochen
  • Kollias, Kostas
  • Kolmogorov, Vladimir
  • Konrad, Christian
  • Kothari, Pravesh K.
  • Kulik, Ariel
  • Kumar, Amit
  • Kumar, Mrinal
  • Künnemann, Marvin
  • Lange, Jane
  • Lee, Chin Ho
  • Lee, Euiwoong
  • Levi, Reut
  • Levin, Asaf
  • Li, Yi
  • Lin, Young-San
  • Liu, Kuikui
  • Liu, Pengda
  • Lovett, Shachar
  • MacRury, Calum
  • Meka, Raghu
  • Mishra, Gopinath
  • Mittal, Kunal
  • Mnich, Matthias
  • Mossel, Saleet
  • Naidu, Kheeran K.
  • Naor, Joseph (Seffi)
  • Narayanan, Anand Kumar
  • Niklanovits, Aikaterini
  • Ostrovsky, Rafail
  • Paraashar, Manaswi
  • Parulekar, Aditya
  • Parulekar, Advait
  • Price, Eric
  • Purohit, Manish
  • Qiao, Mingda
  • Quanrud, Kent
  • Rabani, Yuval
  • Rajgopal, Ninad
  • Rakheja, Akash
  • Rau, Malin
  • Raz, Danny
  • Raz, Ran
  • Reingold, Omer
  • Rubinfeld, Ronitt
  • Röglin, Heiko
  • Saha, Chandan
  • Sanità, Laura
  • Santhanam, Rahul
  • Schmidt, Melanie
  • Schubert, Sebastian
  • Schwartz, Stephan
  • Sellier, François
  • Sen, Sayantan
  • Servedio, Rocco A.
  • Shah, Rikhav
  • Sharma, Eklavya
  • Shoshan, Nadav
  • Silwal, Sandeep
  • Sinclair, Alistair
  • Singer, Noah
  • Singla, Sahil
  • Sricharan, A. R.
  • Srinivasan, Aravind
  • Srinivasan, Srikanth
  • Stein, Clifford
  • Stephens-Davidowitz, Noah
  • Stewart, James
  • Sudan, Madhu
  • Sun, Hao
  • Tal, Avishay
  • Tan, Li-Yang
  • Thankey, Bhargav
  • Thilikos, Dimitrios M.
  • Torres, Manuel R.
  • Tsepenekas, Leonidas
  • Tutas, Malte
  • Vadhan, Salil
  • Vaikuntanathan, Vinod
  • Vaish, Rohit
  • Velusamy, Santhoshini
  • Venkitesh, S.
  • Vigoda, Eric
  • Viola, Emanuele
  • Vullikanti, Anil
  • Wargalla, Julian
  • Woodruff, David P.
  • Wootters, Mary
  • Zeif, Ziena
  • Zhan, Wei
  • Zhang, Xusheng
  • Štefankovič, Daniel
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Wootters, Mary ; Sanità, Laura

    Abstract | Document (454 KB) | BibTeX

    On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
    Authors: Bhaskar, Umang ; Sricharan, A. R. ; Vaish, Rohit

    Abstract | Document (798 KB) | BibTeX

    Optimal Algorithms for Online b-Matching with Variable Vertex Capacities
    Authors: Albers, Susanne ; Schubert, Sebastian

    Abstract | Document (768 KB) | BibTeX

    Bag-Of-Tasks Scheduling on Related Machines
    Authors: Gupta, Anupam ; Kumar, Amit ; Singla, Sahil

    Abstract | Document (747 KB) | BibTeX

    Hardness of Approximation for Euclidean k-Median
    Authors: Bhattacharya, Anup ; Goyal, Dishant ; Jaiswal, Ragesh

    Abstract | Document (842 KB) | BibTeX

    Online Directed Spanners and Steiner Forests
    Authors: Grigorescu, Elena ; Lin, Young-San ; Quanrud, Kent

    Abstract | Document (964 KB) | BibTeX

    Query Complexity of Global Minimum Cut
    Authors: Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath ; Paraashar, Manaswi

    Abstract | Document (815 KB) | BibTeX

    A Constant-Factor Approximation for Weighted Bond Cover
    Authors: Kim, Eun Jung ; Lee, Euiwoong ; Thilikos, Dimitrios M.

    Abstract | Document (829 KB) | BibTeX

    Truly Asymptotic Lower Bounds for Online Vector Bin Packing
    Authors: Balogh, János ; Cohen, Ilan Reuven ; Epstein, Leah ; Levin, Asaf

    Abstract | Document (722 KB) | BibTeX

    Fine-Grained Completeness for Optimization in P
    Authors: Bringmann, Karl ; Cassis, Alejandro ; Fischer, Nick ; Künnemann, Marvin

    Abstract | Document (835 KB) | BibTeX

    An Estimator for Matching Size in Low Arboricity Graphs with Two Applications
    Authors: Jowhari, Hossein

    Abstract | Document (697 KB) | BibTeX

    An Optimal Algorithm for Triangle Counting in the Stream
    Authors: Jayaram, Rajesh ; Kallaugher, John

    Abstract | Document (642 KB) | BibTeX

    Matching Drivers to Riders: A Two-Stage Robust Approach
    Authors: Housni, Omar El ; Goyal, Vineet ; Hanguir, Oussama ; Stein, Clifford

    Abstract | Document (796 KB) | BibTeX

    Secretary Matching Meets Probing with Commitment
    Authors: Borodin, Allan ; MacRury, Calum ; Rakheja, Akash

    Abstract | Document (840 KB) | BibTeX

    Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching Constraint
    Authors: Huang, Chien-Chung ; Sellier, François

    Abstract | Document (715 KB) | BibTeX

    General Knapsack Problems in a Dynamic Setting
    Authors: Fairstein, Yaron ; Kulik, Ariel ; Naor, Joseph (Seffi) ; Raz, Danny

    Abstract | Document (709 KB) | BibTeX

    Min-Sum Clustering (With Outliers)
    Authors: Banerjee, Sandip ; Ostrovsky, Rafail ; Rabani, Yuval

    Abstract | Document (713 KB) | BibTeX

    Streaming Approximation Resistance of Every Ordering CSP
    Authors: Singer, Noah ; Sudan, Madhu ; Velusamy, Santhoshini

    Abstract | Document (967 KB) | BibTeX

    Upper and Lower Bounds for Complete Linkage in General Metric Spaces
    Authors: Arutyunova, Anna ; Großwendt, Anna ; Röglin, Heiko ; Schmidt, Melanie ; Wargalla, Julian

    Abstract | Document (712 KB) | BibTeX

    On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
    Authors: Konrad, Christian ; Naidu, Kheeran K.

    Abstract | Document (1,104 KB) | BibTeX

    Approximation Algorithms for Demand Strip Packing
    Authors: Gálvez, Waldo ; Grandoni, Fabrizio ; Ameli, Afrouz Jabal ; Khodamoradi, Kamyar

    Abstract | Document (961 KB) | BibTeX

    Peak Demand Minimization via Sliced Strip Packing
    Authors: Deppert, Max A. ; Jansen, Klaus ; Khan, Arindam ; Rau, Malin ; Tutas, Malte

    Abstract | Document (912 KB) | BibTeX

    Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
    Authors: Khan, Arindam ; Sharma, Eklavya

    Abstract | Document (869 KB) | BibTeX

    Approximating Two-Stage Stochastic Supplier Problems
    Authors: Brubach, Brian ; Grammel, Nathaniel ; Harris, David G. ; Srinivasan, Aravind ; Tsepenekas, Leonidas ; Vullikanti, Anil

    Abstract | Document (824 KB) | BibTeX

    Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
    Authors: Chekuri, Chandra ; Quanrud, Kent ; Torres, Manuel R.

    Abstract | Document (795 KB) | BibTeX

    Hitting Weighted Even Cycles in Planar Graphs
    Authors: Göke, Alexander ; Koenemann, Jochen ; Mnich, Matthias ; Sun, Hao

    Abstract | Document (1,136 KB) | BibTeX

    Revenue Maximization in Transportation Networks
    Authors: Bhawalkar, Kshipra ; Kollias, Kostas ; Purohit, Manish

    Abstract | Document (859 KB) | BibTeX

    Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs
    Authors: Borndörfer, Ralf ; Casel, Katrin ; Issac, Davis ; Niklanovits, Aikaterini ; Schwartz, Stephan ; Zeif, Ziena

    Abstract | Document (854 KB) | BibTeX

    Better Pseudodistributions and Derandomization for Space-Bounded Computation
    Authors: Hoza, William M.

    Abstract | Document (885 KB) | BibTeX

    On the Hardness of Average-Case k-SUM
    Authors: Brakerski, Zvika ; Stephens-Davidowitz, Noah ; Vaikuntanathan, Vinod

    Abstract | Document (739 KB) | BibTeX

    Improved Hitting Set for Orbit of ROABPs
    Authors: Bhargava, Vishwas ; Ghosh, Sumanta

    Abstract | Document (881 KB) | BibTeX

    A New Notion of Commutativity for the Algorithmic Lovász Local Lemma
    Authors: Harris, David G. ; Iliopoulos, Fotis ; Kolmogorov, Vladimir

    Abstract | Document (786 KB) | BibTeX

    From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk
    Authors: Liu, Kuikui

    Abstract | Document (818 KB) | BibTeX

    Singularity of Random Integer Matrices with Large Entries
    Authors: Karingula, Sankeerth Rao ; Lovett, Shachar

    Abstract | Document (704 KB) | BibTeX

    Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds
    Authors: Chakraborty, Sourav ; Ghosh, Arijit ; Mishra, Gopinath ; Sen, Sayantan

    Abstract | Document (931 KB) | BibTeX

    The Product of Gaussian Matrices Is Close to Gaussian
    Authors: Li, Yi ; Woodruff, David P.

    Abstract | Document (750 KB) | BibTeX

    Fast Mixing via Polymers for Random Graphs with Unbounded Degree
    Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Stewart, James

    Abstract | Document (649 KB) | BibTeX

    Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma
    Authors: Servedio, Rocco A. ; Tan, Li-Yang

    Abstract | Document (884 KB) | BibTeX

    Improved Product-Based High-Dimensional Expanders
    Authors: Golowich, Louis

    Abstract | Document (707 KB) | BibTeX

    Improved Bounds for Coloring Locally Sparse Hypergraphs
    Authors: Iliopoulos, Fotis

    Abstract | Document (660 KB) | BibTeX

    Smoothed Analysis of the Condition Number Under Low-Rank Perturbations
    Authors: Shah, Rikhav ; Silwal, Sandeep

    Abstract | Document (809 KB) | BibTeX

    Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision
    Authors: Ghosh, Sumanta ; Gurjar, Rohit

    Abstract | Document (726 KB) | BibTeX

    On the Probabilistic Degree of an n-Variate Boolean Function
    Authors: Srinivasan, Srikanth ; Venkitesh, S.

    Abstract | Document (799 KB) | BibTeX

    The Swendsen-Wang Dynamics on Trees
    Authors: Blanca, Antonio ; Chen, Zongchen ; Štefankovič, Daniel ; Vigoda, Eric

    Abstract | Document (759 KB) | BibTeX

    Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
    Authors: Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

    Abstract | Document (1,020 KB) | BibTeX

    Decision Tree Heuristics Can Fail, Even in the Smoothed Setting
    Authors: Blanc, Guy ; Lange, Jane ; Qiao, Mingda ; Tan, Li-Yang

    Abstract | Document (713 KB) | BibTeX

    On the Structure of Learnability Beyond P/Poly
    Authors: Rajgopal, Ninad ; Santhanam, Rahul

    Abstract | Document (858 KB) | BibTeX

    The Critical Mean-Field Chayes-Machta Dynamics
    Authors: Blanca, Antonio ; Sinclair, Alistair ; Zhang, Xusheng

    Abstract | Document (667 KB) | BibTeX

    On the Robust Communication Complexity of Bipartite Matching
    Authors: Assadi, Sepehr ; Behnezhad, Soheil

    Abstract | Document (766 KB) | BibTeX

    L1 Regression with Lewis Weights Subsampling
    Authors: Parulekar, Aditya ; Parulekar, Advait ; Price, Eric

    Abstract | Document (781 KB) | BibTeX

    Hitting Sets for Orbits of Circuit Classes and Polynomial Families
    Authors: Saha, Chandan ; Thankey, Bhargav

    Abstract | Document (935 KB) | BibTeX

    Sampling Multiple Edges Efficiently
    Authors: Eden, Talya ; Mossel, Saleet ; Rubinfeld, Ronitt

    Abstract | Document (811 KB) | BibTeX

    Lower Bounds for XOR of Forrelations
    Authors: Girish, Uma ; Raz, Ran ; Zhan, Wei

    Abstract | Document (809 KB) | BibTeX

    Fourier Growth of Structured 𝔽₂-Polynomials and Applications
    Authors: Błasiok, Jarosław ; Ivanov, Peter ; Jin, Yaonan ; Lee, Chin Ho ; Servedio, Rocco A. ; Viola, Emanuele

    Abstract | Document (849 KB) | BibTeX

    Candidate Tree Codes via Pascal Determinant Cubes
    Authors: Ben Yaacov, Inbar ; Cohen, Gil ; Narayanan, Anand Kumar

    Abstract | Document (802 KB) | BibTeX

    Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
    Authors: Biswas, Amartya Shankha ; Eden, Talya ; Rubinfeld, Ronitt

    Abstract | Document (977 KB) | BibTeX

    Ideal-Theoretic Explanation of Capacity-Achieving Decoding
    Authors: Bhandari, Siddharth ; Harsha, Prahladh ; Kumar, Mrinal ; Sudan, Madhu

    Abstract | Document (811 KB) | BibTeX

    Visible Rank and Codes with Locality
    Authors: Alrabiah, Omar ; Guruswami, Venkatesan

    Abstract | Document (685 KB) | BibTeX

    Pseudorandom Generators for Read-Once Monotone Branching Programs
    Authors: Doron, Dean ; Meka, Raghu ; Reingold, Omer ; Tal, Avishay ; Vadhan, Salil

    Abstract | Document (801 KB) | BibTeX

    On the Power of Choice for k-Colorability of Random Graphs
    Authors: Dani, Varsha ; Gupta, Diksha ; Hayes, Thomas P.

    Abstract | Document (725 KB) | BibTeX

    Memory-Sample Lower Bounds for Learning Parity with Noise
    Authors: Garg, Sumegha ; Kothari, Pravesh K. ; Liu, Pengda ; Raz, Ran

    Abstract | Document (774 KB) | BibTeX

    Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs
    Authors: Levi, Reut ; Shoshan, Nadav

    Abstract | Document (869 KB) | BibTeX

    Parallel Repetition for the GHZ Game: A Simpler Proof
    Authors: Girish, Uma ; Holmgren, Justin ; Mittal, Kunal ; Raz, Ran ; Zhan, Wei

    Abstract | Document (742 KB) | BibTeX

    		  



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