APPROX/RANDOM 2023 September 11-13, 2023, Atlanta, Georgia, USA

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



Nicole Megow and Adam Smith (Eds.)
ISBN 978-3-95977-296-9, LIPICS Vol. 275 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 20 MB)
Search Publication Server

Authors
  • Abboud, Amir
  • Abdolazimi, Dorna
  • Allender, Eric
  • Amireddy, Prashanth
  • Anand, Konrad
  • Arviv, Rubi
  • Ashvinkumar, Vikrant
  • Assadi, Sepehr
  • Ayyadevara, Nikhil
  • Bajpai, Tanvi
  • Bansal, Ishan
  • Bansal, Nikhil
  • Bateni, MohammadHossein
  • Becker, Ruben
  • Bennett, Huck
  • Berman, Piotr
  • Bishnu, Arijit
  • Blanca, Antonio
  • Blocki, Jeremiah
  • Bogdanov, Andrej
  • Braverman, Vladimir
  • Bshouty, Nader H.
  • Casteigts, Arnaud
  • Chakraborty, Sourav
  • Chandrasekaran, Karthekeyan
  • Chawla, Shuchi
  • Chekuri, Chandra
  • Chen, Xi
  • Cheriyan, Joe
  • Cheung, Tsun Ming
  • Chlamtáč, Eden
  • Chung, Lily
  • Cohen-Addad, Vincent
  • Coja-Oghlan, Amin
  • Cook, Joshua
  • Crescenzi, Pierluigi
  • de Berg, Mark
  • Deng, Chengyuan
  • Deryckere, Lindsey
  • Dinesh, Krishnamoorthy
  • Doron-Arad, Ilan
  • Dürr, Anita
  • Eden, Talya
  • Efthymiou, Charilaos
  • El Maalouly, Nicolas
  • Feldmann, Andreas Emil
  • Ferreira Pinto Jr., Renato
  • Filmus, Yuval
  • Foos, Josefine
  • Friggstad, Zachary
  • Gajulapalli, Karthik
  • Galanis, Andreas
  • Gao, Jane
  • Gao, Jie
  • Gergatsouli, Evangelia
  • Gharan, Shayan Oveis
  • Ghosh, Arijit
  • Gishboliner, Lior
  • Goldberg, Leslie Ann
  • Golovnev, Alexander
  • Gotlib, Roy
  • Gray, Jacob
  • Grigorescu, Elena
  • Grout, Logan
  • Guo, Siyao
  • Gupta, Anupam
  • Gupta, Meghal
  • Guruswami, Venkatesan
  • Göbel, Andreas
  • Hahn-Klimroth, Max
  • Hayes, Thomas P.
  • Hecht, Yahli
  • Held, Stephan
  • Houen, Jakob Bæk Tejs
  • Höhne, Felix
  • Ibrahimpur, Sharat
  • Impagliazzo, Russell
  • Jeronimo, Fernando Granha
  • Jin, Yaonan
  • Kabanets, Valentine
  • Kapralov, Michael
  • Karakostas, George
  • Karayel, Emin
  • Karthik C. S.
  • Kashaev, Danish
  • Kaufman, Tali
  • Kayal, Chandrima
  • Ke, Yiduo
  • Khuller, Samir
  • Kodric, Bojana
  • Kolliopoulos, Stavros G.
  • Kopparty, Swastik
  • Kulik, Ariel
  • Kumar, Amit
  • Kumar, Nithish
  • Kushnir, Nick
  • Lau, Lap Chi
  • Lee, Chin Ho
  • Lee, Joon
  • Leigh, Itai
  • Lengler, Johannes
  • Levi, Reut
  • Li, Shilun
  • Lieskovský, Matej
  • Lin, Young-San
  • Lindberg, Kasper
  • Liu, Quanquan C.
  • Lui, John C. S.
  • Mahabadi, Sepideh
  • Makarychev, Yury
  • Manning, Joel
  • Martinsson, Anders
  • McMahan, Jeremy
  • Megow, Nicole
  • Minzer, Dor
  • Mishra, Gopinath
  • Mittal, Rajat
  • Monemizadeh, Morteza
  • Moshkovitz, Dana
  • Mousavi, Ramin
  • Mukherjee, Tamalika
  • Munagala, Kamesh
  • Murzabulatov, Meiram
  • Mutreja, Saachi
  • Müller, Noela
  • N, Vishvajeet
  • Nagargoje, Satyajeet
  • Narayanan, Shyam
  • Panigrahi, Debmalya
  • Pappik, Marcus
  • Paraashar, Manaswi
  • Patton, Kalen
  • Peikert, Chris
  • Perkins, Will
  • Peters, Spencer
  • Petrova, Kalina
  • Prabhu, Milind
  • Pyne, Edward
  • Quanrud, Kent
  • Randolph, Tim
  • Raskhodnikova, Sofya
  • Raskin, Michael
  • Renken, Malte
  • Riazanov, Artur
  • Ristache, Dragos
  • Rolvien, Maurice
  • Rosenbaum, Will
  • Rothblum, Ron D.
  • Russo, Matteo
  • Sadhukhan, Arpan
  • Safra, Muli
  • Sankar, Govind S.
  • Sanyal, Swagato
  • Saraogi, Sidhant
  • Saurabh, Nitin
  • Schnider, Patrick
  • Schäfer, Guido
  • Seddighin, Saeed
  • Servedio, Rocco A.
  • Sgall, Jiří
  • Shachnai, Hadas
  • Shapira, Asaf
  • Singer, Noah G.
  • Singla, Sahil
  • Smith, Adam
  • Smolarova, Paulina
  • Sokolov, Dmitry
  • Spieksma, Frits
  • Spitzley, Yannik Kyle Dustin
  • Srinivasan, Srikanth
  • Steiner, Raphael
  • Stephens-Davidowitz, Noah
  • Sudan, Madhu
  • Taylor, Erin
  • Tirumala, Harsha
  • Tzamos, Christos
  • Tětek, Jakub
  • Umboh, Seeun William
  • Vadhan, Salil
  • Vakilian, Ali
  • van Stee, Rob
  • Vigoda, Eric
  • Volkovich, Ilya
  • Wang, Chen
  • Wang, Pengxiang
  • Wang, Robert
  • Wang, Weihang
  • Weber, Simon
  • Welzl, Emo
  • Wu, Zhiwei Steven
  • Wulf, Lasse
  • Yu, Huacheng
  • Zamaraev, Viktor
  • Zhang, Rachel Yun
  • Zhang, Xusheng
  • Zhou, Hong
  • Zhou, Samson
  • Štefankovič, Daniel
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Megow, Nicole ; Smith, Adam

    Abstract | Document (608 KB) | BibTeX

    On Complexity of 1-Center in Various Metrics
    Authors: Abboud, Amir ; Bateni, MohammadHossein ; Cohen-Addad, Vincent ; Karthik C. S. ; Seddighin, Saeed

    Abstract | Document (894 KB) | BibTeX

    Probabilistic Metric Embedding via Metric Labeling
    Authors: Munagala, Kamesh ; Sankar, Govind S. ; Taylor, Erin

    Abstract | Document (617 KB) | BibTeX

    Approximating Submodular k-Partition via Principal Partition Sequence
    Authors: Chandrasekaran, Karthekeyan ; Wang, Weihang

    Abstract | Document (802 KB) | BibTeX

    Experimental Design for Any p-Norm
    Authors: Lau, Lap Chi ; Wang, Robert ; Zhou, Hong

    Abstract | Document (891 KB) | BibTeX

    Approximation Algorithms for Maximum Weighted Throughput on Unrelated Machines
    Authors: Karakostas, George ; Kolliopoulos, Stavros G.

    Abstract | Document (766 KB) | BibTeX

    Facility Location in the Sublinear Geometric Model
    Authors: Monemizadeh, Morteza

    Abstract | Document (1,216 KB) | BibTeX

    Bicriteria Approximation Algorithms for Priority Matroid Median
    Authors: Bajpai, Tanvi ; Chekuri, Chandra

    Abstract | Document (960 KB) | BibTeX

    Approximation Algorithms for Directed Weighted Spanners
    Authors: Grigorescu, Elena ; Kumar, Nithish ; Lin, Young-San

    Abstract | Document (1,023 KB) | BibTeX

    Approximation Algorithms and Lower Bounds for Graph Burning
    Authors: Lieskovský, Matej ; Sgall, Jiří ; Feldmann, Andreas Emil

    Abstract | Document (791 KB) | BibTeX

    The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems
    Authors: Golovnev, Alexander ; Guo, Siyao ; Peters, Spencer ; Stephens-Davidowitz, Noah

    Abstract | Document (722 KB) | BibTeX

    Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
    Authors: Chlamtáč, Eden ; Makarychev, Yury ; Vakilian, Ali

    Abstract | Document (829 KB) | BibTeX

    Efficient Algorithms and Hardness Results for the Weighted k-Server Problem
    Authors: Gupta, Anupam ; Kumar, Amit ; Panigrahi, Debmalya

    Abstract | Document (816 KB) | BibTeX

    A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free Graphs
    Authors: Friggstad, Zachary ; Mousavi, Ramin

    Abstract | Document (784 KB) | BibTeX

    Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of Terminals
    Authors: Bansal, Ishan ; Cheriyan, Joe ; Grout, Logan ; Ibrahimpur, Sharat

    Abstract | Document (852 KB) | BibTeX

    Oblivious Algorithms for the Max-kAND Problem
    Authors: Singer, Noah G.

    Abstract | Document (963 KB) | BibTeX

    A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs
    Authors: Höhne, Felix ; van Stee, Rob

    Abstract | Document (774 KB) | BibTeX

    Online Matching with Set and Concave Delays
    Authors: Deryckere, Lindsey ; Umboh, Seeun William

    Abstract | Document (798 KB) | BibTeX

    An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
    Authors: Dürr, Anita ; El Maalouly, Nicolas ; Wulf, Lasse

    Abstract | Document (924 KB) | BibTeX

    Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
    Authors: Foos, Josefine ; Held, Stephan ; Spitzley, Yannik Kyle Dustin

    Abstract | Document (808 KB) | BibTeX

    Round and Bipartize for Vertex Cover Approximation
    Authors: Kashaev, Danish ; Schäfer, Guido

    Abstract | Document (957 KB) | BibTeX

    On Minimizing Generalized Makespan on Unrelated Machines
    Authors: Ayyadevara, Nikhil ; Bansal, Nikhil ; Prabhu, Milind

    Abstract | Document (667 KB) | BibTeX

    An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding
    Authors: Doron-Arad, Ilan ; Kulik, Ariel ; Shachnai, Hadas

    Abstract | Document (955 KB) | BibTeX

    Submodular Norms with Applications To Online Facility Location and Stochastic Probing
    Authors: Patton, Kalen ; Russo, Matteo ; Singla, Sahil

    Abstract | Document (876 KB) | BibTeX

    Independent Sets in Elimination Graphs with a Submodular Objective
    Authors: Chekuri, Chandra ; Quanrud, Kent

    Abstract | Document (824 KB) | BibTeX

    Improved Diversity Maximization Algorithms for Matching and Pseudoforest
    Authors: Mahabadi, Sepideh ; Narayanan, Shyam

    Abstract | Document (809 KB) | BibTeX

    Approximating Pandora’s Box with Correlations
    Authors: Chawla, Shuchi ; Gergatsouli, Evangelia ; McMahan, Jeremy ; Tzamos, Christos

    Abstract | Document (1,014 KB) | BibTeX

    Stable Approximation Algorithms for Dominating Set and Independent Set
    Authors: de Berg, Mark ; Sadhukhan, Arpan ; Spieksma, Frits

    Abstract | Document (882 KB) | BibTeX

    Scalable Auction Algorithms for Bipartite Maximum Matching Problems
    Authors: Liu, Quanquan C. ; Ke, Yiduo ; Khuller, Samir

    Abstract | Document (935 KB) | BibTeX

    Giant Components in Random Temporal Graphs
    Authors: Becker, Ruben ; Casteigts, Arnaud ; Crescenzi, Pierluigi ; Kodric, Bojana ; Renken, Malte ; Raskin, Michael ; Zamaraev, Viktor

    Abstract | Document (830 KB) | BibTeX

    On Connectivity in Random Graph Models with Limited Dependencies
    Authors: Lengler, Johannes ; Martinsson, Anders ; Petrova, Kalina ; Schnider, Patrick ; Steiner, Raphael ; Weber, Simon ; Welzl, Emo

    Abstract | Document (977 KB) | BibTeX

    Synergy Between Circuit Obfuscation and Circuit Minimization
    Authors: Impagliazzo, Russell ; Kabanets, Valentine ; Volkovich, Ilya

    Abstract | Document (945 KB) | BibTeX

    Interactive Error Correcting Codes: New Constructions and Impossibility Bounds
    Authors: Gupta, Meghal ; Zhang, Rachel Yun

    Abstract | Document (775 KB) | BibTeX

    Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
    Authors: Efthymiou, Charilaos ; Hayes, Thomas P. ; Štefankovič, Daniel ; Vigoda, Eric

    Abstract | Document (652 KB) | BibTeX

    Superpolynomial Lower Bounds for Learning Monotone Classes
    Authors: Bshouty, Nader H.

    Abstract | Document (803 KB) | BibTeX

    An Embarrassingly Parallel Optimal-Space Cardinality Estimation Algorithm
    Authors: Karayel, Emin

    Abstract | Document (987 KB) | BibTeX

    Sampling and Certifying Symmetric Functions
    Authors: Filmus, Yuval ; Leigh, Itai ; Riazanov, Artur ; Sokolov, Dmitry

    Abstract | Document (931 KB) | BibTeX

    Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes
    Authors: Bennett, Huck ; Peikert, Chris

    Abstract | Document (817 KB) | BibTeX

    Perfect Sampling for Hard Spheres from Strong Spatial Mixing
    Authors: Anand, Konrad ; Göbel, Andreas ; Pappik, Marcus ; Perkins, Will

    Abstract | Document (781 KB) | BibTeX

    Subset Sum in Time 2^{n/2} / poly(n)
    Authors: Chen, Xi ; Jin, Yaonan ; Randolph, Tim ; Servedio, Rocco A.

    Abstract | Document (975 KB) | BibTeX

    On Optimization and Counting of Non-Broken Bases of Matroids
    Authors: Abdolazimi, Dorna ; Lindberg, Kasper ; Gharan, Shayan Oveis

    Abstract | Document (731 KB) | BibTeX

    Low-Degree Testing over Grids
    Authors: Amireddy, Prashanth ; Srinivasan, Srikanth ; Sudan, Madhu

    Abstract | Document (946 KB) | BibTeX

    Improved Local Computation Algorithms for Constructing Spanners
    Authors: Arviv, Rubi ; Chung, Lily ; Levi, Reut ; Pyne, Edward

    Abstract | Document (918 KB) | BibTeX

    Classical Simulation of One-Query Quantum Distinguishers
    Authors: Bogdanov, Andrej ; Cheung, Tsun Ming ; Dinesh, Krishnamoorthy ; Lui, John C. S.

    Abstract | Document (733 KB) | BibTeX

    On the Power of Regular and Permutation Branching Programs
    Authors: Lee, Chin Ho ; Pyne, Edward ; Vadhan, Salil

    Abstract | Document (821 KB) | BibTeX

    Private Data Stream Analysis for Universal Symmetric Norm Estimation
    Authors: Braverman, Vladimir ; Manning, Joel ; Wu, Zhiwei Steven ; Zhou, Samson

    Abstract | Document (840 KB) | BibTeX

    Testing Versus Estimation of Graph Properties, Revisited
    Authors: Gishboliner, Lior ; Kushnir, Nick ; Shapira, Asaf

    Abstract | Document (748 KB) | BibTeX

    Efficient Interactive Proofs for Non-Deterministic Bounded Space
    Authors: Cook, Joshua ; Rothblum, Ron D.

    Abstract | Document (872 KB) | BibTeX

    On the Complexity of Triangle Counting Using Emptiness Queries
    Authors: Bishnu, Arijit ; Ghosh, Arijit ; Mishra, Gopinath

    Abstract | Document (997 KB) | BibTeX

    Fine Grained Analysis of High Dimensional Random Walks
    Authors: Gotlib, Roy ; Kaufman, Tali

    Abstract | Document (676 KB) | BibTeX

    A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble
    Authors: Guruswami, Venkatesan ; Li, Shilun

    Abstract | Document (718 KB) | BibTeX

    NP-Hardness of Almost Coloring Almost 3-Colorable Graphs
    Authors: Hecht, Yahli ; Minzer, Dor ; Safra, Muli

    Abstract | Document (747 KB) | BibTeX

    Extracting Mergers and Projections of Partitions
    Authors: Kopparty, Swastik ; N, Vishvajeet

    Abstract | Document (819 KB) | BibTeX

    Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case
    Authors: Blanca, Antonio ; Zhang, Xusheng

    Abstract | Document (839 KB) | BibTeX

    The Full Rank Condition for Sparse Random Matrices
    Authors: Coja-Oghlan, Amin ; Gao, Jane ; Hahn-Klimroth, Max ; Lee, Joon ; Müller, Noela ; Rolvien, Maurice

    Abstract | Document (744 KB) | BibTeX

    Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE
    Authors: Cook, Joshua ; Moshkovitz, Dana

    Abstract | Document (907 KB) | BibTeX

    Robustness for Space-Bounded Statistical Zero Knowledge
    Authors: Allender, Eric ; Gray, Jacob ; Mutreja, Saachi ; Tirumala, Harsha ; Wang, Pengxiang

    Abstract | Document (940 KB) | BibTeX

    On Constructing Spanners from Random Gaussian Projections
    Authors: Assadi, Sepehr ; Kapralov, Michael ; Yu, Huacheng

    Abstract | Document (847 KB) | BibTeX

    Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
    Authors: Ashvinkumar, Vikrant ; Assadi, Sepehr ; Deng, Chengyuan ; Gao, Jie ; Wang, Chen

    Abstract | Document (1,178 KB) | BibTeX

    How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
    Authors: Blocki, Jeremiah ; Grigorescu, Elena ; Mukherjee, Tamalika ; Zhou, Samson

    Abstract | Document (802 KB) | BibTeX

    Fast Decoding of Explicit Almost Optimal ε-Balanced q-Ary Codes And Fast Approximation of Expanding k-CSPs
    Authors: Jeronimo, Fernando Granha

    Abstract | Document (770 KB) | BibTeX

    Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz Functions
    Authors: Ferreira Pinto Jr., Renato

    Abstract | Document (818 KB) | BibTeX

    Bias Reduction for Sum Estimation
    Authors: Eden, Talya ; Houen, Jakob Bæk Tejs ; Narayanan, Shyam ; Rosenbaum, Will ; Tětek, Jakub

    Abstract | Document (832 KB) | BibTeX

    On the Composition of Randomized Query Complexity and Approximate Degree
    Authors: Chakraborty, Sourav ; Kayal, Chandrima ; Mittal, Rajat ; Paraashar, Manaswi ; Sanyal, Swagato ; Saurabh, Nitin

    Abstract | Document (824 KB) | BibTeX

    Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics
    Authors: Galanis, Andreas ; Goldberg, Leslie Ann ; Smolarova, Paulina

    Abstract | Document (651 KB) | BibTeX

    Range Avoidance for Constant Depth Circuits: Hardness and Algorithms
    Authors: Gajulapalli, Karthik ; Golovnev, Alexander ; Nagargoje, Satyajeet ; Saraogi, Sidhant

    Abstract | Document (825 KB) | BibTeX

    Testing Connectedness of Images
    Authors: Berman, Piotr ; Murzabulatov, Meiram ; Raskhodnikova, Sofya ; Ristache, Dragos

    Abstract | Document (925 KB) | BibTeX

    		  



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