Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Stephen Jaud, Anthony Wirth, and Farhana Choudhury. Maximum Coverage in Sublinear Space, Faster. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 21:1-21:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{jaud_et_al:LIPIcs.SEA.2023.21, author = {Jaud, Stephen and Wirth, Anthony and Choudhury, Farhana}, title = {{Maximum Coverage in Sublinear Space, Faster}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {21:1--21:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.21}, URN = {urn:nbn:de:0030-drops-183715}, doi = {10.4230/LIPIcs.SEA.2023.21}, annote = {Keywords: streaming algorithms, subsampling, maximum set cover, k-wise independent hash functions} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha. An Algorithmic Bridge Between Hamming and Levenshtein Distances. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 58:1-58:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goldenberg_et_al:LIPIcs.ITCS.2023.58, author = {Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna}, title = {{An Algorithmic Bridge Between Hamming and Levenshtein Distances}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.58}, URN = {urn:nbn:de:0030-drops-175615}, doi = {10.4230/LIPIcs.ITCS.2023.58}, annote = {Keywords: edit distance, Hamming distance, Longest Common Extension queries} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Debarati Das and Barna Saha. Approximating LCS and Alignment Distance over Multiple Sequences. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 54:1-54:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{das_et_al:LIPIcs.APPROX/RANDOM.2022.54, author = {Das, Debarati and Saha, Barna}, title = {{Approximating LCS and Alignment Distance over Multiple Sequences}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {54:1--54: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.54}, URN = {urn:nbn:de:0030-drops-171762}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.54}, annote = {Keywords: String Algorithms, Approximation Algorithms} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Debarati Das, Tomasz Kociumaka, and Barna Saha. Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 49:1-49:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{das_et_al:LIPIcs.ICALP.2022.49, author = {Das, Debarati and Kociumaka, Tomasz and Saha, Barna}, title = {{Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {49:1--49:20}, 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.49}, URN = {urn:nbn:de:0030-drops-163902}, doi = {10.4230/LIPIcs.ICALP.2022.49}, annote = {Keywords: Dyck Edit Distance, RNA Folding, String Algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Barna Saha. Sublinear Algorithms for Edit Distance (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 5:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{saha:LIPIcs.MFCS.2021.5, author = {Saha, Barna}, title = {{Sublinear Algorithms for Edit Distance}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.5}, URN = {urn:nbn:de:0030-drops-144452}, doi = {10.4230/LIPIcs.MFCS.2021.5}, annote = {Keywords: Edit distance, sublinear algorithms, string processing} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connectivity of Random Annulus Graphs and the Geometric Block Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 53:1-53:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{galhotra_et_al:LIPIcs.APPROX-RANDOM.2019.53, author = {Galhotra, Sainyam and Mazumdar, Arya and Pal, Soumyabrata and Saha, Barna}, title = {{Connectivity of Random Annulus Graphs and the Geometric Block Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {53:1--53:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.53}, URN = {urn:nbn:de:0030-drops-112682}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.53}, annote = {Keywords: random graphs, geometric graphs, community detection, block model} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Barna Saha and Sanjay Subramanian. Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 81:1-81:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{saha_et_al:LIPIcs.ESA.2019.81, author = {Saha, Barna and Subramanian, Sanjay}, title = {{Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {81:1--81:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.81}, URN = {urn:nbn:de:0030-drops-112020}, doi = {10.4230/LIPIcs.ESA.2019.81}, annote = {Keywords: Clustering, Approximation Algorithm, Crowdsourcing, Randomized Algorithm} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Rajesh Jayaram and Barna Saha. Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 19:1-19:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{jayaram_et_al:LIPIcs.ICALP.2017.19, author = {Jayaram, Rajesh and Saha, Barna}, title = {{Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {19:1--19: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.19}, URN = {urn:nbn:de:0030-drops-74548}, doi = {10.4230/LIPIcs.ICALP.2017.19}, annote = {Keywords: Approximation, Edit Distance, Dynamic Programming, Context Free Grammar, Hardness} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Barna Saha. Renting a Cloud. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 437-448, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{saha:LIPIcs.FSTTCS.2013.437, author = {Saha, Barna}, title = {{Renting a Cloud}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {437--448}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.437}, URN = {urn:nbn:de:0030-drops-43918}, doi = {10.4230/LIPIcs.FSTTCS.2013.437}, annote = {Keywords: Scheduling Algorithm, Online Algorithm, Approximation Algorithm} }
Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)
Samir Khuller, Jian Li, and Barna Saha. Energy Efficient Scheduling via Partial Shutdown. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
@InProceedings{khuller_et_al:DagSemProc.10071.5, author = {Khuller, Samir and Li, Jian and Saha, Barna}, title = {{Energy Efficient Scheduling via Partial Shutdown}}, booktitle = {Scheduling}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10071}, editor = {Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.5}, URN = {urn:nbn:de:0030-drops-25435}, doi = {10.4230/DagSemProc.10071.5}, annote = {Keywords: Unrelated parallel machine scheduling, approximation algorithms} }
Feedback for Dagstuhl Publishing