**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Publication# Near-Optimal Noisy Group Testing via Separate Decoding of Items

Abstract

In this paper, we revisit an efficient algorithm for noisy group testing in which each item is decoded separately (Malyutov and Mateev, 1980), and develop novel performance guarantees via an information-theoretic framework for general noise models. For the noiseless and symmetric noise models, we find that the asymptotic number of tests required for vanishing error probability is within a factor log 2 ≈ 0.7 of the informationtheoretic optimum at low parsity levels, and that when a small fraction of incorrectly-decoded items is allowed, this guarantee extends to all sublinear sparsity levels. In many scaling regimes, these are the best known theoretical guarantees for any noisy group testing algorithm.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (34)

Related publications (36)

Related MOOCs (4)

Fraction

A fraction (from fractus, "broken") represents a part of a whole or, more generally, any number of equal parts. When spoken in everyday English, a fraction describes how many parts of a certain size there are, for example, one-half, eight-fifths, three-quarters. A common, vulgar, or simple fraction (examples: and ) consists of an integer numerator, displayed above a line (or before a slash like ), and a non-zero integer denominator, displayed below (or after) that line.

Asymptotic analysis

In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function f (n) as n becomes very large. If f(n) = n2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n2. The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞". This is often written symbolically as f (n) ~ n2, which is read as "f(n) is asymptotic to n2".

Asymptotic expansion

In mathematics, an asymptotic expansion, asymptotic series or Poincaré expansion (after Henri Poincaré) is a formal series of functions which has the property that truncating the series after a finite number of terms provides an approximation to a given function as the argument of the function tends towards a particular, often infinite, point. Investigations by revealed that the divergent part of an asymptotic expansion is latently meaningful, i.e. contains information about the exact value of the expanded function.

We offer the first security analysis of cache compression, a promising architectural technique that is likely to appear in future mainstream processors. We find that cache compression has novel security implications because the compressibility of a cache l ...

Rachid Guerraoui, Nirupam Gupta, John Stephan, Sadegh Farhadkhani, Le Nguyen Hoang, Rafaël Benjamin Pinot

Collaborative learning algorithms, such as distributed SGD (or D-SGD), are prone to faulty machines that may deviate from their prescribed algorithm because of software or hardware bugs, poisoned data or malicious behaviors. While many solutions have been ...

Trigonometric Functions, Logarithms and Exponentials

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Trigonometric Functions, Logarithms and Exponentials

Ce cours donne les connaissances fondamentales liées aux fonctions trigonométriques, logarithmiques et exponentielles. La présentation des concepts et des propositions est soutenue par une grande gamm

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Martin Jaggi, Sebastian Urban Stich, Tao Lin, Lingjing Kong

Deep learning networks are typically trained by Stochastic Gradient Descent (SGD) methods that iteratively improve the model parameters by estimating a gradient on a very small fraction of the training data. A major roadblock faced when increasing the batc ...

2020