The Experts below are selected from a list of 96 Experts worldwide ranked by ideXlab platform
Jesper Nederlof - One of the best experts on this subject based on the ideXlab platform.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
IEEE Transactions on Information Theory, 2018Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets of 0–1 vectors of fixed length form a Uniquely deCodeable Code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
International Symposium on Information Theory, 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets A, B ⊆ {0, 1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a ∈ A, b ∈ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1−e)n and |B| = 2βn, satisfies equation. For sufficiently small e, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop ′98] and Ordentlich and Shayevitz [2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as e approaches 0.
-
ISIT - Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs
2016 IEEE International Symposium on Information Theory (ISIT), 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets A, B ⊆ {0, 1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a ∈ A, b ∈ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1−e)n and |B| = 2βn, satisfies equation. For sufficiently small e, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop ′98] and Ordentlich and Shayevitz [2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as e approaches 0.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
arXiv: Information Theory, 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets $A, B \subseteq \{0, 1\}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $a \in A$, $b \in B$ yields a distinct sum $a+b$, where the addition is over $\mathbb{Z}^n$. We show that every UDCP $A, B$, with $|A| = 2^{(1-\epsilon)n}$ and $|B| = 2^{\beta n}$, satisfies $\beta \leq 0.4228 +\sqrt{\epsilon}$. For sufficiently small $\epsilon$, this bound significantly improves previous bounds by Urbanke and Li~[Information Theory Workshop '98] and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound $\beta$ by $0.4921$ and $0.4798$, respectively, as $\epsilon$ approaches $0$.
-
STACS - Dense Subset Sum may be the hardest
2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^{n/2})-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^{(0.5-delta)*n})-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta = 2^{0.661n}. Consequently, we also obtain a characterization in terms of the popular density parameter n/log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
Dimitris A Pados - One of the best experts on this subject based on the ideXlab platform.
-
Uniquely Decodable Code division via augmented sylvester hadamard matrices
Wireless Communications and Networking Conference, 2012Co-Authors: Michel Kulhandjian, Dimitris A PadosAbstract:We consider the problem of designing binary antipodal Uniquely Decodable (errorless) Code sets for overloaded Code-division multiplexing applications where the number of signals K is larger than the Code length L. Our proposed errorless Code set design aims at identifying the maximum number of columns that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. In particular, we derive formally the maximum number of columns that may be appended to the Sylvester-Hadamard matrix of order L = 8 and use this result as a seed to produce an infinite sequence of designs in increasing L. In the noiseless transmission case, a simple algorithm is developed to Uniquely deCode all signals. In additive white Gaussian noise (AWGN), a slab-sphere decoding scheme can be utilized for efficient and effective decoding.
-
WCNC - Uniquely Decodable Code-division via augmented Sylvester-Hadamard matrices
2012 IEEE Wireless Communications and Networking Conference (WCNC), 2012Co-Authors: Michel Kulhandjian, Dimitris A PadosAbstract:We consider the problem of designing binary antipodal Uniquely Decodable (errorless) Code sets for overloaded Code-division multiplexing applications where the number of signals K is larger than the Code length L. Our proposed errorless Code set design aims at identifying the maximum number of columns that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. In particular, we derive formally the maximum number of columns that may be appended to the Sylvester-Hadamard matrix of order L = 8 and use this result as a seed to produce an infinite sequence of designs in increasing L. In the noiseless transmission case, a simple algorithm is developed to Uniquely deCode all signals. In additive white Gaussian noise (AWGN), a slab-sphere decoding scheme can be utilized for efficient and effective decoding.
-
Uniquely Decodable Code division and low complexity receivers for advanced signal design multiplexing and multiple access communications
Dissertations & Theses @ SUNY Buffalo ProQuest Dissertations & Theses Global, 2012Co-Authors: Dimitris A Pados, Michel KulhandjianAbstract:In the last decade, wireless communication service has experienced explosive growth while communication technologies have progressed generation by generation. Code-division multiplexing (CDM) or Code-division multiple-access (CDMA) is seen as a promising basic technology for 3G/4G cellular communications networks. In such rapidly growing communication systems in which higher number of users share the same channel becomes very challenging problem since it introduces multiple-access interference (MAI). In this dissertation, we investigate the overloaded Code-division multiplexing where the number of multiplexed signals exceeds the Code (signature) length L. We propose overloaded Code design framework where Code set satisfy "errorless" (Uniquely decodability) property in noiseless multiplexed transmission. In this proposed framework we aim to identify the maximum number of Codes/signatures that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. We derive formally the maximum number of columns that may be augmented to the Sylverster-Hadamard matrix of order L = 8. It is known that there is no close form formula to identify the maximum number of users K for a any given signature length L. In such system low-complexity multiuser detection techniques are essential. In the noiseless case, we develop a simple algorithm to Uniquely deCode all signals. To tackle this problem we propose conditional hierarchical criteria for the Code (signature) design framework where a simplified maximum-likelihood (SML) detection scheme can be utilized to make CDM systems practically implementable. In the second part of this work, the problem of list decoding of Reed Solomon Codes over the phased burst channels is investigated. We present evidence that the algorithm development by Guruswami and Rudra can also give improvement for more "irregular" burst errors. Specifically, we present simulation results where such soft decoding of Reed-Solomon Codes outperforms existing soft decoding algorithms proposed by Koetter and Vardy and, more recently, Das and Vardy on Gilbert-Elliott channels. We also present a theoretical result that for certain Gilbert-Elliott channels, with high probability over the errors, the output list size for list decoding Reed-Solomon Codes is one. Finally, in the third part of this work, we focus on steganalysis, which is the countermeasure of steganography. We propose a passive spread-spectrum steganalysis algorithm to decide the presence or absence of spread-spectrum hidden data in a given image (a binary hypothesis testing problem). Unlike conventional feature-based approaches, we develop an unsupervised (blind) low-complexity approach based on generalized least-squares principles that may enable rapid high-volume image processing. We also consider the problem of blindly extracting data embedded over a wide band in a spectrum (transform) domain of a digital medium (image, audio, video). We first develop a multi-signature iterative generalized least-squares (MIGLS) core procedure to seek unknown data hidden in hosts via multi-signature direct-sequence spread-spectrum embedding. Neither the original host nor the embedding signatures are assumed available. Then, cross-correlation enhanced M-IGLS (CCM-IGLS), a procedure based on statistical analysis of repeated independent M-IGLS processing of the host, is seen to offer most effective hidden message recovery.
Per Austrin - One of the best experts on this subject based on the ideXlab platform.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
IEEE Transactions on Information Theory, 2018Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets of 0–1 vectors of fixed length form a Uniquely deCodeable Code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
International Symposium on Information Theory, 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets A, B ⊆ {0, 1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a ∈ A, b ∈ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1−e)n and |B| = 2βn, satisfies equation. For sufficiently small e, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop ′98] and Ordentlich and Shayevitz [2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as e approaches 0.
-
ISIT - Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs
2016 IEEE International Symposium on Information Theory (ISIT), 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets A, B ⊆ {0, 1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a ∈ A, b ∈ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1−e)n and |B| = 2βn, satisfies equation. For sufficiently small e, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop ′98] and Ordentlich and Shayevitz [2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as e approaches 0.
-
sharper upper bounds for unbalanced Uniquely Decodable Code pairs
arXiv: Information Theory, 2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:Two sets $A, B \subseteq \{0, 1\}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $a \in A$, $b \in B$ yields a distinct sum $a+b$, where the addition is over $\mathbb{Z}^n$. We show that every UDCP $A, B$, with $|A| = 2^{(1-\epsilon)n}$ and $|B| = 2^{\beta n}$, satisfies $\beta \leq 0.4228 +\sqrt{\epsilon}$. For sufficiently small $\epsilon$, this bound significantly improves previous bounds by Urbanke and Li~[Information Theory Workshop '98] and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound $\beta$ by $0.4921$ and $0.4798$, respectively, as $\epsilon$ approaches $0$.
-
STACS - Dense Subset Sum may be the hardest
2016Co-Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, Jesper NederlofAbstract:The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^{n/2})-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^{(0.5-delta)*n})-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta = 2^{0.661n}. Consequently, we also obtain a characterization in terms of the popular density parameter n/log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
Yoichiro Watanabe - One of the best experts on this subject based on the ideXlab platform.
-
Uniquely Decodable Code for three user binary adder channel
International Symposium on Information Theory and its Applications, 1994Co-Authors: Yoichiro WatanabeAbstract:A Uniquely Decodable Code (C1,C2,C3) is investigated for the three-user binary adder channel. The Uniquely Decodable Code is constructed as follows: If C1 is a (n. k) linear Code with a generator matrix, C2 is a coset of C1 and C3 is a set of all coset leaders, then the Code (C1,C2,C3) is Uniquely Decodable and its total rate is equal to 1+k/n. An easy decoding rule for those Codes is also presented.
Michel Kulhandjian - One of the best experts on this subject based on the ideXlab platform.
-
Uniquely Decodable Code division via augmented sylvester hadamard matrices
Wireless Communications and Networking Conference, 2012Co-Authors: Michel Kulhandjian, Dimitris A PadosAbstract:We consider the problem of designing binary antipodal Uniquely Decodable (errorless) Code sets for overloaded Code-division multiplexing applications where the number of signals K is larger than the Code length L. Our proposed errorless Code set design aims at identifying the maximum number of columns that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. In particular, we derive formally the maximum number of columns that may be appended to the Sylvester-Hadamard matrix of order L = 8 and use this result as a seed to produce an infinite sequence of designs in increasing L. In the noiseless transmission case, a simple algorithm is developed to Uniquely deCode all signals. In additive white Gaussian noise (AWGN), a slab-sphere decoding scheme can be utilized for efficient and effective decoding.
-
WCNC - Uniquely Decodable Code-division via augmented Sylvester-Hadamard matrices
2012 IEEE Wireless Communications and Networking Conference (WCNC), 2012Co-Authors: Michel Kulhandjian, Dimitris A PadosAbstract:We consider the problem of designing binary antipodal Uniquely Decodable (errorless) Code sets for overloaded Code-division multiplexing applications where the number of signals K is larger than the Code length L. Our proposed errorless Code set design aims at identifying the maximum number of columns that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. In particular, we derive formally the maximum number of columns that may be appended to the Sylvester-Hadamard matrix of order L = 8 and use this result as a seed to produce an infinite sequence of designs in increasing L. In the noiseless transmission case, a simple algorithm is developed to Uniquely deCode all signals. In additive white Gaussian noise (AWGN), a slab-sphere decoding scheme can be utilized for efficient and effective decoding.
-
Uniquely Decodable Code division and low complexity receivers for advanced signal design multiplexing and multiple access communications
Dissertations & Theses @ SUNY Buffalo ProQuest Dissertations & Theses Global, 2012Co-Authors: Dimitris A Pados, Michel KulhandjianAbstract:In the last decade, wireless communication service has experienced explosive growth while communication technologies have progressed generation by generation. Code-division multiplexing (CDM) or Code-division multiple-access (CDMA) is seen as a promising basic technology for 3G/4G cellular communications networks. In such rapidly growing communication systems in which higher number of users share the same channel becomes very challenging problem since it introduces multiple-access interference (MAI). In this dissertation, we investigate the overloaded Code-division multiplexing where the number of multiplexed signals exceeds the Code (signature) length L. We propose overloaded Code design framework where Code set satisfy "errorless" (Uniquely decodability) property in noiseless multiplexed transmission. In this proposed framework we aim to identify the maximum number of Codes/signatures that can be potentially appended to a Sylvester-Hadamard matrix of order L, while maintaining the errorless Code property. We derive formally the maximum number of columns that may be augmented to the Sylverster-Hadamard matrix of order L = 8. It is known that there is no close form formula to identify the maximum number of users K for a any given signature length L. In such system low-complexity multiuser detection techniques are essential. In the noiseless case, we develop a simple algorithm to Uniquely deCode all signals. To tackle this problem we propose conditional hierarchical criteria for the Code (signature) design framework where a simplified maximum-likelihood (SML) detection scheme can be utilized to make CDM systems practically implementable. In the second part of this work, the problem of list decoding of Reed Solomon Codes over the phased burst channels is investigated. We present evidence that the algorithm development by Guruswami and Rudra can also give improvement for more "irregular" burst errors. Specifically, we present simulation results where such soft decoding of Reed-Solomon Codes outperforms existing soft decoding algorithms proposed by Koetter and Vardy and, more recently, Das and Vardy on Gilbert-Elliott channels. We also present a theoretical result that for certain Gilbert-Elliott channels, with high probability over the errors, the output list size for list decoding Reed-Solomon Codes is one. Finally, in the third part of this work, we focus on steganalysis, which is the countermeasure of steganography. We propose a passive spread-spectrum steganalysis algorithm to decide the presence or absence of spread-spectrum hidden data in a given image (a binary hypothesis testing problem). Unlike conventional feature-based approaches, we develop an unsupervised (blind) low-complexity approach based on generalized least-squares principles that may enable rapid high-volume image processing. We also consider the problem of blindly extracting data embedded over a wide band in a spectrum (transform) domain of a digital medium (image, audio, video). We first develop a multi-signature iterative generalized least-squares (MIGLS) core procedure to seek unknown data hidden in hosts via multi-signature direct-sequence spread-spectrum embedding. Neither the original host nor the embedding signatures are assumed available. Then, cross-correlation enhanced M-IGLS (CCM-IGLS), a procedure based on statistical analysis of repeated independent M-IGLS processing of the host, is seen to offer most effective hidden message recovery.
