Portal - APPROX/RANDOM 2019

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

Farach-Colton, Martín

Guruswami, Venkatesan

Harsha, Prahladh

Hayes, Thomas P.

Hershkowitz, David Ellis

Krishnaswamy, Ravishankar

Kulikov, Alexander S.

Mitchell, Joseph S. B.

Papadigenopoulos, Orestis

Sidiropoulos, Anastasios

Thiruvenkatachari, Devanathan

Williamson, Christopher

Woodruff, David P.

Wootters, Mary

Yaroslavtsev, Grigory

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 (609 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

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