Volume

Dagstuhl Seminar Proceedings, Volume 5291

Publication Details

  • published at: 2006-08-28
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.05291.1
05291 Abstracts Collection – Sublinear Algorithms

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

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
DOI: 10.4230/DagSemProc.05291.2
Approximating Average Parameters of Graphs

Authors: Oded Goldreich and Dana Ron

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
DOI: 10.4230/DagSemProc.05291.3
Contemplations on Testing Graph Properties

Authors: Oded Goldreich

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
DOI: 10.4230/DagSemProc.05291.4
Sublinear Geometric Algorithms

Authors: Bernard Chazelle, Ding Liu, and Avner Magen

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}
}

Filters

  • Authors
  • C
  • Chazelle, Bernard
  • Czumaj, Artur
  • G
  • Goldreich, Oded
  • L
  • Liu, Ding
  • M
  • Magen, Avner
  • Muthukrishnan, S. Muthu
  • R
  • Ron, Dana
  • Rubinfeld, Ronitt
  • S
  • Sohler, Christian

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