Search Results

Documents authored by Shokrollahi, M. Amin


Found 2 Possible Name Variants:

Shokrollahi, M. Amin

Document
Coding Theory (Dagstuhl Seminar 11461)

Authors: Joachim Rosenthal, M. Amin Shokrollahi, and Judy L. Walker

Published in: Dagstuhl Reports, Volume 1, Issue 11 (2012)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11461 ``Coding Theory''. A (channel) code is typically a set of vectors of the same length n over a finite alphabet \Sigma. By choosing a fixed codebook, binary strings of appropriate length are injectively mapped into the elements of the code. These elements are then transmitted over a communications channel which induces errors on the codeword. Depending on how well the original code is designed, and which algorithms are used, the result of this transmission and attempts to recover the original vector after transmission can be anywhere between disastrous to excellent. Coding theory is all about the design of excellent codes as a function of the communications channel, and the design of efficient algorithms for choosing the codebook vectors, and more importantly, for recovering the original vector after transmission. As such, successful design of codes requires knowledge and tools in a number of areas such as combinatorics, algorithms design, probability theory and complexity theory, to name a few. The purpose of this workshop is to bring together researchers in the field to discuss recent theoretical advances in algebraic coding, codes on graphs, and network coding, as well as new and emerging applications of coding methods to real-world problems.

Cite as

Joachim Rosenthal, M. Amin Shokrollahi, and Judy L. Walker. Coding Theory (Dagstuhl Seminar 11461). In Dagstuhl Reports, Volume 1, Issue 11, pp. 50-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Article{rosenthal_et_al:DagRep.1.11.50,
  author =	{Rosenthal, Joachim and Shokrollahi, M. Amin and Walker, Judy L.},
  title =	{{Coding Theory (Dagstuhl Seminar 11461)}},
  pages =	{50--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{1},
  number =	{11},
  editor =	{Rosenthal, Joachim and Shokrollahi, M. Amin and Walker, Judy L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.11.50},
  URN =		{urn:nbn:de:0030-drops-33770},
  doi =		{10.4230/DagRep.1.11.50},
  annote =	{Keywords: Algebraic coding theory, complexity theory, cryptography, graph theory, graph based codes, information theory, randomized algorithms, networking}
}

Shokrollahi, Amin

Document
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Authors: Mahdi Cheraghchi and Amin Shokrollahi

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


Abstract
We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.

Cite as

Mahdi Cheraghchi and Amin Shokrollahi. Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 277-288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2009.1817,
  author =	{Cheraghchi, Mahdi and Shokrollahi, Amin},
  title =	{{Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{277--288},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1817},
  URN =		{urn:nbn:de:0030-drops-18174},
  doi =		{10.4230/LIPIcs.STACS.2009.1817},
  annote =	{Keywords: Uniform sampling, Algebraic varieties, Randomized algorithms, Computational complexity}
}
Document
08301 Final Report – Group Testing in the Life Sciences

Authors: Alexander Schliep, Nicolas Thierry-Mieg, and Amin Shokrollahi

Published in: Dagstuhl Seminar Proceedings, Volume 8301, Group Testing in the Life Sciences (2008)


Abstract
Group testing AKA smart-pooling is a general strategy for minimizing the number of tests necessary for identifying positives among a large collection of items. It has the potential to efficiently identify and correct for experimental errors (false–positives and false–negatives). It can be used whenever tests can detect the presence of a positive in a group (or pool) of items, provided that positives are rare. Group testing has numerous applications in the life sciences, such as physical mapping, interactome mapping, drug–resistance screening, or designing DNA-microarrays, and many connections to computer science, mathematics and communications, from error-correcting codes to combinatorial design theory and to statistics. The seminar brought together researchers representing the different communities working on group testing and experimentalists from the life sciences. The desired outcome of the seminar was a better understanding of the requirements for and the possibilities of group testing in the life sciences.

Cite as

Alexander Schliep, Nicolas Thierry-Mieg, and Amin Shokrollahi. 08301 Final Report – Group Testing in the Life Sciences. In Group Testing in the Life Sciences. Dagstuhl Seminar Proceedings, Volume 8301, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{schliep_et_al:DagSemProc.08301.1,
  author =	{Schliep, Alexander and Thierry-Mieg, Nicolas and Shokrollahi, Amin},
  title =	{{08301 Final Report – Group Testing in the Life Sciences}},
  booktitle =	{Group Testing in the Life Sciences},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8301},
  editor =	{Alexander Schliep and Amin Shokrollahi and Nicolas Thierry-Mieg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08301.1},
  URN =		{urn:nbn:de:0030-drops-17806},
  doi =		{10.4230/DagSemProc.08301.1},
  annote =	{Keywords: Group Testing, Pooling, Combinatorics, Design Theory, Error correcting}
}
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