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} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Aditya Krishnan, Sidhanth Mohanty, and David P. Woodruff. On Sketching the q to p Norms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 15:1-15:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{krishnan_et_al:LIPIcs.APPROX-RANDOM.2018.15, author = {Krishnan, Aditya and Mohanty, Sidhanth and Woodruff, David P.}, title = {{On Sketching the q to p Norms}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {15:1--15:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.15}, URN = {urn:nbn:de:0030-drops-94192}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.15}, annote = {Keywords: Dimensionality Reduction, Norms, Sketching, Streaming} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ofer Grossman, Bernhard Haeupler, and Sidhanth Mohanty. Algorithms for Noisy Broadcast with Erasures. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 153:1-153:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{grossman_et_al:LIPIcs.ICALP.2018.153, author = {Grossman, Ofer and Haeupler, Bernhard and Mohanty, Sidhanth}, title = {{Algorithms for Noisy Broadcast with Erasures}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {153:1--153:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.153}, URN = {urn:nbn:de:0030-drops-91576}, doi = {10.4230/LIPIcs.ICALP.2018.153}, annote = {Keywords: noisy broadcast, error correction, erasures, distributed computing with noise} }