BZPEER

preprint2016arXiv

A simple construction of cover-free $(s,\ell)$ -code with certain constant weight

We give a method of constructing a cover-free $(s, \ell)$ -code. For $k > s$ , our construction yields a ${{n \choose s} \choose \ell}\times {n \choose k}$ cover-free $(s, \ell)$ -code with a constant column weight.

preprint2016arXiv

Adaptive Learning a Hidden Hypergraph

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $\mathcal{F}(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$ , the number of edges $|E|\le s$ , $s\ll t$ , and the cardinality of any edge $|e|\le\ell$ , $\ell\ll t$ . Our goal is to identify all edges of $H_{un}\in \mathcal{F}(t,s,\ell)$ by using the minimal number of tests. We provide an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$ .

preprint2016arXiv

On a Hypergraph Approach to Multistage Group Testing Problems

Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$ . In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case $s=2$ , we design an explicit construction, which makes use of $2\log_2t(1+o(1))$ tests in the worst case and consists of $4$ stages.

preprint2016arXiv

On a Hypergraph Approach to Multistage Group Testing Problems

Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\ldots,t\}$ by carrying out tests on properly chosen subsets of $[t]$ . In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case $s=2$ , we design an explicit construction, which makes use of $2\log_2t(1+o(1))$ tests in the worst case and consists of $4$ stages. For the general case $s>2$ , we provide an explicit construction, which uses $(2s-1)\log_2t(1+o(1))$ tests and consists of $2s-1$ rounds.

preprint2016arXiv

On Multistage Learning a Hidden Hypergraph

Learning a hidden hypergraph is a natural generalization of the classical group testing problem that consists in detecting unknown hypergraph $H_{un}=H(V,E)$ by carrying out edge-detecting tests. In the given paper we focus our attention only on a specific family $F(t,s,\ell)$ of localized hypergraphs for which the total number of vertices $|V| = t$ , the number of edges $|E|\le s$ , $s\ll t$ , and the cardinality of any edge $|e|\le\ell$ , $\ell\ll t$ . Our goal is to identify all edges of $H_{un}\in F(t,s,\ell)$ by using the minimal number of tests. We develop an adaptive algorithm that matches the information theory bound, i.e., the total number of tests of the algorithm in the worst case is at most $s\ell\log_2 t(1+o(1))$ . We also discuss a probabilistic generalization of the problem.

preprint2016arXiv

Threshold Decoding for Disjunctive Group Testing

Let $1 \le s < t$ , $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$ -active, $\; s \ll t$ , and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$ -defective and should be replaced by a similar $s$ -active circuit. Suppose that there exists a possibility to run $N$ non-adaptive group tests to check the $s$ -activity of the circuit. As usual, we say that a (disjunctive) group test yields the positive response if the group contains at least one defective element. Along with the conventional decoding algorithm based on disjunctive $s$ -codes, we consider a threshold decision rule with the minimal possible decoding complexity, which is based on the simple comparison of a fixed threshold $T$ , $1 \le T \le N - 1$ , with the number of positive responses $p$ , $0 \le p \le N$ . For the both of decoding algorithms we discuss upper bounds on the $α$ -level of significance of the statistical test for the null hypothesis $\left\{ H_0 \,:\, \text{the circuit is $s$-active} \right\}$ verse the alternative hypothesis $\left\{ H_1 \,:\, \text{the circuit is $s$-defective} \right\}$.

preprint2016arXiv

Threshold Disjunctive Codes

Let $1 \le s < t$ , $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$ -active, $\; s \ll t$ , and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$ -defective and should be substituted for the similar $s$ -active circuit. Suppose that there exists a possibility to check the $s$ -activity of the circuit using $N$ non-adaptive group tests identified by a conventional disjunctive $s$ -code $X$ of size~ $t$ and length~ $N$ . As usually, we say that any group test yields the positive response if the group contains at least one defective element. In this case, there is no any interest to look for the defective elements. We need to decide on the number of the defective elements in the circuit without knowing the code~ $X$ . In addition, the decision has the minimal possible complexity because it is based on the simple comparison of a fixed threshold $T$ , $0 \le T \le N - 1$ , with the number of positive responses $p$ , $0 \le p \le N$ , obtained after carrying out $N$ non-adaptive tests prescribed by the disjunctive $s$ -code~ $X$ . For the introduced group testing problem, a new class of the well-known disjunctive $s$ -codes called the threshold disjunctive $s$ -codes is defined. The aim of our paper is to discuss both some constructions of suboptimal threshold disjunctive $s$ -codes and the best random coding bounds on the rate of threshold disjunctive $s$ -codes.

preprint2014arXiv

Almost Disjunctive List-Decoding Codes

A binary code is said to be a disjunctive list-decoding $s_L$ -code, $s\ge1$ , $L\ge1$ , (briefly, LD $s_L$ -code) if the code is identified by the incidence matrix of a family of finite sets in which the union of any $s$ sets can cover not more than $L-1$ other sets of the family. In this paper, we introduce a natural {\em probabilistic} generalization of LD $s_L$ -code when the code is said to be an almost disjunctive LD $s_L$ -code if the unions of {\em almost all} $s$ sets satisfy the given condition. We develop a random coding method based on the ensemble of binary constant-weight codes to obtain lower bounds on the capacity and error probability exponent of such codes. For the considered ensemble our lower bounds are asymptotically tight.

V. Yu. Shchukin

Research overview

Is this your work?

8 publications

A simple construction of cover-free $(s,\ell)$ -code with certain constant weight

Adaptive Learning a Hidden Hypergraph

On a Hypergraph Approach to Multistage Group Testing Problems

On a Hypergraph Approach to Multistage Group Testing Problems

On Multistage Learning a Hidden Hypergraph

Threshold Decoding for Disjunctive Group Testing

Threshold Disjunctive Codes

Almost Disjunctive List-Decoding Codes

See the researcher in context

Building this map preview

V. Yu. Shchukin

Research overview

Is this your work?

8 publications

A simple construction of cover-free (s,ℓ)(s,\ell)(s,ℓ)-code with certain constant weight

Adaptive Learning a Hidden Hypergraph

On a Hypergraph Approach to Multistage Group Testing Problems

On a Hypergraph Approach to Multistage Group Testing Problems

On Multistage Learning a Hidden Hypergraph

Threshold Decoding for Disjunctive Group Testing

Threshold Disjunctive Codes

Almost Disjunctive List-Decoding Codes

See the researcher in context

Building this map preview

A simple construction of cover-free $(s,\ell)$ -code with certain constant weight