Publication

Near-Optimal Noisy Group Testing via Separate Decoding of Items

Related publications (37)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Polarization and Channel Ordering: Characterizations and Topological Structures

Rajai Nasser

Information theory is the field in which we study the fundamental limitations of communication. Shannon proved in 1948 that there exists a maximum rate, called capacity, at which we can reliably communicate information through a given channel. However, Sha ...

EPFL2017

How little does non-exact recovery help in group testing?

Volkan Cevher, Jonathan Mark Scarlett

We consider the group testing problem, in which one seeks to identify a subset of defective items within a larger set of items based on a number of tests. We characterize the information-theoretic performance limits in the presence of list decoding, in whi ...

Ieee2017

Modelling across extremal dependence classes

Anthony Christopher Davison, Jonathan A. Tawn, Jennifer Lynne Wadsworth

Different dependence scenarios can arise in multivariate extremes, entailing careful selection of an appropriate class of models. In bivariate extremes, the variables are either asymptotically dependent or are asymptotically independent. Most available sta ...

Wiley-Blackwell2017

Optimal Computational Split-state Non-malleable Codes

Divesh Aggarwal, Divya Gupta

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the message contained in the tampered codeword is either the or ...

Springer Int Publishing Ag2016

Analysis of Spatially Coupled Systems using the Potential Functional with Applications to Coding Theory

Rafah El-Khatib

For the past 70 years or so, coding theorists have been aiming at designing transmission schemes with efficient encoding and decoding algorithms that achieve the capacity of various noisy channels. It was not until the '90s that graph-based codes, such as ...

EPFL2016

Polar Codes for Broadcast Channels

Michael Christoph Gastpar, Emmanuel Abbé, Naveen Goela

Polar codes are introduced for discrete memoryless broadcast channels. For m-user deterministic broadcast channels, polarization is applied to map uniformly random message bits from m-independent messages to one codeword while satisfying broadcast constrai ...

Institute of Electrical and Electronics Engineers2015

Re-proving Channel Polarization Theorems

Mine Alsan

The general subject considered in this thesis is a recently discovered coding technique, polar coding, which is used to construct a class of error correction codes with unique properties. In his ground-breaking work, Arikan proved that this class of codes, ...

EPFL2015

Limits on Support Recovery with Probabilistic Models: An Information-Theoretic Framework

Volkan Cevher, Jonathan Mark Scarlett

The support recovery problem consists of deter- mining a sparse subset of a set of variables that is relevant in generating a set of observations, and arises in a diverse range of settings such as group testing, compressive sensing, and subset selection in ...

2015

Sparse Probabilistic Models

Andrei Giurgiu

This thesis is concerned with a number of novel uses of spatial coupling, applied to a class of probabilistic graphical models. These models include error correcting codes, random constraint satisfaction problems (CSPs) and statistical physics models calle ...

EPFL2015

Achieving Marton's Region for Broadcast Channels Using Polar Codes

Rüdiger Urbanke, Seyed Hamed Hassani, Marco Mondelli

We present polar coding schemes for the 2-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region up to date, and it is tight for all classes of 2-user ...

Ieee2014