Search

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform distribution, which strengthens the Ω( n) bound recently shown by Kerenidis et al. (), and answers an open problem from Chakrabarti et al. (). In our second result we prove that the information cost of I P is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω( n) lower bound recently proved by Braverman and Weinstein (Electronic Colloquium on Computational Complexity (ECCC) 18, 164 ). Our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past (Chakrabarti et al. ; Bar-Yossef et al. J. Comput. Syst. Sci. 68(4), 702-732 ; Barak et al. ) used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner. [ABSTRACT FROM AUTHOR]

This paper describes a procedure that computes seeds for LFSR-based generation of partially-functional broadside tests. Existing LFSR-based test data compression methods compute seeds based on incompletely-specified test cubes. Functional broadside tests are fully-specified, and they have fully-specified scan-in states. This is the main challenge that the test generation procedure described in this paper needs to address. It addresses it by using a process that modifies an initial seed si in order to reduce the Hamming distance between the scan-in state pi that si creates and a reachable state rj . When the Hamming distance is reduced to zero, the seed can be used for generating functional broadside tests. When the distance is larger than zero, the tests are partially-functional. Experimental results are presented for transition faults in benchmark circuits to demonstrate the resulting distances and fault coverage. [ABSTRACT FROM AUTHOR]

In computer science, approximate string matching is the technique of finding strings that match a pattern approximately (rather than exactly). Most often when we need to match a pattern exact matching is not possible, due to insufficient data, broken data, or other such reasons. So we try to find a close match instead of an exact match. And for this we need to find the distance between two strings. We have different approaches for the same such as edit distance in the form of Hamming distance, Levenshstien distance, Dameru-Levenshstein distance, Jaro-Winkler distance and Longest Common Subsequence (LCS). Different algorithms have been made for these different approaches, and we will try to analyze some of these algorithms. [ABSTRACT FROM AUTHOR]

Previous interleavers designed for Serially Concatenated Codes (SCCs) have achieved a limited Minimum Hamming Distance (MHD) between the legitimate permutations of the encoded bit sequence. Hence, we propose a novel Evolutionary Algorithm (EA) capable of designing improved interleavers for SCCs, without artificially limiting the achievable MHD. As a result, increased MHDs and therefore reduced error floors are achieved, even if only a modest EA complexity can be afforded. [ABSTRACT FROM PUBLISHER]