Vector symbolic architectures (VSAs) are a family of information representation techniques which enable composition, i.e., creating complex information structures from atomic vectors via binding and superposition, and have recently found wide ranging applications in various neurosymbolic artificial intelligence (AI) systems and hardware systems. Recently, Raviv proposed the use of random linear codes in VSAs, suggesting that their subcode structure enables efficient unbinding, while preserving the quasi-orthogonality that is necessary for neural processing. Yet, random linear codes are difficult to decode under noise, which severely limits the resulting VSA's ability to support recovery, i.e., the retrieval of information objects and their attributes from a noisy compositional representation. In this work we bridge this gap by utilizing coding theoretic tools. First, we argue that the concatenation of Reed-Solomon and Hadamard codes is suitable for VSA, due to the mutual quasi-orthogonality of the resulting codewords (a folklore result). Second, we show that recovery of the resulting compositional representations can be done by solving a problem we call histogram recovery. In histogram recovery, a collection of $N$ histograms over a finite field is given as input, and one must find a collection of Reed-Solomon codewords of length $N$ whose entry-wise symbol frequencies obey those histograms. We present an optimal solution to the histogram recovery problem by using algorithms related to list-decoding, and analyze the resulting noise resilience. Our results give rise to a noise-resilient VSA with formal guarantees regarding efficient encoding, quasi-orthogonality, and recovery, without relying on any heuristics or training, and while operating at improved parameters relative to similar solutions such as the Hadamard code.

In the torn paper channel, a transmitted codeword is broken at random locations into fragments that arrive at the decoder in an unordered manner. A central theoretical challenge within this model is global alignment -- the task of determining each fragment's original position -- in order to faithfully reconstruct the entire codeword. Prior work by Shomorony and Vahid introduced an interleaved-pilot scheme that successfully achieved a vanishing error probability. However, their alignment strategy relies heavily on global statistics, requiring fragments to exceed a minimum length and effectively discarding many shorter ones as erasures, which results in rates significantly below capacity. To address this gap, we propose an improved coding scheme that achieves a provable rate increase through a novel approach we call \textit{local alignment}. This approach identifies global alignment bits within each fragment using only local information, allowing the decoder to determine the positions of fragments that are shorter than those used in previous work. Consequently, the decoder can extract information from a much larger fraction of the channel output than in previous work, yielding significantly higher rates. Furthermore, we extend our analysis to torn paper coding with lost pieces (TPC-LP), a generalized model that accounts for length-dependent fragment deletion. For a class of TPC-LP channels that delete all fragments below a logarithmic length threshold while allowing arbitrary length-dependent deletion probabilities for longer fragments, we show that the proposed local alignment strategy achieves an arbitrarily small additive gap to capacity as the threshold increases.

Partial Information Decomposition (PID) represents multivariate mutual information via antichain-lattice that aims to specify which source groups can recover which informational components of a target. For three or more sources, widely desired PID axioms become mutually incompatible. This is often treated as an axiomatic tuning issue. This paper argues that the obstruction is representational, rooted in the antichain indexing itself, so that purely axiomatic adjustments within an antichain-lattice structure cannot resolve it in general. We first introduce System Information Decomposition (SID) for the special target-free three-variable setting, obtaining a self-consistent entropy decomposition with an operational redundancy definition. More fundamentally, we then show that for general multivariate PID, there is no universal rule that recovers the decomposed mutual information from the antichain-indexed information atoms. In particular, two systems can share identical atoms regardless of any axioms while having different mutual information. These results reveal the limits of antichain-lattice and motivate relation-based foundations for multivariate information measures.

Emerging applications in manufacturing, wireless communication, and molecular data storage require robust coding schemes that remain effective under physical distortions where codewords may be arbitrarily fragmented and partially missing. To address such challenges, we propose a new family of error-correcting codes, termed $(t,s)$-break-resilient codes ($(t,s)$-BRCs). A $(t,s)$-BRC guarantees correct decoding of the original message even after up to~$t$ arbitrary breaks of the codeword and the complete loss of some fragments whose total length is at most~$s$. This model unifies and generalizes previous approaches, extending break-resilient codes (which handle arbitrary fragmentation without fragment loss) and deletion codes (which correct bit losses in unknown positions without fragmentation) into a single information-theoretic framework. We develop a theoretical foundation for $(t,s)$-BRCs, including a formal adversarial channel model, lower bounds on the necessary redundancy, and explicit code constructions that approach these bounds.

In this paper, we address the problem of secure distributed computation in scenarios where user data is not uniformly distributed, extending existing frameworks that assume uniformity, an assumption that is challenging to enforce in data for computation. Motivated by the pervasive reliance on single service providers for data storage and computation, we propose a privacy-preserving scheme that achieves informationtheoretic security guarantees for computing polynomials over non-uniform data distributions. Our framework builds upon the concept of perfect subset privacy and employs linear hashing techniques to transform non-uniform data into approximately uniform distributions, enabling robust and secure computation. We derive leakage bounds and demonstrate that information leakage of any subset of user data to untrusted service providers, i.e., not only to colluding workers but also (and more importantly) to the admin, remains negligible under the proposed scheme.

Differential privacy (DP) has become the gold standard for privacy-preserving data analysis, but its applicability can be limited in scenarios involving complex dependencies between sensitive information and datasets. To address this, we introduce differential confounding privacy (DCP), a specialized form of the Pufferfish privacy (PP) framework that generalizes DP by accounting for broader relationships between sensitive information and datasets. DCP adopts the$(\epsilon, \delta)$-indistinguishability framework to quantify privacy loss. We show that while DCP mechanisms retain privacy guarantees under composition, they lack the graceful compositional properties of DP. To overcome this, we propose an Inverse Composition (IC) framework, where a leader-follower model optimally designs a privacy strategy to achieve target guarantees without relying on worst-case privacy proofs, such as sensitivity calculation. Experimental results validate IC's effectiveness in managing privacy budgets and ensuring rigorous privacy guarantees under composition.

Shared communication media are widely used in many applications including safety-critical applications. However, noise and transient errors can cause transmission failures. We consider the problem of designing and minimizing the length of fault-tolerant static schedules for transmitting messages in these media provided the number of errors fall below some upper bound. To transmitnmessages in a medium while tolerating a maximum offfaults, prior work had shown how to construct schedules which had a fault tolerance overhead ofnf/2. In this paper, we provide an efficient constructive algorithm for producing a schedule for n messages with total lengthn+O(f2log2n) that can toleratefmedium errors. We also provide an algorithm for randomly generating fault-tolerant schedules with lengthn+O(flog(f) log(n)) as well as a technique for quickly verifying these on reasonably small inputs.

We consider the problem of encoding information in a system ofN=K+Rprocessors that operate in a decentralized manner, i.e., without a central processor which orchestrates the operation. The system involvesKsource processors, each holding some data modeled as a vector over a finite field. The remainingRprocessors are sinks, and each of which requires a linear combination of all data vectors. These linear combinations are distinct from one sink to another, and are specified by a generator matrix of a systematic linear code. To capture the communication cost of decentralized encoding, we adopt a linear network model in which the process proceeds in consecutive communication rounds. In every round, every processor sends and receives one message through each one of itspports. Moreover, inspired by network coding literature, we allow processors to transfer linear combinations of their own data and previously received data. We propose a framework that addresses the problem on two levels. On theuniversallevel, we provide a solution to the decentralized encoding problem foranypossible linear code. On thespecificlevel, we further optimize our solution towards systematic Reed-Solomon codes, as well as their variant, Lagrange codes, for their prevalent use in coded storage and computation systems. Our solutions are based on a newly-defined collective communication operation calledall-to-all encode.

A typical setup in many machine learning scenarios involves a server that holds a model and a user that possesses data, and the challenge is to perform inference while safeguarding the privacy of both parties.Private Inferencehas been extensively explored in recent years, mainly from a cryptographic standpoint via techniques like homomorphic encryption and multiparty computation. These approaches often come with high computational overhead and may degrade the accuracy of the model. In our work, we take a different approach inspired by thePrivate Information Retrievalliterature. We view private inference as the task of retrieving inner products of parameter vectors with the data, a fundamental operation in many machine learning models. We introduce schemes that enable such retrieval of inner products for models withquantized(i.e., restricted to a finite set) weights; such models are extensively used in practice due to a wide range of benefits. In addition, our schemes uncover a fundamental tradeoff between user and server privacy. Our information-theoretic approach is applicable to a wide range of problems and robust in privacy guarantees for both the user and the server.

Minimum storage regenerating (MSR) codes are a class of maximum distance separable (MDS) array codes capable of repairing any single failed node by downloading the minimum amount of information from each of the helper nodes. However, MSR codes require large sub-packetization levels, which hinders their usefulness in practical settings. This led to the development of another class of MDS array codes called ε-MSR codes, for which the repair information downloaded from each helper node is at most a factor of (1 + ε) from the minimum amount for some ε > 0. The advantage of ε-MSR codes over MSR codes is their small sub-packetization levels. In previous constructions of epsilon-MSR codes, however, several specific nodes are required to participate in the repair of a failed node, which limits the performance of the code in cases where these nodes are not available. In this work, we present a construction of ε-MSR codes without this restriction. For a code withnnodes, out of whichkstore uncoded information, and for any numberdof helper nodes (k≤dn), the repair of a failed node can be done by contacting any set ofdsurviving nodes. Our construction utilizes group algebra techniques, and requires linear field size. We also generalize the construction to MDS array codes capable of repairinghfailed nodes using d helper nodes with a slightly sub-optimal download from each helper node, for allh≤n−kandk≤d≤n−hsimultaneously.

Encoding data as a set of unordered strings is receiving great attention as it captures one of the basic features of DNA storage systems. However, the challenge of constructing optimal redundancy codes for this channel remained elusive. In this paper, we address this problem and present an order-wise optimal construction of codes that are capable of correcting multiple substitution, deletion, and insertion errors for this channel model. The key ingredient in the code construction is a technique we call robust indexing: simultaneously assigning indices to unordered strings (hence, creating order) and also embedding information in these indices. The encoded indices are resilient to substitution, deletion, and insertion errors, and therefore, so is the entire code.

Feature extraction and selection in the presence of nonlinear dependencies among the data is a fundamental challenge in unsupervised learning. We propose using a Gram-Schmidt (GS) type orthogonalization process over function spaces to detect and map out such dependencies. Specifically, by applying the GS process over some family of functions, we construct a series of covariance matrices that can either be used to identify new large-variance directions, or to remove those dependencies from known directions. In the former case, we provide information-theoretic guarantees in terms of entropy reduction. In the latter, we provide precise conditions by which the chosen function family eliminates existing redundancy in the data. Each approach provides both a feature extraction and a feature selection algorithm. Our feature extraction methods are linear, and can be seen as natural generalization of principal component analysis (PCA). We provide experimental results for synthetic and real-world benchmark datasets which show superior performance over state-of-the-art (linear) feature extraction and selection algorithms. Surprisingly, our linear feature extraction algorithms are comparable and often outperform several important nonlinear feature extraction methods such as autoencoders, kernel PCA, and UMAP. Furthermore, one of our feature selection algorithms strictly generalizes a recent Fourier-based feature selection mechanism (Heidari et al., IEEE Transactions on Information Theory, 2022), yet at significantly reduced complexity.

Delegating large-scale computations to service providers is a common practice which raises privacy concerns. This paper studies information-theoretic privacy-preserving del-egation of data to a service provider, who may further delegate the computation to auxiliary worker nodes, in order to compute a polynomial over that data at a later point in time. We study techniques which are compatible with robust management of distributed computation systems, an area known as coded computing. Privacy in coded computing, however, has tradition-ally addressed the problem of colluding workers, and assumed that the server that administrates the computation is trusted. This viewpoint of privacy does not accurately reflect real-world privacy concerns, since normally, the service provider as a whole (i.e., the administrator and the worker nodes) form one cohesive entity which itself poses a privacy risk. This paper aims to shift the focus of privacy in coded computing to safeguarding the privacy of the user against the service provider as a whole, instead of merely against colluding workers inside the service provider. To this end, we leverage the recently defined notion of perfect subset privacy, which guarantees zero information leakage from all subsets of the data up to a certain size. Using known techniques from Reed-Muller decoding, we provide a scheme which enables polynomial computation with perfect subset privacy in straggler-free systems. Furthermore, by studying information super-sets in Reed-Muller codes, which may be of independent interest, we extend the previous scheme to tolerate straggling worker nodes inside the service provider.

Mutual information between two random variables is a well-studied notion, whose understanding is fairly complete. Mutual information between one random variable and a pair of other random variables, however, is a far more involved notion. Specifically, Shannon's mutual information does not capture fine-grained interactions between those three variables, resulting in limited insights in complex systems. To capture these fine-grained interactions, in 2010 Williams and Beer proposed to decompose this mutual information to information atoms, called unique, redundant, and synergistic, and proposed several operational axioms that these atoms must satisfy. In spite of numerous efforts, a general formula which satisfies these axioms has yet to be found. Inspired by Judea Pearl's do-calculus, we resolve this open problem by introducing the do-operation, an operation over the variable system which sets a certain marginal to a desired value, which is distinct from any existing approaches. Using this operation, we provide the first explicit formula for calculating the information atoms so that Williams and Beer's axioms are satisfied, as well as additional properties from subsequent studies in the field.

Given a real dataset and a computation family, we wish to encode and store the dataset in a distributed system so that any computation from the family can be performed by accessing a small number of nodes. In this work, we focus on the families of linear computations where the coefficients are restricted to a finite set of real values. For two-valued computations, a recent work presented a scheme that gives good feasible points on the access-redundancy tradeoff. This scheme is based on binary covering codes having a certain closure property. In a follow-up work, this scheme was extended to all finite coefficient sets, using a new additive-combinatorics notion called coefficient complexity. In the present paper, we explore non-binary covering codes and develop schemes that outperform the state-of-the-art for some coefficient sets. We provide a more general coefficient complexity definition and show its applicability to the access- redundancy tradeoff.

3D printing brings about a revolution in con-sumption and distribution of goods, but poses a significant risk to public safety. Any individual with internet access and a commodity printer can now produce untraceable firearms, keys, and dangerous counterfeit products. To aid government authorities in combating these new security threats, objects are often tagged with identifying information. This information, also known as fingerprints, is written into the object using various bit embedding techniques, such as varying the width of the molten thermoplastic layers. Yet, due to the adversarial nature of the problem, it is important to devise tamper-resilient fingerprinting techniques, so that the fingerprint could be extracted even if the object was damaged. This paper focuses on a special type of adversarial tampering, where the adversary breaks the object to at most a certain number of parts. This gives rise to a new adversarial coding problem, which is formulated and investigated herein. We survey the existing technology, present an abstract problem definition, provide lower bounds for the required redundancy, and construct a code which attains it up to asymptotically small factors.

Hyperdimensional computing (HDC) is an emerging computational paradigm for representing compositional information as high-dimensional vectors and has a promising potential in applications ranging from machine learning to neuromorphic computing. One of the long-standing challenges in HDC is factoring a compositional representation to its constituent factors, also known as the recovery problem. In this article, we take a novel approach to solve the recovery problem and propose the use of random linear codes. These codes are subspaces over the Boolean field and are a well-studied topic in information theory with various applications in digital communication. We begin by showing that hyperdimensional encoding using random linear codes retains favorable properties of the prevalent (ordinary) random codes; hence, HD representations using the two methods have comparable information storage capabilities. We proceed to show that random linear codes offer a rich subcode structure that can be used to form key-value stores, which encapsulate the most used cases of HDC. Most important, we show that under the framework we develop, random linear codes admit simple recovery algorithms to factor (either bundled or bound) compositional representations. The former relies on constructing certain linear equation systems over the Boolean field, the solution to which reduces the search space dramatically and strictly outperforms exhaustive search in many cases. The latter employs the subspace structure of these codes to achieve provably correct factorization. Both methods are strictly faster than the state-of-the-art resonator networks, often by an order of magnitude. We implemented our techniques in Python using a benchmark software library and demonstrated promising experimental results.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations that are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), have gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where a smaller access parameter requires more redundancy in the system, and vice versa. In this paper, we study this tradeoff and provide several explicit low-access schemes for$\{\pm 1\}$quantized linear computations based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art for two-valued linear computations. We further show that the same storage scheme can be used to retrieve any linear combination with two distinct coefficients—regardless of what those coefficients are—with the same access parameter. This universality result is then extended to all possible quantizations with any number of values; while the storage remains identical, the access parameter increases according to a new additive-combinatorics property we call coefficient complexity. We then turn to study the coefficient complexity—we characterize the complexity of small sets of coefficients, provide bounds, and identify coefficient sets having the highest and lowest complexity. Interestingly, arithmetic progressions have the lowest possible complexity, and some geometric progressions have the highest possible complexity, the former being particularly attractive for its common use in uniform quantization.

Private inference refers to a two-party setting in which one has a model (e.g., a linear classifier), the other has data, and the model is to be applied over the data while safeguarding the privacy of both parties. In particular, models in which the weights are quantized (e.g., to ±1) gained increasing attention lately, due to their benefits in efficient, private, or robust computations.Traditionally, private inference has been studied from a cryptographic standpoint, which suffers from high complexity and degraded accuracy. More recently, Raviv et al. showed that in quantized models, an information theoretic tradeoff exists between the privacy of the parties, and a scheme based on a combination of Boolean and real-valued algebra was presented which attains that tradeoff. Both the scheme and the respective bound required the computation to be done exactly.In this work we show that by relaxing the requirement for exact computation, one can break the information theoretic privacy barrier of Raviv et al., and provide better privacy at the same communication costs. We provide a scheme for such approximate computation, bound its error, show its improved privacy, and devise a respective lower bound for some parameter regimes.

The covering radius is a fundamental property of linear codes that characterizes the trade-off between storage and access in linear data-query protocols. The generalized covering radius was recently defined by Elimelech and Schwartz for applications in joint-recovery of linear data-queries. In this work we extend a known bound on the ordinary covering radius to the generalized one for all codes satisfying the chain condition—a known condition which is satisfied by most known families of codes. Given a generator matrix of a special form, we also provide an algorithm which finds codewords which cover the input vector(s) within the distance specified by the bound. For the case of Reed-Muller codes we provide efficient construction of such generator matrices, therefore providing a faster alternative to a previous generalized covering algorithm for Reed-Muller codes.

Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations which are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as ±1), gained increasing interest lately due to their role in efficient, robust, or private machine learning models. Given a dataset to store in a distributed system, we wish to encode it so that all such computations could be conducted by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks, and reduces the overall communication in the system. Minimizing the access parameter gives rise to an access-redundancy tradeoff, where smaller access parameter requires more redundancy in the system, and vice versa. In this paper we study this tradeoff, and provide several explicit code constructions based on covering codes in a novel way. While the connection to covering codes has been observed in the past, our results strictly outperform the state-of-the-art, and extend the framework to new families of computations.

As blockchains continue to seek to scale to a larger number of nodes, the communication complexity of protocols has become a significant priority as the network can quickly become overburdened. Several schemes have attempted to address this, one of which uses coded computation to lighten the load. Here we seek to address one issue with all such coded blockchain schemes known to the authors: transaction confirmation. In a coded blockchain, only the leader has access to the uncoded block, while the nodes receive encoded data that makes it effectively impossible for them to identify which transactions were included in the block. As a result, a Byzantine leader might choose not to notify a sender or receiver of a transaction that the transaction went into the block, and even with an honest leader, they would not be able to produce a proof of a transaction’s inclusion. To address this, we have constructed a protocol to send the nodes enough information so that a client sending or receiving a transaction is guaranteed to not only be notified but also to receive a proof of that transaction’s inclusion in the block. Crucially, we do this without substantially increasing the bit complexity of the original coded blockchain protocol.

In a Private Inference scenario, a server holds a model (e.g., a neural network), a user holds data, and the user wishes to apply the model on her data. The privacy of both parties must be protected; the user’s data might contain confidential information, and the server’s model is his intellectual property.Private inference has been studied extensively in recent years, mostly from a cryptographic perspective by incorporating homo-morphic encryption and multiparty computation protocols, which incur high computational overhead and degrade the accuracy of the model. In this work we take a perpendicular approach which draws inspiration from the expansive Private Information Retrieval literature. We view private inference as the task of retrieving an inner product of a parameter vector with the data, a fundamental step in most machine learning models.By combining binary arithmetic with real-valued one, we present a scheme which enables the retrieval of the inner product for models whose weights are either binarized, or given in fixed-point representation; such models gained increased attention recently, due to their ease of implementation and increased robustness. We also present a fundamental trade-off between the privacy of the user and that of the server, and show that our scheme is optimal in this sense. Our scheme is simple, universal to a large family of models, provides clear information-theoretic guarantees to both parties with zero accuracy loss, and in addition, is compatible with continuous data distributions and allows infinite precision.

As the size of modern datasets grows, it becomes increasingly common to delegate computational tasks to service providers. Doing so, however, raises privacy concerns. Privatization schemes which enable learning algorithms to be executed unaltered have been recently popularized under the name instance encoding, aiming to circumvent the large overhead of traditional cryptographic primitives. In this work we take an information/coding-theoretic approach towards instance encoding. Specifically, recent works have shown that general-purpose data sharing can be achieved without leaking information about any individual datapoint (marginally), while maintaining high mutual information with the dataset in its entirety. We first extend this framework to capture the entire privacy-utility tradeoff, accounting for the privatization of any subset of the dataset, and provide a coding scheme for doing so. Second, we introduce a necessary algebraic condition for applying unaltered learning algorithms on encrypted data, termed signal preservation, and present an additional scheme which guarantees it. Both schemes achieve almost maximal mutual information with the entire dataset, under appropriate assumptions. The construction relies on some classic ideas such as Shamir secret sharing, as well as a novel technique called random Hadamard coding.

We define all-to-all encode, a collective communication operation serving as a primitive in decentralized computation and storage systems. Consider a scenario where every processor initially has a data packet and requires a linear combination of all data packets; the linear combinations are distinct from one processor to another, and are specified by a generator matrix of an error correcting code. We use a linear network model, in which processors transmit linear combinations of their data and previously received packets, and adopt a standard synchronous system setting to analyze its communication cost. We provide a universal algorithm which computes any matrix in this model by only varying intermediate coefficients, and prove its optimality. When the generator matrix is of the Vandermonde or Lagrange type, we further optimize the communication efficiency of the proposed algorithm.

Although blockchain, the supporting technology of various cryptocurrencies, has offered a potentially effective framework for numerous decentralized trust management systems, its performance is still sub-optimal in real-world networks. With limited bandwidth, the communication complexity for nodes to process a block scales with the growing network size and hence becomes the limiting factor of blockchain’s performance.In this paper, we suggest a re-design of existing blockchain systems, which addresses the issue of the communication burden. First, by employing techniques from Coded Computation, our scheme guarantees correct verification of transactions while reducing the communication complexity dramatically such that it grows logarithmically with network size. Second, by adopting techniques from Information Dispersal and State Machine Replication, our design is provably resilient to Byzantine faults under standard cryptographic assumptions.1

There are various ways to use machine learning to improve data storage techniques. In this paper, we introduce symbolic regression, a machine-learning method for recovering the symbolic form of a function from its samples. We present a new symbolic regression scheme that utilizes side information for higher accuracy and speed in function recovery. The scheme enhances latest results on symbolic regression that were based on recurrent neural networks and genetic programming. The scheme is tested on a new benchmark of functions for data storage.

Despite the considerable success of neural networks in security settings such as malware detection, such models have proved vulnerable to evasion attacks, in which attackers make slight changes to inputs (e.g., malware) to bypass detection. We propose a novel approach, Fourier stabilization, for designing evasion-robust neural networks with binary inputs. This approach, which is complementary to other forms of defense, replaces the weights of individual neurons with robust analogs derived using Fourier analytic tools. The choice of which neurons to stabilize in a neural network is then a combinatorial optimization problem, and we propose several methods for approximately solving it. We provide a formal bound on the per-neuron drop in accuracy due to Fourier stabilization, and experimentally demonstrate the effectiveness of the proposed approach in boosting robustness of neural networks in several detection settings. Moreover, we show that our approach effectively composes with adversarial training.

Although blockchain, the supporting technology of Bitcoin and various cryptocurrencies, has offered a potentially effective framework for numerous applications, it still suffers from the adverse affects of the impossibility triangle. Performance, security, and decentralization of blockchains normally do not scale simultaneously with the number of participants in the network. The recent introduction of error correcting codes in sharded blockchain by Li et al. partially settles this trilemma, boosting throughput without compromising security and decentralization. In this paper, we improve the coded sharding scheme in three ways. First, we propose a novel 2-Dimensional Sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated inter-shard communication protocols. Second, we employ distributed storage techniques in the propagation of blocks, improving latency under restricted bandwidth. Finally, we incorporate polynomial cryptographic primitives of low degree, which brings coded blockchain techniques into the realm of feasible real-world parameters.

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide several constructions, some of which are shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is order-wise equivalent to the amount required in the classical error correcting paradigm.

Data is one of the most important assets of the information age, and its societal impact is undisputed. Yet, rigorous methods of assessing the quality of data are lacking. In this paper, we propose a formal definition for the quality of a given dataset. We assess a dataset's quality by a quantity we call the expected diameter, which measures the expected disagreement between two randomly chosen hypotheses that explain it, and has recently found applications in active learning. We focus on Boolean hyperplanes, and utilize a collection of Fourier analytic, algebraic, and probabilistic methods to come up with theoretical guarantees and practical solutions for the computation of the expected diameter. We also study the behaviour of the expected diameter on algebraically structured datasets, conduct experiments that validate this notion of quality, and demonstrate the feasibility of our techniques.

Deep Neural Networks (DNNs) are a revolutionary force in the ongoing information revolution, and yet their intrinsic properties remain a mystery. In particular, it is widely known that DNNs are highly sensitive to noise, whether adversarial or random. This poses a fundamental challenge for hardware implementations of DNNs, and for their deployment in critical applications such as autonomous driving.In this paper we construct robust DNNs via error correcting codes. By our approach, either the data or internal layers of the DNN are coded with error correcting codes, and successful computation under noise is guaranteed. Since DNNs can be seen as a layered concatenation of classification tasks, our research begins with the core task of classifying noisy coded inputs, and progresses towards robust DNNs.We focus on binary data and linear codes. Our main result is that the prevalent parity code can guarantee robustness for a large family of DNNs, which includes the recently popularized binarized neural networks. Further, we show that the coded classification problem has a deep connection to Fourier analysis of Boolean functions.In contrast to existing solutions in the literature, our results do not rely on altering the training process of the DNN, and provide mathematically rigorous guarantees rather than experimental evidence.

The channel model of encoding data as a set of unordered strings is receiving great attention as it captures the basic features of DNA storage systems. However, the challenge of constructing optimal redundancy codes for this channel remained elusive. In this paper, we solve this open problem and present an order-wise optimal construction of codes that correct multiple substitution errors for this channel model. The key ingredient in the code construction is a technique we call robust indexing: instead of using fixed indices to create order in unordered strings, we use indices that are information dependent and thus eliminate unnecessary redundancy. In addition, our robust indexing technique can be applied to the construction of optimal deletion/insertion codes for this channel.

Gabidulin codes over fields of characteristic zero were recently constructed by Augot et al., whenever the Galois group of the underlying field extension is cyclic. In parallel, the interest in sparse generator matrices of Reed-Solomon and Gabidulin codes has increased lately, due to applications in distributed computations. In particular, a certain condition pertaining to the intersection of zero entries at different rows, was shown to be necessary and sufficient for the existence of the sparsest possible generator matrix of Gabidulin codes over finite fields. In this paper we complete the picture by showing that the same condition is also necessary and sufficient for Gabidulin codes over fields of characteristic zero. Our proof builds upon and extends tools from the finite-field case, combines them with a variant of the Schwartz-Zippel lemma over automorphisms, and provides a simple randomized construction algorithm whose probability of success can be arbitrarily close to one. In addition, potential applications for low-rank matrix recovery are discussed.

Neural networks (NNs) are a driving force behind the ongoing information revolution, with a broad spectrum of applications affecting most aspects of science and technology. The interest in robust neural computation under adversarial noise has increased lately, due applications in sensitive tasks ranging from healthcare to finance and autonomous vehicles. This has ignited an influx of research on the topic, which for the most part focuses on obtaining robustness by altering the training process. In contrast, this paper surveys and develops a recently proposed novel approach to obtain robustness after training, by adding redundancy to the network and to the data in the form of error correcting codes.Since neural networks are essentially a concatenation of linear classifiers, we focus on obtaining robustness for a single linear classifier by coding the input and the classifier, and then apply the results on the network. We address two different types of adversaries, a worst-case one and an average-case one. For a worst-case adversary, that can choose the input to be attacked, we focus on binarized classifiers and show that the problem is related to construction of certain linear codes with restricted weight patterns. As a result, it is shown that the parity code can obtain robustness against any 1-erasure in any binarized NN, and no decoding is required. For an average-case adversary, that is given a uniformly random input to be attacked, it is shown that the optimal weights for any classifier and any code are given by the Fourier coefficients of that classifier. We demonstrate the latter experimentally, exposing improved accuracy-robustness tradeoff in neural classification of several popular datasets under state-of-the-art attacks.

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the ℓ2error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called t-private if the identity of the file remains concealed even if t of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases.

Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov-Tenengolts construction. Our techniques require 7 log (n)+ o(log(n)) redundant bits to encode an n-bit message, which is closer to optimal than previous constructions. Moreover, the encoding and decoding algorithms have O(n) time complexity.

We consider a scenario involving computations over a massive dataset stored distributedly across multiple workers, which is at the core of distributed learning algorithms. We propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide (1) resiliency against stragglers that may prolong computations; (2) security against Byzantine (or malicious) workers that deliberately modify the computation for their benefit; and (3) (information-theoretic) privacy of the dataset amidst possible collusion of workers. LCC, which leverages the well-known Lagrange polynomial to create computation redundancy in a novel coded form across workers, can be applied to any computation scenario in which the function of interest is an arbitrary multivariate polynomial of the input dataset, hence covering many computations of interest in machine learning. LCC significantly generalizes prior works to go beyond linear computations. It also enables secure and private computing in distributed settings, improving the computation and communication efficiency of the state-of-the-art. Furthermore, we prove the optimality of LCC by showing that it achieves the optimal tradeoff between resiliency, security, and privacy, i.e., in terms of tolerating the maximum number of stragglers and adversaries, and providing data privacy against the maximum number of colluding workers. Finally, we show via experiments on Amazon EC2 that LCC speeds up the conventional uncoded implementation of distributed least-squares linear regression by up to $13.43\times$, and also achieves a $2.36\times$-$12.65\times$ speedup over the state-of-the-art straggler mitigation strategies.

Private computation is a generalization of private information retrieval, in which a user is able to compute a function on a distributed dataset without revealing the identity of that function to the servers. In this paper, it is shown that Lagrange encoding, a powerful technique for encoding Reed-Solomon codes, enables private computation in many cases of interest. In particular, we present a scheme that enables private computation of polynomials of any degree on Lagrange encoded data, while being robust to Byzantine and straggling servers, and to servers colluding to attempt to deduce the identities of the functions to be evaluated. Moreover, incorporating ideas from the well-known Shamir secret sharing scheme allows the data itself to be concealed from the servers as well. Our results extend private computation to high degree polynomials and to data-privacy, and reveal a tight connection between private computation and coded computation.

Lagrange Coded Computing (LCC) is a recently proposed technique for resilient, secure, and private computation of arbitrary polynomials in distributed environments. By mapping such computations to composition of polynomials, LCC allows the master node to complete the computation by accessing a minimal number of workers and downloading all of their content, thus providing resiliency to the remaining stragglers. However, in the most common case in which the number of stragglers is less than in the worst case scenario, much of the computational power of the system remains unexploited. To amend this issue, in this paper we expand LCC by studying a fundamental trade-off between download and access, and present two contributions. In the first contribution, it is shown that without any modification to the encoding process, the master can decode the computations by accessing a larger number of nodes, however downloading less information from each node in comparison with LCC (i.e., trading access for download). This scheme relies on decoding a particular polynomial in the ideal that is generated by the polynomials of interest, a technique we call Ideal Decoding. This new scheme also improves LCC in the sense that for systems with adversaries, the overall downloaded bandwidth is smaller than in LCC. In the second contribution we study a real-time model of this trade-off, in which the data from the workers is downloaded sequentially. By clustering nodes of similar delays and encoding the function with Universally Decodable Matrices, the master can decode once sufficient data is downloaded from every cluster, regardless of the internal delays within that cluster. This allows the master to utilize the partial work that is done by stragglers, rather than to ignore it, a feature that most past works in coded computing are lacking.

The interest in channel models in which the data is sent as an unordered set of binary strings has increased lately, due to emerging applications in DNA storage, among others. In this paper we analyze the minimal redundancy of binary codes for this channel under substitution errors, and provide a code construction for a single substitution that is shown to be asymptotically optimal up to constants. The surprising result in this paper is that while the information vector is sliced into a set of unordered strings, the amount of redundant bits that are required to correct errors is orderwise equivalent to the amount required in the classical error correcting paradigm.

In this paper, we introduce a new channel model termed as the q-ary multi-bit channel. This channel models a memory device, where q-ary symbols (q = 2s) are stored in the form of current/voltage levels. The symbols are read in a measurement process, which provides a symbol bit in each measurement step, starting from the most significant bit. An error event occurs when not all the symbol bits are known. To deal with such error events, we use GF(q) lowdensity parity-check (LDPC) codes and analyze their decoding performance. We start with iterative-decoding threshold analysis and derive optimal edge-label distributions for maximizing the decoding threshold. We later move to a finite-length iterative decoding analysis and propose an edge-labeling algorithm for the improved decoding performance. We then provide a finite-length maximum-likelihood decoding analysis for both the standard non-binary random ensemble and LDPC ensembles. Finally, we demonstrate by simulations that the proposed edge-labeling algorithm improves the finite-length decoding performance by orders of magnitude.

Synthesis of DNA molecules offers unprecedented advances in storage technology. Yet, the microscopic world in which these molecules reside induces error patterns that are fundamentally different from their digital counterparts. Hence, to maintain reliability in reading and writing, new coding schemes must be developed. In a reading technique called shotgun sequencing, a long DNA string is read in a sliding window fashion, and a profile vector is produced. It was recently suggested by Kiah et al. that such a vector can represent the permutation which is induced by its entries, and hence a rank-modulation scheme arises. Although this interpretation suggests high error tolerance, it is unclear which permutations are feasible and how to produce a DNA string whose profile vector induces a given permutation. In this paper, by observing some necessary conditions, an upper bound for the number of feasible permutations is given. Furthermore, a technique for deciding the feasibility of a permutation is devised. By using insights from this technique, an algorithm for producing a considerable number of feasible permutations is given, which applies to any alphabet size and any window length.

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favourably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that the normalized adjacency matrix of an expander graph can yield excellent approximate gradient codes, and that this approach allows us to perform significantly less computation compared to exact gradient coding. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.

Erwin Chargaff in 1950 made an experimental observation that the count of A is equal to the count of T and the count of C is equal to the count of G in DNA. This observation played a crucial role in the discovery of the double stranded helix structure by Watson and Crick. However, this symmetry was also observed in single stranded DNA. This phenomenon was termed as the 2nd Chargaff Rule. This symmetry has been verified experimentally in genomes of several different species not only for mononucleotides but also for reverse complement pairs of larger lengths upto a small error. While the symmetry in double stranded DNA is related to base pairing and replication mechanisms, the symmetry in a single stranded DNA is still a mystery in its function and source. In this work, we define a sequence generation model based on reverse complement tandem duplications. We show that this model generates sequences that satisfy the 2nd Chargaff Rule even when the duplication lengths are very small when compared to the length of sequences. We also provide estimates on the number of generations that are needed by this model to generate sequences that satisfy the 2nd Chargaff Rule. We provide theoretical bounds on the disruption in symmetry for different values of duplication lengths under this model. Moreover, we experimentally compare the disruption in the symmetry incurred by our model with what is observed in human genome data.

Recent advances in coding for distributed storage systems have reignited the interest in scalar codes over extension fields. In parallel, the rise of large-scale distributed systems has motivated the study of computing in the presence of stragglers, i.e., servers that are slow to respond or unavailable. This paper addresses storage systems that employ linear codes over extension fields. A common task in such systems is the reconstruction of the entire dataset using sequential symbol transmissions from multiple servers, which are received concurrently at a central data collector. However, a key bottleneck in the reconstruction process is the possible presence of stragglers, which may result in excessive latency. To mitigate the straggler effect, the reconstruction should be possible given any sufficiently large set of sequentially received symbols, regardless of their source. In what follows, an algebraic framework for this scenario is given, and a number of explicit constructions are provided. Our main result is a construction that uses a recursive composition of generalized Reed-Solomon codes over smaller fields. In addition, we show links of this problem to Gabidulin codes and to universally decodable matrices.

Replication is prevalent in both theory and practice as a means for obtaining robustness in distributed storage systems. A system in which every data entry is stored on two separate servers gives rise to a graph structure in a natural way, and the combinatorial properties of this graph shed light on the possible features of the system. One possible feature of interest, that has recently gained renewed attention, is private information retrieval (PIR). A PIR protocol enables a user to obtain a data entry from a storage system without revealing the identity of the requested entry to sets of colluding servers. In this paper we suggest a simple PIR protocol for graph based replication systems, which guarantees perfect secrecy against any set of colluding servers that does not induce a cycle. Furthermore, it is shown that the secrecy deteriorates gracefully with the number of cycles in the colluding set, and that the upload complexity can be reduced for graphs of certain specialized structure.

Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov- Tenengolts construction. Our techniques require 7log(n)+o(log(n) redundant bits to encode an n-bit message, which is near-optimal.

We consider the problem of secure and private multiparty computation (MPC), in which the goal is to compute a general polynomial function distributedly over several workers, while keeping them oblivious to the content of the dataset, and preventing them from maliciously affecting the computation result. We demonstrate the role of Lagrange Coded Computing (LCC), a recently proposed coded computing technique that can be applied to general polynomial computations, on enabling secure and private MPC. We show that LCC offers both private and secure computation simultaneously, and is universal in the sense that all polynomials up to a certain degree can be computed on the same encoding. We also demonstrate that LCC achieves an optimal tradeoff between privacy and security, and requires a minimal amount of added randomness for privacy. Compared to prevalent algorithms in MPC (in particular the celebrated BGW scheme), we show that LCC significantly improves the storage, communication, and secret-sharing overhead needed for MPC.

The problem of storing permutations in a distributed manner arises in several common scenarios, such as efficient updates of a large, encrypted, or compressed data set. This problem may be addressed in either a combinatorial or a coding approach. The former approach boils down to presenting large sets of permutations with locality, that is, any symbol of the permutation can be computed from a small set of other symbols. In the latter approach, a permutation may be coded in order to achieve locality. This paper focuses on the combinatorial approach. We provide upper and lower bounds for the maximal size of a set of permutations with locality, and provide several simple constructions which attain the upper bound. In cases where the upper bound is not attained, we provide alternative constructions using Reed-Solomon codes, permutation polynomials, and multi-permutations.

A subspace of a finite extension field is called a Sidon space if the product of any two of its elements is unique up to a scalar multiplier from the base field. Sidon spaces were recently introduced by Bachoc et al. as a means to characterize multiplicative properties of subspaces, and yet no explicit constructions were given. In this paper, several constructions of Sidon spaces are provided. In particular, in some of the constructions the relation between k, the dimension of the Sidon space, and n, the dimension of the ambient extension field, is optimal. These constructions are shown to provide cyclic subspace codes, which are useful tools in network coding schemes. To the best of our knowledge, this constitutes the first set of constructions of nontrivial cyclic subspace codes in which the relation between k and n is polynomial, and in particular, linear. As a result, a conjecture by Trautmann et al. regarding the existence of non-trivial cyclic subspace codes is resolved for most parameters, and multi-orbit cyclic subspace codes are attained, whose cardinality is within a constant factor (close to 1/2) from the sphere-packing bound for subspace codes.

The study of regenerating codes has advanced tremendously in recent years. However, most known constructions require large field size, and hence may be hard to implement in practice. In this paper, by using notions from field theory and matrix analysis to restructure known coding techniques, two explicit constructions of regenerating codes are obtained. These codes approach the cut-set bound as the reconstruction degree increases, and may be realized over any given field if the file size is large enough. Since distributed storage systems are the main purpose of regenerating codes, this file size restriction is trivially satisfied in most conceivable scenarios. The first construction attains the cut-set bound at the MBR point asymptotically for all parameters, whereas the second one attains the cut-set bound at the MSR point asymptotically for low-rate parameters.

Synthesis of DNA molecules offers unprecedented advances in storage technology. Yet, the microscopic world in which these molecules reside induces error patterns that are fundamentally different from their digital counterparts. Hence, to maintain reliability in reading and writing, new coding schemes must be developed. In a reading technique called shotgun sequencing, a long DNA string is read in a sliding window fashion, and a profile vector is produced. It was recently suggested by Kiah et al. that such a vector can represent the permutation which is induced by its entries, and hence a rank modulation scheme arises. Although this interpretation suggests high error tolerance, it is unclear which permutations are feasible, and how to produce a DNA string whose profile vector induces a given permutation. In this paper, by observing some necessary conditions, an upper bound for the number of feasible permutations is given. Further, a technique for deciding the feasibility of a permutation is devised. By using this technique, an algorithm for producing a considerable number of feasible permutations is given, which applies to any alphabet size and any window length.

The interest in subspace codes has increased in recent years due to their application in error correction for random network coding. In order to study their properties and find good constructions, the notion of cyclic subspace codes was introduced by using the extension field structure of the ambient space. However, to this date there exists no general construction with a polynomial relation between k, the dimension of the codewords, and n, the dimension of the entire space. Independently of the study of cyclic subspace codes, sSidon spaces were recently introduced by Bachoc et al. as a tool for the study of certain multiplicative properties of subspaces over finite fields. In this paper it is shown that Sidon spaces are necessary and sufficient for obtaining a full-orbit cyclic subspace code with minimum distance 2 k - 2. By presenting several constructions of Sidon spaces, full-orbit cyclic subspace codes are obtained, in which n is quadratic in k. The constructions are based on a variety of tools; namely, Sidon sets, that are sets of integers in which all pairwise sums are distinct, irreducible polynomials, and linearized polynomials. Further, the existence of a Sidon space in which n is linear in k is shown, alongside the fact that any Sidon space induces a Sidon set.

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities (i.e., codes with larger number of systematic nodes). This improvement is achieved at the expense of the access-optimality and the field size. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage ℓ in each node, the entire stored data can be recovered from any 2 log2ℓ for two parity nodes, and either 3 log3ℓ or 4 log3ℓ for three parities. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction a field size of at least 6 log3ℓ +1 (or 3 log3ℓ +1 for fields with characteristic 2) is sufficient, and in the second construction the field size is larger, yet linear in log3ℓ. Both constructions with three parities provide a significant improvement over previous works due to either decreased field size or lower subpacketization.

There is an error in the above titled paper[1]. As a result, the main statement of the paper is true for a subset of the Gabidulin codes for which it was initially stated. To be precise, our results on the list decodability still hold for the same parameters of$n$and$m$, but the evaluation points have to be of a certain structure.

This paper presents a new construction of high-rate minimum storage regenerating codes. In addition to a minimum storage in a node, these codes have the following two important properties: first, given storage ℓ in each node, the entire stored data can be recovered from any 2 log2ℓ (any 3 log3ℓ) nodes for two parities (for three parities, respectively); second, a helper node accesses the minimum number of its symbols for repair of a failed systematic node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, the field size is 6 log3ℓ+1 (or 3 log3ℓ+1 for fields with characteristic 2), where only non-explicit constructions with exponential field size (in log3ℓ) were known so far.

Subspace codes have received an increasing interest recently due to their application in error correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper, we consider such cyclic codes and provide constructions of optimal codes for which their codewords do not have full orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes, which are cyclic and analyze their parameters.

Gabidulin codes can be seen as the rank-metric equivalent of Reed-Solomon codes. It was recently proved, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially sized lists exist for codes with specific parameters. The second bound presents exponentially sized lists explicitly for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding several families of Gabidulin codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes. Using a standard operation called lifting, identical results also follow for an important class of constant dimension subspace codes.

Subspace codes have received an increasing interest recently due to their application in error-correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper we consider such cyclic codes. We provide constructions of optimal cyclic codes for which their codewords do not have full length orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes which are cyclic and analyze their parameters.

Distributed storage systems based on intersecting constant dimension (equidistant) codes are presented. These intersecting codes are constructed using the Plücker embedding, which is essential in the repair and the reconstruction algorithms. These systems possess several useful properties such as high failure resilience, minimum bandwidth, low overall storage, simple algebraic repair and reconstruction algorithms, good locality, and compatibility with small fields.

Gabidulin codes can be seen as the rank-metric equivalent of Reed-Solomon codes. It was recently proven, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the minimum possible list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially-sized lists exist for codes with specific parameters. The second bound presents exponentially-sized lists explicitly, for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding their respective families of codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes.