Search Results

Documents authored by Ganguly, Sumit

Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2018
LIPIcs, Volume 122, FSTTCS'18, Complete Volume

Authors: Sumit Ganguly and Paritosh Pandya

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
LIPIcs, Volume 122, FSTTCS'18, Complete Volume
Cite as

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{ganguly_et_al:LIPIcs.FSTTCS.2018,
  title =	{{LIPIcs, Volume 122, FSTTCS'18, Complete Volume}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018},
  URN =		{urn:nbn:de:0030-drops-100240},
  doi =		{10.4230/LIPIcs.FSTTCS.2018},
  annote =	{Keywords: Theory of Computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sumit Ganguly and Paritosh Pandya

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganguly_et_al:LIPIcs.FSTTCS.2018.0,
  author =	{Ganguly, Sumit and Pandya, Paritosh},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.0},
  URN =		{urn:nbn:de:0030-drops-98992},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.58
High Probability Frequency Moment Sketches

Authors: Sumit Ganguly and David P. Woodruff

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the problem of sketching the p-th frequency moment of a vector, p>2, with multiplicative error at most 1 +/- epsilon and with high confidence 1-delta. Despite the long sequence of work on this problem, tight bounds on this quantity are only known for constant delta. While one can obtain an upper bound with error probability delta by repeating a sketching algorithm with constant error probability O(log(1/delta)) times in parallel, and taking the median of the outputs, we show this is a suboptimal algorithm! Namely, we show optimal upper and lower bounds of Theta(n^{1-2/p} log(1/delta) + n^{1-2/p} log^{2/p} (1/delta) log n) on the sketching dimension, for any constant approximation. Our result should be contrasted with results for estimating frequency moments for 1 <= p <= 2, for which we show the optimal algorithm for general delta is obtained by repeating the optimal algorithm for constant error probability O(log(1/delta)) times and taking the median output. We also obtain a matching lower bound for this problem, up to constant factors.
Cite as

Sumit Ganguly and David P. Woodruff. High Probability Frequency Moment Sketches. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ganguly_et_al:LIPIcs.ICALP.2018.58,
  author =	{Ganguly, Sumit and Woodruff, David P.},
  title =	{{High Probability Frequency Moment Sketches}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.58},
  URN =		{urn:nbn:de:0030-drops-90623},
  doi =		{10.4230/LIPIcs.ICALP.2018.58},
  annote =	{Keywords: Data Streams, Frequency Moments, High Confidence}
}
Document
DOI: 10.4230/DagSemProc.08341.4
Lower bound for estimating frequency for update data streams

Authors: Sumit Ganguly

Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)

Abstract
We consider general update streams, where, the stream is a sequence of updates of the form $(index, i, v)$, where, $i in {1,2 ldots, n}$ and $v in {-1,+1}$, signifying deletion or insertion, respectively of an instance of $i$. The frequency of $i in {1,2,ldots, n}$ is given as the sum of the updates to $i$, that is, $f_i(sigma) = sum_{(index,i,v) in sigma} v $. The $n$-dimensional vector $f(sigma)$ with $i$th coordinate $f_i(sigma)$ is called the frequency vector of the stream $sigma$. We consider the problem of finding an n-dimensional integer vector $hat{f}(sigma)$ that estimates the frequency vector $f(sigma)$ of an input stream $sigma$ in the following sense: orm{hat{f} (sigma)- f(sigma)} le epsilon orm{f(sigma)}_p For $p=1$ and $2$, there are randomized algorithms known with space bound $ ilde{O}(epsilon^{-p})$. A space lower bound of $Omega(epsilon^{-1} log (nepsilon))$ is also known. However, the deterministic space upper bound is $ ilde{O}(epsilon^{-2})$. In this work, we present a deterministic space lower bound of $Omega(n^{2-2/p}epsilon^{-2} log |{sigma}|)$, for $1le p < 2$ and $1/4 le epsilon = Omega(n^{1/2-1/p})$. For $p ge 2$, we show an $Omega(n)$ space lower bound for all $epsilon < 1/4$. The results are obtained using a new characterization of data stream computations, that show that any uniform computation over a data stream may be viewed as an appropriate linear map.
Cite as

Sumit Ganguly. Lower bound for estimating frequency for update data streams. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ganguly:DagSemProc.08341.4,
  author =	{Ganguly, Sumit},
  title =	{{Lower bound for estimating frequency for update data streams}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8341},
  editor =	{Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.4},
  URN =		{urn:nbn:de:0030-drops-16959},
  doi =		{10.4230/DagSemProc.08341.4},
  annote =	{Keywords: Data stream, lower bound, frequency estimation, stream automata, linear map}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact