Aaltodoc Repository :: Browsing by Department "Algebra and Discrete Mathematics"

Browsing by Department "Algebra and Discrete Mathematics"

Now showing 1 - 20 of 39

Analog Secure Distributed Matrix Multiplication over Complex Numbers
(2022) Makkonen, Okko; Hollanti, Camilla; Algebra and Discrete Mathematics; Department of Mathematics and Systems Analysis
This work considers the problem of distributing matrix multiplication over the real or complex numbers to helper servers, such that the information leakage to these servers is close to being information-theoretically secure. These servers are assumed to be honest-but-curious, i.e., they work according to the protocol, but try to deduce information about the data. The problem of secure distributed matrix multiplication (SDMM) has been considered in the context of matrix multiplication over finite fields, which is not always feasible in real world applications. We present two schemes, which allow for variable degree of security based on the use case and allow for colluding and straggling servers. We analyze the security and the numerical accuracy of the schemes and observe a trade-off between accuracy and security.
Applications of polymatroid theory to distributed storage systems
(2016-04-04) Westerbäck, Thomas; Freij-Hollanti, Ragnar; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Communications Theory; Algebra and Discrete Mathematics; Department of Communications and Networking
In this paper, a link between polymatroid theory and locally repairable codes (LRCs) is established. The codes considered here are completely general in that they are subsets of An, where A is an arbitrary finite set. Three classes of LRCs are considered, both with and without availability, and for both information-symbol and all-symbol locality. The parameters and classes of LRCs are generalized to polymatroids, and a generalized Singelton bound on the parameters for these three classes of polymatroids and LRCs is given. This result generalizes the earlier Singleton-type bounds given for LRCs. Codes achieving these bounds are coined perfect, as opposed to the more common term optimal used earlier, since they might not always exist. Finally, new constructions of perfect linear LRCs are derived from gammoids, which are a special class of matroids. Matroids, for their part, form a subclass of polymatroids and have proven useful in analyzing and constructing linear LRCs.
An approximation of theta functions with applications to communications
(Society for Industrial and Applied Mathematics (SIAM), 2020) Barreal, Amaro; Damir, Mohamed Taoufiq; Freij-Hollanti, Ragnar; Hollanti, Camilla; Coop IT Digital Analytics and AI; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics
Computing the theta series of an arbitrary lattice, and more specifically a related quantity known as the flatness factor, has been recently shown to be important for lattice code design in various wireless communication setups. However, the theta series is in general not known in closed form, excluding a small set of very special lattices. In this article, motivated by the practical applications as well as the mathematical problem itself, a simple approximation of the theta series of a lattice is derived. A rigorous analysis of its accuracy is provided. In relation to this, maximum-likelihood decoding in the context of compute-and-forward relaying is studied. Following previous work, it is shown that the related metric can exhibit a flat behavior, which can be characterized by the flatness factor of the decoding function. Contrary to common belief, we note that the decoding metric can be rewritten as a sum over a random lattice only when at most two sources are considered. Using a particular matrix decomposition, a link between the random lattice and the code lattice employed at the transmitter is established, which leads to an explicit criterion for code design, in contrast to implicit criteria derived previously. Finally, candidate lattices are examined with respect to the proposed criterion using the derived theta series approximation.
Bounds on Binary Locally Repairable Codes Tolerating Multiple Erasures
(2018-02-21) Grezet, Matthias; Freij-Hollanti, Ragnar; Westerbäck, Thomas; Olmez, Oktay; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Technische Universität München; Ankara University; Algebra and Discrete Mathematics; Lapidoth, Amos; Moser, Stefan M.
Recently, locally repairable codes have gained significant interest for their potential applications in distributed storage systems. However, most constructions in existence are over fields with size that grows with the number of servers, which makes the systems computationally expensive and difficult to maintain. Here, we study linear locally repairable codes over the binary field, tolerating multiple local erasures. We derive bounds on the minimum distance on such codes, and give examples of LRCs achieving these bounds. Our main technical tools come from matroid theory, and as a byproduct of our proofs, we show that the lattice of cyclic flats of a simple binary matroid is atomic.
Bounds on the maximal minimum distance of linear locally repairable codes
(IEEE, 2016-08-10) Pöllänen, Antti; Westerbäck, Thomas; Freij-Hollanti, Ragnar; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Communications Theory; Algebra and Discrete Mathematics; Department of Communications and Networking
Locally repairable codes (LRCs) are error correcting codes used in distributed data storage. Besides a global level, they enable errors to be corrected locally, reducing the need for communication between storage nodes. There is a close connection between almost affine LRCs and matroid theory which can be utilized to construct good LRCs and derive bounds on their performance. A generalized Singleton bound for linear LRCs with parameters (n; k; d; r; δ) was given in [N. Prakash et al., 'Optimal Linear Codes with a Local-Error-Correction Property', IEEE Int. Symp. Inf. Theory]. In this paper, a LRC achieving this bound is called perfect. Results on the existence and nonexistence of linear perfect (n; k; d; r; δ)-LRCs were given in [W. Song et al., 'Optimal locally repairable codes', IEEE J. Sel. Areas Comm.]. Using matroid theory, these existence and nonexistence results were later strengthened in [T. Westerbäck et al., 'On the Combinatorics of Locally Repairable Codes', Arxiv: 1501.00153], which also provided a general lower bound on the maximal achievable minimum distance dmax(n; k; r; δ) that a linear LRC with parameters (n; k; r; δ) can have. This article expands the class of parameters (n; k; d; r; δ) for which there exist perfect linear LRCs and improves the lower bound for dmax(n; k; r; δ). Further, this bound is proved to be optimal for the class of matroids that is used to derive the existence bounds of linear LRCs.
Capacity and security of heterogeneous distributed storage systems
(2013) Ernvall, Toni; El Rouayheb, Salim; Hollanti, Camilla; Poor, Vincent; University of Turku; Algebra and Discrete Mathematics; Department of Mathematics and Systems Analysis
Coded Caching Clusters with Device-to-Device Communications
(2019-02-01) Paakkonen, Joonas; Barreal, Amaro; Hollanti, Camilla; Tirkkonen, Olav; Department of Communications and Networking; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics; Communications Theory
We consider a geographically constrained caching community where popular data files are cached on mobile terminals and distributed through Device-to-Device (D2D) communications. To ensure availability, data files are protected against user mobility, or churn, with select caching and erasure coding methods. Communication and storage costs are considered, with an objective of minimizing the consumption of radio resources, given an available storage size. We focus on finding the coding method that minimizes the overall cost. Closed-form expressions for the expected consumption of radio resources incurred by data delivery and redundancy maintenance are derived. Closed form transmission costs in a circular caching community with a specific node density and caching method are calculated, when cost obeys a power law of distance. Our results are illustrated by numerical examples and verified by extensive computer simulations.
A comparison of skewed and orthogonal lattices in Gaussian wiretap channels
(2015-06-24) Karrila, Alex; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics
We consider lattice coset-coded transmissions over a wiretap channel with additive white Gaussian noise (AWGN). Examining a function that can be interpreted as either the legitimate receiver's error probability or the eavesdropper's correct decision probability, we rigorously show that, albeit offering simple bit labeling, orthogonal nested lattices are suboptimal for coset coding in terms of both the legitimate receiver's and the eavesdropper's probabilities.
The complete hierarchical locality of the punctured Simplex code
(Springer Netherlands, 2021-01) Grezet, Matthias; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics
This paper presents a new alphabet-dependent bound for codes with hierarchical locality. Then, the complete list of possible localities is derived for a class of codes obtained by deleting specific columns from a Simplex code. This list is used to show that these codes are optimal codes with hierarchical locality.
The Complete Hierarchical Locality of the Punctured Simplex Code
(IEEE, 2019) Grezet, Matthias; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics
This paper presents a new alphabet-dependent bound for codes with hierarchical locality. Then, the complete list of possible localities is derived for a class of codes obtained by deleting specific columns from a Simplex code. This list is used to show that these codes are optimal codes with hierarchical locality.
Computational Code-Based Single-Server Private Information Retrieval
(IEEE, 2020-06) Holzbaur, Lukas; Hollanti, Camilla; Wachter-Zeh, Antonia; Technical University of Munich; Algebra and Discrete Mathematics; Department of Mathematics and Systems Analysis
A new computational private information retrieval (PIR) scheme based on random linear codes is presented. A matrix of messages from a McEliece scheme is used to query the server with carefully chosen errors. The server responds with the sum of the scalar multiple of the rows of the query matrix and the files. The user recovers the desired file by erasure decoding the response. Contrary to code-based cryptographic systems, the scheme presented here enables to use truly random codes, not only codes disguised as such. Further, we show the relation to the so-called error subspace search problem and quotient error search problem, which we assume to be difficult, and show that the scheme is secure against attacks based on solving these problems.
A connection between locally repairable codes and exact regenerating codes
(IEEE, 2016-08-10) Ernvall, Toni; Westerbäck, Thomas; Freij-Hollanti, Ragnar; Hollanti, Camilla; University of Turku; Department of Mathematics and Systems Analysis; Communications Theory; Algebra and Discrete Mathematics; Department of Communications and Networking
Typically, locally repairable codes (LRCs) and regenerating codes have been studied independently of each other, and it has not been clear how the parameters of one relate to those of the other. In this paper, a novel connection between locally repairable codes and exact regenerating codes is established. Via this connection, locally repairable codes are interpreted as exact regenerating codes. Further, some of these codes are shown to perform better than time-sharing codes between minimum bandwidth regenerating and minimum storage regenerating codes.
Constructions and Properties of Linear Locally Repairable Codes
(2016-03) Ernvall, Toni; Westerbäck, Thomas; Freij-Hollanti, Ragnar; Hollanti, Camilla; Department of Mathematics and Systems Analysis; Communications Theory; Algebra and Discrete Mathematics; Department of Communications and Networking
In this paper, locally repairable codes with all-symbol locality are studied. Methods to modify already existing codes are presented. It is also shown that, with high probability, a random matrix with a few extra columns guaranteeing the locality property is a generator matrix for a locally repairable code with a good minimum distance. The proof of the result provides a constructive method to find locally repairable codes. Finally, constructions of three infinite classes of optimal vector-linear locally repairable codes over a small alphabet independent of the code size are given.
Cyclic flats of binary matroids
(Academic Press Inc., 2021-06) Freij-Hollanti, Ragnar; Grezet, Matthias; Hollanti, Camilla; Westerbäck, Thomas; Algebra and Discrete Mathematics; Department of Mathematics and Systems Analysis; Mälardalen University
In this paper, first steps are taken towards characterizing rank-decorated lattices of cyclic flats Z(M) that belong to matroids M that can be represented over a prescribed finite field Fq. Two natural maps from Z(M) to the lattice of cyclic flats of a minor of M are given. Binary matroids are characterized via their lattice of cyclic flats. It is shown that the lattice of cyclic flats of a simple binary matroid without isthmuses is atomic.
Device-to-Device Data Storage for Mobile Cellular Systems
(2013) Pääkkönen, Joonas; Hollanti, Camilla; Tirkkonen, Olav; Algebra and Discrete Mathematics; Communications Theory; Department of Communications and Networking; Department of Mathematics and Systems Analysis
Device-to-device data storage with regenerating codes
(2015) Pääkkönen, Joonas; Hollanti, Camilla; Tirkkonen, Olav; Algebra and Discrete Mathematics; Communications Theory; Department of Communications and Networking; Department of Mathematics and Systems Analysis
Caching data files directly on mobile user devices combined with device-to-device (D2D) communications has recently been suggested to improve the capacity of wireless networks. We investigate the performance of regenerating codes in terms of the total energy consumption of a cellular network. We show that regenerating codes can offer large performance gains. It turns out that using redundancy against storage node failures is only beneficial if the popularity of the data is between certain thresholds. As our major contribution, we investigate under which circumstances regenerating codes with multiple redundant data fragments outdo uncoded caching.
Efficiently sphere-decodable physical layer transmission schemes for wireless storage networks
(2016-12-01) Lu, Hsiao feng (Francis); Barreal, Amaro; Karpuk, David; Hollanti, Camilla; National Yang Ming Chiao Tung University; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics
Three transmission schemes over a new type of multiple-access channel (MAC) model with inter-source communication links are proposed and investigated in this paper. This new channel model is well motivated by, e.g., wireless distributed storage networks, where communication to repair a lost node takes place from helper nodes to a repairing node over a wireless channel. Since in many wireless networks nodes can come and go in an arbitrary manner, there must be an inherent capability of inter-node communication between every pair of nodes. Assuming that communication is possible between every pair of helper nodes, the newly proposed schemes are based on various smart time-sharing and relaying strategies. In other words, certain helper nodes will be regarded as relays, thereby converting the conventional uncooperative multiple-access channel to a multiple-access relay channel (MARC). The diversity-multiplexing gain tradeoff (DMT) of the system together with efficient sphere-decodability and low structural complexity in terms of the number of antennas required at each end is used as the main design objectives. While the optimal DMT for the new channel model is fully open, it is shown that the proposed schemes outperform the DMT of the simple time-sharing protocol and, in some cases, even the optimal uncooperative MAC DMT. While using a wireless distributed storage network as a motivating example throughout the paper, the MAC transmission techniques proposed here are completely general and as such applicable to any MAC communication with inter-source communication links.
The extension theorem for bi-invariant weights over Frobenius rings and Frobenius bimodules
(AMER MATHEMATICAL SOC, 2019) Gnilke, Oliver W.; Greferath, Marcus; Honold, Thomas; Wood, Jay A.; Zumbraegel, Jens; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics; Zhejiang University; Western Michigan University; University of Passau; Leroy, A; Lomp, C; LopezPermouth, S; Oggier, F
We give a sufficient condition for a bi-invariant weight on a Frobenius bimodule to satisfy the extension property. This condition applies to bi-invariant weights on a finite Frobenius ring as a special case. The complex-valued functions on a Frobenius bimodule are viewed as a module over the complex monoid algebra of the multiplicative monoid of the coefficient ring.
Fast-decodable asymmetric space-time codes from division algebras
(2012) Vehkalahti, Roope; Hollanti, Camilla; Oggier, Frédérique; Algebra and Discrete Mathematics; Department of Mathematics and Systems Analysis
Fast-Decodable Space-Time Codes for the N-Relay and Multiple-Access MIMO Channel
(2016-03-01) Barreal, Amaro; Hollanti, Camilla; Markin, Nadya; Department of Mathematics and Systems Analysis; Algebra and Discrete Mathematics; Nanyang Technological University
In this article, the first general constructions of fast-decodable, more specifically (conditionally) g-group decodable, space-time block codes for the nonorthogonal amplify and forward (NAF) multiple-input multiple-output (MIMO) relay channel under the half-duplex constraint are proposed. In this scenario, the source and the intermediate relays used for data amplification are allowed to employ multiple antennas for data transmission and reception. The worst-case decoding complexity of the obtained codes is reduced by up to 75%. In addition to being fast-decodable, the proposed codes achieve full-diversity and have nonvanishing determinants, which has been shown to be useful for achieving the optimal diversity-multiplexing tradeoff (DMT) of the NAF channel. Furthermore, it is shown that the same techniques as in the cooperative scenario can be utilized to achieve fast-decodability for K-user MIMO multiple-access channel (MAC) space-time block codes. The resulting codes in addition exhibit the conditional nonvanishing determinant property which, for its part, has been shown to be useful for achieving the optimal MAC-DMT.

Browsing by Department "Algebra and Discrete Mathematics"

Results Per Page

Sort Options