Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, and Huacheng Yu. On the Amortized Complexity of Approximate Counting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{adenali_et_al:LIPIcs.APPROX/RANDOM.2024.33, author = {Aden-Ali, Ishaq and Han, Yanjun and Nelson, Jelani and Yu, Huacheng}, title = {{On the Amortized Complexity of Approximate Counting}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {33:1--33:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.33}, URN = {urn:nbn:de:0030-drops-210264}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.33}, annote = {Keywords: streaming, approximate counting, information complexity, lower bounds} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen. When Can an Expander Code Correct Ω(n) Errors in O(n) Time?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.61, author = {Cheng, Kuan and Ouyang, Minghui and Shangguan, Chong and Shen, Yuanting}, title = {{When Can an Expander Code Correct \Omega(n) Errors in O(n) Time?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {61:1--61:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.61}, URN = {urn:nbn:de:0030-drops-210543}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.61}, annote = {Keywords: expander codes, expander graphs, linear-time decoding} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Yotam Dikstein and Irit Dinur. Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 62:1-62:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dikstein_et_al:LIPIcs.APPROX/RANDOM.2024.62, author = {Dikstein, Yotam and Dinur, Irit}, title = {{Coboundary and Cosystolic Expansion Without Dependence on Dimension or Degree}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {62:1--62:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.62}, URN = {urn:nbn:de:0030-drops-210556}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.62}, annote = {Keywords: High Dimensional Expanders, HDX, Spectral Expansion, Coboundary Expansion, Cocycle Expansion, Cosystolic Expansion} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Inbar Ben Yaacov, Yotam Dikstein, and Gal Maor. Sparse High Dimensional Expanders via Local Lifts. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 68:1-68:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2024.68, author = {Ben Yaacov, Inbar and Dikstein, Yotam and Maor, Gal}, title = {{Sparse High Dimensional Expanders via Local Lifts}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {68:1--68:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.68}, URN = {urn:nbn:de:0030-drops-210612}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.68}, annote = {Keywords: High Dimensional Expanders, HDX, Spectral Expansion, Lifts, Covers, Explicit Constructions, Randomized Constructions, Deterministic Constructions} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Andreas Galanis, Alkis Kalavasis, and Anthimos Vardis Kandiros. On Sampling from Ising Models with Spectral Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galanis_et_al:LIPIcs.APPROX/RANDOM.2024.70, author = {Galanis, Andreas and Kalavasis, Alkis and Kandiros, Anthimos Vardis}, title = {{On Sampling from Ising Models with Spectral Constraints}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {70:1--70:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.70}, URN = {urn:nbn:de:0030-drops-210638}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.70}, annote = {Keywords: Ising model, spectral constraints, Glauber dynamics, mean-field Ising, random regular graphs} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {8:1--8:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.8}, URN = {urn:nbn:de:0030-drops-204045}, doi = {10.4230/LIPIcs.CCC.2024.8}, annote = {Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Amit Chakrabarti and Manuel Stoeckl. Finding Missing Items Requires Strong Forms of Randomness. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2024.28, author = {Chakrabarti, Amit and Stoeckl, Manuel}, title = {{Finding Missing Items Requires Strong Forms of Randomness}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.28}, URN = {urn:nbn:de:0030-drops-204242}, doi = {10.4230/LIPIcs.CCC.2024.28}, annote = {Keywords: Data streaming, lower bounds, space complexity, adversarial robustness, derandomization, sketching, sampling} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shuichi Hirahara and Naoto Ohsaka. Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 85:1-85:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hirahara_et_al:LIPIcs.ICALP.2024.85, author = {Hirahara, Shuichi and Ohsaka, Naoto}, title = {{Optimal PSPACE-Hardness of Approximating Set Cover Reconfiguration}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {85:1--85:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.85}, URN = {urn:nbn:de:0030-drops-202283}, doi = {10.4230/LIPIcs.ICALP.2024.85}, annote = {Keywords: reconfiguration problems, hardness of approximation, probabilistic proof systems, FGLSS reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 113:1-113:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ohsaka:LIPIcs.ICALP.2024.113, author = {Ohsaka, Naoto}, title = {{Alphabet Reduction for Reconfiguration Problems}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {113:1--113:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.113}, URN = {urn:nbn:de:0030-drops-202560}, doi = {10.4230/LIPIcs.ICALP.2024.113}, annote = {Keywords: reconfiguration problems, hardness of approximation, Hadamard codes, alphabet reduction} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Venkatesan Guruswami, Peter Manohar, and Jonathan Mosheiff. 𝓁_p-Spread and Restricted Isometry Properties of Sparse Random Matrices. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.CCC.2022.7, author = {Guruswami, Venkatesan and Manohar, Peter and Mosheiff, Jonathan}, title = {{𝓁\underlinep-Spread and Restricted Isometry Properties of Sparse Random Matrices}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {7:1--7:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.7}, URN = {urn:nbn:de:0030-drops-165695}, doi = {10.4230/LIPIcs.CCC.2022.7}, annote = {Keywords: Spread Subspaces, Euclidean Sections, Restricted Isometry Property, Sparse Matrices} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Jun-Ting Hsieh, Sidhanth Mohanty, and Jeff Xu. Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hsieh_et_al:LIPIcs.CCC.2022.11, author = {Hsieh, Jun-Ting and Mohanty, Sidhanth and Xu, Jeff}, title = {{Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {11:1--11:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.11}, URN = {urn:nbn:de:0030-drops-165735}, doi = {10.4230/LIPIcs.CCC.2022.11}, annote = {Keywords: constraint satisfaction problems, certified counting, random graphs} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Theo McKenzie and Sidhanth Mohanty. High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 96:1-96:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mckenzie_et_al:LIPIcs.ICALP.2021.96, author = {McKenzie, Theo and Mohanty, Sidhanth}, title = {{High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {96:1--96:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.96}, URN = {urn:nbn:de:0030-drops-141655}, doi = {10.4230/LIPIcs.ICALP.2021.96}, annote = {Keywords: expander graphs, Ramanujan graphs, vertex expansion, girth} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. The SDP Value for Random Two-Eigenvalue CSPs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 50:1-50:45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mohanty_et_al:LIPIcs.STACS.2020.50, author = {Mohanty, Sidhanth and O'Donnell, Ryan and Paredes, Pedro}, title = {{The SDP Value for Random Two-Eigenvalue CSPs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {50:1--50:45}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.50}, URN = {urn:nbn:de:0030-drops-119110}, doi = {10.4230/LIPIcs.STACS.2020.50}, annote = {Keywords: Semidefinite programming, constraint satisfaction problems} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang. High-Dimensional Expanders from Expanders. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 12:1-12:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{liu_et_al:LIPIcs.ITCS.2020.12, author = {Liu, Siqi and Mohanty, Sidhanth and Yang, Elizabeth}, title = {{High-Dimensional Expanders from Expanders}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {12:1--12:32}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.12}, URN = {urn:nbn:de:0030-drops-116974}, doi = {10.4230/LIPIcs.ITCS.2020.12}, annote = {Keywords: High-Dimensional Expanders, Markov Chains} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. Pseudo-Deterministic Streaming. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 79:1-79:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2020.79, author = {Goldwasser, Shafi and Grossman, Ofer and Mohanty, Sidhanth and Woodruff, David P.}, title = {{Pseudo-Deterministic Streaming}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {79:1--79:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.79}, URN = {urn:nbn:de:0030-drops-117644}, doi = {10.4230/LIPIcs.ITCS.2020.79}, annote = {Keywords: streaming, pseudo-deterministic} }
Feedback for Dagstuhl Publishing