The virtual conference to be held August 17-19 and has three components:
- 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.
- Recorded roughly 25 minute talks for each accepted paper available on youtube. (Linked to in the schedule below).
- Invited talks and a gather.town 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 gather.town 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:10 | Arindam Khan and Madhusudhan Reddy Pittu. On guillotine separability of squares and rectangles paper, presentation | |
| 7:10-7:20 | Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat and Przemysław Uznański. Improved Circular k-Mismatch Sketches paper, presentation | |
| 7:20-7:30 | Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos and Adam Polak. Online Coloring of Short Intervals paper, presentation | |
| 7:30-7:40 | Nicole Megow and Lukas Nölke. Online Minimum Cost Matching with Recourse on the Line paper, presentation | |
| 7:40-8:00 | Coffee Break | |
| RANDOM Session 1 | APPROX Session 2 (chair: Harald Räcke) | |
| 8:00-8:10 | Ronen 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:20 | Sumegha 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:30 | Shuichi 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:40 | Shalev Ben-David, Mika Göös, Robin Kothari and Thomas Watson.When Is Amplification Necessary for Composition in Randomized Query Complexity? | |
| 8:40-9:00 | Coffee break | |
| 9:00-9:55 | Invited talk Shachar Lovett. Point location: an interface between geometry, machine learning and complexity | |
| 9:55-10:20 | Coffee break | |
| RANDOM Session 2 | APPROX Session 3 (chair: Chaitanya Swamy) | |
| 10:20-10:30 | Eric 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:40 | Eric 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:50 | Artur 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:00 | Jeff 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:20 | Coffee break | |
| RANDOM Session 3 | ||
| 11:20-11:30 | Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank | |
| 11:30-11:40 | Markus Bläser and Anurag Pandey. Polynomial identity testing for low degree polynomials with optimal randomness | |
| 11:40-11:50 | Zeyu Guo and Rohit Gurjar. Improved explicit hitting-sets for ROABPs | |
| 11:50-12:00 | Dean 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:10 | Syamantak Das, Lavina Jain and Nikhil Kumar. A Constant Factor Approximation for Capacitated Min-Max Tree Cover paper, presentation | |
| 7:10-7:20 | Chan 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:30 | Roy Schwartz and Yotam Sharoni. Approximating Requirement Cut via a Configuration LP paper, presentation | |
| 7:30-7:40 | Amey Bhangale, Diptarka Chakraborty and Rajendra Kumar. Hardness of Approximation of (Multi-)LCS over Small Alphabet paper, presentation | |
| 7:40-8:00 | Coffee Break | |
| APPROX Session 5 (chair: Nikhil Bansal) | ||
| 8:00-8:10 | Chien-Chung Huang, Theophile Thiery and Justin Ward. Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints paper, presentation | |
| 8:10-8:20 | Tatiana Starikovskaya, Michal Svagerka and Przemysław Uznański. $L_p$ Pattern Matching in a Stream paper, presentation | |
| 8:20-8:30 | Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi and David P. Woodruff. Streaming Complexity of SVMs paper, presentation | |
| 8:30-8:40 | Ainesh Bakshi, Nadiia Chepurko and David P. Woodruff. Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams paper, presentation | |
| 8:40-9:00 | Coffee break | |
| 9:00-9:55 | Social event Gather meeting | |
| 9:55-10:20 | Coffee break | |
| RANDOM Session 4 | APPROX Session 6 (chair: Chaitanya Swamy) | |
| 10:20-10:30 | Sarah 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:40 | Noga 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:50 | Jan 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:00 | Amit 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:20 | Coffee break | |
| RANDOM Session 5 | ||
| 11:20-11:30 | Reut Levi and Moti Medina. Distributed Testing of Graph Isomorphism in the CONGEST model | |
| 11:30-11:40 | Dana Ron and Asaf Rosin. Almost Optimal Distribution-Free Sample-Based Testing of k-Modality | |
| 11:40-11:50 | Nader Bshouty. Almost Optimal Testers for Concise Representations | |
| 11:50-12:00 | Clément Canonne and Karl Wimmer. Testing Data Binnings | |
| 12:00-12:10 | Anup 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:10 | Fedor Fomin, Petr Golovach, Fahad Panolan and Kirill Simonov. Low-rank binary matrix approximation in column-sum norm paper, presentation | |
| 7:10-7:20 | Dor Katzelnick and Roy Schwartz. Maximizing the Correlation: Extending Grothendieck’s Inequality to Large Domains paper, presentation | |
| 7:20-7:30 | Sayan Bandyapadhyay. On Perturbation Resilience of Non-Uniform k-Center paper, presentation | |
| 7:30-7:40 | Gá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:00 | Coffee Break | |
| APPROX Session 8 (chair: Andreas Feldmann) | ||
| 8:00-8:10 | Venkatesan Guruswami, Jakub Opršal and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP paper, presentation | |
| 8:10-8:20 | Petr Kolman and Eden Chlamtac. How to Cut a Ball without Separating: Improved Approximations for Length Bounded Cut paper, presentation | |
| 8:20-8:30 | Eunou Lee, Sean Hallgren and Ojas Parekh. An approximation algorithm for the MAX-2-Local Hamiltonian problem paper, presentation | |
| 8:30-9:00 | Coffee break | |
| 9:00-9:55 | Invited talk (chair: Anupam Gupta) Nathan Klein. A (Slightly) Improved Approximation Algorithm for Metric TSP | |
| 9:55-10:20 | Coffee break | |
| RANDOM Session 6 | APPROX Session 9 (chair: Anupam Gupta) | |
| 10:20-10:30 | Kwangjun 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:40 | Divesh 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:50 | Nicolas 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:00 | Aditya 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:20 | Coffee break | |
| RANDOM Session 7 | ||
| 11:20-11:30 | Tali Kaufman and Ella Sharakanski. Chernoff Bound for High-Dimensional Expanders | |
| 11:30-11:40 | Calvin Beideman, Karthekeyan Chandrasekaran and Chao Xu. Multicriteria cuts and size-constrained k-cuts in hypergraphs | |
| 11:40-11:50 | Linh Tran and Van Vu. Reaching a Consensus on Random Networks: The Power of Few | |
| 11:50-12:00 | Cyrus Rashtchian, David P. Woodruff and Hanlin Zhu. Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems | |
| 12:00-12:10 | Ali Pourmiri, Catherine Greenhill and Bernard Mans. Balanced Allocation on Dynamic Hypergraphs | |
APPROX CONFERENCE 