Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be d...
详细信息
ISBN:
(纸本)9783959770408
Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their non-adaptive counterparts, in which all queries are independent of answers obtained from previous *** this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of "rounds of adaptivity" it uses. More accurately, we say that a tester is k-(round) adaptive if it makes queries in k + 1 rounds, where the queries in the i'th round may depend on the answers obtained in the previous i − 1 rounds. Then, we ask the following question:Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity?We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n ε N and 0 ≤ k ≤ n0.99 there exists a property Pn,k of functions for which (1) there exists a k-adaptive tester for Pn,k with query complexity Õ(k), yet (2) any (k − 1)-adaptive tester for Pn,k must make Ω(n) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resi...
详细信息
ISBN:
(纸本)9783959771160
We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in *** our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.
Forward error correction technique based on the optimization procedures for multithreshold decoding algorithms is *** advances as well as new opportunities of the multithreshold decoders for use in the systems working...
详细信息
Forward error correction technique based on the optimization procedures for multithreshold decoding algorithms is *** advances as well as new opportunities of the multithreshold decoders for use in the systems working at the Shannon's limit are *** of the multithreshold decoders for self-orthogonal binary and non-binary codes over Gaussian channels are *** results of BER performance of proposed decoder is shown to be close to the results provided by optimum total search methods.
Adaptive codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been introduced in [6] as a new class of non-standard var...
详细信息
ISBN:
(纸本)9781595931702
Adaptive codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been introduced in [6] as a new class of non-standard variable-length codes. New algorithms for data compression, based on adaptive codes of order one and Huffman codes, have been presented in [7], where we have behaviorally shown that for a large class of input data strings, these algorithms substantially outperform the Lempel-Ziv universal data compression algorithm [12]. EAH has been introduced in [8], as an improved generalization of these algorithms. In this paper, we introduce Meta-EAH, an adaptive version of the EAH algorithm. Some comparisons between Meta-EAH and the Lempel-Ziv universal data compression algorithm are reported.
Summary: Voices or faces that fall outside of the norm are the memorable ones. Recent human neuroimaging work, however, indicates that the average voice holds considerable currency for neuronal coding. The study also ...
详细信息
Summary: Voices or faces that fall outside of the norm are the memorable ones. Recent human neuroimaging work, however, indicates that the average voice holds considerable currency for neuronal coding. The study also forges a bridge with the face recognition literature. [ABSTRACT FROM AUTHOR]
Secret image sharing is a useful way to protect a secret image by sharing it to several shadow *** proposed scheme is an improvement of the secret image sharing method,in order to prevent the shadow images from reveal...
详细信息
Secret image sharing is a useful way to protect a secret image by sharing it to several shadow *** proposed scheme is an improvement of the secret image sharing method,in order to prevent the shadow images from revealing the shape of the original secret *** the reason that the adjacent pixels of an image is highly close,the shadow images,the result of the general image sharing process,always give out the shape information of the secret which can be the main target of *** improved method to solve this problem is using a function,also called the key,to permute the pixels of the original image before sharing process,but the custody of the key brings new *** proposed scheme offers a special method to generate the key using the secret image itself,so there is no need to safeguard the key.
This paper will focus on the construction of superimposed codes using incidence matrices. Such constructions require a set of elements and a partial order defined on the set. We will define a partial order on partitio...
详细信息
This paper will focus on the construction of superimposed codes using incidence matrices. Such constructions require a set of elements and a partial order defined on the set. We will define a partial order on partitions. The construction will be made using elements from the partially ordered set of partitions of n elements. (C) 2005 Elsevier Ltd. All rights reserved.
暂无评论