12 Search Results for "Muthukrishnan, S."


Document
The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

Authors: Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)


Abstract
Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs. * (Insert-Only Streams) We present a one-pass algorithm that takes O(alpha log n) space and approximates the size of the maximum matching in graphs with arboricity alpha within a factor of O(alpha). This improves significantly upon the state-of-the-art tilde{O}(alpha n^{2/3})-space streaming algorithms, and is the first poly-logarithmic space algorithm for this problem. * (Dynamic Streams) Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying alpha-bounded arboricity graph, we present an one-pass algorithm that uses space tilde{O}(alpha^{10/3}n^{2/3}) and returns an O(alpha)-estimator for the size of the maximum matching on the condition that the number edge deletions in the stream is bounded by O(alpha n). For this class of inputs, our algorithm improves the state-of-the-art tilde{O}(\alpha n^{4/5})-space algorithms, where the \tilde{O}(.) notation hides logarithmic in n dependencies. In contrast to prior work, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.

Cite as

Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan. The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{cormode_et_al:LIPIcs.ESA.2017.29,
  author =	{Cormode, Graham and Jowhari, Hossein and Monemizadeh, Morteza and Muthukrishnan, S.},
  title =	{{The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.29},
  URN =		{urn:nbn:de:0030-drops-78499},
  doi =		{10.4230/LIPIcs.ESA.2017.29},
  annote =	{Keywords: streaming algorithms, matching size}
}
Document
Testable Bounded Degree Graph Properties Are Random Order Streamable

Authors: Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We study which property testing and sublinear time algorithms can be transformed into graph streaming algorithms for random order streams. Our main result is that for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams. Our result is obtained by estimating the distribution of local neighborhoods of the vertices on a random order graph stream using constant space. We then show that our approach can also be applied to constant time approximation algorithms for bounded degree graphs in the adjacency list model: As an example, we obtain a constant-space single-pass random order streaming algorithms for approximating the size of a maximum matching with additive error epsilon n (n is the number of nodes). Our result establishes for the first time that a large class of sublinear algorithms can be simulated in random order streams, while Omega(n) space is needed for many graph streaming problems for adversarial orders.

Cite as

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, and Christian Sohler. Testable Bounded Degree Graph Properties Are Random Order Streamable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 131:1-131:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{monemizadeh_et_al:LIPIcs.ICALP.2017.131,
  author =	{Monemizadeh, Morteza and Muthukrishnan, S. and Peng, Pan and Sohler, Christian},
  title =	{{Testable Bounded Degree Graph Properties Are Random Order Streamable}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{131:1--131:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.131},
  URN =		{urn:nbn:de:0030-drops-74782},
  doi =		{10.4230/LIPIcs.ICALP.2017.131},
  annote =	{Keywords: Graph streaming algorithms, graph property testing, constant-time approximation algorithms}
}
Document
Functionally Private Approximations of Negligibly-Biased Estimators

Authors: André Madeira and S. Muthukrishnan

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


Abstract
We study functionally private approximations. An approximation function $g$ is {\em functionally private} with respect to $f$ if, for any input $x$, $g(x)$ reveals no more information about $x$ than $f(x)$. Our main result states that a function $f$ admits an efficiently-computable functionally private approximation $g$ if there exists an efficiently-computable and negligibly-biased estimator for $f$. Contrary to previous generic results, our theorem is more general and has a wider application reach.We provide two distinct applications of the above result to demonstrate its flexibility. In the data stream model, we provide a functionally private approximation to the $L_p$-norm estimation problem, a quintessential application in streaming, using only polylogarithmic space in the input size. The privacy guarantees rely on the use of pseudo-random {\em functions} (PRF) (a stronger cryptographic notion than pseudo-random generators) of which can be based on common cryptographic assumptions.The application of PRFs in this context appears to be novel and we expect other results to follow suit.Moreover, this is the first known functionally private streaming result for {\em any} problem. Our second application result states that every problem in some subclasses of \SP of hard counting problems admit efficient and functionally private approximation protocols. This result is based on a functionally private approximation for the \SDNF problem (or estimating the number of satisfiable truth assignments to a Boolean formula in disjunctive normal form), which is an application of our main theorem and previously known results.

Cite as

André Madeira and S. Muthukrishnan. Functionally Private Approximations of Negligibly-Biased Estimators. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 323-334, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{madeira_et_al:LIPIcs.FSTTCS.2009.2329,
  author =	{Madeira, Andr\'{e} and Muthukrishnan, S.},
  title =	{{Functionally Private Approximations of Negligibly-Biased Estimators}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{323--334},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2329},
  URN =		{urn:nbn:de:0030-drops-23298},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2329},
  annote =	{Keywords: Functional privacy, privacy, data streams, #P-complete}
}
Document
Optimal Cache-Aware Suffix Selection

Authors: Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)


Abstract
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the suffix selection problem in the cache-aware model that captures two-level memory inherent in computing systems, for a \emph{cache} of limited size $M$ and block size $B$. The complexity of interest is the number of block transfers. We present an optimal suffix selection algorithm in the cache-aware model, requiring $\Theta\left(N/B\right)$ block transfers, for any string $S$ over an unbounded alphabet (where characters can only be compared), under the common tall-cache assumption (i.e. $M=\Omega\left(B^{1+\epsilon}\right)$, where $\epsilon<1$). Our algorithm beats the bottleneck bound for permuting an input array to the desired output array, which holds for nearly any nontrivial problem in hierarchical memory models.

Cite as

Gianni Franceschini, Roberto Grossi, and S. Muthukrishnan. Optimal Cache-Aware Suffix Selection. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 457-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{franceschini_et_al:LIPIcs.STACS.2009.1845,
  author =	{Franceschini, Gianni and Grossi, Roberto and Muthukrishnan, S.},
  title =	{{Optimal Cache-Aware Suffix Selection}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{457--468},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1845},
  URN =		{urn:nbn:de:0030-drops-18452},
  doi =		{10.4230/LIPIcs.STACS.2009.1845},
  annote =	{Keywords: }
}
Document
08341 Abstracts Collection – Sublinear Algorithms

Authors: Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler

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


Abstract
From August 17 to August 22, 2008, the Dagstuhl Seminar 08341 ``Sublinear Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 08341 Abstracts Collection – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:DagSemProc.08341.1,
  author =	{Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian},
  title =	{{08341 Abstracts Collection – Sublinear Algorithms}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--19},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.1},
  URN =		{urn:nbn:de:0030-drops-16981},
  doi =		{10.4230/DagSemProc.08341.1},
  annote =	{Keywords: Sublinear algorithms, property testing, data streaming, graph algorithms, approximation algorithms}
}
Document
08341 Executive Summary – Sublinear Algorithms

Authors: Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler

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


Abstract
This report summarizes the content and structure of the Dagstuhl seminar `Sublinear Algorithms', which was held from 17.8.2008 to 22.8.2008 in Schloss Dagstuhl, Germany.

Cite as

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 08341 Executive Summary – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:DagSemProc.08341.2,
  author =	{Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian},
  title =	{{08341 Executive Summary – Sublinear Algorithms}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--2},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.2},
  URN =		{urn:nbn:de:0030-drops-16964},
  doi =		{10.4230/DagSemProc.08341.2},
  annote =	{Keywords: Sublinear algorithms, property testing, data streaming, graph algorithms, approximation algorithms}
}
Document
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

Authors: Tali Kaufman, Simon Litsyn, and Ning Xie

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


Abstract
For Boolean functions that are $epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted by $extsc{rej}(epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. This problem is arguably the most fundamental and extensively studied problem in property testing of Boolean functions. The previously best bounds for $extsc{rej}(epsilon)$ were obtained by Bellare, Coppersmith, H{{a}}stad, Kiwi and Sudan. They used Fourier analysis to show that $ extsc{rej}(epsilon) geq e$ for every $0 leq epsilon leq frac{1}{2}$. They also conjectured that this bound might not be tight for $epsilon$'s which are close to $1/2$. In this paper we show that this indeed is the case. Specifically, we improve the lower bound of $ extsc{rej}(epsilon) geq epsilon$ by an additive constant that depends only on $epsilon$: $extsc{rej}(epsilon) geq epsilon + min {1376epsilon^{3}(1-2epsilon)^{12}, frac{1}{4}epsilon(1-2epsilon)^{4}}$, for every $0 leq epsilon leq frac{1}{2}$. Our analysis is based on a relationship between $extsc{rej}(epsilon)$ and the weight distribution of a coset of the Hadamard code. We use both Fourier analysis and coding theory tools to estimate this weight distribution.

Cite as

Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2). In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:DagSemProc.08341.3,
  author =	{Kaufman, Tali and Litsyn, Simon and Xie, Ning},
  title =	{{Breaking the \$\backslashepsilon\$-Soundness Bound of the Linearity Test over GF(2)}},
  booktitle =	{Sublinear Algorithms},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.3},
  URN =		{urn:nbn:de:0030-drops-16971},
  doi =		{10.4230/DagSemProc.08341.3},
  annote =	{Keywords: Linearity test, Fourier analysis, coding theory}
}
Document
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-dev.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}
}
Document
05291 Abstracts Collection – Sublinear Algorithms

Authors: Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler

Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)


Abstract
From 17.07.05 to 22.07.05, the Dagstuhl Seminar 05291 ``Sublinear Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, and Christian Sohler. 05291 Abstracts Collection – Sublinear Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{czumaj_et_al:DagSemProc.05291.1,
  author =	{Czumaj, Artur and Muthukrishnan, S. Muthu and Rubinfeld, Ronitt and Sohler, Christian},
  title =	{{05291 Abstracts Collection – Sublinear Algorithms}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5291},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.1},
  URN =		{urn:nbn:de:0030-drops-6814},
  doi =		{10.4230/DagSemProc.05291.1},
  annote =	{Keywords: Property testing, sublinear time approximation algorithms, data streaming algorithms}
}
Document
Approximating Average Parameters of Graphs

Authors: Oded Goldreich and Dana Ron

Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)


Abstract
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the i'th neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial.

Cite as

Oded Goldreich and Dana Ron. Approximating Average Parameters of Graphs. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{goldreich_et_al:DagSemProc.05291.2,
  author =	{Goldreich, Oded and Ron, Dana},
  title =	{{Approximating Average Parameters of Graphs}},
  booktitle =	{Sublinear Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5291},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.2},
  URN =		{urn:nbn:de:0030-drops-5531},
  doi =		{10.4230/DagSemProc.05291.2},
  annote =	{Keywords: Graph parameters, degree, distance}
}
Document
Contemplations on Testing Graph Properties

Authors: Oded Goldreich

Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)


Abstract
This note documents two programmatic comments regarding testing graph properties, which I made during the workshop. The first comment advocates paying more attention to the dependence of the tester's complexity on the proximity parameter. The second comment advocates paying more attention to the question of testing general graphs (rather than dense or bounded-degree ones). In addition, this note includes a suggestion to view property testing within the framework of promise problems.

Cite as

Oded Goldreich. Contemplations on Testing Graph Properties. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{goldreich:DagSemProc.05291.3,
  author =	{Goldreich, Oded},
  title =	{{Contemplations on Testing Graph Properties}},
  booktitle =	{Sublinear Algorithms},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5291},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.3},
  URN =		{urn:nbn:de:0030-drops-5552},
  doi =		{10.4230/DagSemProc.05291.3},
  annote =	{Keywords: Property testing, graph properties}
}
Document
Sublinear Geometric Algorithms

Authors: Bernard Chazelle, Ding Liu, and Avner Magen

Published in: Dagstuhl Seminar Proceedings, Volume 5291, Sublinear Algorithms (2006)


Abstract
We present sublinear algorithms to such problems as Detecting of Polytope intersection, Shortest Path on 3D convex Polytopes and volume approximation.

Cite as

Bernard Chazelle, Ding Liu, and Avner Magen. Sublinear Geometric Algorithms. In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 5291, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:DagSemProc.05291.4,
  author =	{Chazelle, Bernard and Liu, Ding and Magen, Avner},
  title =	{{Sublinear Geometric Algorithms}},
  booktitle =	{Sublinear Algorithms},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5291},
  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-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05291.4},
  URN =		{urn:nbn:de:0030-drops-5548},
  doi =		{10.4230/DagSemProc.05291.4},
  annote =	{Keywords: Sublinear algorithms, computational geometry}
}
  • Refine by Author
  • 4 Muthukrishnan, S.
  • 4 Sohler, Christian
  • 3 Czumaj, Artur
  • 3 Muthukrishnan, S. Muthu
  • 3 Rubinfeld, Ronitt
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 3 Sublinear algorithms
  • 2 Property testing
  • 2 approximation algorithms
  • 2 data streaming
  • 2 graph algorithms
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 4 2006
  • 4 2008
  • 2 2009
  • 2 2017

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