Portal - APPROX/RANDOM 2020

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

Chakraborty, Diptarka

Chakraborty, Sourav

Chalermsook, Parinya

Chan, Chun-Hsiang

Chandrasekaran, Karthekeyan

Chybowska-Sokół, Joanna

Fichtenberger, Hendrik

Guruswami, Venkatesan

Junosza-Szaniawski, Konstanty

Krishnaswamy, Ravishankar

Pittu, Madhusudhan Reddy

Saranurak, Thatchaphol

Sidiropoulos, Anastasios

Silas, Shashwat

Simonov, Kirill

Sohler, Christian

Starikovskaya, Tatiana

Stephens-Davidowitz, Noah

Streib, Amanda Pascoe

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

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