BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
I. V. Vorobyev appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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.
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))$.
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.
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.
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.
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\}$.
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.
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.