Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Barna Saha
@inproceedings{DBLP:conf/innovations/HenzingerSSY24,
author = {Monika Henzinger and
Barna Saha and
Martin P. Seybold and
Christopher Ye},
editor = {Venkatesan Guruswami},
title = {On the Complexity of Algorithms with Predictions for Dynamic Graph
Problems},
booktitle = {15th Innovations in Theoretical Computer Science Conference, {ITCS}
2024, January 30 to February 2, 2024, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {287},
pages = {62:1--62:25},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2024},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2024.62},
doi = {10.4230/LIPICS.ITCS.2024.62},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/HenzingerSSY24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/SahaY24,
author = {Barna Saha and
Christopher Ye},
editor = {David P. Woodruff},
title = {Faster Approximate All Pairs Shortest Paths},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {4758--4827},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.170},
doi = {10.1137/1.9781611977912.170},
timestamp = {Thu, 04 Apr 2024 19:38:10 +0200},
biburl = {https://dblp.org/rec/conf/soda/SahaY24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2402-07443,
author = {Barna Saha and
Christopher Ye},
title = {The {I/O} Complexity of Attention, or How Optimal is Flash Attention?},
journal = {CoRR},
volume = {abs/2402.07443},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.07443},
doi = {10.48550/ARXIV.2402.07443},
eprinttype = {arXiv},
eprint = {2402.07443},
timestamp = {Fri, 16 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-07443.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Kociumaka0S23,
author = {Tomasz Kociumaka and
Anish Mukherjee and
Barna Saha},
title = {Approximating Edit Distance in the Fully Dynamic Model},
booktitle = {64th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2023, Santa Cruz, CA, USA, November 6-9, 2023},
pages = {1628--1638},
publisher = {{IEEE}},
year = {2023},
url = {https://doi.org/10.1109/FOCS57990.2023.00098},
doi = {10.1109/FOCS57990.2023.00098},
timestamp = {Tue, 02 Jan 2024 14:56:14 +0100},
biburl = {https://dblp.org/rec/conf/focs/Kociumaka0S23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/GoldenbergKKS23,
author = {Elazar Goldenberg and
Tomasz Kociumaka and
Robert Krauthgamer and
Barna Saha},
editor = {Yael Tauman Kalai},
title = {An Algorithmic Bridge Between Hamming and Levenshtein Distances},
booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS}
2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}},
series = {LIPIcs},
volume = {251},
pages = {58:1--58:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2023},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.58},
doi = {10.4230/LIPICS.ITCS.2023.58},
timestamp = {Thu, 02 Feb 2023 12:50:42 +0100},
biburl = {https://dblp.org/rec/conf/innovations/GoldenbergKKS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/0001GHKS23,
author = {Debarati Das and
Jacob Gilbert and
MohammadTaghi Hajiaghayi and
Tomasz Kociumaka and
Barna Saha},
editor = {Barna Saha and
Rocco A. Servedio},
title = {Weighted Edit Distance Computation: Strings, Trees, and Dyck},
booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
pages = {377--390},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246.3585178},
doi = {10.1145/3564246.3585178},
timestamp = {Mon, 22 May 2023 13:01:48 +0200},
biburl = {https://dblp.org/rec/conf/stoc/0001GHKS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/stoc/2023,
editor = {Barna Saha and
Rocco A. Servedio},
title = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing,
{STOC} 2023, Orlando, FL, USA, June 20-23, 2023},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3564246},
doi = {10.1145/3564246},
isbn = {978-1-4503-9913-5},
timestamp = {Mon, 22 May 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stoc/2023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2302-04229,
author = {Debarati Das and
Jacob Gilbert and
MohammadTaghi Hajiaghayi and
Tomasz Kociumaka and
Barna Saha},
title = {Weighted Edit Distance Computation: Strings, Trees and Dyck},
journal = {CoRR},
volume = {abs/2302.04229},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2302.04229},
doi = {10.48550/ARXIV.2302.04229},
eprinttype = {arXiv},
eprint = {2302.04229},
timestamp = {Fri, 10 Feb 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2302-04229.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-07175,
author = {Tomasz Kociumaka and
Anish Mukherjee and
Barna Saha},
title = {Approximating Edit Distance in the Fully Dynamic Model},
journal = {CoRR},
volume = {abs/2307.07175},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.07175},
doi = {10.48550/ARXIV.2307.07175},
eprinttype = {arXiv},
eprint = {2307.07175},
timestamp = {Mon, 13 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-07175.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-16771,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha and
Martin P. Seybold and
Christopher Ye},
title = {On the Complexity of Algorithms with Predictions for Dynamic Graph
Problems},
journal = {CoRR},
volume = {abs/2307.16771},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.16771},
doi = {10.48550/ARXIV.2307.16771},
eprinttype = {arXiv},
eprint = {2307.16771},
timestamp = {Wed, 02 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-16771.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2309-13225,
author = {Barna Saha and
Christopher Ye},
title = {Faster Approximate All Pairs Shortest Paths},
journal = {CoRR},
volume = {abs/2309.13225},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2309.13225},
doi = {10.48550/ARXIV.2309.13225},
eprinttype = {arXiv},
eprint = {2309.13225},
timestamp = {Wed, 27 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2309-13225.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/DasS22,
author = {Debarati Das and
Barna Saha},
editor = {Amit Chakrabarti and
Chaitanya Swamy},
title = {Approximating {LCS} and Alignment Distance over Multiple Sequences},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2022, September 19-21, 2022, University
of Illinois, Urbana-Champaign, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {245},
pages = {54:1--54:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.54},
doi = {10.4230/LIPICS.APPROX/RANDOM.2022.54},
timestamp = {Mon, 26 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/DasS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GoldenbergKKS22,
author = {Elazar Goldenberg and
Tomasz Kociumaka and
Robert Krauthgamer and
Barna Saha},
title = {Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {674--685},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00070},
doi = {10.1109/FOCS54457.2022.00070},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GoldenbergKKS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/0001GHKSS22,
author = {Debarati Das and
Jacob Gilbert and
MohammadTaghi Hajiaghayi and
Tomasz Kociumaka and
Barna Saha and
Hamed Saleh},
title = {{\~{O}}(n+poly(k))-time Algorithm for Bounded Tree Edit Distance},
booktitle = {63rd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2022, Denver, CO, USA, October 31 - November 3, 2022},
pages = {686--697},
publisher = {{IEEE}},
year = {2022},
url = {https://doi.org/10.1109/FOCS54457.2022.00071},
doi = {10.1109/FOCS54457.2022.00071},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/0001GHKSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/0001KS22,
author = {Debarati Das and
Tomasz Kociumaka and
Barna Saha},
editor = {Mikolaj Bojanczyk and
Emanuela Merelli and
David P. Woodruff},
title = {Improved Approximation Algorithms for Dyck Edit Distance and {RNA}
Folding},
booktitle = {49th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2022, July 4-8, 2022, Paris, France},
series = {LIPIcs},
volume = {229},
pages = {49:1--49:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2022.49},
doi = {10.4230/LIPICS.ICALP.2022.49},
timestamp = {Tue, 28 Jun 2022 15:52:51 +0200},
biburl = {https://dblp.org/rec/conf/icalp/0001KS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigmod/GalhotraFSS22,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
editor = {Zachary G. Ives and
Angela Bonifati and
Amr El Abbadi},
title = {Hierarchical Entity Resolution using an Oracle},
booktitle = {{SIGMOD} '22: International Conference on Management of Data, Philadelphia,
PA, USA, June 12 - 17, 2022},
pages = {414--428},
publisher = {{ACM}},
year = {2022},
url = {https://doi.org/10.1145/3514221.3526147},
doi = {10.1145/3514221.3526147},
timestamp = {Thu, 16 Mar 2023 09:51:25 +0100},
biburl = {https://dblp.org/rec/conf/sigmod/GalhotraFSS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HenzingerLS22,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {The Complexity of Average-Case Dynamic Subgraph Counting},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {459--498},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.23},
doi = {10.1137/1.9781611977073.23},
timestamp = {Tue, 12 Apr 2022 11:24:56 +0200},
biburl = {https://dblp.org/rec/conf/soda/HenzingerLS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KempaS22,
author = {Dominik Kempa and
Barna Saha},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {An Upper Bound and Linear-Space Queries on the LZ-End Parsing},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {2847--2866},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.111},
doi = {10.1137/1.9781611977073.111},
timestamp = {Tue, 12 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/KempaS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/GaneshKLS22,
author = {Arun Ganesh and
Tomasz Kociumaka and
Andrea Lincoln and
Barna Saha},
editor = {Joseph (Seffi) Naor and
Niv Buchbinder},
title = {How Compression and Approximation Affect Efficiency in String Distance
Measures},
booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
12, 2022},
pages = {2867--2919},
publisher = {{SIAM}},
year = {2022},
url = {https://doi.org/10.1137/1.9781611977073.112},
doi = {10.1137/1.9781611977073.112},
timestamp = {Tue, 12 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/GaneshKLS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-11303,
author = {Sainyam Galhotra and
Arya Mazumdar and
Soumyabrata Pal and
Barna Saha},
title = {Community Recovery in the Geometric Block Model},
journal = {CoRR},
volume = {abs/2206.11303},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.11303},
doi = {10.48550/ARXIV.2206.11303},
eprinttype = {arXiv},
eprint = {2206.11303},
timestamp = {Mon, 27 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-11303.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2209-07524,
author = {Debarati Das and
Jacob Gilbert and
MohammadTaghi Hajiaghayi and
Tomasz Kociumaka and
Barna Saha and
Hamed Saleh},
title = {O{\~}(n+poly(k))-time Algorithm for Bounded Tree Edit Distance},
journal = {CoRR},
volume = {abs/2209.07524},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2209.07524},
doi = {10.48550/ARXIV.2209.07524},
eprinttype = {arXiv},
eprint = {2209.07524},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2209-07524.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2211-12496,
author = {Elazar Goldenberg and
Tomasz Kociumaka and
Robert Krauthgamer and
Barna Saha},
title = {An Algorithmic Bridge Between Hamming and Levenshtein Distances},
journal = {CoRR},
volume = {abs/2211.12496},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2211.12496},
doi = {10.48550/ARXIV.2211.12496},
eprinttype = {arXiv},
eprint = {2211.12496},
timestamp = {Thu, 24 Nov 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2211-12496.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/AddankiGS21,
author = {Raghavendra Addanki and
Sainyam Galhotra and
Barna Saha},
title = {How to Design Robust Algorithms using Noisy Comparison Oracle},
journal = {Proc. {VLDB} Endow.},
volume = {14},
number = {10},
pages = {1703--1716},
year = {2021},
url = {http://www.vldb.org/pvldb/vol14/p1703-galhotra.pdf},
doi = {10.14778/3467861.3467862},
timestamp = {Thu, 21 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/AddankiGS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/vldb/GalhotraFSS21,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
title = {Efficient and effective {ER} with progressive blocking},
journal = {{VLDB} J.},
volume = {30},
number = {4},
pages = {537--557},
year = {2021},
url = {https://doi.org/10.1007/s00778-021-00656-7},
doi = {10.1007/S00778-021-00656-7},
timestamp = {Thu, 29 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/vldb/GalhotraFSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/Saha21,
author = {Barna Saha},
editor = {Filippo Bonchi and
Simon J. Puglisi},
title = {Sublinear Algorithms for Edit Distance (Invited Talk)},
booktitle = {46th International Symposium on Mathematical Foundations of Computer
Science, {MFCS} 2021, August 23-27, 2021, Tallinn, Estonia},
series = {LIPIcs},
volume = {202},
pages = {5:1--5:1},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.MFCS.2021.5},
doi = {10.4230/LIPICS.MFCS.2021.5},
timestamp = {Wed, 25 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/Saha21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/Saha21,
author = {Barna Saha},
editor = {Leonid Libkin and
Reinhard Pichler and
Paolo Guagliardo},
title = {Approximation Algorithms for Large Scale Data Analysis},
booktitle = {PODS'21: Proceedings of the 40th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium
on Principles of Database Systems, Virtual Event, China, June 20-25,
2021},
pages = {30--32},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3452021.3458813},
doi = {10.1145/3452021.3458813},
timestamp = {Mon, 21 Jun 2021 12:19:15 +0200},
biburl = {https://dblp.org/rec/conf/pods/Saha21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigmod/GalhotraFSS21,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
editor = {Guoliang Li and
Zhanhuai Li and
Stratos Idreos and
Divesh Srivastava},
title = {{BEER:} Blocking for Effective Entity Resolution},
booktitle = {{SIGMOD} '21: International Conference on Management of Data, Virtual
Event, China, June 20-25, 2021},
pages = {2711--2715},
publisher = {{ACM}},
year = {2021},
url = {https://doi.org/10.1145/3448016.3452747},
doi = {10.1145/3448016.3452747},
timestamp = {Mon, 21 Jun 2021 11:48:16 +0200},
biburl = {https://dblp.org/rec/conf/sigmod/GalhotraFSS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2105-05782,
author = {Raghavendra Addanki and
Sainyam Galhotra and
Barna Saha},
title = {How to Design Robust Algorithms using Noisy Comparison Oracle},
journal = {CoRR},
volume = {abs/2105.05782},
year = {2021},
url = {https://arxiv.org/abs/2105.05782},
eprinttype = {arXiv},
eprint = {2105.05782},
timestamp = {Tue, 18 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2105-05782.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2108-09115,
author = {Elazar Goldenberg and
Aviad Rubinstein and
Barna Saha},
title = {Does Preprocessing help in Fast Sequence Comparisons?},
journal = {CoRR},
volume = {abs/2108.09115},
year = {2021},
url = {https://arxiv.org/abs/2108.09115},
eprinttype = {arXiv},
eprint = {2108.09115},
timestamp = {Mon, 23 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2108-09115.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-12402,
author = {Debarati Das and
Barna Saha},
title = {Approximating {LCS} and Alignment Distance over Multiple Sequences},
journal = {CoRR},
volume = {abs/2110.12402},
year = {2021},
url = {https://arxiv.org/abs/2110.12402},
eprinttype = {arXiv},
eprint = {2110.12402},
timestamp = {Fri, 05 Nov 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-12402.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2111-12706,
author = {Elazar Goldenberg and
Tomasz Kociumaka and
Robert Krauthgamer and
Barna Saha},
title = {Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal},
journal = {CoRR},
volume = {abs/2111.12706},
year = {2021},
url = {https://arxiv.org/abs/2111.12706},
eprinttype = {arXiv},
eprint = {2111.12706},
timestamp = {Fri, 26 Nov 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2111-12706.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-05836,
author = {Arun Ganesh and
Tomasz Kociumaka and
Andrea Lincoln and
Barna Saha},
title = {How Compression and Approximation Affect Efficiency in String Distance
Measures},
journal = {CoRR},
volume = {abs/2112.05836},
year = {2021},
url = {https://arxiv.org/abs/2112.05836},
eprinttype = {arXiv},
eprint = {2112.05836},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-05836.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-05866,
author = {Debarati Das and
Tomasz Kociumaka and
Barna Saha},
title = {Improved Approximation Algorithms for Dyck Edit Distance and {RNA}
Folding},
journal = {CoRR},
volume = {abs/2112.05866},
year = {2021},
url = {https://arxiv.org/abs/2112.05866},
eprinttype = {arXiv},
eprint = {2112.05866},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-05866.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/HenzingerLS21,
author = {Monika Henzinger and
Andrea Lincoln and
Barna Saha},
title = {The Complexity of Average-Case Dynamic Subgraph Counting},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR21-157}},
year = {2021},
url = {https://eccc.weizmann.ac.il/report/2021/157},
eprinttype = {ECCC},
eprint = {TR21-157},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/HenzingerLS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/KociumakaS20,
author = {Tomasz Kociumaka and
Barna Saha},
editor = {Sandy Irani},
title = {Sublinear-Time Algorithms for Computing {\&} Embedding Gap Edit
Distance},
booktitle = {61st {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2020, Durham, NC, USA, November 16-19, 2020},
pages = {1168--1179},
publisher = {{IEEE}},
year = {2020},
url = {https://doi.org/10.1109/FOCS46700.2020.00112},
doi = {10.1109/FOCS46700.2020.00112},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/KociumakaS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/GoldenbergRS20,
author = {Elazar Goldenberg and
Aviad Rubinstein and
Barna Saha},
editor = {Konstantin Makarychev and
Yury Makarychev and
Madhur Tulsiani and
Gautam Kamath and
Julia Chuzhoy},
title = {Does preprocessing help in fast sequence comparisons?},
booktitle = {Proceedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020},
pages = {657--670},
publisher = {{ACM}},
year = {2020},
url = {https://doi.org/10.1145/3357713.3384300},
doi = {10.1145/3357713.3384300},
timestamp = {Mon, 18 Dec 2023 07:33:37 +0100},
biburl = {https://dblp.org/rec/conf/stoc/GoldenbergRS20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2002-03508,
author = {Saba Ahmadi and
Sainyam Galhotra and
Barna Saha and
Roy Schwartz},
title = {Fair Correlation Clustering},
journal = {CoRR},
volume = {abs/2002.03508},
year = {2020},
url = {https://arxiv.org/abs/2002.03508},
eprinttype = {arXiv},
eprint = {2002.03508},
timestamp = {Wed, 23 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2002-03508.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2005-14326,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
title = {Efficient and Effective {ER} with Progressive Blocking},
journal = {CoRR},
volume = {abs/2005.14326},
year = {2020},
url = {https://arxiv.org/abs/2005.14326},
eprinttype = {arXiv},
eprint = {2005.14326},
timestamp = {Wed, 03 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2005-14326.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2007-12762,
author = {Tomasz Kociumaka and
Barna Saha},
title = {Sublinear-Time Algorithms for Computing {\&} Embedding Gap Edit
Distance},
journal = {CoRR},
volume = {abs/2007.12762},
year = {2020},
url = {https://arxiv.org/abs/2007.12762},
eprinttype = {arXiv},
eprint = {2007.12762},
timestamp = {Wed, 29 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-12762.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BringmannGSW19,
author = {Karl Bringmann and
Fabrizio Grandoni and
Barna Saha and
Virginia Vassilevska Williams},
title = {Truly Subcubic Algorithms for Language Edit Distance and {RNA} Folding
via Fast Bounded-Difference Min-Plus Product},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {2},
pages = {481--512},
year = {2019},
url = {https://doi.org/10.1137/17M112720X},
doi = {10.1137/17M112720X},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/BringmannGSW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/GalhotraMPS19,
author = {Sainyam Galhotra and
Arya Mazumdar and
Soumyabrata Pal and
Barna Saha},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Connectivity of Random Annulus Graphs and the Geometric Block Model},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2019, September 20-22, 2019, Massachusetts
Institute of Technology, Cambridge, MA, {USA}},
series = {LIPIcs},
volume = {145},
pages = {53:1--53:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.53},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.53},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/GalhotraMPS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/SahaS19,
author = {Barna Saha and
Sanjay Subramanian},
editor = {Michael A. Bender and
Ola Svensson and
Grzegorz Herman},
title = {Correlation Clustering with Same-Cluster Queries Bounded by Optimal
Cost},
booktitle = {27th Annual European Symposium on Algorithms, {ESA} 2019, September
9-11, 2019, Munich/Garching, Germany},
series = {LIPIcs},
volume = {144},
pages = {81:1--81:17},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.ESA.2019.81},
doi = {10.4230/LIPICS.ESA.2019.81},
timestamp = {Sun, 08 Sep 2019 01:20:11 +0200},
biburl = {https://dblp.org/rec/conf/esa/SahaS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/GoldenbergKS19,
author = {Elazar Goldenberg and
Robert Krauthgamer and
Barna Saha},
editor = {David Zuckerman},
title = {Sublinear Algorithms for Gap Edit Distance},
booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2019, Baltimore, Maryland, USA, November 9-12, 2019},
pages = {1101--1120},
publisher = {{IEEE} Computer Society},
year = {2019},
url = {https://doi.org/10.1109/FOCS.2019.00070},
doi = {10.1109/FOCS.2019.00070},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/GoldenbergKS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/AhmadiKS19,
author = {Saba Ahmadi and
Samir Khuller and
Barna Saha},
editor = {Andrea Lodi and
Viswanath Nagarajan},
title = {Min-Max Correlation Clustering via MultiCut},
booktitle = {Integer Programming and Combinatorial Optimization - 20th International
Conference, {IPCO} 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {11480},
pages = {13--26},
publisher = {Springer},
year = {2019},
url = {https://doi.org/10.1007/978-3-030-17953-3\_2},
doi = {10.1007/978-3-030-17953-3\_2},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/AhmadiKS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kdd/KobrenSM19,
author = {Ari Kobren and
Barna Saha and
Andrew McCallum},
editor = {Ankur Teredesai and
Vipin Kumar and
Ying Li and
R{\'{o}}mer Rosales and
Evimaria Terzi and
George Karypis},
title = {Paper Matching with Local Fairness Constraints},
booktitle = {Proceedings of the 25th {ACM} {SIGKDD} International Conference on
Knowledge Discovery {\&} Data Mining, {KDD} 2019, Anchorage, AK,
USA, August 4-8, 2019},
pages = {1247--1257},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3292500.3330899},
doi = {10.1145/3292500.3330899},
timestamp = {Tue, 16 Aug 2022 23:04:27 +0200},
biburl = {https://dblp.org/rec/conf/kdd/KobrenSM19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sebd/GalhotraFSS19,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
editor = {Massimo Mecella and
Giuseppe Amato and
Claudio Gennaro},
title = {Crowd-Sourced Entity Resolution with Control Queries},
booktitle = {Proceedings of the 27th Italian Symposium on Advanced Database Systems,
Castiglione della Pescaia (Grosseto), Italy, June 16-19, 2019},
series = {{CEUR} Workshop Proceedings},
volume = {2400},
publisher = {CEUR-WS.org},
year = {2019},
url = {https://ceur-ws.org/Vol-2400/paper-26.pdf},
timestamp = {Fri, 10 Mar 2023 16:23:21 +0100},
biburl = {https://dblp.org/rec/conf/sebd/GalhotraFSS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/AbboudA0PS19,
author = {Amir Abboud and
Raghavendra Addanki and
Fabrizio Grandoni and
Debmalya Panigrahi and
Barna Saha},
editor = {Moses Charikar and
Edith Cohen},
title = {Dynamic set cover: improved algorithms and lower bounds},
booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019},
pages = {114--125},
publisher = {{ACM}},
year = {2019},
url = {https://doi.org/10.1145/3313276.3316376},
doi = {10.1145/3313276.3316376},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/AbboudA0PS19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1905-11924,
author = {Ari Kobren and
Barna Saha and
Andrew McCallum},
title = {Paper Matching with Local Fairness Constraints},
journal = {CoRR},
volume = {abs/1905.11924},
year = {2019},
url = {http://arxiv.org/abs/1905.11924},
eprinttype = {arXiv},
eprint = {1905.11924},
timestamp = {Mon, 03 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1905-11924.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1907-00117,
author = {Saba Ahmadi and
Sainyam Galhotra and
Samir Khuller and
Barna Saha and
Roy Schwartz},
title = {Min-Max Correlation Clustering via MultiCut},
journal = {CoRR},
volume = {abs/1907.00117},
year = {2019},
url = {http://arxiv.org/abs/1907.00117},
eprinttype = {arXiv},
eprint = {1907.00117},
timestamp = {Wed, 23 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1907-00117.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1908-04976,
author = {Barna Saha and
Sanjay Subramanian},
title = {Correlation Clustering with Same-Cluster Queries Bounded by Optimal
Cost},
journal = {CoRR},
volume = {abs/1908.04976},
year = {2019},
url = {http://arxiv.org/abs/1908.04976},
eprinttype = {arXiv},
eprint = {1908.04976},
timestamp = {Mon, 19 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1908-04976.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1910-00901,
author = {Elazar Goldenberg and
Robert Krauthgamer and
Barna Saha},
title = {Sublinear Algorithms for Gap Edit Distance},
journal = {CoRR},
volume = {abs/1910.00901},
year = {2019},
url = {http://arxiv.org/abs/1910.00901},
eprinttype = {arXiv},
eprint = {1910.00901},
timestamp = {Fri, 04 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1910-00901.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/debu/FirmaniGSS18,
author = {Donatella Firmani and
Sainyam Galhotra and
Barna Saha and
Divesh Srivastava},
title = {Robust Entity Resolution Using a CrowdOracle},
journal = {{IEEE} Data Eng. Bull.},
volume = {41},
number = {2},
pages = {91--103},
year = {2018},
url = {http://sites.computer.org/debull/A18june/p91.pdf},
timestamp = {Tue, 10 Mar 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/debu/FirmaniGSS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/SahaS18,
author = {Barna Saha and
Aravind Srinivasan},
title = {A new approximation technique for resource-allocation problems},
journal = {Random Struct. Algorithms},
volume = {52},
number = {4},
pages = {680--715},
year = {2018},
url = {https://doi.org/10.1002/rsa.20756},
doi = {10.1002/RSA.20756},
timestamp = {Thu, 21 Jun 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/SahaS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/BhattacharyyaGN18,
author = {Arnab Bhattacharyya and
Fabrizio Grandoni and
Aleksandar Nikolov and
Barna Saha and
Saket Saurabh and
Aravindan Vijayaraghavan and
Qin Zhang},
title = {Editorial: {ACM-SIAM} Symposium on Discrete Algorithms {(SODA)} 2016
Special Issue},
journal = {{ACM} Trans. Algorithms},
volume = {14},
number = {3},
pages = {26:1--26:2},
year = {2018},
url = {https://doi.org/10.1145/3230647},
doi = {10.1145/3230647},
timestamp = {Mon, 03 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/BhattacharyyaGN18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaai/GalhotraMPS18,
author = {Sainyam Galhotra and
Arya Mazumdar and
Soumyabrata Pal and
Barna Saha},
editor = {Sheila A. McIlraith and
Kilian Q. Weinberger},
title = {The Geometric Block Model},
booktitle = {Proceedings of the Thirty-Second {AAAI} Conference on Artificial Intelligence,
(AAAI-18), the 30th innovative Applications of Artificial Intelligence
(IAAI-18), and the 8th {AAAI} Symposium on Educational Advances in
Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February
2-7, 2018},
pages = {2215--2222},
publisher = {{AAAI} Press},
year = {2018},
url = {https://doi.org/10.1609/aaai.v32i1.11905},
doi = {10.1609/AAAI.V32I1.11905},
timestamp = {Mon, 04 Sep 2023 12:29:24 +0200},
biburl = {https://dblp.org/rec/conf/aaai/GalhotraMPS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/allerton/GalhotraPMS18,
author = {Sainyam Galhotra and
Soumyabrata Pal and
Arya Mazumdar and
Barna Saha},
title = {The Geometric Block Model and Applications},
booktitle = {56th Annual Allerton Conference on Communication, Control, and Computing,
Allerton 2018, Monticello, IL, USA, October 2-5, 2018},
pages = {1147--1150},
publisher = {{IEEE}},
year = {2018},
url = {https://doi.org/10.1109/ALLERTON.2018.8635938},
doi = {10.1109/ALLERTON.2018.8635938},
timestamp = {Wed, 16 Oct 2019 14:14:55 +0200},
biburl = {https://dblp.org/rec/conf/allerton/GalhotraPMS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sigmod/GalhotraFSS18,
author = {Sainyam Galhotra and
Donatella Firmani and
Barna Saha and
Divesh Srivastava},
editor = {Gautam Das and
Christopher M. Jermaine and
Philip A. Bernstein},
title = {Robust Entity Resolution using Random Graphs},
booktitle = {Proceedings of the 2018 International Conference on Management of
Data, {SIGMOD} Conference 2018, Houston, TX, USA, June 10-15, 2018},
pages = {3--18},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3183713.3183755},
doi = {10.1145/3183713.3183755},
timestamp = {Sat, 19 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/sigmod/GalhotraFSS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-03197,
author = {Raghavendra Addanki and
Barna Saha},
title = {Fully Dynamic Set Cover - Improved and Simple},
journal = {CoRR},
volume = {abs/1804.03197},
year = {2018},
url = {http://arxiv.org/abs/1804.03197},
eprinttype = {arXiv},
eprint = {1804.03197},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-03197.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1804-05013,
author = {Sainyam Galhotra and
Arya Mazumdar and
Soumyabrata Pal and
Barna Saha},
title = {Connectivity in Random Annulus Graphs and the Geometric Block Model},
journal = {CoRR},
volume = {abs/1804.05013},
year = {2018},
url = {http://arxiv.org/abs/1804.05013},
eprinttype = {arXiv},
eprint = {1804.05013},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1804-05013.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/aaai/MazumdarS17,
author = {Arya Mazumdar and
Barna Saha},
editor = {Satinder Singh and
Shaul Markovitch},
title = {A Theoretical Analysis of First Heuristics of Crowdsourced Entity
Resolution},
booktitle = {Proceedings of the Thirty-First {AAAI} Conference on Artificial Intelligence,
February 4-9, 2017, San Francisco, California, {USA}},
pages = {970--976},
publisher = {{AAAI} Press},
year = {2017},
url = {https://doi.org/10.1609/aaai.v31i1.10636},
doi = {10.1609/AAAI.V31I1.10636},
timestamp = {Mon, 04 Sep 2023 14:40:32 +0200},
biburl = {https://dblp.org/rec/conf/aaai/MazumdarS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Saha17,
author = {Barna Saha},
editor = {Chris Umans},
title = {Fast {\&} Space-Efficient Approximations of Language Edit Distance
and {RNA} Folding: An Amnesic Dynamic Programming Approach},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {295--306},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.35},
doi = {10.1109/FOCS.2017.35},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Saha17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/JayaramS17,
author = {Rajesh Jayaram and
Barna Saha},
editor = {Ioannis Chatzigiannakis and
Piotr Indyk and
Fabian Kuhn and
Anca Muscholl},
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, July 10-14, 2017, Warsaw, Poland},
series = {LIPIcs},
volume = {80},
pages = {19:1--19:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2017.19},
doi = {10.4230/LIPICS.ICALP.2017.19},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/JayaramS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/MazumdarS17,
author = {Arya Mazumdar and
Barna Saha},
editor = {Isabelle Guyon and
Ulrike von Luxburg and
Samy Bengio and
Hanna M. Wallach and
Rob Fergus and
S. V. N. Vishwanathan and
Roman Garnett},
title = {Query Complexity of Clustering with Side Information},
booktitle = {Advances in Neural Information Processing Systems 30: Annual Conference
on Neural Information Processing Systems 2017, December 4-9, 2017,
Long Beach, CA, {USA}},
pages = {4682--4693},
year = {2017},
url = {https://proceedings.neurips.cc/paper/2017/hash/03e7ef47cee6fa4ae7567394b99912b7-Abstract.html},
timestamp = {Thu, 21 Jan 2021 13:58:27 +0100},
biburl = {https://dblp.org/rec/conf/nips/MazumdarS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/MazumdarS17a,
author = {Arya Mazumdar and
Barna Saha},
editor = {Isabelle Guyon and
Ulrike von Luxburg and
Samy Bengio and
Hanna M. Wallach and
Rob Fergus and
S. V. N. Vishwanathan and
Roman Garnett},
title = {Clustering with Noisy Queries},
booktitle = {Advances in Neural Information Processing Systems 30: Annual Conference
on Neural Information Processing Systems 2017, December 4-9, 2017,
Long Beach, CA, {USA}},
pages = {5788--5799},
year = {2017},
url = {https://proceedings.neurips.cc/paper/2017/hash/db5cea26ca37aa09e5365f3e7f5dd9eb-Abstract.html},
timestamp = {Thu, 21 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/MazumdarS17a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/MazumdarS17,
author = {Arya Mazumdar and
Barna Saha},
title = {A Theoretical Analysis of First Heuristics of Crowdsourced Entity
Resolution},
journal = {CoRR},
volume = {abs/1702.01208},
year = {2017},
url = {http://arxiv.org/abs/1702.01208},
eprinttype = {arXiv},
eprint = {1702.01208},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/MazumdarS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/MazumdarS17a,
author = {Arya Mazumdar and
Barna Saha},
title = {Clustering with Noisy Queries},
journal = {CoRR},
volume = {abs/1706.07510},
year = {2017},
url = {http://arxiv.org/abs/1706.07510},
eprinttype = {arXiv},
eprint = {1706.07510},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/MazumdarS17a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/MazumdarS17b,
author = {Arya Mazumdar and
Barna Saha},
title = {Query Complexity of Clustering with Side Information},
journal = {CoRR},
volume = {abs/1706.07719},
year = {2017},
url = {http://arxiv.org/abs/1706.07719},
eprinttype = {arXiv},
eprint = {1706.07719},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/MazumdarS17b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BringmannGSW17,
author = {Karl Bringmann and
Fabrizio Grandoni and
Barna Saha and
Virginia Vassilevska Williams},
title = {Truly Sub-cubic Algorithms for Language Edit Distance and {RNA} Folding
via Fast Bounded-Difference Min-Plus Product},
journal = {CoRR},
volume = {abs/1707.05095},
year = {2017},
url = {http://arxiv.org/abs/1707.05095},
eprinttype = {arXiv},
eprint = {1707.05095},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BringmannGSW17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1709-05510,
author = {Sainyam Galhotra and
Arya Mazumdar and
Soumyabrata Pal and
Barna Saha},
title = {The Geometric Block Model},
journal = {CoRR},
volume = {abs/1709.05510},
year = {2017},
url = {http://arxiv.org/abs/1709.05510},
eprinttype = {arXiv},
eprint = {1709.05510},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1709-05510.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/KhullerSS16,
author = {Samir Khuller and
Barna Saha and
Kanthi K. Sarpatwar},
title = {New Approximation Results for Resource Replication Problems},
journal = {Algorithmica},
volume = {74},
number = {3},
pages = {969--991},
year = {2016},
url = {https://doi.org/10.1007/s00453-015-9978-9},
doi = {10.1007/S00453-015-9978-9},
timestamp = {Wed, 17 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/KhullerSS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/FirmaniSS16,
author = {Donatella Firmani and
Barna Saha and
Divesh Srivastava},
title = {Online Entity Resolution Using an Oracle},
journal = {Proc. {VLDB} Endow.},
volume = {9},
number = {5},
pages = {384--395},
year = {2016},
url = {http://www.vldb.org/pvldb/vol9/p384-firmani.pdf},
doi = {10.14778/2876473.2876474},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/FirmaniSS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/HajiaghayiHLLS16,
author = {Mohammad Taghi Hajiaghayi and
Wei Hu and
Jian Li and
Shi Li and
Barna Saha},
title = {A Constant Factor Approximation Algorithm for Fault-Tolerant \emph{k}-Median},
journal = {{ACM} Trans. Algorithms},
volume = {12},
number = {3},
pages = {36:1--36:19},
year = {2016},
url = {https://doi.org/10.1145/2854153},
doi = {10.1145/2854153},
timestamp = {Thu, 29 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/talg/HajiaghayiHLLS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/allerton/MazumdarS16,
author = {Arya Mazumdar and
Barna Saha},
title = {Clustering with an oracle},
booktitle = {54th Annual Allerton Conference on Communication, Control, and Computing,
Allerton 2016, Monticello, IL, USA, September 27-30, 2016},
pages = {738--739},
publisher = {{IEEE}},
year = {2016},
url = {https://doi.org/10.1109/ALLERTON.2016.7852305},
doi = {10.1109/ALLERTON.2016.7852305},
timestamp = {Wed, 16 Oct 2019 14:14:55 +0200},
biburl = {https://dblp.org/rec/conf/allerton/MazumdarS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BringmannGSW16,
author = {Karl Bringmann and
Fabrizio Grandoni and
Barna Saha and
Virginia Vassilevska Williams},
editor = {Irit Dinur},
title = {Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding
via Fast Bounded-Difference Min-Plus Product},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {375--384},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.48},
doi = {10.1109/FOCS.2016.48},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BringmannGSW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/MazumdarS16,
author = {Arya Mazumdar and
Barna Saha},
title = {Clustering Via Crowdsourcing},
journal = {CoRR},
volume = {abs/1604.01839},
year = {2016},
url = {http://arxiv.org/abs/1604.01839},
eprinttype = {arXiv},
eprint = {1604.01839},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/MazumdarS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mor/Krishnaswamy0NS15,
author = {Ravishankar Krishnaswamy and
Amit Kumar and
Viswanath Nagarajan and
Yogish Sabharwal and
Barna Saha},
title = {Facility Location with Matroid or Knapsack Constraints},
journal = {Math. Oper. Res.},
volume = {40},
number = {2},
pages = {446--459},
year = {2015},
url = {https://doi.org/10.1287/moor.2014.0678},
doi = {10.1287/MOOR.2014.0678},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mor/Krishnaswamy0NS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/YingKSS15,
author = {Shanshan Ying and
Flip Korn and
Barna Saha and
Divesh Srivastava},
title = {TreeScope: Finding Structural Anomalies In Semi-Structured Data},
journal = {Proc. {VLDB} Endow.},
volume = {8},
number = {12},
pages = {1904--1907},
year = {2015},
url = {http://www.vldb.org/pvldb/vol8/p1904-Ying.pdf},
doi = {10.14778/2824032.2824097},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/YingKSS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Saha15,
author = {Barna Saha},
editor = {Venkatesan Guruswami},
title = {Language Edit Distance and Maximum Likelihood Parsing of Stochastic
Grammars: Faster Algorithms and Connection to Fundamental Graph Problems},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {118--135},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.17},
doi = {10.1109/FOCS.2015.17},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Saha15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icde/GolabKLSS15,
author = {Lukasz Golab and
Flip Korn and
Feng Li and
Barna Saha and
Divesh Srivastava},
editor = {Johannes Gehrke and
Wolfgang Lehner and
Kyuseok Shim and
Sang Kyun Cha and
Guy M. Lohman},
title = {Size-Constrained Weighted Set Cover},
booktitle = {31st {IEEE} International Conference on Data Engineering, {ICDE} 2015,
Seoul, South Korea, April 13-17, 2015},
pages = {879--890},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/ICDE.2015.7113341},
doi = {10.1109/ICDE.2015.7113341},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icde/GolabKLSS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/tkde/GolabKKSS14,
author = {Lukasz Golab and
Howard J. Karloff and
Flip Korn and
Barna Saha and
Divesh Srivastava},
title = {Discovering Conservation Rules},
journal = {{IEEE} Trans. Knowl. Data Eng.},
volume = {26},
number = {6},
pages = {1332--1348},
year = {2014},
url = {https://doi.org/10.1109/TKDE.2012.171},
doi = {10.1109/TKDE.2012.171},
timestamp = {Sat, 20 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/tkde/GolabKKSS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/Saha14,
author = {Barna Saha},
title = {The Dyck Language Edit Distance Problem in Near-Linear Time},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {611--620},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.71},
doi = {10.1109/FOCS.2014.71},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/Saha14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icde/SahaS14,
author = {Barna Saha and
Divesh Srivastava},
editor = {Isabel F. Cruz and
Elena Ferrari and
Yufei Tao and
Elisa Bertino and
Goce Trajcevski},
title = {Data quality: The other face of Big Data},
booktitle = {{IEEE} 30th International Conference on Data Engineering, Chicago,
{ICDE} 2014, IL, USA, March 31 - April 4, 2014},
pages = {1294--1297},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/ICDE.2014.6816764},
doi = {10.1109/ICDE.2014.6816764},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icde/SahaS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/HajiaghayiHLLS14,
author = {MohammadTaghi Hajiaghayi and
Wei Hu and
Jian Li and
Shi Li and
Barna Saha},
editor = {Chandra Chekuri},
title = {A Constant Factor Approximation Algorithm for Fault-Tolerant \emph{k}-Median},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1--12},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.1},
doi = {10.1137/1.9781611973402.1},
timestamp = {Thu, 29 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/HajiaghayiHLLS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/spaa/HajiaghayiJKS14,
author = {Mohammad Taghi Hajiaghayi and
Theodore Johnson and
Mohammad Reza Khani and
Barna Saha},
editor = {Guy E. Blelloch and
Peter Sanders},
title = {Hierarchical graph partitioning},
booktitle = {26th {ACM} Symposium on Parallelism in Algorithms and Architectures,
{SPAA} '14, Prague, Czech Republic - June 23 - 25, 2014},
pages = {51--60},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2612669.2612699},
doi = {10.1145/2612669.2612699},
timestamp = {Wed, 21 Nov 2018 11:18:43 +0100},
biburl = {https://dblp.org/rec/conf/spaa/HajiaghayiJKS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ssdbm/GolabHKS14,
author = {Lukasz Golab and
Marios Hadjieleftheriou and
Howard J. Karloff and
Barna Saha},
editor = {Christian S. Jensen and
Hua Lu and
Torben Bach Pedersen and
Christian Thomsen and
Kristian Torp},
title = {Distributed data placement to minimize communication costs via graph
partitioning},
booktitle = {Conference on Scientific and Statistical Database Management, {SSDBM}
'14, Aalborg, Denmark, June 30 - July 02, 2014},
pages = {20:1--20:12},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2618243.2618258},
doi = {10.1145/2618243.2618258},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/ssdbm/GolabHKS14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Saha14,
author = {Barna Saha},
title = {Faster Language Edit Distance, Connection to All-pairs Shortest Paths
and Related Problems},
journal = {CoRR},
volume = {abs/1411.7315},
year = {2014},
url = {http://arxiv.org/abs/1411.7315},
eprinttype = {arXiv},
eprint = {1411.7315},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Saha14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/KornSSY13,
author = {Flip Korn and
Barna Saha and
Divesh Srivastava and
Shanshan Ying},
title = {On Repairing Structural Problems In Semi-structured Data},
journal = {Proc. {VLDB} Endow.},
volume = {6},
number = {9},
pages = {601--612},
year = {2013},
url = {http://www.vldb.org/pvldb/vol6/p601-korn.pdf},
doi = {10.14778/2536360.2536361},
timestamp = {Mon, 28 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/KornSSY13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/cloud/LeePS13,
author = {Seungjoon Lee and
Manish Purohit and
Barna Saha},
editor = {Guy M. Lohman},
title = {Firewall placement in cloud data centers},
booktitle = {{ACM} Symposium on Cloud Computing, {SOCC} '13, Santa Clara, CA, USA,
October 1-3, 2013},
pages = {52:1--52:2},
publisher = {{ACM}},
year = {2013},
url = {https://doi.org/10.1145/2523616.2525960},
doi = {10.1145/2523616.2525960},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/cloud/LeePS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/Saha13,
author = {Barna Saha},
editor = {Anil Seth and
Nisheeth K. Vishnoi},
title = {Renting a Cloud},
booktitle = {{IARCS} Annual Conference on Foundations of Software Technology and
Theoretical Computer Science, {FSTTCS} 2013, December 12-14, 2013,
Guwahati, India},
series = {LIPIcs},
volume = {24},
pages = {437--448},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2013.437},
doi = {10.4230/LIPICS.FSTTCS.2013.437},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/Saha13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isit/MazumdarPS13,
author = {Arya Mazumdar and
Yury Polyanskiy and
Barna Saha},
title = {On Chebyshev radius of a set in Hamming space and the closest string
problem},
booktitle = {Proceedings of the 2013 {IEEE} International Symposium on Information
Theory, Istanbul, Turkey, July 7-12, 2013},
pages = {1401--1405},
publisher = {{IEEE}},
year = {2013},
url = {https://doi.org/10.1109/ISIT.2013.6620457},
doi = {10.1109/ISIT.2013.6620457},
timestamp = {Wed, 16 Oct 2019 14:14:48 +0200},
biburl = {https://dblp.org/rec/conf/isit/MazumdarPS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/HajiaghayiHLLS13,
author = {Mohammad Taghi Hajiaghayi and
Wei Hu and
Jian Li and
Shi Li and
Barna Saha},
title = {A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median},
journal = {CoRR},
volume = {abs/1307.2808},
year = {2013},
url = {http://arxiv.org/abs/1307.2808},
eprinttype = {arXiv},
eprint = {1307.2808},
timestamp = {Thu, 29 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/HajiaghayiHLLS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/Saha13,
author = {Barna Saha},
title = {Efficiently Computing Edit Distance to Dyck Language},
journal = {CoRR},
volume = {abs/1311.2557},
year = {2013},
url = {http://arxiv.org/abs/1311.2557},
eprinttype = {arXiv},
eprint = {1311.2557},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/Saha13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/GolabHKS13,
author = {Lukasz Golab and
Marios Hadjieleftheriou and
Howard J. Karloff and
Barna Saha},
title = {Distributed Data Placement via Graph Partitioning},
journal = {CoRR},
volume = {abs/1312.0285},
year = {2013},
url = {http://arxiv.org/abs/1312.0285},
eprinttype = {arXiv},
eprint = {1312.0285},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/GolabHKS13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/DongSS12,
author = {Xin Luna Dong and
Barna Saha and
Divesh Srivastava},
title = {Less is More: Selecting Sources Wisely for Integration},
journal = {Proc. {VLDB} Endow.},
volume = {6},
number = {2},
pages = {37--48},
year = {2012},
url = {http://www.vldb.org/pvldb/vol6/p37-dong.pdf},
doi = {10.14778/2535568.2448938},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/DongSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/KhullerSS12,
author = {Samir Khuller and
Barna Saha and
Kanthi K. Sarpatwar},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {New Approximation Results for Resource Replication Problems},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 15th International Workshop, {APPROX} 2012, and 16th
International Workshop, {RANDOM} 2012, Cambridge, MA, USA, August
15-17, 2012. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7408},
pages = {218--230},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_19},
doi = {10.1007/978-3-642-32512-0\_19},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/KhullerSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/SahaK12,
author = {Barna Saha and
Samir Khuller},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Set Cover Revisited: Hypergraph Cover with Hard Capacities},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {762--773},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_64},
doi = {10.1007/978-3-642-31594-7\_64},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/SahaK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icde/GolabKKSS12,
author = {Lukasz Golab and
Howard J. Karloff and
Flip Korn and
Barna Saha and
Divesh Srivastava},
editor = {Anastasios Kementsietsidis and
Marcos Antonio Vaz Salles},
title = {Discovering Conservation Rules},
booktitle = {{IEEE} 28th International Conference on Data Engineering {(ICDE} 2012),
Washington, DC, {USA} (Arlington, Virginia), 1-5 April, 2012},
pages = {738--749},
publisher = {{IEEE} Computer Society},
year = {2012},
url = {https://doi.org/10.1109/ICDE.2012.105},
doi = {10.1109/ICDE.2012.105},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icde/GolabKKSS12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/basesearch/Saha11,
author = {Barna Saha},
title = {Approximation Algorithms for Resource Allocation},
school = {University of Maryland, College Park, MD, {USA}},
year = {2011},
url = {https://hdl.handle.net/1903/11974},
timestamp = {Wed, 04 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/phd/basesearch/Saha11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/HaeuplerSS11,
author = {Bernhard Haeupler and
Barna Saha and
Aravind Srinivasan},
title = {New Constructive Aspects of the Lov{\'{a}}sz Local Lemma},
journal = {J. {ACM}},
volume = {58},
number = {6},
pages = {28:1--28:28},
year = {2011},
url = {https://doi.org/10.1145/2049697.2049702},
doi = {10.1145/2049697.2049702},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/HaeuplerSS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/vldb/LiSD11,
author = {Jian Li and
Barna Saha and
Amol Deshpande},
title = {A unified approach to ranking in probabilistic databases},
journal = {{VLDB} J.},
volume = {20},
number = {2},
pages = {249--275},
year = {2011},
url = {https://doi.org/10.1007/s00778-011-0220-3},
doi = {10.1007/S00778-011-0220-3},
timestamp = {Sat, 06 Jan 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/vldb/LiSD11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BansalKS11,
author = {Nikhil Bansal and
Ravishankar Krishnaswamy and
Barna Saha},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {On Capacitated Set Cover Problems},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques - 14th International Workshop, {APPROX} 2011, and 15th
International Workshop, {RANDOM} 2011, Princeton, NJ, USA, August
17-19, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6845},
pages = {38--49},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_4},
doi = {10.1007/978-3-642-22935-0\_4},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/approx/BansalKS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/AlaeiHLPS11,
author = {Saeed Alaei and
Mohammad Taghi Hajiaghayi and
Vahid Liaghat and
Dan Pei and
Barna Saha},
editor = {Camil Demetrescu and
Magn{\'{u}}s M. Halld{\'{o}}rsson},
title = {AdCell: Ad Allocation in Cellular Networks},
booktitle = {Algorithms - {ESA} 2011 - 19th Annual European Symposium, Saarbr{\"{u}}cken,
Germany, September 5-9, 2011. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6942},
pages = {311--322},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-23719-5\_27},
doi = {10.1007/978-3-642-23719-5\_27},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/esa/AlaeiHLPS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/semweb/ThorARNSKZ11,
author = {Andreas Thor and
Philip Anderson and
Louiqa Raschid and
Saket Navlakha and
Barna Saha and
Samir Khuller and
Xiao{-}Ning Zhang},
editor = {Lora Aroyo and
Chris Welty and
Harith Alani and
Jamie Taylor and
Abraham Bernstein and
Lalana Kagal and
Natasha Fridman Noy and
Eva Blomqvist},
title = {Link Prediction for Annotation Graphs Using Graph Summarization},
booktitle = {The Semantic Web - {ISWC} 2011 - 10th International Semantic Web Conference,
Bonn, Germany, October 23-27, 2011, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7031},
pages = {714--729},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-25073-6\_45},
doi = {10.1007/978-3-642-25073-6\_45},
timestamp = {Tue, 07 Sep 2021 13:47:52 +0200},
biburl = {https://dblp.org/rec/conf/semweb/ThorARNSKZ11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KrishnaswamyKNSS11,
author = {Ravishankar Krishnaswamy and
Amit Kumar and
Viswanath Nagarajan and
Yogish Sabharwal and
Barna Saha},
editor = {Dana Randall},
title = {The Matroid Median Problem},
booktitle = {Proceedings of the Twenty-Second Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2011, San Francisco, California, USA, January 23-25,
2011},
pages = {1117--1130},
publisher = {{SIAM}},
year = {2011},
url = {https://doi.org/10.1137/1.9781611973082.84},
doi = {10.1137/1.9781611973082.84},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/KrishnaswamyKNSS11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-5396,
author = {Saeed Alaei and
Mohammad Taghi Hajiaghayi and
Vahid Liaghat and
Dan Pei and
Barna Saha},
title = {AdCell: Ad Allocation in Cellular Networks},
journal = {CoRR},
volume = {abs/1112.5396},
year = {2011},
url = {http://arxiv.org/abs/1112.5396},
eprinttype = {arXiv},
eprint = {1112.5396},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-5396.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/HaeuplerSS10,
author = {Bernhard Haeupler and
Barna Saha and
Aravind Srinivasan},
title = {New Constructive Aspects of the Lovasz Local Lemma},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {397--406},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.45},
doi = {10.1109/FOCS.2010.45},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/HaeuplerSS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icde/SahaSC10,
author = {Barna Saha and
Ioana Stanoi and
Kenneth L. Clarkson},
editor = {Feifei Li and
Mirella M. Moro and
Shahram Ghandeharizadeh and
Jayant R. Haritsa and
Gerhard Weikum and
Michael J. Carey and
Fabio Casati and
Edward Y. Chang and
Ioana Manolescu and
Sharad Mehrotra and
Umeshwar Dayal and
Vassilis J. Tsotras},
title = {Schema covering: a step towards enabling reuse in information integration},
booktitle = {Proceedings of the 26th International Conference on Data Engineering,
{ICDE} 2010, March 1-6, 2010, Long Beach, California, {USA}},
pages = {285--296},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/ICDE.2010.5447853},
doi = {10.1109/ICDE.2010.5447853},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icde/SahaSC10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/SahaS10,
author = {Barna Saha and
Aravind Srinivasan},
editor = {Andrew Chi{-}Chih Yao},
title = {A New Approximation Technique for Resource-Allocation Problems},
booktitle = {Innovations in Computer Science - {ICS} 2010, Tsinghua University,
Beijing, China, January 5-7, 2010. Proceedings},
pages = {342--357},
publisher = {Tsinghua University Press},
year = {2010},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2010/content/papers/27.html},
timestamp = {Wed, 04 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/SahaS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/recomb/SahaHKRZ10,
author = {Barna Saha and
Allison Hoch and
Samir Khuller and
Louiqa Raschid and
Xiao{-}Ning Zhang},
editor = {Bonnie Berger},
title = {Dense Subgraphs with Restrictions and Applications to Gene Annotation
Graphs},
booktitle = {Research in Computational Molecular Biology, 14th Annual International
Conference, {RECOMB} 2010, Lisbon, Portugal, April 25-28, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6044},
pages = {456--472},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-12683-3\_30},
doi = {10.1007/978-3-642-12683-3\_30},
timestamp = {Sat, 19 Oct 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/recomb/SahaHKRZ10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/KhullerLS10,
author = {Samir Khuller and
Jian Li and
Barna Saha},
editor = {Moses Charikar},
title = {Energy Efficient Scheduling via Partial Shutdown},
booktitle = {Proceedings of the Twenty-First Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2010, Austin, Texas, USA, January 17-19, 2010},
pages = {1360--1372},
publisher = {{SIAM}},
year = {2010},
url = {https://doi.org/10.1137/1.9781611973075.110},
doi = {10.1137/1.9781611973075.110},
timestamp = {Tue, 02 Feb 2021 17:07:39 +0100},
biburl = {https://dblp.org/rec/conf/soda/KhullerLS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/dagstuhl/KhullerLS10,
author = {Samir Khuller and
Jian Li and
Barna Saha},
editor = {Susanne Albers and
Sanjoy K. Baruah and
Rolf H. M{\"{o}}hring and
Kirk Pruhs},
title = {Energy Efficient Scheduling via Partial Shutdown},
booktitle = {Scheduling, 14.02. - 19.02.2010},
series = {Dagstuhl Seminar Proceedings},
volume = {10071},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2010},
url = {http://drops.dagstuhl.de/opus/volltexte/2010/2543/},
timestamp = {Thu, 10 Jun 2021 13:02:08 +0200},
biburl = {https://dblp.org/rec/conf/dagstuhl/KhullerLS10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1001-1231,
author = {Bernhard Haeupler and
Barna Saha and
Aravind Srinivasan},
title = {New Constructive Aspects of the Lovasz Local Lemma},
journal = {CoRR},
volume = {abs/1001.1231},
year = {2010},
url = {http://arxiv.org/abs/1001.1231},
eprinttype = {arXiv},
eprint = {1001.1231},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1001-1231.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1001-1470,
author = {Barna Saha and
Aravind Srinivasan},
title = {A New Approximation Technique for Resource-Allocation Problems},
journal = {CoRR},
volume = {abs/1001.1470},
year = {2010},
url = {http://arxiv.org/abs/1001.1470},
eprinttype = {arXiv},
eprint = {1001.1470},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1001-1470.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/pvldb/LiSD09,
author = {Jian Li and
Barna Saha and
Amol Deshpande},
title = {A Unified Approach to Ranking in Probabilistic Databases},
journal = {Proc. {VLDB} Endow.},
volume = {2},
number = {1},
pages = {502--513},
year = {2009},
url = {http://www.vldb.org/pvldb/vol2/vldb09-769.pdf},
doi = {10.14778/1687627.1687685},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/pvldb/LiSD09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/KhullerS09,
author = {Samir Khuller and
Barna Saha},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {On Finding Dense Subgraphs},
booktitle = {Automata, Languages and Programming, 36th International Colloquium,
{ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {5555},
pages = {597--608},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_50},
doi = {10.1007/978-3-642-02927-1\_50},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/KhullerS09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sdm/SahaG09,
author = {Barna Saha and
Lise Getoor},
title = {On Maximum Coverage in the Streaming Model {\&} Application to
Multi-topic Blog-Watch},
booktitle = {Proceedings of the {SIAM} International Conference on Data Mining,
{SDM} 2009, April 30 - May 2, 2009, Sparks, Nevada, {USA}},
pages = {697--708},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611972795.60},
doi = {10.1137/1.9781611972795.60},
timestamp = {Wed, 17 May 2017 14:24:53 +0200},
biburl = {https://dblp.org/rec/conf/sdm/SahaG09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0904-1366,
author = {Jian Li and
Barna Saha and
Amol Deshpande},
title = {A Unified Approach to Ranking in Probabilistic Databases},
journal = {CoRR},
volume = {abs/0904.1366},
year = {2009},
url = {http://arxiv.org/abs/0904.1366},
eprinttype = {arXiv},
eprint = {0904.1366},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0904-1366.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0912-1329,
author = {Samir Khuller and
Jian Li and
Barna Saha},
title = {Energy Efficient Scheduling via Partial Shutdown},
journal = {CoRR},
volume = {abs/0912.1329},
year = {2009},
url = {http://arxiv.org/abs/0912.1329},
eprinttype = {arXiv},
eprint = {0912.1329},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0912-1329.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/birte/AlexeGHHHKPSS08,
author = {Bogdan Alexe and
Michael N. Gubanov and
Mauricio A. Hern{\'{a}}ndez and
C. T. Howard Ho and
Jen{-}Wei Huang and
Yannis Katsis and
Lucian Popa and
Barna Saha and
Ioana Stanoi},
editor = {Mal{\'{u}} Castellanos and
Umeshwar Dayal and
Timos Sellis},
title = {Simplifying Information Integration: Object-Based Flow-of-Mappings
Framework for Integration},
booktitle = {Business Intelligence for the Real-Time Enterprise - Second International
Workshop, {BIRTE} 2008, Auckland, New Zealand, August 24, 2008, Revised
Selected Papers},
series = {Lecture Notes in Business Information Processing},
volume = {27},
pages = {108--121},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-642-03422-0\_9},
doi = {10.1007/978-3-642-03422-0\_9},
timestamp = {Fri, 02 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/birte/AlexeGHHHKPSS08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sdm/SahaM07,
author = {Barna Saha and
Pabitra Mitra},
title = {Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree},
booktitle = {Proceedings of the Seventh {SIAM} International Conference on Data
Mining, April 26-28, 2007, Minneapolis, Minnesota, {USA}},
pages = {581--586},
publisher = {{SIAM}},
year = {2007},
url = {https://doi.org/10.1137/1.9781611972771.65},
doi = {10.1137/1.9781611972771.65},
timestamp = {Wed, 17 May 2017 14:24:53 +0200},
biburl = {https://dblp.org/rec/conf/sdm/SahaM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icdm/SahaM06,
author = {Barna Saha and
Pabitra Mitra},
title = {Dynamic Algorithm for Graph Clustering Using Minimum Cut Tree},
booktitle = {Workshops Proceedings of the 6th {IEEE} International Conference on
Data Mining {(ICDM} 2006), 18-22 December 2006, Hong Kong, China},
pages = {667--671},
publisher = {{IEEE} Computer Society},
year = {2006},
url = {https://doi.org/10.1109/ICDMW.2006.65},
doi = {10.1109/ICDMW.2006.65},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icdm/SahaM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/isaac/GangulyS06,
author = {Sumit Ganguly and
Barna Saha},
editor = {Tetsuo Asano},
title = {On Estimating Path Aggregates over Streaming Graphs},
booktitle = {Algorithms and Computation, 17th International Symposium, {ISAAC}
2006, Kolkata, India, December 18-20, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4288},
pages = {163--172},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11940128\_18},
doi = {10.1007/11940128\_18},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/isaac/GangulyS06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-08 00:50 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
