We propose a simple but novel self-decoding model for neural coding based on the principle that the neuron body represents ongoing stimulus while dendrites are used to store that stimulus as a memory. Suppose$t$spiking presynaptic neurons transmit any stimulus directly to a population of$n$postsynaptic neurons, a postsynaptic neuron spikes if it does not connect to an inhibitory presynaptic neuron, and every stimulus is represented by up to$d$spiking postsynaptic neurons. Our hypothesis is that the brain is organized to functionally satisfy the following six criteria: (i) decoding objective, i.e., there are up to$r-1\geq 0$additional spiking postsynaptic neurons in response to a stimulus along with the spiking postsynaptic neurons representing the stimulus, (ii) smoothness, i.e., similar stimuli are encoded similarly by the presynaptic neurons, (iii) optimal information transmission, i.e.,$t$is minimized, (iv) optimal energetic cost, i.e., only the$t$presynaptic neurons and the postsynaptic neurons representing a stimulus spike, (v) low-dimensional representation, i.e.,$d=o(n)$, and (vi) sparse coding, i.e.,$t=o(n)$. Our finding is that some criteria cause or correlate with others. Let the characteristic set of a postsynaptic neuron be the set of the presynaptic neurons it connects with. We prove that (i) holds if and only if the union of the$r$characteristic sets of any$r$postsynaptic neurons is not included in the union of the$d$characteristic sets of$d$other postsynaptic neurons. Consequently, (ii) is attained. More importantly, we suggest that the decoding objective (i) and optimal information transmission (iii) play a fundamental role in neural computation, while (v) and (vi) correlate to each other and correlate with (iii) and (iv), We examine our hypothesis by statistically testing functional connectivity network in human and the presynaptic-postsynaptic connectivity of a rat. The full version is available in [1].

Given$d$defective items in a population of$n$items with$d\ll n$, in threshold group testing without gap, the outcome of a test on a subset of items is positive if the subset has at least$u$defective items and negative otherwise, where$1 \leq u \leq d$. The basic goal of threshold group testing is to quickly identify the defective items via a small number of tests. In non-adaptive design, all tests are designed indepen-dently and can be performed in parallel. The decoding time in the non-adaptive state-of-the-art work is a polynomial of$(d/u)^{u}(d/(d-u))^{d-u}, d$, and$\log n$. In this work, we present a novel design that significantly reduces the number of tests and the decoding time to polynomials of$\min\{u^{u},\ (d-u)^{d-u}\}, d$, and$\log n$. In particular, when$u$is a constant, the number of tests and the decoding time are$O(d^{3}(\log^{2}n)\log(n/d))$and$O(d^{3}(\log^{A}n)\log(n/d)+d^{2}(\log n)\log^{3}(n/d))$, respectively. For a special case when$u=2$, with non-adaptive design, the number of tests and the decoding time are$O(d^{3}(\log n)\log(n/d))$and$O(d^{2}(\text{log} n+\log^{2}(n/d)))$, respectively. Moreover, with 2-stage design, the number of tests and the decoding time are$O(d^{2}\log^{2}(n/d))$. The full version is available at [1].

In this paper, we introduce a variation of the group testing problem capturing the idea that a positive test requires a combination of multiple “types” of items. Specifically, we assume that there are multiple disjointsemi-defective sets, and a test is positive if and only if it contains at least one item from each of these sets. The goal is to reliably identify all of the semi-defective sets using as few tests as possible, and we refer to this problem asConcomitant Group Testing(ConcGT). We derive a variety of algorithms for this task, focusing primarily on the case that there are two semi-defective sets. Our algorithms are distinguished by (i) whether they are deterministic (zero-error) or randomized (small-error), and (ii) whether they are non-adaptive, fully adaptive, or have limited adaptivity (namely, 2 or 3 stages). Both our deterministic adaptive algorithm and our randomized algorithms (non-adaptive or limited adaptivity) are order-optimal in broad scaling regimes of interest, and improve significantly over baseline results that are based on solving a more general problem as an intermediate step (e.g., hypergraph learning).

The main goal of group testing is to identify a small number of positive items among a large population of n items. In this work, we consider a new model of group testing in which the input items are linearly ordered, and the positives are subsets of small blocks (at unknown locations) of consecutive items over that order. When the number of blocks is at least one and at most k, and the number of items in a block is at most d, we show that there exists a deterministic and explicit design that can identify the positives with O(k2d log (n/d)) tests in O(poly(k, n/d)+kd) time. The number of tests in our proposed design is less than that of in standard combinatorial group testing by a factor of at least d/ log (kd). We also show that there exists a randomized design that can identify the positives with O(k(log (n/d)+d log k)) tests in O(k(log2(n/d)+k log k+d log k)) time with high probability.

The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items that returns positive if the subset contains at least one positive and negative otherwise. In non-adaptive group testing, all tests are independent, can be performed in parallel, and represented as a measurement matrix. In this work, we consider non-adaptive group testing with consecutive positives in which the items are linearly ordered and the positives are consecutive in that order. We present two algorithms for efficiently identifying consecutive positives. In particular, without storing measurement matrices, we can identify up to$d$consecutive positives with$2 \log_{2}\frac{\mathrm{n}}{d}+2d (4\log_{2}\frac{n}{d}+2d,\ resp.)$tests in$O(\log_{2}^{2}\frac{n}{d}+d)\ (O(\log_{2}\frac{n}{d}+d)$, resp.) time. These results significantly improve the state-of-the-art scheme in which it takes$5 \log_{2}\frac{n}{d} +2d+21$tests to identify the positives in$O(\frac{n}{d}\log_{2}\frac{n}{d}+d^{2})$time with the measurement matrices associated with the scheme stored somewhere.

The basic goal of threshold group testing is to identify up to$d$defective items among a population of$n$items, where$d$is usually much smaller than$n$. The outcome of a test on a subset of items is positive if the subset has at least$u$defective items, negative if it has up to$\ell $defective items, where$0 \leq \ell < u$, and arbitrary otherwise. This is called threshold group testing. The parameter$g = u - \ell - 1$is calledthe gap. In this paper, we focus on the case$g > 0$, i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case$g = 0$; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems.

The basic goal of threshold group testing is to identify up to d defective items among a population of n items (d≪n). The outcome of a test on a subset of the items is positive if the subset has at least u defective items, negative if it has up to ℓ defective items, where 0≤ ℓ <; u, and arbitrary otherwise. There are a few reported studies on test designs and decoding algorithms for identifying defective items. Most of the approaches in previous studies have not been feasible, because their problems settings have numerous constraints or the decoding complexities of their proposed schemes are relatively large.This paper makes four contributions. The first is a corrected theorem for a non-adaptive algorithm proposed by Chen and Fu for threshold group testing. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing. Specifically, we present a better upper bound on the number of tests for disjunct matrices as compared to previous work. The last two contributions include a reduction in the number of tests and a reduction in the decoding time for deterministically identifying defective items in a noisy setting on test outcomes. A full version of this paper is accessible at: https://arxiv.org/abs/2001.01008.

We consider non-adaptive threshold group testing for identification of up to d defective items in a set of n items, where a test is positive if it contains at least 2 ≤ u ≤ d defective items, and negative otherwise. The defective items can be identified using t = O ((d/u)u(d/d-u)d-u(u log d/u + log 1/∈)·d2log n) tests with probability at least 1 - ∈ for any ∈ > 0 or t = O((d/u)u(d/d-u)d-ud3log n · log d/n) tests with probability 1. The decoding time is t × poly(d2log n). This result significantly improves the best known results for decoding non-adaptive threshold group testing: O(n log n + n log 1/∈) for probabilistic decoding, where ∈ > 0, and O(nulog n) for deterministic decoding.

We consider non-adaptive threshold group testing for identification of up to d defective items in a set of n items, where a test is positive if it contains at least 2 ≤ u ≤ d defective items, and negative otherwise. The defective items can be identified using t=O(( [d/u])u([d/(d-u)])d-u(ulog[d/u]+log[1/(ε)])d2logn) tests with probability at least 1-ε for any or t = O(([b/u])u([d/(d-u)])d-u·d3logn ·log[n/d]) tests with probability 1. The decoding time is t× poly (d2logn). This result significantly improves the best known results for decoding non-adaptive threshold group testing: O(n logn+nlog[1/(ε)]) for probabilistic decoding, where , and O(nulogn) for deterministic decoding.

Wireless Sensor Networks (WSNs) are being used more and more and are becoming a key technology in applications ranging from military ones to ones used in daily life. There are basic architectures: one comprising sensors and a server and one comprising sensors, a server, and storage nodes between them ("two-tiered architecture"). We investigate this second type as it has many advantages in terms of energy usage, computation, and data transmission. Although two-tiered wireless sensor networks have many advantages, security is a critical due to three main problems. First, sensors located in hostile areas can be surreptitiously replaced with fake ones that send bogus data. Second, an attacker could install new sensors with valid authentication keys that send bogus data to storage nodes and deceive the server. Third, a storage nodes could be compromised and reveal data received from sensors. Therefore, the server must authenticate sensors before accepting data from them, detect whether a key was intercepted and identify which one, and handle the most common queries while preserving the privacy of data received from storage nodes. W have developed a novel solution using Non-Adaptive Group Testing that enables a server to perform these tasks efficiently and effectively. This solution is secure with high probability against an attack that tries to guess sensor data and thus protects data confidentiality.