Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Amit Chakrabarti
@article{DBLP:journals/corr/abs-2403-14087,
author = {Amit Chakrabarti and
Andrew McGregor and
Anthony Wirth},
title = {Improved Algorithms for Maximum Coverage in Dynamic and Random Order
Streams},
journal = {CoRR},
volume = {abs/2403.14087},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2403.14087},
doi = {10.48550/ARXIV.2403.14087},
eprinttype = {arXiv},
eprint = {2403.14087},
timestamp = {Tue, 09 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2403-14087.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ni/GazulaRHBZVKMCBNSSKKKGKKBBDPPSHTVBBF23,
author = {Harshvardhan Gazula and
Kelly Rootes{-}Murdy and
Bharath Holla and
Sunitha Basodi and
Zuo Zhang and
Eric Verner and
Ross Kelly and
Pratima Murthy and
Amit Chakrabarti and
Debasish Basu and
Subodh Bhagyalakshmi Nanjayya and
Rajkumar Lenin Singh and
Roshan Lourembam Singh and
Kartik Kalyanram and
Kamakshi Kartik and
Kalyanaraman Kumaran and
Krishnaveni Ghattu and
Rebecca Kuriyan and
Sunita Simon Kurpad and
Gareth J. Barker and
Rose Dawn Bharath and
Sylvane Desrivi{\`{e}}res and
Meera Purushottam and
Dimitri Papadopoulos{-}Orfanos and
Eesha Sharma and
Matthew Hickman and
Mireille Toledano and
Nilakshi Vaidya and
Tobias Banaschewski and
Arun L. W. Bokde and
Herta Flor and
Antoine Grigis and
Hugh Garavan and
Penny A. Gowland and
Andreas Heinz and
R{\"{u}}diger Br{\"{u}}hl and
Jean{-}Luc Martinot and
Marie{-}Laure Paill{\`{e}}re{-}Martinot and
Eric Artiges and
Frauke Nees and
Tom{\'{a}}s Paus and
Luise Poustka and
Juliane H. Fr{\"{o}}hner and
Lauren Robinson and
Michael N. Smolka and
Henrik Walter and
Jeanne Winterer and
Robert Whelan and
Jessica A. Turner and
Anand D. Sarwate and
Sergey M. Plis and
Vivek Benegal and
Gunter Schumann and
Vince D. Calhoun},
title = {Federated Analysis in {COINSTAC} Reveals Functional Network Connectivity
and Spectral Links to Smoking and Alcohol Consumption in Nearly 2,000
Adolescent Brains},
journal = {Neuroinformatics},
volume = {21},
number = {2},
pages = {287--301},
year = {2023},
url = {https://doi.org/10.1007/s12021-022-09604-4},
doi = {10.1007/S12021-022-09604-4},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/ni/GazulaRHBZVKMCBNSSKKKGKKBBDPPSHTVBBF23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/AssadiCGS23,
author = {Sepehr Assadi and
Amit Chakrabarti and
Prantar Ghosh and
Manuel Stoeckl},
editor = {Floris Geerts and
Hung Q. Ngo and
Stavros Sintos},
title = {Coloring in Graph Streams via Deterministic and Adversarially Robust
Algorithms},
booktitle = {Proceedings of the 42nd {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles
of Database Systems, {PODS} 2023, Seattle, WA, USA, June 18-23, 2023},
pages = {141--153},
publisher = {{ACM}},
year = {2023},
url = {https://doi.org/10.1145/3584372.3588681},
doi = {10.1145/3584372.3588681},
timestamp = {Thu, 15 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/pods/AssadiCGS23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-03634,
author = {Amit Chakrabarti and
Manuel Stoeckl},
title = {When a random tape is not enough: lower bounds for a problem in adversarially
robust streaming},
journal = {CoRR},
volume = {abs/2310.03634},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.03634},
doi = {10.48550/ARXIV.2310.03634},
eprinttype = {arXiv},
eprint = {2310.03634},
timestamp = {Thu, 19 Oct 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-03634.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/esa/ChakrabartiH22,
author = {Amit Chakrabarti and
Themistoklis K. Haris},
editor = {Shiri Chechik and
Gonzalo Navarro and
Eva Rotenberg and
Grzegorz Herman},
title = {Counting Simplices in Hypergraph Streams},
booktitle = {30th Annual European Symposium on Algorithms, {ESA} 2022, September
5-9, 2022, Berlin/Potsdam, Germany},
series = {LIPIcs},
volume = {244},
pages = {32:1--32:19},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ESA.2022.32},
doi = {10.4230/LIPICS.ESA.2022.32},
timestamp = {Wed, 28 Feb 2024 00:16:41 +0100},
biburl = {https://dblp.org/rec/conf/esa/ChakrabartiH22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ChakrabartiGS22,
author = {Amit Chakrabarti and
Prantar Ghosh and
Manuel Stoeckl},
editor = {Mark Braverman},
title = {Adversarially Robust Coloring for Graph Streams},
booktitle = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {215},
pages = {37:1--37:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2022.37},
doi = {10.4230/LIPICS.ITCS.2022.37},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/ChakrabartiGS22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@proceedings{DBLP:conf/approx/2022,
editor = {Amit Chakrabarti and
Chaitanya Swamy},
title = {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},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://www.dagstuhl.de/dagpub/978-3-95977-249-5},
isbn = {978-3-95977-249-5},
timestamp = {Sat, 17 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/2022.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-10641,
author = {Sepehr Assadi and
Amit Chakrabarti and
Prantar Ghosh and
Manuel Stoeckl},
title = {Coloring in Graph Streams via Deterministic and Adversarially Robust
Algorithms},
journal = {CoRR},
volume = {abs/2212.10641},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.10641},
doi = {10.48550/ARXIV.2212.10641},
eprinttype = {arXiv},
eprint = {2212.10641},
timestamp = {Wed, 04 Jan 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-10641.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ni/GazulaHZXVKJBBB21,
author = {Harshvardhan Gazula and
Bharath Holla and
Zuo Zhang and
Jiayuan Xu and
Eric Verner and
Ross Kelly and
Sanjeev Jain and
Rose Dawn Bharath and
Gareth J. Barker and
Debasish Basu and
Amit Chakrabarti and
Kartik Kalyanram and
Kalyanaraman Kumaran and
Rajkumar Lenin Singh and
Rebecca Kuriyan and
Pratima Murthy and
Vivek Benega and
Sergey M. Plis and
Anand D. Sarwate and
Jessica A. Turner and
Gunter Schumann and
Vince D. Calhoun},
title = {Decentralized Multisite {VBM} Analysis During Adolescence Shows Structural
Changes Linked to Age, Body Mass Index, and Smoking: a {COINSTAC}
Analysis},
journal = {Neuroinformatics},
volume = {19},
number = {4},
pages = {553--566},
year = {2021},
url = {https://doi.org/10.1007/s12021-020-09502-7},
doi = {10.1007/S12021-020-09502-7},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ni/GazulaHZXVKJBBB21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2105-08215,
author = {Amit Chakrabarti and
Prantar Ghosh and
Andrew McGregor and
Sofya Vorotnikova},
title = {Vertex Ordering Problems in Directed Graph Streams},
journal = {CoRR},
volume = {abs/2105.08215},
year = {2021},
url = {https://arxiv.org/abs/2105.08215},
eprinttype = {arXiv},
eprint = {2105.08215},
timestamp = {Mon, 31 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2105-08215.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2107-05810,
author = {Amit Chakrabarti and
Manuel Stoeckl},
title = {The Element Extraction Problem and the Cost of Determinism and Limited
Adaptivity in Linear Queries},
journal = {CoRR},
volume = {abs/2107.05810},
year = {2021},
url = {https://arxiv.org/abs/2107.05810},
eprinttype = {arXiv},
eprint = {2107.05810},
timestamp = {Wed, 21 Jul 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2107-05810.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2109-11130,
author = {Amit Chakrabarti and
Prantar Ghosh and
Manuel Stoeckl},
title = {Adversarially Robust Coloring for Graph Streams},
journal = {CoRR},
volume = {abs/2109.11130},
year = {2021},
url = {https://arxiv.org/abs/2109.11130},
eprinttype = {arXiv},
eprint = {2109.11130},
timestamp = {Mon, 27 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2109-11130.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2112-11016,
author = {Amit Chakrabarti and
Themistoklis K. Haris},
title = {Counting Simplices in Hypergraph Streams},
journal = {CoRR},
volume = {abs/2112.11016},
year = {2021},
url = {https://arxiv.org/abs/2112.11016},
eprinttype = {arXiv},
eprint = {2112.11016},
timestamp = {Tue, 04 Jan 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2112-11016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChakrabartiGT20,
author = {Amit Chakrabarti and
Prantar Ghosh and
Justin Thaler},
editor = {Jaroslaw Byrka and
Raghu Meka},
title = {Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear
Sketches},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2020, August 17-19, 2020, Virtual
Conference},
series = {LIPIcs},
volume = {176},
pages = {22:1--22:23},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.22},
doi = {10.4230/LIPICS.APPROX/RANDOM.2020.22},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/approx/ChakrabartiGT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BeraCG20,
author = {Suman K. Bera and
Amit Chakrabarti and
Prantar Ghosh},
editor = {Artur Czumaj and
Anuj Dawar and
Emanuela Merelli},
title = {Graph Coloring via Degeneracy in Streaming and Other Space-Conscious
Models},
booktitle = {47th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2020, July 8-11, 2020, Saarbr{\"{u}}cken, Germany (Virtual
Conference)},
series = {LIPIcs},
volume = {168},
pages = {11:1--11:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2020.11},
doi = {10.4230/LIPICS.ICALP.2020.11},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/BeraCG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabartiG0V20,
author = {Amit Chakrabarti and
Prantar Ghosh and
Andrew McGregor and
Sofya Vorotnikova},
editor = {Shuchi Chawla},
title = {Vertex Ordering Problems in Directed Graph Streams},
booktitle = {Proceedings of the 2020 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2020, Salt Lake City, UT, USA, January 5-8, 2020},
pages = {1786--1802},
publisher = {{SIAM}},
year = {2020},
url = {https://doi.org/10.1137/1.9781611975994.109},
doi = {10.1137/1.9781611975994.109},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabartiG0V20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2007-03039,
author = {Amit Chakrabarti and
Prantar Ghosh and
Justin Thaler},
title = {Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear
Sketches},
journal = {CoRR},
volume = {abs/2007.03039},
year = {2020},
url = {https://arxiv.org/abs/2007.03039},
eprinttype = {arXiv},
eprint = {2007.03039},
timestamp = {Sat, 18 Jul 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2007-03039.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiGT20,
author = {Amit Chakrabarti and
Prantar Ghosh and
Justin Thaler},
title = {Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear
Sketches},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR20-100}},
year = {2020},
url = {https://eccc.weizmann.ac.il/report/2020/100},
eprinttype = {ECCC},
eprint = {TR20-100},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiGT20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiC0TV19,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler and
Suresh Venkatasubramanian},
title = {Verifiable Stream Computation and Arthur-Merlin Communication},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {4},
pages = {1265--1299},
year = {2019},
url = {https://doi.org/10.1137/17M112289X},
doi = {10.1137/17M112289X},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiC0TV19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChakrabartiG19,
author = {Amit Chakrabarti and
Prantar Ghosh},
editor = {Dimitris Achlioptas and
L{\'{a}}szl{\'{o}} A. V{\'{e}}gh},
title = {Streaming Verification of Graph Computations via Graph Structure},
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 = {70:1--70:20},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2019},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.70},
doi = {10.4230/LIPICS.APPROX-RANDOM.2019.70},
timestamp = {Mon, 05 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/approx/ChakrabartiG19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1905-00566,
author = {Suman K. Bera and
Amit Chakrabarti and
Prantar Ghosh},
title = {Graph Coloring via Degeneracy in Streaming and Other Space-Conscious
Models},
journal = {CoRR},
volume = {abs/1905.00566},
year = {2019},
url = {http://arxiv.org/abs/1905.00566},
eprinttype = {arXiv},
eprint = {1905.00566},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1905-00566.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiG19,
author = {Amit Chakrabarti and
Prantar Ghosh},
title = {Streaming Verification of Graph Computations via Graph Structure},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR19-101}},
year = {2019},
url = {https://eccc.weizmann.ac.il/report/2019/101},
eprinttype = {ECCC},
eprint = {TR19-101},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiG19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BeraC17,
author = {Suman K. Bera and
Amit Chakrabarti},
editor = {Heribert Vollmer and
Brigitte Vall{\'{e}}e},
title = {Towards Tighter Space Bounds for Counting Triangles and Other Substructures
in Graph Streams},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science, {STACS}
2017, March 8-11, 2017, Hannover, Germany},
series = {LIPIcs},
volume = {66},
pages = {11:1--11:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.STACS.2017.11},
doi = {10.4230/LIPICS.STACS.2017.11},
timestamp = {Thu, 07 Jul 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BeraC17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1712-01330,
author = {Amit Chakrabarti and
Yining Chen},
title = {Time-Space Tradeoffs for the Memory Game},
journal = {CoRR},
volume = {abs/1712.01330},
year = {2017},
url = {http://arxiv.org/abs/1712.01330},
eprinttype = {arXiv},
eprint = {1712.01330},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1712-01330.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/BrodyCKWY16,
author = {Joshua Brody and
Amit Chakrabarti and
Ranganath Kondapally and
David P. Woodruff and
Grigory Yaroslavtsev},
title = {Certifying Equality With Limited Interaction},
journal = {Algorithmica},
volume = {76},
number = {3},
pages = {796--845},
year = {2016},
url = {https://doi.org/10.1007/s00453-016-0163-6},
doi = {10.1007/S00453-016-0163-6},
timestamp = {Mon, 05 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/BrodyCKWY16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toc/ChakrabartiC016,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
title = {Robust Lower Bounds for Communication and Stream Computation},
journal = {Theory Comput.},
volume = {12},
number = {1},
pages = {1--35},
year = {2016},
url = {https://doi.org/10.4086/toc.2016.v012a010},
doi = {10.4086/TOC.2016.V012A010},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toc/ChakrabartiC016.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiK16,
author = {Amit Chakrabarti and
Sagar Kale},
editor = {Irit Dinur},
title = {Strong Fooling Sets for Multi-player Communication with Applications
to Deterministic Estimation of Stream Statistics},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {41--50},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.14},
doi = {10.1109/FOCS.2016.14},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabartiW16,
author = {Amit Chakrabarti and
Anthony Wirth},
editor = {Robert Krauthgamer},
title = {Incidence Geometries and the Pass Complexity of Semi-Streaming Set
Cover},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {1365--1373},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch94},
doi = {10.1137/1.9781611974331.CH94},
timestamp = {Tue, 02 Feb 2021 17:07:56 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabartiW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:reference/algo/Chakrabarti16,
author = {Amit Chakrabarti},
title = {Communication Complexity},
booktitle = {Encyclopedia of Algorithms},
pages = {349--357},
year = {2016},
url = {https://doi.org/10.1007/978-1-4939-2864-4\_799},
doi = {10.1007/978-1-4939-2864-4\_799},
timestamp = {Wed, 12 Jul 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/reference/algo/Chakrabarti16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiK16,
author = {Amit Chakrabarti and
Sagar Kale},
title = {Strong Fooling Sets for Multi-Player Communication with Applications
to Deterministic Estimation of Stream Statistics},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-111}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/111},
eprinttype = {ECCC},
eprint = {TR16-111},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiK16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ijrr/WangBC15,
author = {Weifu Wang and
Devin J. Balkcom and
Amit Chakrabarti},
title = {A fast online spanner for roadmap construction},
journal = {Int. J. Robotics Res.},
volume = {34},
number = {11},
pages = {1418--1432},
year = {2015},
url = {https://doi.org/10.1177/0278364915576491},
doi = {10.1177/0278364915576491},
timestamp = {Wed, 14 Apr 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ijrr/WangBC15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/mp/ChakrabartiK15,
author = {Amit Chakrabarti and
Sagar Kale},
title = {Submodular maximization meets streaming: matchings, matroids, and
more},
journal = {Math. Program.},
volume = {154},
number = {1-2},
pages = {225--247},
year = {2015},
url = {https://doi.org/10.1007/s10107-015-0900-7},
doi = {10.1007/S10107-015-0900-7},
timestamp = {Sun, 02 Oct 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/mp/ChakrabartiK15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BeraC15,
author = {Suman K. Bera and
Amit Chakrabarti},
editor = {David Zuckerman},
title = {A Depth-Five Lower Bound for Iterated Matrix Multiplication},
booktitle = {30th Conference on Computational Complexity, {CCC} 2015, June 17-19,
2015, Portland, Oregon, {USA}},
series = {LIPIcs},
volume = {33},
pages = {183--197},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.CCC.2015.183},
doi = {10.4230/LIPICS.CCC.2015.183},
timestamp = {Thu, 02 Feb 2023 13:27:06 +0100},
biburl = {https://dblp.org/rec/conf/coco/BeraC15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChakrabartiCMTV15,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler and
Suresh Venkatasubramanian},
editor = {David Zuckerman},
title = {Verifiable Stream Computation and Arthur-Merlin Communication},
booktitle = {30th Conference on Computational Complexity, {CCC} 2015, June 17-19,
2015, Portland, Oregon, {USA}},
series = {LIPIcs},
volume = {33},
pages = {217--243},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.CCC.2015.217},
doi = {10.4230/LIPICS.CCC.2015.217},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/coco/ChakrabartiCMTV15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/fsttcs/BishnuCNS15,
author = {Arijit Bishnu and
Amit Chakrabarti and
Subhas C. Nandy and
Sandeep Sen},
editor = {Prahladh Harsha and
G. Ramalingam},
title = {On Density, Threshold and Emptiness Queries for Intervals in the Streaming
Model},
booktitle = {35th {IARCS} Annual Conference on Foundation of Software Technology
and Theoretical Computer Science, {FSTTCS} 2015, December 16-18, 2015,
Bangalore, India},
series = {LIPIcs},
volume = {45},
pages = {336--349},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2015},
url = {https://doi.org/10.4230/LIPIcs.FSTTCS.2015.336},
doi = {10.4230/LIPICS.FSTTCS.2015.336},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/fsttcs/BishnuCNS15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChakrabartiW15,
author = {Amit Chakrabarti and
Anthony Wirth},
title = {Incidence Geometries and the Pass Complexity of Semi-Streaming Set
Cover},
journal = {CoRR},
volume = {abs/1507.04645},
year = {2015},
url = {http://arxiv.org/abs/1507.04645},
eprinttype = {arXiv},
eprint = {1507.04645},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChakrabartiW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiW15,
author = {Amit Chakrabarti and
Anthony Wirth},
title = {Incidence Geometries and the Pass Complexity of Semi-Streaming Set
Cover},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR15-113}},
year = {2015},
url = {https://eccc.weizmann.ac.il/report/2015/113},
eprinttype = {ECCC},
eprint = {TR15-113},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/ChakrabartiCMT14,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler},
title = {Annotations in Data Streams},
journal = {{ACM} Trans. Algorithms},
volume = {11},
number = {1},
pages = {7:1--7:30},
year = {2014},
url = {https://doi.org/10.1145/2636924},
doi = {10.1145/2636924},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/ChakrabartiCMT14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BrodyCKWY14,
author = {Joshua Brody and
Amit Chakrabarti and
Ranganath Kondapally and
David P. Woodruff and
Grigory Yaroslavtsev},
editor = {Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Nikhil R. Devanur and
Cristopher Moore},
title = {Certifying Equality With Limited Interaction},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2014, September 4-6, 2014, Barcelona,
Spain},
series = {LIPIcs},
volume = {28},
pages = {545--581},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2014},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.545},
doi = {10.4230/LIPICS.APPROX-RANDOM.2014.545},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/BrodyCKWY14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/ChakrabartiK14,
author = {Amit Chakrabarti and
Sagar Kale},
editor = {Jon Lee and
Jens Vygen},
title = {Submodular Maximization Meets Streaming: Matchings, Matroids, and
More},
booktitle = {Integer Programming and Combinatorial Optimization - 17th International
Conference, {IPCO} 2014, Bonn, Germany, June 23-25, 2014. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {8494},
pages = {210--221},
publisher = {Springer},
year = {2014},
url = {https://doi.org/10.1007/978-3-319-07557-0\_18},
doi = {10.1007/978-3-319-07557-0\_18},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/ChakrabartiK14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/podc/BrodyCKWY14,
author = {Joshua Brody and
Amit Chakrabarti and
Ranganath Kondapally and
David P. Woodruff and
Grigory Yaroslavtsev},
editor = {Magn{\'{u}}s M. Halld{\'{o}}rsson and
Shlomi Dolev},
title = {Beyond set disjointness: the communication complexity of finding the
intersection},
booktitle = {{ACM} Symposium on Principles of Distributed Computing, {PODC} '14,
Paris, France, July 15-18, 2014},
pages = {106--113},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2611462.2611501},
doi = {10.1145/2611462.2611501},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/podc/BrodyCKWY14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabartiCGT14,
author = {Amit Chakrabarti and
Graham Cormode and
Navin Goyal and
Justin Thaler},
editor = {Chandra Chekuri},
title = {Annotations for Sparse Data Streams},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {687--706},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.52},
doi = {10.1137/1.9781611973402.52},
timestamp = {Tue, 02 Feb 2021 17:07:40 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabartiCGT14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCMTV14,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler and
Suresh Venkatasubramanian},
title = {Verifiable Stream Computation and Arthur-Merlin Communication},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR14-086}},
year = {2014},
url = {https://eccc.weizmann.ac.il/report/2014/086},
eprinttype = {ECCC},
eprint = {TR14-086},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCMTV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiCKM13,
author = {Amit Chakrabarti and
Graham Cormode and
Ranganath Kondapally and
Andrew McGregor},
title = {Information Cost Tradeoffs for Augmented Index and Streaming Language
Recognition},
journal = {{SIAM} J. Comput.},
volume = {42},
number = {1},
pages = {61--83},
year = {2013},
url = {https://doi.org/10.1137/100816481},
doi = {10.1137/100816481},
timestamp = {Fri, 02 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiCKM13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/iros/WangBC13,
author = {Weifu Wang and
Devin J. Balkcom and
Amit Chakrabarti},
title = {A fast streaming spanner algorithm for incrementally constructing
sparse roadmaps},
booktitle = {2013 {IEEE/RSJ} International Conference on Intelligent Robots and
Systems, {IROS} 2013, Tokyo, Japan, November 3-7, 2013},
pages = {1257--1263},
publisher = {{IEEE}},
year = {2013},
url = {https://doi.org/10.1109/IROS.2013.6696511},
doi = {10.1109/IROS.2013.6696511},
timestamp = {Tue, 05 Sep 2023 15:06:24 +0200},
biburl = {https://dblp.org/rec/conf/iros/WangBC13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1304-3816,
author = {Amit Chakrabarti and
Graham Cormode and
Navin Goyal and
Justin Thaler},
title = {Annotations for Sparse Data Streams},
journal = {CoRR},
volume = {abs/1304.3816},
year = {2013},
url = {http://arxiv.org/abs/1304.3816},
eprinttype = {arXiv},
eprint = {1304.3816},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1304-3816.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChakrabartiK13,
author = {Amit Chakrabarti and
Sagar Kale},
title = {Submodular Maximization Meets Streaming: Matchings, Matroids, and
More},
journal = {CoRR},
volume = {abs/1309.2038},
year = {2013},
url = {http://arxiv.org/abs/1309.2038},
eprinttype = {arXiv},
eprint = {1309.2038},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChakrabartiK13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCMTV13,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler and
Suresh Venkatasubramanian},
title = {On Interactivity in Arthur-Merlin Communication and Stream Computation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-180}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/180},
eprinttype = {ECCC},
eprint = {TR13-180},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCMTV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Chakrabarti12,
author = {Amit Chakrabarti},
title = {A note on randomized streaming space bounds for the longest increasing
subsequence problem},
journal = {Inf. Process. Lett.},
volume = {112},
number = {7},
pages = {261--263},
year = {2012},
url = {https://doi.org/10.1016/j.ipl.2011.12.008},
doi = {10.1016/J.IPL.2011.12.008},
timestamp = {Tue, 06 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Chakrabarti12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiR12,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance},
journal = {{SIAM} J. Comput.},
volume = {41},
number = {5},
pages = {1299--1317},
year = {2012},
url = {https://doi.org/10.1137/120861072},
doi = {10.1137/120861072},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChakrabartiKW12,
author = {Amit Chakrabarti and
Ranganath Kondapally and
Zhenghui Wang},
editor = {Anupam Gupta and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Rocco A. Servedio},
title = {Information Complexity versus Corruption and Applications to Orthogonality
and Gap-Hamming},
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 = {483--494},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-32512-0\_41},
doi = {10.1007/978-3-642-32512-0\_41},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChakrabartiKW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChakrabartiFW12,
author = {Amit Chakrabarti and
Lisa Fleischer and
Christophe Weibel},
editor = {Howard J. Karloff and
Toniann Pitassi},
title = {When the cut condition is enough: a complete characterization for
multiflow problems in series-parallel networks},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference,
{STOC} 2012, New York, NY, USA, May 19 - 22, 2012},
pages = {19--26},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2213977.2213980},
doi = {10.1145/2213977.2213980},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChakrabartiFW12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1203-4041,
author = {Amit Chakrabarti and
Lisa Fleischer and
Christophe Weibel},
title = {When the Cut Condition is Enough: {A} Complete Characterization for
Multiflow Problems in Series-Parallel Networks},
journal = {CoRR},
volume = {abs/1203.4041},
year = {2012},
url = {http://arxiv.org/abs/1203.4041},
eprinttype = {arXiv},
eprint = {1203.4041},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1203-4041.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1205-0968,
author = {Amit Chakrabarti and
Ranganath Kondapally and
Zhenghui Wang},
title = {Information Complexity versus Corruption and Applications to Orthogonality
and Gap-Hamming},
journal = {CoRR},
volume = {abs/1205.0968},
year = {2012},
url = {http://arxiv.org/abs/1205.0968},
eprinttype = {arXiv},
eprint = {1205.0968},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1205-0968.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BrodyCK12,
author = {Joshua Brody and
Amit Chakrabarti and
Ranganath Kondapally},
title = {Certifying Equality With Limited Interaction},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-153}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/153},
eprinttype = {ECCC},
eprint = {TR12-153},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BrodyCK12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCMT12,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor and
Justin Thaler},
title = {Annotations in Data Streams},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR12-022}},
year = {2012},
url = {https://eccc.weizmann.ac.il/report/2012/022},
eprinttype = {ECCC},
eprint = {TR12-022},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCMT12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/acta/ChakrabartiGWW11,
author = {Amit Chakrabarti and
Venkatesan Guruswami and
Andrew Wirth and
Anthony Wirth},
title = {The query complexity of estimating weighted averages},
journal = {Acta Informatica},
volume = {48},
number = {7-8},
pages = {417--426},
year = {2011},
url = {https://doi.org/10.1007/s00236-011-0145-8},
doi = {10.1007/S00236-011-0145-8},
timestamp = {Sun, 21 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/acta/ChakrabartiGWW11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jgt/ChakrabartiK11,
author = {Amit Chakrabarti and
Subhash Khot},
title = {Combinatorial theorems about embedding trees on the real line},
journal = {J. Graph Theory},
volume = {67},
number = {2},
pages = {153--168},
year = {2011},
url = {https://doi.org/10.1002/jgt.20608},
doi = {10.1002/JGT.20608},
timestamp = {Fri, 02 Oct 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jgt/ChakrabartiK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/CalinescuCKR11,
author = {Gruia C{\u{a}}linescu and
Amit Chakrabarti and
Howard J. Karloff and
Yuval Rabani},
title = {An improved approximation algorithm for resource allocation},
journal = {{ACM} Trans. Algorithms},
volume = {7},
number = {4},
pages = {48:1--48:7},
year = {2011},
url = {https://doi.org/10.1145/2000807.2000816},
doi = {10.1145/2000807.2000816},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/CalinescuCKR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChakrabartiK11,
author = {Amit Chakrabarti and
Ranganath Kondapally},
editor = {Leslie Ann Goldberg and
Klaus Jansen and
R. Ravi and
Jos{\'{e}} D. P. Rolim},
title = {Everywhere-Tight Information Cost Tradeoffs for Augmented Index},
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 = {448--459},
publisher = {Springer},
year = {2011},
url = {https://doi.org/10.1007/978-3-642-22935-0\_38},
doi = {10.1007/978-3-642-22935-0\_38},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChakrabartiK11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChakrabartiR11,
author = {Amit Chakrabarti and
Oded Regev},
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {An optimal lower bound on the communication complexity of gap-hamming-distance},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages = {51--60},
publisher = {{ACM}},
year = {2011},
url = {https://doi.org/10.1145/1993636.1993644},
doi = {10.1145/1993636.1993644},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChakrabartiR11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCM11,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
title = {Robust Lower Bounds for Communication and Stream Computation},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-062}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/062},
eprinttype = {ECCC},
eprint = {TR11-062},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCM11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiR10,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest
Neighbor Searching},
journal = {{SIAM} J. Comput.},
volume = {39},
number = {5},
pages = {1919--1940},
year = {2010},
url = {https://doi.org/10.1137/080729955},
doi = {10.1137/080729955},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/ChakrabartiCM10,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
title = {A near-optimal algorithm for estimating the entropy of a stream},
journal = {{ACM} Trans. Algorithms},
volume = {6},
number = {3},
pages = {51:1--51:21},
year = {2010},
url = {https://doi.org/10.1145/1798596.1798604},
doi = {10.1145/1798596.1798604},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/ChakrabartiCM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BrodyCRVW10,
author = {Joshua Brody and
Amit Chakrabarti and
Oded Regev and
Thomas Vidick and
Ronald de Wolf},
editor = {Maria J. Serna and
Ronen Shaltiel and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim},
title = {Better Gap-Hamming Lower Bounds via Better Round Elimination},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, 13th International Workshop, {APPROX} 2010, and 14th
International Workshop, {RANDOM} 2010, Barcelona, Spain, September
1-3, 2010. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {6302},
pages = {476--489},
publisher = {Springer},
year = {2010},
url = {https://doi.org/10.1007/978-3-642-15369-3\_36},
doi = {10.1007/978-3-642-15369-3\_36},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/BrodyCRVW10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiCKM10,
author = {Amit Chakrabarti and
Graham Cormode and
Ranganath Kondapally and
Andrew McGregor},
title = {Information Cost Tradeoffs for Augmented Index and Streaming Language
Recognition},
booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2010, October 23-26, 2010, Las Vegas, Nevada, {USA}},
pages = {387--396},
publisher = {{IEEE} Computer Society},
year = {2010},
url = {https://doi.org/10.1109/FOCS.2010.44},
doi = {10.1109/FOCS.2010.44},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiCKM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1004-3304,
author = {Amit Chakrabarti and
Graham Cormode and
Ranganath Kondapally and
Andrew McGregor},
title = {Information Cost Tradeoffs for Augmented Index and Streaming Language
Recognition},
journal = {CoRR},
volume = {abs/1004.3304},
year = {2010},
url = {http://arxiv.org/abs/1004.3304},
eprinttype = {arXiv},
eprint = {1004.3304},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1004-3304.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1009-3460,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance},
journal = {CoRR},
volume = {abs/1009.3460},
year = {2010},
url = {http://arxiv.org/abs/1009.3460},
eprinttype = {arXiv},
eprint = {1009.3460},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1009-3460.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Chakrabarti10,
author = {Amit Chakrabarti},
title = {A Note on Randomized Streaming Space Bounds for the Longest Increasing
Subsequence Problem},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-100}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/100},
eprinttype = {ECCC},
eprint = {TR10-100},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Chakrabarti10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiCKM10,
author = {Amit Chakrabarti and
Graham Cormode and
Ranganath Kondapally and
Andrew McGregor},
title = {Information Cost Tradeoffs for Augmented Index and Streaming Language
Recognition},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-076}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/076},
eprinttype = {ECCC},
eprint = {TR10-076},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiCKM10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ChakrabartiR10,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-140}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/140},
eprinttype = {ECCC},
eprint = {TR10-140},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ChakrabartiR10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/cc/BeameC09,
author = {Paul Beame and
Amit Chakrabarti},
title = {Special Issue "Conference on Computational Complexity 2008"
Guest Editors' Foreword},
journal = {Comput. Complex.},
volume = {18},
number = {2},
pages = {169--170},
year = {2009},
url = {https://doi.org/10.1007/s00037-009-0271-7},
doi = {10.1007/S00037-009-0271-7},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/cc/BeameC09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BrodyC09,
author = {Joshua Brody and
Amit Chakrabarti},
title = {A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences},
booktitle = {Proceedings of the 24th Annual {IEEE} Conference on Computational
Complexity, {CCC} 2009, Paris, France, 15-18 July 2009},
pages = {358--368},
publisher = {{IEEE} Computer Society},
year = {2009},
url = {https://doi.org/10.1109/CCC.2009.31},
doi = {10.1109/CCC.2009.31},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BrodyC09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ArackaparambilBC09,
author = {Chrisil Arackaparambil and
Joshua Brody and
Amit Chakrabarti},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {Functional Monitoring without Monotonicity},
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 = {95--106},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_10},
doi = {10.1007/978-3-642-02927-1\_10},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ArackaparambilBC09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ChakrabartiCM09,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
editor = {Susanne Albers and
Alberto Marchetti{-}Spaccamela and
Yossi Matias and
Sotiris E. Nikoletseas and
Wolfgang Thomas},
title = {Annotations in Data Streams},
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 = {222--234},
publisher = {Springer},
year = {2009},
url = {https://doi.org/10.1007/978-3-642-02927-1\_20},
doi = {10.1007/978-3-642-02927-1\_20},
timestamp = {Fri, 02 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icalp/ChakrabartiCM09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0902-2399,
author = {Joshua Brody and
Amit Chakrabarti},
title = {A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences},
journal = {CoRR},
volume = {abs/0902.2399},
year = {2009},
url = {http://arxiv.org/abs/0902.2399},
eprinttype = {arXiv},
eprint = {0902.2399},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0902-2399.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0912-5276,
author = {Joshua Brody and
Amit Chakrabarti and
Oded Regev and
Thomas Vidick and
Ronald de Wolf},
title = {Better Gap-Hamming Lower Bounds via Better Round Elimination},
journal = {CoRR},
volume = {abs/0912.5276},
year = {2009},
url = {http://arxiv.org/abs/0912.5276},
eprinttype = {arXiv},
eprint = {0912.5276},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0912-5276.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BrodyC09,
author = {Joshua Brody and
Amit Chakrabarti},
title = {A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR09-015}},
year = {2009},
url = {https://eccc.weizmann.ac.il/report/2009/015},
eprinttype = {ECCC},
eprint = {TR09-015},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BrodyC09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiJLV08,
author = {Amit Chakrabarti and
Alexander Jaffe and
James R. Lee and
Justin Vincent},
title = {Embeddings of Topological Graphs: Lossy Invariants, Linearization,
and 2-Sums},
booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS}
2008, October 25-28, 2008, Philadelphia, PA, {USA}},
pages = {761--770},
publisher = {{IEEE} Computer Society},
year = {2008},
url = {https://doi.org/10.1109/FOCS.2008.79},
doi = {10.1109/FOCS.2008.79},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiJLV08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabartiJP08,
author = {Amit Chakrabarti and
T. S. Jayram and
Mihai P{u{a}}tra{c{s}}cu},
editor = {Shang{-}Hua Teng},
title = {Tight lower bounds for selection in randomly ordered streams},
booktitle = {Proceedings of the Nineteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2008, San Francisco, California, USA, January 20-22,
2008},
pages = {720--729},
publisher = {{SIAM}},
year = {2008},
url = {http://dl.acm.org/citation.cfm?id=1347082.1347161},
timestamp = {Fri, 07 Dec 2012 17:02:08 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabartiJP08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/BrodyC08,
author = {Joshua Brody and
Amit Chakrabarti},
editor = {Susanne Albers and
Pascal Weil},
title = {Sublinear Communication Protocols for Multi-Party Pointer Jumping
and a Related Lower Bound},
booktitle = {{STACS} 2008, 25th Annual Symposium on Theoretical Aspects of Computer
Science, Bordeaux, France, February 21-23, 2008, Proceedings},
series = {LIPIcs},
volume = {1},
pages = {145--156},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, Germany},
year = {2008},
url = {https://doi.org/10.4230/LIPIcs.STACS.2008.1341},
doi = {10.4230/LIPICS.STACS.2008.1341},
timestamp = {Tue, 22 Jun 2021 15:44:08 +0200},
biburl = {https://dblp.org/rec/conf/stacs/BrodyC08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChakrabartiCM08,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
editor = {Cynthia Dwork},
title = {Robust lower bounds for communication and stream computation},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {641--650},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374470},
doi = {10.1145/1374376.1374470},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChakrabartiCM08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0802-2843,
author = {Joshua Brody and
Amit Chakrabarti},
title = {Sublinear Communication Protocols for Multi-Party Pointer Jumping
and a Related Lower Bound},
journal = {CoRR},
volume = {abs/0802.2843},
year = {2008},
url = {http://arxiv.org/abs/0802.2843},
eprinttype = {arXiv},
eprint = {0802.2843},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0802-2843.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/algorithmica/ChakrabartiCGK07,
author = {Amit Chakrabarti and
Chandra Chekuri and
Anupam Gupta and
Amit Kumar},
title = {Approximation Algorithms for the Unsplittable Flow Problem},
journal = {Algorithmica},
volume = {47},
number = {1},
pages = {53--78},
year = {2007},
url = {https://doi.org/10.1007/s00453-006-1210-5},
doi = {10.1007/S00453-006-1210-5},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/algorithmica/ChakrabartiCGK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/rsa/ChakrabartiK07,
author = {Amit Chakrabarti and
Subhash Khot},
title = {Improved lower bounds on the randomized complexity of graph properties},
journal = {Random Struct. Algorithms},
volume = {30},
number = {3},
pages = {427--440},
year = {2007},
url = {https://doi.org/10.1002/rsa.20164},
doi = {10.1002/RSA.20164},
timestamp = {Thu, 08 Jun 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/rsa/ChakrabartiK07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/Chakrabarti07,
author = {Amit Chakrabarti},
title = {Lower Bounds for Multi-Player Pointer Jumping},
booktitle = {22nd Annual {IEEE} Conference on Computational Complexity {(CCC} 2007),
13-16 June 2007, San Diego, California, {USA}},
pages = {33--45},
publisher = {{IEEE} Computer Society},
year = {2007},
url = {https://doi.org/10.1109/CCC.2007.14},
doi = {10.1109/CCC.2007.14},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/Chakrabarti07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mfcs/ChakrabartiS07,
author = {Amit Chakrabarti and
Anna Shubina},
editor = {Ludek Kucera and
Anton{\'{\i}}n Kucera},
title = {Nearly Private Information Retrieval},
booktitle = {Mathematical Foundations of Computer Science 2007, 32nd International
Symposium, {MFCS} 2007, Cesk{\'{y}} Krumlov, Czech Republic,
August 26-31, 2007, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {4708},
pages = {383--393},
publisher = {Springer},
year = {2007},
url = {https://doi.org/10.1007/978-3-540-74456-6\_35},
doi = {10.1007/978-3-540-74456-6\_35},
timestamp = {Fri, 30 Aug 2019 10:02:28 +0200},
biburl = {https://dblp.org/rec/conf/mfcs/ChakrabartiS07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChakrabartiCM07,
author = {Amit Chakrabarti and
Graham Cormode and
Andrew McGregor},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {A near-optimal algorithm for computing the entropy of a stream},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {328--335},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283418},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChakrabartiCM07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Chakrabarti07,
author = {Amit Chakrabarti},
title = {Lower Bounds for Multi-Player Pointer Jumping},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-014}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-014/index.html},
eprinttype = {ECCC},
eprint = {TR07-014},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Chakrabarti07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/im/ChakrabartiBM06,
author = {Amit Chakrabarti and
Khanh Do Ba and
S. Muthukrishnan},
title = {Estimating Entropy and Entropy Norm on Data Streams},
journal = {Internet Math.},
volume = {3},
number = {1},
pages = {63--78},
year = {2006},
url = {https://doi.org/10.1080/15427951.2006.10129117},
doi = {10.1080/15427951.2006.10129117},
timestamp = {Fri, 07 May 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/im/ChakrabartiBM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/kdd/ZhangCFM06,
author = {Sheng Zhang and
Amit Chakrabarti and
James Ford and
Fillia Makedon},
editor = {Tina Eliassi{-}Rad and
Lyle H. Ungar and
Mark Craven and
Dimitrios Gunopulos},
title = {Attack detection in time series for recommender systems},
booktitle = {Proceedings of the Twelfth {ACM} {SIGKDD} International Conference
on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August
20-23, 2006},
pages = {809--814},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1150402.1150508},
doi = {10.1145/1150402.1150508},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/kdd/ZhangCFM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChakrabartiBM06,
author = {Amit Chakrabarti and
Khanh Do Ba and
S. Muthukrishnan},
editor = {Bruno Durand and
Wolfgang Thomas},
title = {Estimating Entropy and Entropy Norm on Data Streams},
booktitle = {{STACS} 2006, 23rd Annual Symposium on Theoretical Aspects of Computer
Science, Marseille, France, February 23-25, 2006, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3884},
pages = {196--205},
publisher = {Springer},
year = {2006},
url = {https://doi.org/10.1007/11672142\_15},
doi = {10.1007/11672142\_15},
timestamp = {Wed, 19 May 2021 12:05:43 +0200},
biburl = {https://dblp.org/rec/conf/stacs/ChakrabartiBM06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BansalCES06,
author = {Nikhil Bansal and
Amit Chakrabarti and
Amir Epstein and
Baruch Schieber},
editor = {Jon M. Kleinberg},
title = {A quasi-PTAS for unsplittable flow on line graphs},
booktitle = {Proceedings of the 38th Annual {ACM} Symposium on Theory of Computing,
Seattle, WA, USA, May 21-23, 2006},
pages = {721--729},
publisher = {{ACM}},
year = {2006},
url = {https://doi.org/10.1145/1132516.1132617},
doi = {10.1145/1132516.1132617},
timestamp = {Tue, 15 Feb 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BansalCES06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiR04,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest
Neighbour Searching},
booktitle = {45th Symposium on Foundations of Computer Science {(FOCS} 2004), 17-19
October 2004, Rome, Italy, Proceedings},
pages = {473--482},
publisher = {{IEEE} Computer Society},
year = {2004},
url = {https://doi.org/10.1109/FOCS.2004.12},
doi = {10.1109/FOCS.2004.12},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiR04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/mm/WangMC04,
author = {Yuhang Wang and
Fillia Makedon and
Amit Chakrabarti},
editor = {Henning Schulzrinne and
Nevenka Dimitrova and
Martina Angela Sasse and
Sue B. Moon and
Rainer Lienhart},
title = {R*-Histograms: efficient representation of spatial relations between
objects of arbitrary topology},
booktitle = {Proceedings of the 12th {ACM} International Conference on Multimedia,
New York, NY, USA, October 10-16, 2004},
pages = {356--359},
publisher = {{ACM}},
year = {2004},
url = {https://doi.org/10.1145/1027527.1027610},
doi = {10.1145/1027527.1027610},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/mm/WangMC04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/ChakrabartiKS03,
author = {Amit Chakrabarti and
Subhash Khot and
Xiaodong Sun},
title = {Near-Optimal Lower Bounds on the Multi-Party Communication Complexity
of Set Disjointness},
booktitle = {18th Annual {IEEE} Conference on Computational Complexity (Complexity
2003), 7-10 July 2003, Aarhus, Denmark},
pages = {107--117},
publisher = {{IEEE} Computer Society},
year = {2003},
url = {https://doi.org/10.1109/CCC.2003.1214414},
doi = {10.1109/CCC.2003.1214414},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/ChakrabartiKS03.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ECCC-TR03-070,
author = {Amit Chakrabarti and
Oded Regev},
title = {An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest
Neighbour Searching},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR03-070}},
year = {2003},
url = {https://eccc.weizmann.ac.il/eccc-reports/2003/TR03-070/index.html},
eprinttype = {ECCC},
eprint = {TR03-070},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ECCC-TR03-070.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/ChakrabartiCGK02,
author = {Amit Chakrabarti and
Chandra Chekuri and
Anupam Gupta and
Amit Kumar},
editor = {Klaus Jansen and
Stefano Leonardi and
Vijay V. Vazirani},
title = {Approximation Algorithms for the Unsplittable Flow Problem},
booktitle = {Approximation Algorithms for Combinatorial Optimization, 5th International
Workshop, {APPROX} 2002, Rome, Italy, September 17-21, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2462},
pages = {51--66},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-45753-4\_7},
doi = {10.1007/3-540-45753-4\_7},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/approx/ChakrabartiCGK02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/ipco/CalinescuCKR02,
author = {Gruia C{\u{a}}linescu and
Amit Chakrabarti and
Howard J. Karloff and
Yuval Rabani},
editor = {William J. Cook and
Andreas S. Schulz},
title = {Improved Approximation Algorithms for Resource Allocation},
booktitle = {Integer Programming and Combinatorial Optimization, 9th International
{IPCO} Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2337},
pages = {401--414},
publisher = {Springer},
year = {2002},
url = {https://doi.org/10.1007/3-540-47867-1\_28},
doi = {10.1007/3-540-47867-1\_28},
timestamp = {Tue, 14 May 2019 10:00:50 +0200},
biburl = {https://dblp.org/rec/conf/ipco/CalinescuCKR02.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ChakrabartiKS01,
author = {Amit Chakrabarti and
Subhash Khot and
Yaoyun Shi},
title = {Evasiveness of Subgraph Containment and Related Properties},
journal = {{SIAM} J. Comput.},
volume = {31},
number = {3},
pages = {866--875},
year = {2001},
url = {https://doi.org/10.1137/S0097539700382005},
doi = {10.1137/S0097539700382005},
timestamp = {Wed, 14 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/siamcomp/ChakrabartiKS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ChakrabartiSWY01,
author = {Amit Chakrabarti and
Yaoyun Shi and
Anthony Wirth and
Andrew Chi{-}Chih Yao},
title = {Informational Complexity and the Direct Sum Problem for Simultaneous
Message Complexity},
booktitle = {42nd Annual Symposium on Foundations of Computer Science, {FOCS} 2001,
14-17 October 2001, Las Vegas, Nevada, {USA}},
pages = {270--278},
publisher = {{IEEE} Computer Society},
year = {2001},
url = {https://doi.org/10.1109/SFCS.2001.959901},
doi = {10.1109/SFCS.2001.959901},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ChakrabartiSWY01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/ChakrabartiK01,
author = {Amit Chakrabarti and
Subhash Khot},
editor = {Fernando Orejas and
Paul G. Spirakis and
Jan van Leeuwen},
title = {Improved Lower Bounds on the Randomized Complexity of Graph Properties},
booktitle = {Automata, Languages and Programming, 28th International Colloquium,
{ICALP} 2001, Crete, Greece, July 8-12, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2076},
pages = {285--296},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-48224-5\_24},
doi = {10.1007/3-540-48224-5\_24},
timestamp = {Tue, 14 May 2019 10:00:44 +0200},
biburl = {https://dblp.org/rec/conf/icalp/ChakrabartiK01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/ChakrabartiKS01,
author = {Amit Chakrabarti and
Subhash Khot and
Yaoyun Shi},
editor = {Afonso Ferreira and
Horst Reichel},
title = {Evasiveness of Subgraph Containment and Related Properties},
booktitle = {{STACS} 2001, 18th Annual Symposium on Theoretical Aspects of Computer
Science, Dresden, Germany, February 15-17, 2001, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {2010},
pages = {110--120},
publisher = {Springer},
year = {2001},
url = {https://doi.org/10.1007/3-540-44693-1\_10},
doi = {10.1007/3-540-44693-1\_10},
timestamp = {Tue, 14 May 2019 10:00:48 +0200},
biburl = {https://dblp.org/rec/conf/stacs/ChakrabartiKS01.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ChakrabartiCGL99,
author = {Amit Chakrabarti and
Bernard Chazelle and
Benjamin Gum and
Alexey Lvov},
editor = {Jeffrey Scott Vitter and
Lawrence L. Larmore and
Frank Thomson Leighton},
title = {A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching
on the Hamming Cube},
booktitle = {Proceedings of the Thirty-First Annual {ACM} Symposium on Theory of
Computing, May 1-4, 1999, Atlanta, Georgia, {USA}},
pages = {305--311},
publisher = {{ACM}},
year = {1999},
url = {https://doi.org/10.1145/301250.301325},
doi = {10.1145/301250.301325},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ChakrabartiCGL99.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-25 02:22 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:
