Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Diba Hashemi and Weronika Wrzos-Kaminska. Weighted Matching in the Random-Order Streaming and Robust Communication Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hashemi_et_al:LIPIcs.APPROX/RANDOM.2024.16, author = {Hashemi, Diba and Wrzos-Kaminska, Weronika}, title = {{Weighted Matching in the Random-Order Streaming and Robust Communication Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {16:1--16:26}, 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.16}, URN = {urn:nbn:de:0030-drops-210097}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.16}, annote = {Keywords: Maximum Weight Matching, Streaming, Random-Order Streaming, Robust Communication Complexity} }
Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)
Benny Applebaum, Kaartik Bhushan, and Manoj Prabhakaran. Communication Complexity vs Randomness Complexity in Interactive Proofs. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{applebaum_et_al:LIPIcs.ITC.2024.2, author = {Applebaum, Benny and Bhushan, Kaartik and Prabhakaran, Manoj}, title = {{Communication Complexity vs Randomness Complexity in Interactive Proofs}}, booktitle = {5th Conference on Information-Theoretic Cryptography (ITC 2024)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-333-1}, ISSN = {1868-8969}, year = {2024}, volume = {304}, editor = {Aggarwal, Divesh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.2}, URN = {urn:nbn:de:0030-drops-205103}, doi = {10.4230/LIPIcs.ITC.2024.2}, annote = {Keywords: Interactive Proof Systems, Communication Complexity, Hash Functions, Pseudo-Random Generators, Compression} }
Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)
Yuval Ishai, Mahimna Kelkar, Daniel Lee, and Yiping Ma. Information-Theoretic Single-Server PIR in the Shuffle Model. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ishai_et_al:LIPIcs.ITC.2024.6, author = {Ishai, Yuval and Kelkar, Mahimna and Lee, Daniel and Ma, Yiping}, title = {{Information-Theoretic Single-Server PIR in the Shuffle Model}}, booktitle = {5th Conference on Information-Theoretic Cryptography (ITC 2024)}, pages = {6:1--6:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-333-1}, ISSN = {1868-8969}, year = {2024}, volume = {304}, editor = {Aggarwal, Divesh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.6}, URN = {urn:nbn:de:0030-drops-205142}, doi = {10.4230/LIPIcs.ITC.2024.6}, annote = {Keywords: Private information retrieval, Shuffle model} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2024.38, author = {Chalermsook, Parinya and Gupta, Manoj and Jiamjitrak, Wanchote and Pareek, Akash and Yingchareonthawornchai, Sorrachai}, title = {{The Group Access Bounds for Binary Search Trees}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {38:1--38: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.38}, URN = {urn:nbn:de:0030-drops-201817}, doi = {10.4230/LIPIcs.ICALP.2024.38}, annote = {Keywords: Dynamic Optimality, Binary Search Tree, Online Algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Aditi Dudeja. Decremental Matching in General Weighted Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 59:1-59:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dudeja:LIPIcs.ICALP.2024.59, author = {Dudeja, Aditi}, title = {{Decremental Matching in General Weighted Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {59:1--59: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.59}, URN = {urn:nbn:de:0030-drops-202020}, doi = {10.4230/LIPIcs.ICALP.2024.59}, annote = {Keywords: Weighted Matching, Dynamic Algorithms, Adaptive Adversary} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Dipan Dey and Manoj Gupta. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dey_et_al:LIPIcs.ESA.2022.42, author = {Dey, Dipan and Gupta, Manoj}, title = {{Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {42:1--42:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.42}, URN = {urn:nbn:de:0030-drops-169800}, doi = {10.4230/LIPIcs.ESA.2022.42}, annote = {Keywords: distance sensitivity oracle, single-source replacement paths} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Manoj Gupta and Aditi Singh. Generic Single Edge Fault Tolerant Exact Distance Oracle. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2018.72, author = {Gupta, Manoj and Singh, Aditi}, title = {{Generic Single Edge Fault Tolerant Exact Distance Oracle}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {72:1--72:15}, 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.72}, URN = {urn:nbn:de:0030-drops-90766}, doi = {10.4230/LIPIcs.ICALP.2018.72}, annote = {Keywords: Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, Data-Structures} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Sayan Bhattacharya, Manoj Gupta, and Divyarthi Mohan. Improved Algorithm for Dynamic b-Matching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2017.15, author = {Bhattacharya, Sayan and Gupta, Manoj and Mohan, Divyarthi}, title = {{Improved Algorithm for Dynamic b-Matching}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.15}, URN = {urn:nbn:de:0030-drops-78443}, doi = {10.4230/LIPIcs.ESA.2017.15}, annote = {Keywords: dynamic data structures, graph algorithms} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Manoj Gupta and Shahbaz Khan. Multiple Source Dual Fault Tolerant BFS Trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 127:1-127:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{gupta_et_al:LIPIcs.ICALP.2017.127, author = {Gupta, Manoj and Khan, Shahbaz}, title = {{Multiple Source Dual Fault Tolerant BFS Trees}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {127:1--127:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.127}, URN = {urn:nbn:de:0030-drops-74184}, doi = {10.4230/LIPIcs.ICALP.2017.127}, annote = {Keywords: BFS, fault-tolerant, graph, algorithms, data-structures} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Manoj Gupta. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 227-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{gupta:LIPIcs.FSTTCS.2014.227, author = {Gupta, Manoj}, title = {{Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {227--239}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.227}, URN = {urn:nbn:de:0030-drops-48453}, doi = {10.4230/LIPIcs.FSTTCS.2014.227}, annote = {Keywords: Graph Algorithm, Dynamic Graph} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 257-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{anand_et_al:LIPIcs.FSTTCS.2012.257, author = {Anand, Abhash and Baswana, Surender and Gupta, Manoj and Sen, Sandeep}, title = {{Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {257--266}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.257}, URN = {urn:nbn:de:0030-drops-38648}, doi = {10.4230/LIPIcs.FSTTCS.2012.257}, annote = {Keywords: Matching, Dynamic Algorithm, Graph Algorithm} }
Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Manoj Gupta, Yogish Sabharwal, and Sandeep Sen. The update complexity of selection and related problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 325-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2011.325, author = {Gupta, Manoj and Sabharwal, Yogish and Sen, Sandeep}, title = {{The update complexity of selection and related problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {325--338}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.325}, URN = {urn:nbn:de:0030-drops-33314}, doi = {10.4230/LIPIcs.FSTTCS.2011.325}, annote = {Keywords: Uncertain data, Competitive analysis} }
Feedback for Dagstuhl Publishing