Search Results

Documents authored by Rotschild, Amir


Document
Explicit Non-Adaptive Combinatorial Group Testing Schemes

Authors: Ely Porat and Amir Rotschild

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)


Abstract
Group testing is a long studied problem in combinatorics: A small set of r ill people should be identified out of the whole (n people) by using only queries (tests) of the form "Does set X contain an ill human?". In this paper we provide an explicit construction of a testing scheme which is better (smaller) than any known explicit construction. This scheme has \Theta(min[r2 log n, n])tests which is as many as the best non-explicit schemes have. In our construction we use a fact that may have a value by its own right: Linear error-correction codes with parameters [m, k, \delta m]q meeting the Gilbert-Varshamov bound may be constructed quite efficiently, in \Theta[q^{k}m) time.

Cite as

Ely Porat and Amir Rotschild. Explicit Non-Adaptive Combinatorial Group Testing Schemes. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{porat_et_al:DagSemProc.09281.2,
  author =	{Porat, Ely and Rotschild, Amir},
  title =	{{Explicit Non-Adaptive Combinatorial Group Testing Schemes}},
  booktitle =	{Search Methodologies},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.2},
  URN =		{urn:nbn:de:0030-drops-22414},
  doi =		{10.4230/DagSemProc.09281.2},
  annote =	{Keywords: Prime Numbers, Group Testing, Streaming, Pattern Matching}
}
Document
Pattern matching with don't cares and few errors

Authors: Raphael Clifford, Klim Efremo, Ely Porat, and Amir Rotschild

Published in: Dagstuhl Seminar Proceedings, Volume 9281, Search Methodologies (2009)


Abstract
We present solutions for the k-mismatch pattern matching problem with don't cares. Given a text t of length n and a pattern p of length m with don't care symbols and a bound k, our algorithms find all the places that the pattern matches the text with at most k mismatches. We first give an \Theta(n(k + logmlog k) log n) time randomised algorithm which finds the correct answer with high probability. We then present a new deter- ministic \Theta(nk^2 log^m)time solution that uses tools originally developed for group testing. Taking our derandomisation approach further we de- velop an approach based on k-selectors that runs in \Theta(nk polylogm) time. Further, in each case the location of the mismatches at each alignment is also given at no extra cost.

Cite as

Raphael Clifford, Klim Efremo, Ely Porat, and Amir Rotschild. Pattern matching with don't cares and few errors. In Search Methodologies. Dagstuhl Seminar Proceedings, Volume 9281, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{clifford_et_al:DagSemProc.09281.5,
  author =	{Clifford, Raphael and Efremo, Klim and Porat, Ely and Rotschild, Amir},
  title =	{{Pattern matching with don't cares and few errors}},
  booktitle =	{Search Methodologies},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9281},
  editor =	{Rudolf Ahlswede and Ferdinando Cicalese and Ugo Vaccaro},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09281.5},
  URN =		{urn:nbn:de:0030-drops-22442},
  doi =		{10.4230/DagSemProc.09281.5},
  annote =	{Keywords: Prime Numbers, Group Testing, Streaming, Pattern Matching}
}
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