The virtual conference to be held August 17-19 and has three components:

  1. A short 10 minute live presentation/Q&A on each paper. This will be the main substitute for the live conference. These will be over zoom and the schedule is below.
  2. Recorded roughly 25 minute talks for each accepted paper available on youtube. (Linked to in the schedule below).
  3. Invited talks and a event on August 18th

For APPROX sessions and Wednesday invited talk Zoom Room A; For RANDOM sessions and Monday invited talk Zoom Room B. For event please follow this link.

The proceedings of the conference are available freely via LIPICS. APPROX prerecorded talk videos are available on this youtube channel. More details on RANDOM talks are available here.

A slack channel is created for paper discussions.

All times are in Pacific Daylight time (UTC -7).

Monday 17th August

APPROX Session 1 (chair: Harald Räcke)
7:00-7:10Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles paper, presentation
7:10-7:20Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Przemysław Uznański. Improved Circular k-Mismatch Sketches paper, presentation
7:20-7:30Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos and Adam Polak. Online Coloring of Short Intervals paper, presentation
7:30-7:40Nicole Megow and Lukas Nölke. Online Minimum Cost Matching with Recourse on the Line paper, presentation
7:40-8:00Coffee Break
RANDOM Session 1 APPROX Session 2 (chair: Harald Räcke)
8:00-8:10Ronen Shaltiel. Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle? Alexander Wei. Better and Simpler Learning-Augmented Online Caching paper, presentation
8:10-8:20Sumegha Garg, Pravesh K. Kothari and Ran Raz. Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich’s PRG Sébastien Bubeck and Yuval Rabani. Parametrized Metrical Task Systems paper, presentation
8:20-8:30Shuichi Hirahara and Osamu Watanabe.On Nonadaptive Security Reductions of Hitting Set Generators Bohan Fan, Diego Ihara Centurion, Neshat Mohammadi, Francesco Sgherzi, Anastasios Sidiropoulos, Mina Valizadeh. Learning Lines with Ordinal Constraints paper, presentation
8:30-8:40Shalev Ben-David, Mika Göös, Robin Kothari and Thomas Watson.When Is Amplification Necessary for Composition in Randomized Query Complexity?
8:40-9:00Coffee break
9:00-9:55Invited talk
Shachar Lovett. Point location: an interface between geometry, machine learning and complexity
9:55-10:20Coffee break
RANDOM Session 2 APPROX Session 3 (chair: Chaitanya Swamy)
10:20-10:30Eric Blais and Abhinav Bommireddi. On testing and robust characterizations of convexity Varun Gupta, Ravishankar Krishnaswamy and Sai Sandeep. PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching paper, presentation
10:30-10:40Eric Price and Jonathan Scarlett. A Fast Binary Splitting Approach to Non-Adaptive Group Testing Xiangyu Guo, Janardhan Kulkarni, Shi Li and Jiayi Xian. On the Facility Location Problem in Online and Dynamic Models paper, presentation
10:40-10:50Artur Czumaj, Hendrik Fichtenberger, Pan Peng and Christian Sohler. Testable Properties in General Graphs and Random Order Streaming Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai. Maximizing Throughput in Flow Shop Real-time Scheduling paper, presentation
10:50-11:00Jeff Phillips and Wai Ming Tai.The Gaussian Sketch for Almost Relative Error Kernel Distance Nima Anari and Thuy-Duong Vuong. An Extension of Plücker Relations with Applications to Subdeterminant Maximization paper, presentation
11:00-11:20Coffee break
RANDOM Session 3
11:20-11:30Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank
11:30-11:40Markus Bläser and Anurag Pandey. Polynomial identity testing for low degree polynomials with optimal randomness
11:40-11:50Zeyu Guo and Rohit Gurjar. Improved explicit hitting-sets for ROABPs
11:50-12:00Dean Doron, Amnon Ta-Shma and Roei Tell. On Hitting-Set Generators for Polynomials that Vanish Rarely

Tuesday 18th August

APPROX Session 4 (chair: Nikhil Bansal)
7:00-7:10Syamantak Das, Lavina Jain and Nikhil Kumar. A Constant Factor Approximation for Capacitated Min-Max Tree Cover paper, presentation
7:10-7:20Chan Chun-Hsiang, Bundit Laekhanukit, Hao-Ting Wei and Yuhao Zhang. Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs paper, presentation
7:20-7:30Roy Schwartz and Yotam Sharoni. Approximating Requirement Cut via a Configuration LP paper, presentation
7:30-7:40Amey Bhangale, Diptarka Chakraborty and Rajendra Kumar. Hardness of Approximation of (Multi-)LCS over Small Alphabet paper, presentation
7:40-8:00Coffee Break
APPROX Session 5 (chair: Nikhil Bansal)
8:00-8:10Chien-Chung Huang, Theophile Thiery and Justin Ward. Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints paper, presentation
8:10-8:20Tatiana Starikovskaya, Michal Svagerka and Przemysław Uznański. $L_p$ Pattern Matching in a Stream paper, presentation
8:20-8:30Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi and David P. Woodruff. Streaming Complexity of SVMs paper, presentation
8:30-8:40Ainesh Bakshi, Nadiia Chepurko and David P. Woodruff. Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams paper, presentation
8:40-9:00Coffee break
9:00-9:55Social event
Gather meeting
9:55-10:20Coffee break
RANDOM Session 4 APPROX Session 6 (chair: Chaitanya Swamy)
10:20-10:30Sarah Miracle, Amanda Streib and Noah Streib. Iterated Decomposition of Biased Permutations Via New Bounds on the Spectral Gap of Markov chains Vadim Grinberg and Buddhima Gamlath. Approximating Star Cover Problems paper, presentation
10:30-10:40Noga Alon and Sepehr Assadi. Palette Sparsification Beyond (Delta+1) Vertex Coloring Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltan Szigeti and Lu Wang. A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case paper, presentation
10:40-10:50Jan Dreier, Philipp Kuinke and Peter Rossmanith. Maximum Shallow Clique Minors in Preferential Attachment Graphs have Polylogarithmic Size Xiangyu Guo, Guy Kortsarz, Bundit Laekhanukit, Shi Li, Daniel Vaz and Jiayi Xian. On Approximating Degree-Bounded Network Design Problems paper, presentation
10:50-11:00Amit Chakrabarti, Prantar Ghosh and Justin Thaler.Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches Neng Huang and Aaron Potechin. On the Approximability of Presidential Type Predicates paper, presentation
11:00-11:20Coffee break
RANDOM Session 5
11:20-11:30Reut Levi and Moti Medina. Distributed Testing of Graph Isomorphism in the CONGEST model
11:30-11:40Dana Ron and Asaf Rosin. Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
11:40-11:50Nader Bshouty. Almost Optimal Testers for Concise Representations
11:50-12:00Clément Canonne and Karl Wimmer. Testing Data Binnings
12:00-12:10Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra and Manaswi Paraashar. Disjointness through the Lens of VC-dimension: Sparsity and Beyond

Wednesday 19th August

APPROX Session 7 (chair: Pasin Manurangsi)
7:00-7:10Fedor Fomin, Petr Golovach, Fahad Panolan and Kirill Simonov. Low-rank binary matrix approximation in column-sum norm paper, presentation
7:10-7:20Dor Katzelnick and Roy Schwartz. Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains paper, presentation
7:20-7:30Sayan Bandyapadhyay. On Perturbation Resilience of Non-Uniform k-Center paper, presentation
7:30-7:40Gálvez Waldo, Fabrizio Grandoni, Afrouz Jabal Ameli, Klaus Jansen, Arindam Khan and Malin Rau. A Tight $(3/2+\varepsilon)$ Approximation for Skewed Strip Packing paper, presentation
7:40-8:00Coffee Break
APPROX Session 8 (chair: Andreas Feldmann)
8:00-8:10Venkatesan Guruswami, Jakub Opršal and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP paper, presentation
8:10-8:20Petr Kolman and Eden Chlamtac. How to Cut a Ball without Separating: Improved Approximations for Length Bounded Cut paper, presentation
8:20-8:30Eunou Lee, Sean Hallgren and Ojas Parekh. An approximation algorithm for the MAX-2-Local Hamiltonian problem paper, presentation
8:30-9:00Coffee break
9:00-9:55Invited talk (chair: Anupam Gupta)
Nathan Klein. A (Slightly) Improved Approximation Algorithm for Metric TSP
9:55-10:20Coffee break
RANDOM Session 6 APPROX Session 9 (chair: Anupam Gupta)
10:20-10:30Kwangjun Ahn. A Simpler Strong Refutation of Random k-XOR Spoorthy Gunda, Pallavi Jain, Daniel Lokshtanov, Saket Saurabh and Prafullkumar Tale. On the Parameterized Approximability of Contraction to Classes of Chordal Graphs paper, presentation
10:30-10:40Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro and Noah Stephens-Davidowitz. Extractor lower bounds, revisited Parinya Chalermsook, Julia Chuzhoy and Thatchaphol Saranurak. Pinning Down the Strong Wilber 1 Bound for Binary Search Trees paper, presentation
10:40-10:50Nicolas Resch, Venkatesan Guruswami, Jonathan Mosheiff, Ray Li, Shashwat Silas and Mary Wootters. Bounds for list-decoding and list-recovery of random linear codes Karine Chubarian and Anastasios Sidiropoulos. Computing Bi-Lipschitz Outlier Embeddings into the Line paper, presentation
10:50-11:00Aditya Potukuchi and Ben Lund. On the list recoverability of randomly punctured codes Ishan Agarwal, Oded Regev and Yi Tang. Nearly Optimal Embeddings of Flat Tori paper, presentation
11:00-11:20Coffee break
RANDOM Session 7
11:20-11:30Tali Kaufman and Ella Sharakanski. Chernoff Bound for High-Dimensional Expanders
11:30-11:40Calvin Beideman, Karthekeyan Chandrasekaran and Chao Xu. Multicriteria cuts and size-constrained k-cuts in hypergraphs
11:40-11:50Linh Tran and Van Vu. Reaching a Consensus on Random Networks: The Power of Few
11:50-12:00Cyrus Rashtchian, David P. Woodruff and Hanlin Zhu. Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
12:00-12:10Ali Pourmiri, Catherine Greenhill and Bernard Mans. Balanced Allocation on Dynamic Hypergraphs