APPROX/RANDOM 2019 September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA

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



Dimitris Achlioptas and László A. Végh (Eds.)
ISBN 978-3-95977-125-2, LIPICS Vol. 145 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 41 MB)
Search Publication Server


Authors
  • Achlioptas, Dimitris
  • Agrawal, Rohit
  • Albers, Susanne
  • Allender, Eric
  • Anastos, Michael
  • Arvind, V.
  • Austrin, Per
  • Ban, Frank
  • Beimel, Amos
  • Ben-Aroya, Avraham
  • Bercea, Ioana O.
  • Bhaskar, Umang
  • Birx, Alexander
  • Blanca, Antonio
  • Bogdanov, Andrej
  • Bradac, Domagoj
  • Braverman, Vladimir
  • Bun, Mark
  • Cannon, Sarah
  • Carpenter, Timothy
  • Chakrabarti, Amit
  • Chatterjee, Abhranil
  • Chen, Xi
  • Chen, Zongchen
  • Chlamtác, Eden
  • Chou, Chi-Ning
  • Cohen, Gil
  • Cohen, Ilan Reuven
  • Datta, Rajit
  • Daymude, Joshua J.
  • Devvrit,
  • Diaz, Josep
  • Dinitz, Michael
  • Dinur, Irit
  • Disser, Yann
  • Doron, Dean
  • Eden, Alon
  • Efthymiou, Charilaos
  • Emiris, Ioannis Z.
  • Fahrbach, Matthew
  • Farach-Colton, Martín
  • Feige, Uriel
  • Feldman, Dan
  • Feldman, Michal
  • Fernández V, Manuel
  • Fiat, Amos
  • Filtser, Arnold
  • Fotakis, Dimitris
  • Frieze, Alan
  • Galanis, Andreas
  • Galhotra, Sainyam
  • Gharibian, Sevag
  • Gheissari, Reza
  • Ghosh, Prantar
  • Ghoshal, Suprovat
  • Goldberg, Leslie Ann
  • Golin, Mordecai
  • Golovnev, Alexander
  • Golubev, Konstantin
  • Gotlib, Roy
  • Groß, Martin
  • Guruswami, Venkatesan
  • Gökmen, Cem
  • Göös, Mika
  • Harsha, Prahladh
  • Hayes, Thomas P.
  • Hershkowitz, David Ellis
  • Huang, Chien-Chung
  • Hulett, Reyna
  • Jagadeesan, Meena
  • Janson, Svante
  • Jayaram, Rajesh
  • Jez, Lukasz
  • Kale, Sagar
  • Kaufman, Tali
  • Khan, Arindam
  • Khot, Subhash
  • Khuller, Samir
  • Knierim, Charlotte
  • Kopparty, Swastik
  • Krishnaswamy, Ravishankar
  • Kulikov, Alexander S.
  • Kumar, Aounon
  • Kumar, Gunjan
  • Kumar, Neeraj
  • Ladewig, Leon
  • Lang, Harry
  • Lee, Euiwoong
  • Lei, Zhixian
  • Lengler, Johannes
  • Li, Fu
  • Li, Ray
  • Liao, Chao
  • Lin, Jiabao
  • Logunov, Alexander
  • Louis, Anand
  • Lu, Pinyan
  • Mande, Nikhil S.
  • Mao, Zhenyu
  • Margonis, Vasilis
  • Mari, Mathieu
  • Mathieu, Claire
  • Matuschke, Jannik
  • Mazumdar, Arya
  • Michaeli, Peleg
  • Mihajlin, Ivan
  • Miller, Gary L.
  • Mitchell, Joseph S. B.
  • Moseley, Benjamin
  • Mukhopadhyay, Partha
  • Murtagh, Jack
  • Mustafa, Nabil H.
  • Nakkiran, Preetum
  • Narayanan, Shyam
  • Nikolaev, Maksim
  • Nissim, Kobbi
  • Pal, Soumyabrata
  • Papadigenopoulos, Orestis
  • Parekh, Ojas
  • Perkins, Will
  • Petti, Samantha
  • Pfister, Pascal
  • Psarros, Ioannis
  • Quanrud, Kent
  • Rajaraman, Nived
  • Randall, Dana
  • Ravi, R.
  • Raychaudhury, Rahul
  • Reichman, Daniel
  • Reingold, Omer
  • Resch, Nicolas
  • Richa, Andréa W.
  • Robinson, Thomas
  • Rohatgi, Dhruv
  • Ron-Zewi, Noga
  • Rubinfeld, Ronitt
  • Rus, Daniela
  • Rösner, Clemens
  • Saha, Barna
  • Salmasi, Ario
  • Sandeep, Sai
  • Saraf, Shubhangi
  • Schaller, Ulysse
  • Schewior, Kevin
  • Schmidt, Daniel R.
  • Schmidt, Melanie
  • Schoenebeck, Grant
  • Schulz, Andreas S.
  • Servedio, Rocco A.
  • Shinkar, Igor
  • Sidford, Aaron
  • Sidiropoulos, Anastasios
  • Silas, Shashwat
  • Singla, Sahil
  • Sinha, Sandip
  • Sintos, Stavros
  • Sorkin, Gregory B.
  • Spang, Bruce
  • Stankovic, Aleksa
  • Stefankovic, Daniel
  • Steger, Angelika
  • Stewart, James
  • Suri, Subhash
  • Sviridenko, Maxim
  • Ta-Shma, Amnon
  • Tan, Li-Yang
  • Tao, Biaoshuai
  • Tao, Runzhou
  • Thaler, Justin
  • Thiruvenkatachari, Devanathan
  • Tsai, Meng-Tsung
  • Udwani, Rajan
  • Ullah, Enayat
  • Vadhan, Salil
  • Vasilyan, Arsen
  • Vempala, Santosh S.
  • Vigoda, Eric
  • Végh, László A.
  • Walkington, Noel J.
  • Wang, Alex L.
  • Watson, Thomas
  • Williamson, Christopher
  • Woodruff, David P.
  • Wootters, Mary
  • Yaroslavtsev, Grigory
  • Yasuda, Taisuke
  • Yu, Fang-Yi
  • Zaheri, Mohammad
  • Zhou, Samson
  • Zuckerman, David
  • Zuzic, Goran

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Achlioptas, Dimitris ; Végh, László A.

    Abstract | Document (356 KB) | BibTeX

    The Query Complexity of Mastermind with l_p Distances
    Authors: Fernández V, Manuel ; Woodruff, David P. ; Yasuda, Taisuke

    Abstract | Document (541 KB) | BibTeX

    Tracking the l_2 Norm with Constant Update Time
    Authors: Chou, Chi-Ning ; Lei, Zhixian ; Nakkiran, Preetum

    Abstract | Document (612 KB) | BibTeX

    Submodular Optimization with Contention Resolution Extensions
    Authors: Moseley, Benjamin ; Sviridenko, Maxim

    Abstract | Document (585 KB) | BibTeX

    Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
    Authors: Hershkowitz, David Ellis ; Ravi, R. ; Singla, Sahil

    Abstract | Document (588 KB) | BibTeX

    Streaming Hardness of Unique Games
    Authors: Guruswami, Venkatesan ; Tao, Runzhou

    Abstract | Document (477 KB) | BibTeX

    On Strong Diameter Padded Decompositions
    Authors: Filtser, Arnold

    Abstract | Document (802 KB) | BibTeX

    Max-Min Greedy Matching
    Authors: Eden, Alon ; Feige, Uriel ; Feldman, Michal

    Abstract | Document (683 KB) | BibTeX

    Hardy-Muckenhoupt Bounds for Laplacian Eigenvalues
    Authors: Miller, Gary L. ; Walkington, Noel J. ; Wang, Alex L.

    Abstract | Document (502 KB) | BibTeX

    Improved 3LIN Hardness via Linear Label Cover
    Authors: Harsha, Prahladh ; Khot, Subhash ; Lee, Euiwoong ; Thiruvenkatachari, Devanathan

    Abstract | Document (606 KB) | BibTeX

    Dynamic Pricing of Servers on Trees
    Authors: Cohen, Ilan Reuven ; Eden, Alon ; Fiat, Amos ; Jez, Lukasz

    Abstract | Document (1,312 KB) | BibTeX

    Approximating the Norms of Graph Spanners
    Authors: Chlamtác, Eden ; Dinitz, Michael ; Robinson, Thomas

    Abstract | Document (575 KB) | BibTeX

    Conditional Hardness of Earth Mover Distance
    Authors: Rohatgi, Dhruv

    Abstract | Document (503 KB) | BibTeX

    Single-Elimination Brackets Fail to Approximate Copeland Winner
    Authors: Hulett, Reyna

    Abstract | Document (473 KB) | BibTeX

    Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
    Authors: Carpenter, Timothy ; Salmasi, Ario ; Sidiropoulos, Anastasios

    Abstract | Document (571 KB) | BibTeX

    Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
    Authors: Guruswami, Venkatesan ; Sandeep, Sai

    Abstract | Document (565 KB) | BibTeX

    Syntactic Separation of Subset Satisfiability Problems
    Authors: Allender, Eric ; Farach-Colton, Martín ; Tsai, Meng-Tsung

    Abstract | Document (658 KB) | BibTeX

    Malleable Scheduling Beyond Identical Machines
    Authors: Fotakis, Dimitris ; Matuschke, Jannik ; Papadigenopoulos, Orestis

    Abstract | Document (550 KB) | BibTeX

    On the Cost of Essentially Fair Clusterings
    Authors: Bercea, Ioana O. ; Groß, Martin ; Khuller, Samir ; Kumar, Aounon ; Rösner, Clemens ; Schmidt, Daniel R. ; Schmidt, Melanie

    Abstract | Document (605 KB) | BibTeX

    The Maximum Exposure Problem
    Authors: Kumar, Neeraj ; Sintos, Stavros ; Suri, Subhash

    Abstract | Document (740 KB) | BibTeX

    Small Space Stream Summary for Matroid Center
    Authors: Kale, Sagar

    Abstract | Document (558 KB) | BibTeX

    Improved Bounds for Open Online Dial-a-Ride on the Line
    Authors: Birx, Alexander ; Disser, Yann ; Schewior, Kevin

    Abstract | Document (591 KB) | BibTeX

    Improved Online Algorithms for Knapsack and GAP in the Random Order Model
    Authors: Albers, Susanne ; Khan, Arindam ; Ladewig, Leon

    Abstract | Document (624 KB) | BibTeX

    Fast and Deterministic Approximations for k-Cut
    Authors: Quanrud, Kent

    Abstract | Document (558 KB) | BibTeX

    Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
    Authors: Austrin, Per ; Stankovic, Aleksa

    Abstract | Document (541 KB) | BibTeX

    Robust Appointment Scheduling with Heterogeneous Costs
    Authors: Schulz, Andreas S. ; Udwani, Rajan

    Abstract | Document (501 KB) | BibTeX

    Collapsing Superstring Conjecture
    Authors: Golovnev, Alexander ; Kulikov, Alexander S. ; Logunov, Alexander ; Mihajlin, Ivan ; Nikolaev, Maksim

    Abstract | Document (648 KB) | BibTeX

    Improved Algorithms for Time Decay Streams
    Authors: Braverman, Vladimir ; Lang, Harry ; Ullah, Enayat ; Zhou, Samson

    Abstract | Document (568 KB) | BibTeX

    Approximation Algorithms for Partially Colorable Graphs
    Authors: Ghoshal, Suprovat ; Louis, Anand ; Raychaudhury, Rahul

    Abstract | Document (585 KB) | BibTeX

    Towards Optimal Moment Estimation in Streaming and Distributed Models
    Authors: Jayaram, Rajesh ; Woodruff, David P.

    Abstract | Document (640 KB) | BibTeX

    The Complexity of Partial Function Extension for Coverage Functions
    Authors: Bhaskar, Umang ; Kumar, Gunjan

    Abstract | Document (552 KB) | BibTeX

    Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut
    Authors: Gharibian, Sevag ; Parekh, Ojas

    Abstract | Document (517 KB) | BibTeX

    Maximizing Covered Area in the Euclidean Plane with Connectivity Constraint
    Authors: Huang, Chien-Chung ; Mari, Mathieu ; Mathieu, Claire ; Mitchell, Joseph S. B. ; Mustafa, Nabil H.

    Abstract | Document (2,166 KB) | BibTeX

    Robust Correlation Clustering
    Authors: Devvrit, ; Krishnaswamy, Ravishankar ; Rajaraman, Nived

    Abstract | Document (594 KB) | BibTeX

    Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
    Authors: Liao, Chao ; Lin, Jiabao ; Lu, Pinyan ; Mao, Zhenyu

    Abstract | Document (515 KB) | BibTeX

    The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions
    Authors: Diaz, Josep ; Golin, Mordecai

    Abstract | Document (924 KB) | BibTeX

    On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs
    Authors: Anastos, Michael ; Frieze, Alan

    Abstract | Document (508 KB) | BibTeX

    Slow Mixing of Glauber Dynamics for the Six-Vertex Model in the Ordered Phases
    Authors: Fahrbach, Matthew ; Randall, Dana

    Abstract | Document (1,282 KB) | BibTeX

    Lifted Multiplicity Codes and the Disjoint Repair Group Property
    Authors: Li, Ray ; Wootters, Mary

    Abstract | Document (559 KB) | BibTeX

    Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
    Authors: Schoenebeck, Grant ; Tao, Biaoshuai ; Yu, Fang-Yi

    Abstract | Document (666 KB) | BibTeX

    Direct Sum Testing: The General Case
    Authors: Dinur, Irit ; Golubev, Konstantin

    Abstract | Document (474 KB) | BibTeX

    Fast Algorithms at Low Temperatures via Markov Chains
    Authors: Chen, Zongchen ; Galanis, Andreas ; Goldberg, Leslie Ann ; Perkins, Will ; Stewart, James ; Vigoda, Eric

    Abstract | Document (518 KB) | BibTeX

    Deterministic Approximation of Random Walks in Small Space
    Authors: Murtagh, Jack ; Reingold, Omer ; Sidford, Aaron ; Vadhan, Salil

    Abstract | Document (590 KB) | BibTeX

    Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions
    Authors: Ben-Aroya, Avraham ; Cohen, Gil ; Doron, Dean ; Ta-Shma, Amnon

    Abstract | Document (529 KB) | BibTeX

    Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions
    Authors: Ban, Frank ; Chen, Xi ; Servedio, Rocco A. ; Sinha, Sandip

    Abstract | Document (588 KB) | BibTeX

    Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas
    Authors: Servedio, Rocco A. ; Tan, Li-Yang

    Abstract | Document (719 KB) | BibTeX

    Unconstraining Graph-Constrained Group Testing
    Authors: Spang, Bruce ; Wootters, Mary

    Abstract | Document (765 KB) | BibTeX

    Near-Neighbor Preserving Dimension Reduction for Doubling Subsets of l_1
    Authors: Emiris, Ioannis Z. ; Margonis, Vasilis ; Psarros, Ioannis

    Abstract | Document (501 KB) | BibTeX

    Improved Strong Spatial Mixing for Colorings on Trees
    Authors: Efthymiou, Charilaos ; Galanis, Andreas ; Hayes, Thomas P. ; Stefankovic, Daniel ; Vigoda, Eric

    Abstract | Document (551 KB) | BibTeX

    (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
    Authors: Bradac, Domagoj ; Singla, Sahil ; Zuzic, Goran

    Abstract | Document (653 KB) | BibTeX

    Testing Odd Direct Sums Using High Dimensional Expanders
    Authors: Gotlib, Roy ; Kaufman, Tali

    Abstract | Document (540 KB) | BibTeX

    A Lower Bound for Sampling Disjoint Sets
    Authors: Göös, Mika ; Watson, Thomas

    Abstract | Document (547 KB) | BibTeX

    Approximating the Noise Sensitivity of a Monotone Boolean Function
    Authors: Rubinfeld, Ronitt ; Vasilyan, Arsen

    Abstract | Document (551 KB) | BibTeX

    Connectivity of Random Annulus Graphs and the Geometric Block Model
    Authors: Galhotra, Sainyam ; Mazumdar, Arya ; Pal, Soumyabrata ; Saha, Barna

    Abstract | Document (601 KB) | BibTeX

    A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
    Authors: Cannon, Sarah ; Daymude, Joshua J. ; Gökmen, Cem ; Randall, Dana ; Richa, Andréa W.

    Abstract | Document (1,941 KB) | BibTeX

    The Large-Error Approximate Degree of AC^0
    Authors: Bun, Mark ; Thaler, Justin

    Abstract | Document (613 KB) | BibTeX

    String Matching: Communication, Circuits, and Learning
    Authors: Golovnev, Alexander ; Göös, Mika ; Reichman, Daniel ; Shinkar, Igor

    Abstract | Document (574 KB) | BibTeX

    Efficient Black-Box Identity Testing for Free Group Algebras
    Authors: Arvind, V. ; Chatterjee, Abhranil ; Datta, Rajit ; Mukhopadhyay, Partha

    Abstract | Document (489 KB) | BibTeX

    The Maximum Label Propagation Algorithm on Sparse Random Graphs
    Authors: Knierim, Charlotte ; Lengler, Johannes ; Pfister, Pascal ; Schaller, Ulysse ; Steger, Angelika

    Abstract | Document (573 KB) | BibTeX

    Samplers and Extractors for Unbounded Functions
    Authors: Agrawal, Rohit

    Abstract | Document (561 KB) | BibTeX

    Successive Minimum Spanning Trees
    Authors: Janson, Svante ; Sorkin, Gregory B.

    Abstract | Document (586 KB) | BibTeX

    Simple Analysis of Sparse, Sign-Consistent JL
    Authors: Jagadeesan, Meena

    Abstract | Document (520 KB) | BibTeX

    Streaming Coreset Constructions for M-Estimators
    Authors: Braverman, Vladimir ; Feldman, Dan ; Lang, Harry ; Rus, Daniela

    Abstract | Document (538 KB) | BibTeX

    Pairwise Independent Random Walks Can Be Slightly Unbounded
    Authors: Narayanan, Shyam

    Abstract | Document (488 KB) | BibTeX

    Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
    Authors: Chen, Zongchen ; Vempala, Santosh S.

    Abstract | Document (461 KB) | BibTeX

    Exploring Differential Obliviousness
    Authors: Beimel, Amos ; Nissim, Kobbi ; Zaheri, Mohammad

    Abstract | Document (631 KB) | BibTeX

    Thresholds in Random Motif Graphs
    Authors: Anastos, Michael ; Michaeli, Peleg ; Petti, Samantha

    Abstract | Document (580 KB) | BibTeX

    Random-Cluster Dynamics in Z^2: Rapid Mixing with General Boundary Conditions
    Authors: Blanca, Antonio ; Gheissari, Reza ; Vigoda, Eric

    Abstract | Document (609 KB) | BibTeX

    On List Recovery of High-Rate Tensor Codes
    Authors: Kopparty, Swastik ; Resch, Nicolas ; Ron-Zewi, Noga ; Saraf, Shubhangi ; Silas, Shashwat

    Abstract | Document (613 KB) | BibTeX

    Approximate F_2-Sketching of Valuation Functions
    Authors: Yaroslavtsev, Grigory ; Zhou, Samson

    Abstract | Document (629 KB) | BibTeX

    Streaming Verification of Graph Computations via Graph Structure
    Authors: Chakrabarti, Amit ; Ghosh, Prantar

    Abstract | Document (569 KB) | BibTeX

    Approximate Degree, Secret Sharing, and Concentration Phenomena
    Authors: Bogdanov, Andrej ; Mande, Nikhil S. ; Thaler, Justin ; Williamson, Christopher

    Abstract | Document (568 KB) | BibTeX

    Improved Extractors for Recognizable and Algebraic Sources
    Authors: Li, Fu ; Zuckerman, David

    Abstract | Document (567 KB) | BibTeX

      




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