LIPIcs, Volume 245
APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference)
Editors: Amit Chakrabarti and Chaitanya Swamy
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Prantar Ghosh and Vihan Shah. New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 53:1-53:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ghosh_et_al:LIPIcs.ITCS.2024.53, author = {Ghosh, Prantar and Shah, Vihan}, title = {{New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {53:1--53:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.53}, URN = {urn:nbn:de:0030-drops-195815}, doi = {10.4230/LIPIcs.ITCS.2024.53}, annote = {Keywords: Graph Algorithms, Streaming, Communication Complexity, Stream Verification, Merlin-Arthur Communication, Lower Bounds} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Amit Chakrabarti and Chaitanya Swamy. LIPIcs, Volume 245, APPROX/RANDOM 2022, Complete Volume. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1-1064, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Proceedings{chakrabarti_et_al:LIPIcs.APPROX/RANDOM.2022, title = {{LIPIcs, Volume 245, APPROX/RANDOM 2022, Complete Volume}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {1--1064}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022}, URN = {urn:nbn:de:0030-drops-171211}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022}, annote = {Keywords: LIPIcs, Volume 245, APPROX/RANDOM 2022, Complete Volume} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Amit Chakrabarti and Chaitanya Swamy. Front Matter, Table of Contents, Preface, Conference Organization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chakrabarti_et_al:LIPIcs.APPROX/RANDOM.2022.0, author = {Chakrabarti, Amit and Swamy, Chaitanya}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {0:i--0:xx}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.0}, URN = {urn:nbn:de:0030-drops-171229}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A Unified Approach to Discrepancy Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1:1-1:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.APPROX/RANDOM.2022.1, author = {Bansal, Nikhil and Laddha, Aditi and Vempala, Santosh}, title = {{A Unified Approach to Discrepancy Minimization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {1:1--1:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.1}, URN = {urn:nbn:de:0030-drops-171238}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.1}, annote = {Keywords: Discrepancy theory, smoothed analysis} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Chin Ho Lee, Edward Pyne, and Salil Vadhan. Fourier Growth of Regular Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lee_et_al:LIPIcs.APPROX/RANDOM.2022.2, author = {Lee, Chin Ho and Pyne, Edward and Vadhan, Salil}, title = {{Fourier Growth of Regular Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {2:1--2:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.2}, URN = {urn:nbn:de:0030-drops-171247}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.2}, annote = {Keywords: pseudorandomness, fourier analysis} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Tali Kaufman and David Mass. Double Balanced Sets in High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 3:1-3:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.3, author = {Kaufman, Tali and Mass, David}, title = {{Double Balanced Sets in High Dimensional Expanders}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {3:1--3:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.3}, URN = {urn:nbn:de:0030-drops-171257}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.3}, annote = {Keywords: High dimensional expanders, Double balanced sets, Pseudorandom functions} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Antonio Blanca, Sarah Cannon, and Will Perkins. Fast and Perfect Sampling of Subgraphs and Polymer Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 4:1-4:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{blanca_et_al:LIPIcs.APPROX/RANDOM.2022.4, author = {Blanca, Antonio and Cannon, Sarah and Perkins, Will}, title = {{Fast and Perfect Sampling of Subgraphs and Polymer Systems}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {4:1--4:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.4}, URN = {urn:nbn:de:0030-drops-171261}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.4}, annote = {Keywords: Random Sampling, perfect sampling, graphlets, polymer models, spin systems, percolation} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Tali Kaufman and Izhar Oppenheim. High Dimensional Expansion Implies Amplified Local Testability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 5:1-5:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.5, author = {Kaufman, Tali and Oppenheim, Izhar}, title = {{High Dimensional Expansion Implies Amplified Local Testability}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {5:1--5:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.5}, URN = {urn:nbn:de:0030-drops-171276}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.5}, annote = {Keywords: Locally testable codes, High dimensional expanders, Amplified testing} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan. Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2022.6, author = {Girish, Uma and Mittal, Kunal and Raz, Ran and Zhan, Wei}, title = {{Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {6:1--6:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.6}, URN = {urn:nbn:de:0030-drops-171286}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.6}, annote = {Keywords: Parallel repetition, Multi-prover games, Fourier analysis} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Hermish Mehta and Daniel Reichman. Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{mehta_et_al:LIPIcs.APPROX/RANDOM.2022.7, author = {Mehta, Hermish and Reichman, Daniel}, title = {{Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.7}, URN = {urn:nbn:de:0030-drops-171299}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.7}, annote = {Keywords: Graph Algorithms, Random Graphs, Data Structures and Algorithms, Discrete Mathematics} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, and Ke Wu. Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 8:1-8:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gabrys_et_al:LIPIcs.APPROX/RANDOM.2022.8, author = {Gabrys, Ryan and Guruswami, Venkatesan and Ribeiro, Jo\~{a}o and Wu, Ke}, title = {{Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {8:1--8:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.8}, URN = {urn:nbn:de:0030-drops-171302}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.8}, annote = {Keywords: Synchronization errors, Optimal redundancy, Explicit codes} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine Extractors and AC0-Parity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2022.9, author = {Huang, Xuangui and Ivanov, Peter and Viola, Emanuele}, title = {{Affine Extractors and AC0-Parity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.9}, URN = {urn:nbn:de:0030-drops-171313}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.9}, annote = {Keywords: affine extractor, resilient function, constant-depth circuit, parity gate, inner product} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Zhao Song and Ruizhe Zhang. Hyperbolic Concentration, Anti-Concentration, and Discrepancy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 10:1-10:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{song_et_al:LIPIcs.APPROX/RANDOM.2022.10, author = {Song, Zhao and Zhang, Ruizhe}, title = {{Hyperbolic Concentration, Anti-Concentration, and Discrepancy}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {10:1--10:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.10}, URN = {urn:nbn:de:0030-drops-171324}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.10}, annote = {Keywords: Hyperbolic polynomial, Chernoff bound, Concentration, Discrepancy theory, Anti-concentration} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Dan Karliner and Amnon Ta-Shma. Improved Local Testing for Multiplicity Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{karliner_et_al:LIPIcs.APPROX/RANDOM.2022.11, author = {Karliner, Dan and Ta-Shma, Amnon}, title = {{Improved Local Testing for Multiplicity Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.11}, URN = {urn:nbn:de:0030-drops-171339}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.11}, annote = {Keywords: local testing, multiplicity codes, Reed Muller codes} }
Feedback for Dagstuhl Publishing