LIPIcs, Volume 4
FSTTCS 2009, December 15-17, 2009, Kanpur, India
Editors: Ravi Kannan and K. Narayan Kumar
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, and Sagnik Mukhopadhyay. Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{assadi_et_al:LIPIcs.CCC.2024.7, author = {Assadi, Sepehr and Ghosh, Prantar and Loff, Bruno and Mittal, Parth and Mukhopadhyay, Sagnik}, title = {{Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {7:1--7: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.7}, URN = {urn:nbn:de:0030-drops-204035}, doi = {10.4230/LIPIcs.CCC.2024.7}, annote = {Keywords: Graph streaming, Lower bounds, Communication complexity, k-Cores and degeneracy} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena. Information Dissemination via Broadcasts in the Presence of Adversarial Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 19:1-19:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{efremenko_et_al:LIPIcs.CCC.2024.19, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Raz, Ran and Saxena, Raghuvansh R.}, title = {{Information Dissemination via Broadcasts in the Presence of Adversarial Noise}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {19:1--19:33}, 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.19}, URN = {urn:nbn:de:0030-drops-204159}, doi = {10.4230/LIPIcs.CCC.2024.19}, annote = {Keywords: Radio Networks, Interactive Coding, Error Correcting Codes} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum. Distribution-Free Proofs of Proximity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2024.24, author = {Aaronson, Hugo and Gur, Tom and Rajgopal, Ninad and Rothblum, Ron D.}, title = {{Distribution-Free Proofs of Proximity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {24:1--24:18}, 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.24}, URN = {urn:nbn:de:0030-drops-204204}, doi = {10.4230/LIPIcs.CCC.2024.24}, annote = {Keywords: Property Testing, Interactive Proofs, Distribution-Free Property Testing} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Adil Chhabra, Marcelo Fonseca Faraj, Christian Schulz, and Daniel Seemaier. Buffered Streaming Edge Partitioning. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chhabra_et_al:LIPIcs.SEA.2024.5, author = {Chhabra, Adil and Fonseca Faraj, Marcelo and Schulz, Christian and Seemaier, Daniel}, title = {{Buffered Streaming Edge Partitioning}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.5}, URN = {urn:nbn:de:0030-drops-203701}, doi = {10.4230/LIPIcs.SEA.2024.5}, annote = {Keywords: graph partitioning, edge partitioning, streaming, online, buffered partitioning} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{abbasi_et_al:LIPIcs.ICALP.2024.6, author = {Abbasi, Fateme and Banerjee, Sandip and Byrka, Jaros{\l}aw and Chalermsook, Parinya and Gadekar, Ameet and Khodamoradi, Kamyar and Marx, D\'{a}niel and Sharma, Roohani and Spoerhase, Joachim}, title = {{Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-201494}, doi = {10.4230/LIPIcs.ICALP.2024.6}, annote = {Keywords: Clustering, approximation algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37, author = {Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia}, title = {{Fast Approximate Counting of Cycles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {37:1--37:20}, 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.37}, URN = {urn:nbn:de:0030-drops-201809}, doi = {10.4230/LIPIcs.ICALP.2024.37}, annote = {Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.45, author = {Chen, Li and Ye, Mingquan}, title = {{High-Accuracy Multicommodity Flows via Iterative Refinement}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {45:1--45:19}, 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.45}, URN = {urn:nbn:de:0030-drops-201887}, doi = {10.4230/LIPIcs.ICALP.2024.45}, annote = {Keywords: High-accuracy multicommodity flow, Iterative refinement framework, Convex flow solver} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Yu Chen, Michael Kapralov, Mikhail Makarov, and Davide Mazzali. On the Streaming Complexity of Expander Decomposition. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.46, author = {Chen, Yu and Kapralov, Michael and Makarov, Mikhail and Mazzali, Davide}, title = {{On the Streaming Complexity of Expander Decomposition}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {46:1--46:20}, 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.46}, URN = {urn:nbn:de:0030-drops-201890}, doi = {10.4230/LIPIcs.ICALP.2024.46}, annote = {Keywords: Graph Sketching, Dynamic Streaming, Expander Decomposition} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50:20}, 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.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sami Davies, Benjamin Moseley, and Heather Newman. Simultaneously Approximating All 𝓁_p-Norms in Correlation Clustering. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{davies_et_al:LIPIcs.ICALP.2024.52, author = {Davies, Sami and Moseley, Benjamin and Newman, Heather}, title = {{Simultaneously Approximating All 𝓁\underlinep-Norms in Correlation Clustering}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {52:1--52:20}, 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.52}, URN = {urn:nbn:de:0030-drops-201950}, doi = {10.4230/LIPIcs.ICALP.2024.52}, annote = {Keywords: Approximation algorithms, correlation clustering, all-norms, lp-norms} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Chiranjib Bhattacharyya, Ravindran Kannan, and Amit Kumar. Random Separating Hyperplane Theorem and Learning Polytopes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhattacharyya_et_al:LIPIcs.ICALP.2024.25, author = {Bhattacharyya, Chiranjib and Kannan, Ravindran and Kumar, Amit}, title = {{Random Separating Hyperplane Theorem and Learning Polytopes}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {25:1--25:20}, 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.25}, URN = {urn:nbn:de:0030-drops-201687}, doi = {10.4230/LIPIcs.ICALP.2024.25}, annote = {Keywords: Separating Hyperplane Theorem, Learning Polytopes, Optimization Oracles} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27:20}, 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.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski. Dynamic PageRank: Algorithms and Lower Bounds. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 90:1-90:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jayaram_et_al:LIPIcs.ICALP.2024.90, author = {Jayaram, Rajesh and {\L}\k{a}cki, Jakub and Mitrovi\'{c}, Slobodan and Onak, Krzysztof and Sankowski, Piotr}, title = {{Dynamic PageRank: Algorithms and Lower Bounds}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {90:1--90:19}, 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.90}, URN = {urn:nbn:de:0030-drops-202336}, doi = {10.4230/LIPIcs.ICALP.2024.90}, annote = {Keywords: PageRank, dynamic algorithms, graph algorithms} }
Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, and Samson Zhou. Differentially Private Aggregation via Imperfect Shuffling. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 17:1-17:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ITC.2023.17, author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin and Nelson, Jelani and Zhou, Samson}, title = {{Differentially Private Aggregation via Imperfect Shuffling}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {17:1--17:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.17}, URN = {urn:nbn:de:0030-drops-183453}, doi = {10.4230/LIPIcs.ITC.2023.17}, annote = {Keywords: Differential privacy, private summation, shuffle model} }