Portal - APPROX/RANDOM 2022

APPROX/RANDOM 2022	September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference)
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) Amit Chakrabarti and Chaitanya Swamy (Eds.)
ISBN 978-3-95977-249-5, LIPICS Vol. 245	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 22 MB)
Search Publication Server

Authors

Biswas, Amartya Shankha

Guruswami, Venkatesan

Shahrasbi, Amirbehshad

Velusamy, Santhoshini

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Chakrabarti, Amit ; Swamy, Chaitanya

Abstract | Document (555 KB) | BibTeX

A Unified Approach to Discrepancy Minimization

Authors: Bansal, Nikhil ; Laddha, Aditi ; Vempala, Santosh

Abstract | Document (859 KB) | BibTeX

Fourier Growth of Regular Branching Programs

Authors: Lee, Chin Ho ; Pyne, Edward ; Vadhan, Salil

Abstract | Document (830 KB) | BibTeX

Double Balanced Sets in High Dimensional Expanders

Authors: Kaufman, Tali ; Mass, David

Abstract | Document (669 KB) | BibTeX

Fast and Perfect Sampling of Subgraphs and Polymer Systems

Authors: Blanca, Antonio ; Cannon, Sarah ; Perkins, Will

Abstract | Document (701 KB) | BibTeX

High Dimensional Expansion Implies Amplified Local Testability

Authors: Kaufman, Tali ; Oppenheim, Izhar

Abstract | Document (628 KB) | BibTeX

Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs

Authors: Girish, Uma ; Mittal, Kunal ; Raz, Ran ; Zhan, Wei

Abstract | Document (690 KB) | BibTeX

Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks

Authors: Mehta, Hermish ; Reichman, Daniel

Abstract | Document (656 KB) | BibTeX

Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions

Authors: Gabrys, Ryan ; Guruswami, Venkatesan ; Ribeiro, João ; Wu, Ke

Abstract | Document (776 KB) | BibTeX

Affine Extractors and AC0-Parity

Authors: Huang, Xuangui ; Ivanov, Peter ; Viola, Emanuele

Abstract | Document (654 KB) | BibTeX

Hyperbolic Concentration, Anti-Concentration, and Discrepancy

Authors: Song, Zhao ; Zhang, Ruizhe

Abstract | Document (815 KB) | BibTeX

Improved Local Testing for Multiplicity Codes

Authors: Karliner, Dan ; Ta-Shma, Amnon

Abstract | Document (777 KB) | BibTeX

Unbalanced Expanders from Multiplicity Codes

Authors: Kalev, Itay ; Ta-Shma, Amnon

Abstract | Document (746 KB) | BibTeX

Streaming Algorithms with Large Approximation Factors

Authors: Li, Yi ; Lin, Honghao ; Woodruff, David P. ; Zhang, Yuheng

Abstract | Document (933 KB) | BibTeX

Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems

Authors: Kedia, Hridesh ; Oh, Shunhao ; Randall, Dana

Abstract | Document (813 KB) | BibTeX

Tight Chernoff-Like Bounds Under Limited Independence

Authors: Skorski, Maciej

Abstract | Document (781 KB) | BibTeX

Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Authors: Gaitonde, Jason ; Hopkins, Max ; Kaufman, Tali ; Lovett, Shachar ; Zhang, Ruizhe

Abstract | Document (798 KB) | BibTeX

Accelerating Polarization via Alphabet Extension

Authors: Duursma, Iwan ; Gabrys, Ryan ; Guruswami, Venkatesan ; Lin, Ting-Chun ; Wang, Hsin-Po

Abstract | Document (726 KB) | BibTeX

Sketching Distances in Monotone Graph Classes

Authors: Esperet, Louis ; Harms, Nathaniel ; Kupavskii, Andrey

Abstract | Document (876 KB) | BibTeX

Communication Complexity of Collision

Authors: Göös, Mika ; Jain, Siddhartha

Abstract | Document (710 KB) | BibTeX

Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness

Authors: Guruswami, Venkatesan ; Lyu, Xin ; Wang, Xiuhan

Abstract | Document (867 KB) | BibTeX

Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case

Authors: Bhargava, Vishwas ; Garg, Ankit ; Kayal, Neeraj ; Saha, Chandan

Abstract | Document (849 KB) | BibTeX

Lower Bound Methods for Sign-Rank and Their Limitations

Authors: Hatami, Hamed ; Hatami, Pooya ; Pires, William ; Tao, Ran ; Zhao, Rosie

Abstract | Document (854 KB) | BibTeX

Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time

Authors: Arvind, V. ; Chatterjee, Abhranil ; Mukhopadhyay, Partha

Abstract | Document (733 KB) | BibTeX

Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics

Authors: Blanca, Antonio ; Gheissari, Reza

Abstract | Document (807 KB) | BibTeX

Improved Bounds for Randomly Colouring Simple Hypergraphs

Authors: Feng, Weiming ; Guo, Heng ; Wang, Jiaheng

Abstract | Document (879 KB) | BibTeX

Lifting with Inner Functions of Polynomial Discrepancy

Authors: Manor, Yahel ; Meir, Or

Abstract | Document (703 KB) | BibTeX

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing

Authors: Chakraborty, Sourav ; Fischer, Eldar ; Ghosh, Arijit ; Mishra, Gopinath ; Sen, Sayantan

Abstract | Document (840 KB) | BibTeX

A Sublinear Local Access Implementation for the Chinese Restaurant Process

Authors: Mörters, Peter ; Sohler, Christian ; Walzer, Stefan

Abstract | Document (822 KB) | BibTeX

A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Authors: Gao, Pu ; MacRury, Calum ; Prałat, Paweł

Abstract | Document (847 KB) | BibTeX

Cover and Hitting Times of Hyperbolic Random Graphs

Authors: Kiwi, Marcos ; Schepers, Markus ; Sylvester, John

Abstract | Document (867 KB) | BibTeX

Adaptive Sketches for Robust Regression with Importance Sampling

Authors: Mahabadi, Sepideh ; Woodruff, David P. ; Zhou, Samson

Abstract | Document (927 KB) | BibTeX

Finding the KT Partition of a Weighted Graph in Near-Linear Time

Authors: Apers, Simon ; Gawrychowski, Paweł ; Lee, Troy

Abstract | Document (686 KB) | BibTeX

Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model

Authors: Feldman, Moran ; Szarf, Ariel

Abstract | Document (921 KB) | BibTeX

Ordered k-Median with Outliers

Authors: Deng, Shichuan ; Zhang, Qianfan

Abstract | Document (916 KB) | BibTeX

Sketching Approximability of (Weak) Monarchy Predicates

Authors: Chou, Chi-Ning ; Golovnev, Alexander ; Shahrasbi, Amirbehshad ; Sudan, Madhu ; Velusamy, Santhoshini

Abstract | Document (847 KB) | BibTeX

Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling

Authors: Fukunaga, Takuro

Abstract | Document (650 KB) | BibTeX

Fair Correlation Clustering in General Graphs

Authors: Schwartz, Roy ; Zats, Roded

Abstract | Document (860 KB) | BibTeX

On Sketching Approximations for Symmetric Boolean CSPs

Authors: Boyland, Joanna ; Hwang, Michael ; Prasad, Tarun ; Singer, Noah ; Velusamy, Santhoshini

Abstract | Document (1,131 KB) | BibTeX

Massively Parallel Algorithms for Small Subgraph Counting

Authors: Biswas, Amartya Shankha ; Eden, Talya ; Liu, Quanquan C. ; Rubinfeld, Ronitt ; Mitrović, Slobodan

Abstract | Document (1,000 KB) | BibTeX

Hardness Results for Weaver’s Discrepancy Problem

Authors: Spielman, Daniel A. ; Zhang, Peng

Abstract | Document (673 KB) | BibTeX

Relative Survivable Network Design

Authors: Dinitz, Michael ; Koranteng, Ama ; Kortsarz, Guy

Abstract | Document (689 KB) | BibTeX

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number

Authors: Guruswami, Venkatesan ; Kothari, Pravesh K. ; Manohar, Peter

Abstract | Document (592 KB) | BibTeX

Approximating CSPs with Outliers

Authors: Ghoshal, Suprovat ; Louis, Anand

Abstract | Document (744 KB) | BibTeX

Submodular Dominance and Applications

Authors: Qiu, Frederick ; Singla, Sahil

Abstract | Document (801 KB) | BibTeX

Online Facility Location with Linear Delay

Authors: Bienkowski, Marcin ; Böhm, Martin ; Byrka, Jarosław ; Marcinkowski, Jan

Abstract | Document (872 KB) | BibTeX

Prophet Matching in the Probe-Commit Model

Authors: Borodin, Allan ; MacRury, Calum ; Rakheja, Akash

Abstract | Document (856 KB) | BibTeX

The Biased Homogeneous r-Lin Problem

Authors: Ghoshal, Suprovat

Abstract | Document (733 KB) | BibTeX

Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting

Authors: Assadi, Sepehr ; Nguyen, Hoai-An

Abstract | Document (1,233 KB) | BibTeX

Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint

Authors: Klimm, Max ; Knaack, Martin

Abstract | Document (755 KB) | BibTeX

Some Results on Approximability of Minimum Sum Vertex Cover

Authors: Stanković, Aleksa

Abstract | Document (722 KB) | BibTeX

(1+ε)-Approximate Shortest Paths in Dynamic Streams

Authors: Elkin, Michael ; Trehan, Chhaya

Abstract | Document (922 KB) | BibTeX

Caching with Reserves

Authors: Ibrahimpur, Sharat ; Purohit, Manish ; Svitkina, Zoya ; Vee, Erik ; Wang, Joshua R.

Abstract | Document (727 KB) | BibTeX

Space Optimal Vertex Cover in Dynamic Streams

Authors: Naidu, Kheeran K. ; Shah, Vihan

Abstract | Document (835 KB) | BibTeX

Approximating LCS and Alignment Distance over Multiple Sequences

Authors: Das, Debarati ; Saha, Barna

Abstract | Document (1,853 KB) | BibTeX

A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs

Authors: Friedrich, Tobias ; Issac, Davis ; Kumar, Nikhil ; Mallek, Nadym ; Zeif, Ziena

Abstract | Document (2,695 KB) | BibTeX

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

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