BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Alexandros G. Dimakis

Alexandros G. Dimakis appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITNetworking and Internet ArchitectureMachine LearningDistributed, Parallel, and Cluster ComputingData Structures and AlgorithmsArtificial IntelligenceCryptography and Securitymath.OCSocial and Information NetworksComputation and LanguageDiscrete MathematicsComputer Science and Game TheoryComputer Visioneess.IVeess.SPmath.COmath.NAmath.PRNeural and Evolutionary ComputingSoftware EngineeringSystems and Control

Catalog footprint

What is connected

63works
22topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

63 published item(s)

preprint2026arXiv

optimize_anything: A Universal API for Optimizing any Text Parameter

Can a single LLM-based optimization system match specialized tools across fundamentally different domains? We show that when optimization problems are formulated as improving a text artifact evaluated by a scoring function, a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs-achieves state-of-the-art results across six diverse tasks. Our system discovers agent architectures that nearly triple Gemini Flash's ARC-AGI accuracy (32.5% to 89.5%), finds scheduling algorithms that cut cloud costs by 40%, generates CUDA kernels where 87% match or beat PyTorch, and outperforms AlphaEvolve's reported circle packing solution (n=26). Ablations across three domains reveal that actionable side information yields faster convergence and substantially higher final scores than score-only feedback, and that multi-task search outperforms independent optimization given equivalent per-problem budget through cross-task transfer, with benefits scaling with the number of related tasks. Together, we show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm, unifying tasks traditionally requiring domain-specific algorithms under a single framework. We open-source optimize\_anything with support for multiple backends as part of the GEPA project at https://github.com/gepa-ai/gepa .

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Discovering the Hidden Vocabulary of DALLE-2

We discover that DALLE-2 seems to have a hidden vocabulary that can be used to generate images with absurd prompts. For example, it seems that \texttt{Apoploe vesrreaitais} means birds and \texttt{Contarra ccetnxniams luryca tanniounons} (sometimes) means bugs or pests. We find that these prompts are often consistent in isolation but also sometimes in combinations. We present our black-box method to discover words that seem random but have some correspondence to visual concepts. This creates important security and interpretability challenges.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Model-Based Deep Learning

Signal processing, communications, and control have traditionally relied on classical statistical modeling techniques. Such model-based methods utilize mathematical formulations that represent the underlying physics, prior information and additional domain knowledge. Simple classical models are useful but sensitive to inaccuracies and may lead to poor performance when real systems display complex or dynamic behavior. On the other hand, purely data-driven approaches that are model-agnostic are becoming increasingly popular as datasets become abundant and the power of modern deep learning pipelines increases. Deep neural networks (DNNs) use generic architectures which learn to operate from data, and demonstrate excellent performance, especially for supervised problems. However, DNNs typically require massive amounts of data and immense computational resources, limiting their applicability for some signal processing scenarios. We are interested in hybrid techniques that combine principled mathematical models with data-driven systems to benefit from the advantages of both approaches. Such model-based deep learning methods exploit both partial domain knowledge, via mathematical structures designed for specific problems, as well as learning from limited data. In this article we survey the leading approaches for studying and designing model-based deep learning systems. We divide hybrid model-based/data-driven systems into categories based on their inference mechanism. We provide a comprehensive review of the leading approaches for combining model-based algorithms with deep learning in a systematic manner, along with concrete guidelines and detailed signal processing oriented examples from recent literature. Our aim is to facilitate the design and study of future systems on the intersection of signal processing and machine learning that incorporate the advantages of both domains.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems

We prove fast mixing and characterize the stationary distribution of the Langevin Algorithm for inverting random weighted DNN generators. This result extends the work of Hand and Voroninski from efficient inversion to efficient posterior sampling. In practice, to allow for increased expressivity, we propose to do posterior sampling in the latent space of a pre-trained generative model. To achieve that, we train a score-based model in the latent space of a StyleGAN-2 and we use it to solve inverse problems. Our framework, Score-Guided Intermediate Layer Optimization (SGILO), extends prior work by replacing the sparsity regularization with a generative prior in the intermediate layer. Experimentally, we obtain significant improvements over the previous state-of-the-art, especially in the low measurement regime.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Exactly Computing the Local Lipschitz Constant of ReLU Networks

The local Lipschitz constant of a neural network is a useful metric with applications in robustness, generalization, and fairness evaluation. We provide novel analytic results relating the local Lipschitz constant of nonsmooth vector-valued functions to a maximization over the norm of the generalized Jacobian. We present a sufficient condition for which backpropagation always returns an element of the generalized Jacobian, and reframe the problem over this broad class of functions. We show strong inapproximability results for estimating Lipschitz constants of ReLU networks, and then formulate an algorithm to compute these quantities exactly. We leverage this algorithm to evaluate the tightness of competing Lipschitz estimators and the effects of regularized training on the Lipschitz constant.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Intermediate Layer Optimization for Inverse Problems using Deep Generative Models

We propose Intermediate Layer Optimization (ILO), a novel optimization algorithm for solving inverse problems with deep generative models. Instead of optimizing only over the initial latent code, we progressively change the input layer obtaining successively more expressive generators. To explore the higher dimensional spaces, our method searches for latent codes that lie within a small $l_1$ ball around the manifold induced by the previous layer. Our theoretical analysis shows that by keeping the radius of the ball relatively small, we can improve the established error bound for compressed sensing with deep generative models. We empirically show that our approach outperforms state-of-the-art methods introduced in StyleGAN-2 and PULSE for a wide range of inverse problems including inpainting, denoising, super-resolution and compressed sensing.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Deep Learning Techniques for Inverse Problems in Imaging

Recent work in machine learning shows that deep neural networks can be used to solve a wide variety of inverse problems arising in computational imaging. We explore the central prevailing themes of this emerging area and present a taxonomy that can be used to categorize different problems and reconstruction methods. Our taxonomy is organized along two central axes: (1) whether or not a forward model is known and to what extent it is used in training and testing, and (2) whether or not the learning is supervised or unsupervised, i.e., whether or not the training relies on access to matched ground truth image and measurement pairs. We also discuss the trade-offs associated with these different reconstruction approaches, caveats and common failure modes, plus open problems and avenues for future work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

SGD Learns One-Layer Networks in WGANs

Generative adversarial networks (GANs) are a widely used framework for learning generative models. Wasserstein GANs (WGANs), one of the most successful variants of GANs, require solving a minmax optimization problem to global optimality, but are in practice successfully trained using stochastic gradient descent-ascent. In this paper, we show that, when the generator is a one-layer network, stochastic gradient descent-ascent converges to a global solution with polynomial time and sample complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bipartite Correlation Clustering -- Maximizing Agreements

In Bipartite Correlation Clustering (BCC) we are given a complete bipartite graph $G$ with `+' and `-' edges, and we seek a vertex clustering that maximizes the number of agreements: the number of all `+' edges within clusters plus all `-' edges cut across clusters. BCC is known to be NP-hard. We present a novel approximation algorithm for $k$-BCC, a variant of BCC with an upper bound $k$ on the number of clusters. Our algorithm outputs a $k$-clustering that provably achieves a number of agreements within a multiplicative ${(1-δ)}$-factor from the optimal, for any desired accuracy $δ$. It relies on solving a combinatorially constrained bilinear maximization on the bi-adjacency matrix of $G$. It runs in time exponential in $k$ and $δ^{-1}$, but linear in the size of the input. Further, we show that, in the (unconstrained) BCC setting, an ${(1-δ)}$-approximation can be achieved by $O(δ^{-1})$ clusters regardless of the size of the graph. In turn, our $k$-BCC algorithm implies an Efficient PTAS for the BCC objective of maximizing agreements.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Contextual Bandits with Latent Confounders: An NMF Approach

Motivated by online recommendation and advertising systems, we consider a causal model for stochastic contextual bandits with a latent low-dimensional confounder. In our model, there are $L$ observed contexts and $K$ arms of the bandit. The observed context influences the reward obtained through a latent confounder variable with cardinality $m$ ($m \ll L,K$). The arm choice and the latent confounder causally determines the reward while the observed context is correlated with the confounder. Under this model, the $L \times K$ mean reward matrix $\mathbf{U}$ (for each context in $[L]$ and each arm in $[K]$) factorizes into non-negative factors $\mathbf{A}$ ($L \times m$) and $\mathbf{W}$ ($m \times K$). This insight enables us to propose an $ε$-greedy NMF-Bandit algorithm that designs a sequence of interventions (selecting specific arms), that achieves a balance between learning this low-dimensional structure and selecting the best arm to minimize regret. Our algorithm achieves a regret of $\mathcal{O}\left(L\mathrm{poly}(m, \log K) \log T \right)$ at time $T$, as compared to $\mathcal{O}(LK\log T)$ for conventional contextual bandits, assuming a constant gap between the best arm and the rest for each context. These guarantees are obtained under mild sufficiency conditions on the factors that are weaker versions of the well-known Statistical RIP condition. We further propose a class of generative models that satisfy our sufficient conditions, and derive a lower bound of $\mathcal{O}\left(Km\log T\right)$. These are the first regret guarantees for online matrix completion with bandit feedback, when the rank is greater than one. We further compare the performance of our algorithm with the state of the art, on synthetic and real world data-sets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distributed Estimation of Graph 4-Profiles

We present a novel distributed algorithm for counting all four-node induced subgraphs in a big graph. These counts, called the $4$-profile, describe a graph's connectivity properties and have found several uses ranging from bioinformatics to spam detection. We also study the more complicated problem of estimating the local $4$-profiles centered at each vertex of the graph. The local $4$-profile embeds every vertex in an $11$-dimensional space that characterizes the local geometry of its neighborhood: vertices that connect different clusters will have different local $4$-profiles compared to those that are only part of one dense cluster. Our algorithm is a local, distributed message-passing scheme on the graph and computes all the local $4$-profiles in parallel. We rely on two novel theoretical contributions: we show that local $4$-profiles can be calculated using compressed two-hop information and also establish novel concentration results that show that graphs can be substantially sparsified and still retain good approximation quality for the global $4$-profile. We empirically evaluate our algorithm using a distributed GraphLab implementation that we scaled up to $640$ cores. We show that our algorithm can compute global and local $4$-profiles of graphs with millions of edges in a few minutes, significantly improving upon the previous state of the art.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Entropic Causal Inference

We consider the problem of identifying the causal direction between two discrete random variables using observational data. Unlike previous work, we keep the most general functional model but make an assumption on the unobserved exogenous variable: Inspired by Occam's razor, we assume that the exogenous variable is simple in the true causal direction. We quantify simplicity using Rényi entropy. Our main result is that, under natural assumptions, if the exogenous variable has low $H_0$ entropy (cardinality) in the true direction, it must have high $H_0$ entropy in the wrong direction. We establish several algorithmic hardness results about estimating the minimum entropy exogenous variable. We show that the problem of finding the exogenous variable with minimum entropy is equivalent to the problem of finding minimum joint entropy given $n$ marginal distributions, also known as minimum entropy coupling problem. We propose an efficient greedy algorithm for the minimum entropy coupling problem, that for $n=2$ provably finds a local optimum. This gives a greedy algorithm for finding the exogenous variable with minimum $H_1$ (Shannon Entropy). Our greedy entropy-based causal inference algorithm has similar performance to the state of the art additive noise models in real datasets. One advantage of our approach is that we make no use of the values of random variables but only their distributions. Our method can therefore be used for causal inference for both ordinal and also categorical data, unlike additive noise models.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Single Pass PCA of Matrix Products

In this paper we present a new algorithm for computing a low rank approximation of the product $A^TB$ by taking only a single pass of the two matrices $A$ and $B$. The straightforward way to do this is to (a) first sketch $A$ and $B$ individually, and then (b) find the top components using PCA on the sketch. Our algorithm in contrast retains additional summary information about $A,B$ (e.g. row and column norms etc.) and uses this additional information to obtain an improved approximation from the sketches. Our main analytical result establishes a comparable spectral norm guarantee to existing two-pass methods; in addition we also provide results from an Apache Spark implementation that shows better computational and statistical performance on real-world and synthetic evaluation datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs

We study the problem of approximating the $3$-profile of a large graph. $3$-profiles are generalizations of triangle counts that specify the number of times a small graph appears as an induced subgraph of a large graph. Our algorithm uses the novel concept of $3$-profile sparsifiers: sparse graphs that can be used to approximate the full $3$-profile counts for a given large graph. Further, we study the problem of estimating local and ego $3$-profiles, two graph quantities that characterize the local neighborhood of each vertex of a graph. Our algorithm is distributed and operates as a vertex program over the GraphLab PowerGraph framework. We introduce the concept of edge pivoting which allows us to collect $2$-hop information without maintaining an explicit $2$-hop neighborhood list at each vertex. This enables the computation of all the local $3$-profiles in parallel with minimal communication. We test out implementation in several experiments scaling up to $640$ cores on Amazon EC2. We find that our algorithm can estimate the $3$-profile of a graph in approximately the same time as triangle counting. For the harder problem of ego $3$-profiles, we introduce an algorithm that can estimate profiles of hundreds of thousands of vertices in parallel, in the timescale of minutes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Finite Length Analysis of Caching-Aided Coded Multicasting

In this work, we study a noiseless broadcast link serving $K$ users whose requests arise from a library of $N$ files. Every user is equipped with a cache of size $M$ files each. It has been shown that by splitting all the files into packets and placing individual packets in a random independent manner across all the caches, it requires at most $N/M$ file transmissions for any set of demands from the library. The achievable delivery scheme involves linearly combining packets of different files following a greedy clique cover solution to the underlying index coding problem. This remarkable multiplicative gain of random placement and coded delivery has been established in the asymptotic regime when the number of packets per file $F$ scales to infinity. In this work, we initiate the finite-length analysis of random caching schemes when the number of packets $F$ is a function of the system parameters $M,N,K$. Specifically, we show that existing random placement and clique cover delivery schemes that achieve optimality in the asymptotic regime can have at most a multiplicative gain of $2$ if the number of packets is sub-exponential. Further, for any clique cover based coded delivery and a large class of random caching schemes, that includes the existing ones, we show that the number of packets required to get a multiplicative gain of $\frac{4}{3}g$ is at least $O((N/M)^g)$. We exhibit a random placement and an efficient clique cover based coded delivery scheme that approximately achieves this lower bound. We also provide tight concentration results that show that the average (over the random caching involved) number of transmissions concentrates very well requiring only polynomial number of packets in the rest of the parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

FrogWild! -- Fast PageRank Approximations on Graph Engines

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs of running traditional PageRank algorithms. Our algorithm can be seen as a quantized version of power iteration that performs multiple parallel random walks over a directed graph. One important innovation is that we introduce a modification to the GraphLab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional PageRank algorithms, thus greatly reducing the per-iteration cost of PageRank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate PageRank. Our main theoretical innovation is the analysis of the correlations introduced by this partial synchronization process and a bound establishing that our approximation is close to the true PageRank vector. We implement our algorithm in GraphLab and compare it against the default PageRank implementation. We show that our algorithm is very fast, performing each iteration in less than one second on the Twitter graph and can be up to 7x faster compared to the standard GraphLab PageRank implementation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Learning Causal Graphs with Small Interventions

We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previous work has focused on the use of separating systems for complete graphs for this task. We prove that any deterministic adaptive algorithm needs to be a separating system in order to learn complete graphs in the worst case. In addition, we present a novel separating system construction, whose size is close to optimal and is arguably simpler than previous work in combinatorics. We also develop a novel information theoretic lower bound on the number of interventions that applies in full generality, including for randomized adaptive learning algorithms. For general chordal graphs, we derive worst case lower bounds on the number of interventions. Building on observations about induced trees, we give a new deterministic adaptive algorithm to learn directions on any chordal skeleton completely. In the worst case, our achievable scheme is an $α$-approximation algorithm where $α$ is the independence number of the graph. We also show that there exist graph classes for which the sufficient number of experiments is close to the lower bound. In the other extreme, there are graph classes for which the required number of experiments is multiplicatively $α$ away from our lower bound. In simulations, our algorithm almost always performs very close to the lower bound, while the approach based on separating systems for complete graphs is significantly worse for random chordal graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Approximating the Sum-Rate for Multiple-Unicasts

We study upper bounds on the sum-rate of multiple-unicasts. We approximate the Generalized Network Sharing Bound (GNS cut) of the multiple-unicasts network coding problem with $k$ independent sources. Our approximation algorithm runs in polynomial time and yields an upper bound on the joint source entropy rate, which is within an $O(\log^2 k)$ factor from the GNS cut. It further yields a vector-linear network code that achieves joint source entropy rate within an $O(\log^2 k)$ factor from the GNS cut, but \emph{not} with independent sources: the code induces a correlation pattern among the sources. Our second contribution is establishing a separation result for vector-linear network codes: for any given field $\mathbb{F}$ there exist networks for which the optimum sum-rate supported by vector-linear codes over $\mathbb{F}$ for independent sources can be multiplicatively separated by a factor of $k^{1-δ}$, for any constant ${δ>0}$, from the optimum joint entropy rate supported by a code that allows correlation between sources. Finally, we establish a similar separation result for the asymmetric optimum vector-linear sum-rates achieved over two distinct fields $\mathbb{F}_{p}$ and $\mathbb{F}_{q}$ for independent sources, revealing that the choice of field can heavily impact the performance of a linear network code.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sparse PCA via Bipartite Matchings

We consider the following multi-component sparse PCA problem: given a set of data points, we seek to extract a small number of sparse components with disjoint supports that jointly capture the maximum possible variance. These components can be computed one by one, repeatedly solving the single-component problem and deflating the input data matrix, but as we show this greedy procedure is suboptimal. We present a novel algorithm for sparse PCA that jointly optimizes multiple disjoint components. The extracted features capture variance that lies within a multiplicative factor arbitrarily close to 1 from the optimal. Our algorithm is combinatorial and computes the desired components by solving multiple instances of the bipartite maximum weight matching problem. Its complexity grows as a low order polynomial in the ambient dimension of the input data matrix, but exponentially in its rank. However, it can be effectively applied on a low-dimensional sketch of the data; this allows us to obtain polynomial-time approximation guarantees via spectral bounds. We evaluate our algorithm on real data-sets and empirically demonstrate that in many cases it outperforms existing, deflation-based approaches.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stay on path: PCA along graph paths

We introduce a variant of (sparse) PCA in which the set of feasible support sets is determined by a graph. In particular, we consider the following setting: given a directed acyclic graph $G$ on $p$ vertices corresponding to variables, the non-zero entries of the extracted principal component must coincide with vertices lying along a path in $G$. From a statistical perspective, information on the underlying network may potentially reduce the number of observations required to recover the population principal component. We consider the canonical estimator which optimally exploits the prior knowledge by solving a non-convex quadratic maximization on the empirical covariance. We introduce a simple network and analyze the estimator under the spiked covariance model. We show that side information potentially improves the statistical complexity. We propose two algorithms to approximate the solution of the constrained quadratic maximization, and recover a component with the desired properties. We empirically evaluate our schemes on synthetic and real datasets.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Auditing for Distributed Storage Systems

Distributed storage codes have recently received a lot of attention in the community. Independently, another body of work has proposed integrity checking schemes for cloud storage, none of which, however, is customized for coding-based storage or can efficiently support repair. In this work, we bridge the gap between these two currently disconnected bodies of work. We propose NC-Audit, a novel cryptography-based remote data integrity checking scheme, designed specifically for network coding-based distributed storage systems. NC-Audit combines, for the first time, the following desired properties: (i) efficient checking of data integrity, (ii) efficient support for repairing failed nodes, and (iii) protection against information leakage when checking is performed by a third party. The key ingredient of the design of NC-Audit is a novel combination of SpaceMac, a homomorphic message authentication code (MAC) scheme for network coding, and NCrypt, a novel chosen-plaintext attack (CPA) secure encryption scheme that is compatible with SpaceMac. Our evaluation of a Java implementation of NC-Audit shows that an audit costs the storage node and the auditor a modest amount computation time and lower bandwidth than prior work.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Batch Codes through Dense Graphs without Short Cycles

Consider a large database of $n$ data items that need to be stored using $m$ servers. We study how to encode information so that a large number $k$ of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai [17]. We give families of multiset batch codes with asymptotically optimal rates of the form $1-1/\text{poly}(k)$ and a number of servers $m$ scaling polynomially in the number of read requests $k$. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graph-theoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounding Multiple Unicasts through Index Coding and Locally Repairable Codes

We establish a duality result between linear index coding and Locally Repairable Codes (LRCs). Specifically, we show that a natural extension of LRCs we call Generalized Locally Repairable Codes (GLCRs) are exactly dual to linear index codes. In a GLRC, every node is decodable from a specific set of other nodes and these sets induce a recoverability directed graph. We show that the dual linear subspace of a GLRC is a solution to an index coding instance where the side information graph is this GLRC recoverability graph. We show that the GLRC rate is equivalent to the complementary index coding rate, i.e. the number of transmissions saved by coding. Our second result uses this duality to establish a new upper bound for the multiple unicast network coding problem. In multiple unicast network coding, we are given a directed acyclic graph and r sources that want to send independent messages to r corresponding destinations. Our new upper bound is efficiently computable and relies on a strong approximation result for complementary index coding. We believe that our bound could lead to a logarithmic approximation factor for multiple unicast network coding if a plausible connection we state is verified.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Graph Theory versus Minimum Rank for Index Coding

We obtain novel index coding schemes and show that they provably outperform all previously known graph theoretic bounds proposed so far. Further, we establish a rather strong negative result: all known graph theoretic bounds are within a logarithmic factor from the chromatic number. This is in striking contrast to minrank since prior work has shown that it can outperform the chromatic number by a polynomial factor in some cases. The conclusion is that all known graph theoretic bounds are not much stronger than the chromatic number.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Index Coding with Coded Side-Information

This letter investigates a new class of index coding problems. One sender broadcasts packets to multiple users, each desiring a subset, by exploiting prior knowledge of linear combinations of packets. We refer to this class of problems as index coding with coded side-information. Our aim is to characterize the minimum index code length that the sender needs to transmit to simultaneously satisfy all user requests. We show that the optimal binary vector index code length is equal to the minimum rank (minrank) of a matrix whose elements consist of the sets of desired packet indices and side- information encoding matrices. This is the natural extension of matrix minrank in the presence of coded side information. Using the derived expression, we propose a greedy randomized algorithm to minimize the rank of the derived matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Locality and Availability in Distributed Storage

This paper studies the problem of code symbol availability: a code symbol is said to have $(r, t)$-availability if it can be reconstructed from $t$ disjoint groups of other symbols, each of size at most $r$. For example, $3$-replication supports $(1, 2)$-availability as each symbol can be read from its $t= 2$ other (disjoint) replicas, i.e., $r=1$. However, the rate of replication must vanish like $\frac{1}{t+1}$ as the availability increases. This paper shows that it is possible to construct codes that can support a scaling number of parallel reads while keeping the rate to be an arbitrarily high constant. It further shows that this is possible with the minimum distance arbitrarily close to the Singleton bound. This paper also presents a bound demonstrating a trade-off between minimum distance, availability and locality. Our codes match the aforementioned bound and their construction relies on combinatorial objects called resolvable designs. From a practical standpoint, our codes seem useful for distributed storage applications involving hot data, i.e., the information which is frequently accessed by multiple processes in parallel.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Locally Repairable Codes

Distributed storage systems for large-scale applications typically use replication for reliability. Recently, erasure codes were used to reduce the large storage overhead, while increasing data reliability. A main limitation of off-the-shelf erasure codes is their high-repair cost during single node failure events. A major open problem in this area has been the design of codes that {\it i)} are repair efficient and {\it ii)} achieve arbitrarily high data rates. In this paper, we explore the repair metric of {\it locality}, which corresponds to the number of disk accesses required during a {\color{black}single} node repair. Under this metric we characterize an information theoretic trade-off that binds together locality, code distance, and the storage capacity of each node. We show the existence of optimal {\it locally repairable codes} (LRCs) that achieve this trade-off. The achievability proof uses a locality aware flow-graph gadget which leads to a randomized code construction. Finally, we present an optimal and explicit LRC that achieves arbitrarily high data-rates. Our locality optimal construction is based on simple combinations of Reed-Solomon blocks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Network Codes for Real-Time Applications

We consider the scenario of broadcasting for real-time applications and loss recovery via instantly decodable network coding. Past work focused on minimizing the completion delay, which is not the right objective for real-time applications that have strict deadlines. In this work, we are interested in finding a code that is instantly decodable by the maximum number of users. First, we prove that this problem is NP-Hard in the general case. Then we consider the practical probabilistic scenario, where users have i.i.d. loss probability and the number of packets is linear or polynomial in the number of users. In this scenario, we provide a polynomial-time (in the number of users) algorithm that finds the optimal coded packet. The proposed algorithm is evaluated using both simulation and real network traces of a real-time Android application. Both results show that the proposed coding scheme significantly outperforms the state-of-the-art baselines: an optimal repetition code and a COPE-like greedy scheme.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Information Theoretic Limits of Learning Ising Models

We provide a general framework for computing lower-bounds on the sample complexity of recovering the underlying graphs of Ising models, given i.i.d samples. While there have been recent results for specific graph classes, these involve fairly extensive technical arguments that are specialized to each specific graph class. In contrast, we isolate two key graph-structural ingredients that can then be used to specify sample complexity lower-bounds. Presence of these structural properties makes the graph class hard to learn. We derive corollaries of our main result that not only recover existing recent results, but also provide lower bounds for novel graph classes not considered previously. We also extend our framework to the random graph setting and derive corollaries for Erdős-Rényi graphs in a certain dense setting.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Repairable Fountain Codes

We introduce a new family of Fountain codes that are systematic and also have sparse parities. Given an input of $k$ symbols, our codes produce an unbounded number of output symbols, generating each parity independently by linearly combining a logarithmic number of randomly selected input symbols. The construction guarantees that for any $ε>0$ accessing a random subset of $(1+ε)k$ encoded symbols, asymptotically suffices to recover the $k$ input symbols with high probability. Our codes have the additional benefit of logarithmic locality: a single lost symbol can be repaired by accessing a subset of $O(\log k)$ of the remaining encoded symbols. This is a desired property for distributed storage systems where symbols are spread over a network of storage nodes. Beyond recovery upon loss, local reconstruction provides an efficient alternative for reading symbols that cannot be accessed directly. In our code, a logarithmic number of disjoint local groups is associated with each systematic symbol, allowing multiple parallel reads. Our main mathematical contribution involves analyzing the rank of sparse random matrices with specific structure over finite fields. We rely on establishing that a new family of sparse random bipartite graphs have perfect matchings with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sparse PCA through Low-rank Approximations

We introduce a novel algorithm that computes the $k$-sparse principal component of a positive semidefinite matrix $A$. Our algorithm is combinatorial and operates by examining a discrete set of special vectors lying in a low-dimensional eigen-subspace of $A$. We obtain provable approximation guarantees that depend on the spectral decay profile of the matrix: the faster the eigenvalue decay, the better the quality of our approximation. For example, if the eigenvalues of $A$ follow a power-law decay, we obtain a polynomial-time approximation algorithm for any desired accuracy. A key algorithmic component of our scheme is a combinatorial feature elimination step that is provably safe and in practice significantly reduces the running complexity of our algorithm. We implement our algorithm and test it on multiple artificial and real data sets. Due to the feature elimination step, it is possible to perform sparse PCA on data sets consisting of millions of entries in a few minutes. Our experimental evaluation shows that our scheme is nearly optimal while finding very sparse vectors. We compare to the prior state of the art and show that our scheme matches or outperforms previous algorithms in all tested data sets.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sparse Polynomial Learning and Graph Sketching

Let $f:\{-1,1\}^n$ be a polynomial with at most $s$ non-zero real coefficients. We give an algorithm for exactly reconstructing f given random examples from the uniform distribution on $\{-1,1\}^n$ that runs in time polynomial in $n$ and $2s$ and succeeds if the function satisfies the unique sign property: there is one output value which corresponds to a unique set of values of the participating parities. This sufficient condition is satisfied when every coefficient of f is perturbed by a small random noise, or satisfied with high probability when s parity functions are chosen randomly or when all the coefficients are positive. Learning sparse polynomials over the Boolean domain in time polynomial in $n$ and $2s$ is considered notoriously hard in the worst-case. Our result shows that the problem is tractable for almost all sparse polynomials. Then, we show an application of this result to hypergraph sketching which is the problem of learning a sparse (both in the number of hyperedges and the size of the hyperedges) hypergraph from uniformly drawn random cuts. We also provide experimental results on a real world dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Repair Framework for Scalar MDS Codes

Several works have developed vector-linear maximum-distance separable (MDS) storage codes that min- imize the total communication cost required to repair a single coded symbol after an erasure, referred to as repair bandwidth (BW). Vector codes allow communicating fewer sub-symbols per node, instead of the entire content. This allows non trivial savings in repair BW. In sharp contrast, classic codes, like Reed- Solomon (RS), used in current storage systems, are deemed to suffer from naive repair, i.e. downloading the entire stored message to repair one failed node. This mainly happens because they are scalar-linear. In this work, we present a simple framework that treats scalar codes as vector-linear. In some cases, this allows significant savings in repair BW. We show that vectorized scalar codes exhibit properties that simplify the design of repair schemes. Our framework can be seen as a finite field analogue of real interference alignment. Using our simplified framework, we design a scheme that we call clique-repair which provably identifies the best linear repair strategy for any scalar 2-parity MDS code, under some conditions on the sub-field chosen for vectorization. We specify optimal repair schemes for specific (5,3)- and (6,4)-Reed- Solomon (RS) codes. Further, we present a repair strategy for the RS code currently deployed in the Facebook Analytics Hadoop cluster that leads to 20% of repair BW savings over naive repair which is the repair scheme currently used for this code.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Base-Station Assisted Device-to-Device Communications for High-Throughput Wireless Video Networks

We propose a new scheme for increasing the throughput of video files in cellular communications systems. This scheme exploits (i) the redundancy of user requests as well as (ii) the considerable storage capacity of smartphones and tablets. Users cache popular video files and - after receiving requests from other users - serve these requests via device-to-device localized transmissions. The file placement is optimal when a central control knows a priori the locations of wireless devices when file requests occur. However, even a purely random caching scheme shows only a minor performance loss compared to such a genie-aided scheme. We then analyze the optimal collaboration distance, trading off frequency reuse with the probability of finding a requested file within the collaboration distance. We show that an improvement of spectral efficiency of one to two orders of magnitude is possible, even if there is not very high redundancy in video requests.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

FemtoCaching: Wireless Video Content Delivery through Distributed Caching Helpers

Video on-demand streaming from Internet-based servers is becoming one of the most important services offered by wireless networks today. In order to improve the area spectral efficiency of video transmission in cellular systems, small cells heterogeneous architectures (e.g., femtocells, WiFi off-loading) are being proposed, such that video traffic to nomadic users can be handled by short-range links to the nearest small cell access points (referred to as "helpers"). As the helper deployment density increases, the backhaul capacity becomes the system bottleneck. In order to alleviate such bottleneck we propose a system where helpers with low-rate backhaul but high storage capacity cache popular video files. Files not available from helpers are transmitted by the cellular base station. We analyze the optimum way of assigning files to the helpers, in order to minimize the expected downloading time for files. We distinguish between the uncoded case (where only complete files are stored) and the coded case, where segments of Fountain-encoded versions of the video files are stored at helpers. We show that the uncoded optimum file assignment is NP-hard, and develop a greedy strategy that is provably within a factor 2 of the optimum. Further, for a special case we provide an efficient algorithm achieving a provably better approximation ratio of $1-(1-1/d)^d$, where $d$ is the maximum number of helpers a user can be connected to. We also show that the coded optimum cache assignment problem is convex that can be further reduced to a linear program. We present numerical results comparing the proposed schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Index Coding Problem with Side Information Repositories

To tackle the expected enormous increase in mobile video traffic in cellular networks, an architecture involving a base station along with caching femto stations (referred to as helpers), storing popular files near users, has been proposed [1]. The primary benefit of caching is the enormous increase in downloading rate when a popular file is available at helpers near a user requesting that file. In this work, we explore a secondary benefit of caching in this architecture through the lens of index coding. We assume a system with n users and constant number of caching helpers. Only helpers store files, i.e. have side information. We investigate the following scenario: Each user requests a distinct file that is not found in the set of helpers nearby. Users are served coded packets (through an index code) by an omniscient base station. Every user decodes its desired packet from the coded packets and the side information packets from helpers nearby. We assume that users can obtain any file stored in their neighboring helpers without incurring transmission costs. With respect to the index code employed, we investigate two achievable schemes: 1) XOR coloring based on coloring of the side information graph associated with the problem and 2)Vector XOR coloring based on fractional coloring of the side information graph. We show that the general problem reduces to a canonical problem where every user is connected to exactly one helper under some topological constraints. For the canonical problem, with constant number of helpers (k), we show that the complexity of computing the best XOR/vector XOR coloring schemes are polynomial in the number of users n. The result exploits a special complete bi-partite structure that the side information graphs exhibit for any finite k.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local Graph Coloring and Index Coding

We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal Locally Repairable Codes and Connections to Matroid Theory

Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly sub-optimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and optimal LRCs that are simple to construct. Our construction is based on grouping Reed-Solomon (RS) coded symbols to obtain RS coded symbols over a larger finite field. We then partition these RS symbols in small groups, and re-encode them using a simple local code that offers low repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code generator matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

XORing Elephants: Novel Erasure Codes for Big Data

Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability. This paper shows how to overcome this limitation. We present a novel family of erasure codes that are efficiently repairable and offer higher reliability compared to Reed-Solomon codes. We show analytically that our codes are optimal on a recently identified tradeoff between locality and minimum distance. We implement our new codes in Hadoop HDFS and compare to a currently deployed HDFS module that uses Reed-Solomon codes. Our modified HDFS implementation shows a reduction of approximately 2x on the repair disk I/O and repair network traffic. The disadvantage of the new coding scheme is that it requires 14% more storage compared to Reed-Solomon codes, an overhead shown to be information theoretically optimal to obtain locality. Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Allocations for Heterogenous Distributed Storage

We study the problem of storing a data object in a set of data nodes that fail independently with given probabilities. Our problem is a natural generalization of a homogenous storage allocation problem where all the nodes had the same reliability and is naturally motivated for peer-to-peer and cloud storage systems with different types of nodes. Assuming optimal erasure coding (MDS), the goal is to find a storage allocation (i.e, how much to store in each node) to maximize the probability of successful recovery. This problem turns out to be a challenging combinatorial optimization problem. In this work we introduce an approximation framework based on large deviation inequalities and convex optimization. We propose two approximation algorithms and study the asymptotic performance of the resulting allocations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Connectivity and equilibrium in random games

We study how the structure of the interaction graph of a game affects the existence of pure Nash equilibria. In particular, for a fixed interaction graph, we are interested in whether there are pure Nash equilibria arising when random utility tables are assigned to the players. We provide conditions for the structure of the graph under which equilibria are likely to exist and complementary conditions which make the existence of equilibria highly unlikely. Our results have immediate implications for many deterministic graphs and generalize known results for random games on the complete graph. In particular, our results imply that the probability that bounded degree graphs have pure Nash equilibria is exponentially small in the size of the graph and yield a simple algorithm that finds small nonexistence certificates for a large family of graphs. Then we show that in any strongly connected graph of n vertices with expansion $(1+Ω(1))\log_2(n)$ the distribution of the number of equilibria approaches the Poisson distribution with parameter 1, asymptotically as $n \to +\infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Distributed Storage Allocations

We examine the problem of allocating a given total storage budget in a distributed storage system for maximum reliability. A source has a single data object that is to be coded and stored over a set of storage nodes; it is allowed to store any amount of coded data in each node, as long as the total amount of storage used does not exceed the given budget. A data collector subsequently attempts to recover the original data object by accessing only the data stored in a random subset of the nodes. By using an appropriate code, successful recovery can be achieved whenever the total amount of data accessed is at least the size of the original data object. The goal is to find an optimal storage allocation that maximizes the probability of successful recovery. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models. The optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) are determined for a variety of cases. Our results indicate that the optimal allocations often have nonintuitive structure and are difficult to specify. We also show that depending on the circumstances, coding may or may not be beneficial for reliable storage.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Femtocaching and Device-to-Device Collaboration: A New Architecture for Wireless Video Distribution

We present a new architecture to handle the ongoing explosive increase in the demand for video content in wireless networks. It is based on distributed caching of the content in femto-basestations with small or non-existing backhaul capacity but with considerable storage space, called helper nodes. We also consider using the mobile terminals themselves as caching helpers, which can distribute video through device-to-device communications. This approach allows an improvement in the video throughput without deployment of any additional infrastructure. The new architecture can improve video throughput by one to two orders-of-magnitude.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Delay Advantage of Coding in Packet Erasure Networks

We consider the delay of network coding compared to routing with retransmissions in packet erasure networks with probabilistic erasures. We investigate the sub-linear term in the block delay required for unicasting $n$ packets and show that there is an unbounded gap between network coding and routing. In particular, we show that delay benefit of network coding scales at least as $\sqrt{n}$. Our analysis of the delay function for the routing strategy involves a major technical challenge of computing the expectation of the maximum of two negative binomial random variables. This problem has been studied previously and we derive the first exact characterization which may be of independent interest. We also use a martingale bounded differences argument to show that the actual coding delay is tightly concentrated around its expectation.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Scaling Behaviors of Wireless Device-to-Device Communications with Distributed Caching

We analyze a novel architecture for caching popular video content to enable wireless device-to-device collaboration. We focus on the asymptotic scaling characteristics and show how they depends on video content popularity statistics. We identify a fundamental conflict between collaboration distance and interference and show how to optimize the transmission power to maximize frequency reuse. Our main result is a closed form expression of the optimal collaboration distance as a function of the model parameters. Under the common assumption of a Zipf distribution for content reuse, we show that if the Zipf exponent is greater than 1, it is possible to have a number of D2D interference-free collaboration pairs that scales linearly in the number of nodes. If the Zipf exponent is smaller than 1, we identify the best possible scaling in the number of D2D collaborating links. Surprisingly, a very simple distributed caching policy achieves the optimal scaling behavior and therefore there is no need to centrally coordinate what each node is caching.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Wireless Device-to-Device Communications with Distributed Caching

We introduce a novel wireless device-to-device (D2D) collaboration architecture that exploits distributed storage of popular content to enable frequency reuse. We identify a fundamental conflict between collaboration distance and interference and show how to optimize the transmission power to maximize frequency reuse. Our analysis depends on the user content request statistics which are modeled by a Zipf distribution. Our main result is a closed form expression of the optimal collaboration distance as a function of the content reuse distribution parameters. We show that if the Zipf exponent of the content reuse distribution is greater than 1, it is possible to have a number of D2D interference-free collaboration pairs that scales linearly in the number of nodes. If the Zipf exponent is smaller than 1, we identify the best possible scaling in the number of D2D collaborating links. Surprisingly, a very simple distributed caching policy achieves the optimal scaling behavior and therefore there is no need to centrally coordinate what each node is caching.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Storage Allocations for Optimal Delay

We examine the problem of creating an encoded distributed storage representation of a data object for a network of mobile storage nodes so as to achieve the optimal recovery delay. A source node creates a single data object and disseminates an encoded representation of it to other nodes for storage, subject to a given total storage budget. A data collector node subsequently attempts to recover the original data object by contacting other nodes and accessing the data stored in them. By using an appropriate code, successful recovery is achieved when the total amount of data accessed is at least the size of the original data object. The goal is to find an allocation of the given budget over the nodes that optimizes the recovery delay incurred by the data collector; two objectives are considered: (i) maximization of the probability of successful recovery by a given deadline, and (ii) minimization of the expected recovery delay. We solve the problem completely for the second objective in the case of symmetric allocations (in which all nonempty nodes store the same amount of data), and show that the optimal symmetric allocation for the two objectives can be quite different. A simple data dissemination and storage protocol for a mobile delay-tolerant network is evaluated under various scenarios via simulations. Our results show that the choice of storage allocation can have a significant impact on the recovery delay performance, and that coding may or may not be beneficial depending on the circumstances.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Distributed Storage Codes through Hadamard Designs

In distributed storage systems that employ erasure coding, the issue of minimizing the total {\it repair bandwidth} required to exactly regenerate a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Minimizing it requires that undesired data during a repair align in the smallest possible spaces, using the concept of interference alignment (IA). Here, a points-on-a-lattice representation of the symbol extension IA of Cadambe {\it et al.} provides cues to perfect IA instances which we combine with fundamental properties of Hadamard matrices to construct a new storage code with favorable repair properties. Specifically, we build an explicit $(k+2,k)$ storage code over $\mathbb{GF}(3)$, whose single systematic node failures can be repaired with bandwidth that matches exactly the theoretical minimum. Moreover, the repair of single parity node failures generates at most the same repair bandwidth as any systematic node failure. Our code can tolerate any single node failure and any pair of failures that involves at most one systematic failure.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Interference Alignment as a Rank Constrained Rank Minimization

We show that the maximization of the sum degrees-of-freedom for the static flat-fading multiple-input multiple-output (MIMO) interference channel is equivalent to a rank constrained rank minimization problem (RCRM), when the signal spaces span all available dimensions. The rank minimization corresponds to maximizing interference alignment (IA) so that interference spans the lowest dimensional subspace possible. The rank constraints account for the useful signal spaces spanning all available spatial dimensions. That way, we reformulate all IA requirements to requirements involving ranks. Then, we present a convex relaxation of the RCRM problem inspired by recent results in compressed sensing and low-rank matrix completion theory that rely on approximating rank with the nuclear norm. We show that the convex envelope of the sum of ranks of the interference matrices is the normalized sum of their corresponding nuclear norms and introduce tractable constraints that are asymptotically equivalent to the rank constraints for the initial problem. We also show that our heuristic relaxation can be tuned for the multi-cell interference channel. Furthermore, we experimentally show that in many cases the proposed algorithm attains perfect interference alignment and in some cases outperforms previous approaches for finding precoding and zero-forcing matrices for interference alignment.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

LDPC Codes for Compressed Sensing

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, \emph{channel coding linear programming decoding (CC-LPD)}, which is a well-known relaxation o maximum-likelihood channel decoding for binary linear codes, and, on the other hand, \emph{compressed sensing linear programming decoding (CS-LPD)}, also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an under-determined system of linear equations. More specifically, we establis a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of "good" channel codes can be used as provably "good" measurement matrices under basis pursuit. In particular, we provide the first deterministic construction of compressed sensing measurement matrices with an order-optimal number of rows using high-girth low-density parity-check (LDPC) codes constructed by Gallager.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Repair Optimal Erasure Codes through Hadamard Designs

In distributed storage systems that employ erasure coding, the issue of minimizing the total {\it communication} required to exactly rebuild a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Designing high-rate maximum-distance separable (MDS) codes that achieve the optimum repair communication has been a well-known open problem. In this work, we use Hadamard matrices to construct the first explicit 2-parity MDS storage code with optimal repair properties for all single node failures, including the parities. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite file size, or number of extensions. We generalize this construction to design $m$-parity MDS codes that achieve the optimum repair communication for single systematic node failures and show that there is an interesting connection between our $m$-parity codes and the systematic-repair optimal permutation-matrix based codes of Tamo {\it et al.} \cite{Tamo} and Cadambe {\it et al.} \cite{PermCodes_ISIT, PermCodes}.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Reweighted LP Decoding for LDPC Codes

We introduce a novel algorithm for decoding binary linear codes by linear programming. We build on the LP decoding algorithm of Feldman et al. and introduce a post-processing step that solves a second linear program that reweights the objective function based on the outcome of the original LP decoder output. Our analysis shows that for some LDPC ensembles we can improve the provable threshold guarantees compared to standard LP decoding. We also show significant empirical performance gains for the reweighted LP decoding algorithm with very small additional computational complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Simple Regenerating Codes: Network Coding for Cloud Storage

Network codes designed specifically for distributed storage systems have the potential to provide dramatically higher storage efficiency for the same availability. One main challenge in the design of such codes is the exact repair problem: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. One of the main open problems in this emerging area has been the design of simple coding schemes that allow exact and low cost repair of failed nodes and have high data rates. In particular, all prior known explicit constructions have data rates bounded by 1/2. In this paper we introduce the first family of distributed storage codes that have simple look-up repair and can achieve arbitrarily high rates. Our constructions are very simple to implement and perform exact repair by simple XORing of packets. We experimentally evaluate the proposed codes in a realistic cloud storage simulator and show significant benefits in both performance and reliability compared to replication and standard Reed-Solomon codes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Impact of Mobility on Gossip Algorithms

The influence of node mobility on the convergence time of averaging gossip algorithms in networks is studied. It is shown that a small number of fully mobile nodes can yield a significant decrease in convergence time. A method is developed for deriving lower bounds on the convergence time by merging nodes according to their mobility pattern. This method is used to show that if the agents have one-dimensional mobility in the same direction the convergence time is improved by at most a constant. Upper bounds are obtained on the convergence time using techniques from the theory of Markov chains and show that simple models of mobility can dramatically accelerate gossip as long as the mobility paths significantly overlap. Simulations verify that different mobility patterns can have significantly different effects on the convergence of distributed algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Survey on Network Codes for Distributed Storage

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Distributed Storage Codes Meet Multiple-Access Wiretap Channels

We consider {\it i)} the overhead minimization of maximum-distance separable (MDS) storage codes for the repair of a single failed node and {\it ii)} the total secure degrees-of-freedom (S-DoF) maximization in a multiple-access compound wiretap channel. We show that the two problems are connected. Specifically, the overhead minimization for a single node failure of an {\it optimal} MDS code, i.e. one that can achieve the information theoretic overhead minimum, is equivalent to maximizing the S-DoF in a multiple-access compound wiretap channel. Additionally, we show that maximizing the S-DoF in a multiple-access compound wiretap channel is equivalent to minimizing the overhead of an MDS code for the repair of a departed node. An optimal MDS code maps to a full S-DoF channel and a full S-DoF channel maps to an MDS code with minimum repair overhead for one failed node. We also state a general framework for code-to-channel and channel-to-code mappings and performance bounds between the two settings. The underlying theme for all connections presented is interference alignment (IA). The connections between the two problems become apparent when we restate IA as an optimization problem. Specifically, we formulate the overhead minimization and the S-DoF maximization as rank constrained, sum-rank and max-rank minimization problems respectively. The derived connections allow us to map repair strategies of recently discovered repair codes to beamforming matrices and characterize the maximum S-DoF for the single antenna multiple-access compound wiretap channel.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Efficient Algorithms for Renewable Energy Allocation to Delay Tolerant Consumers

We investigate the problem of allocating energy from renewable sources to flexible consumers in electricity markets. We assume there is a renewable energy supplier that provides energy according to a time-varying (and possibly unpredictable) supply process. The plant must serve consumers within a specified delay window, and incurs a cost of drawing energy from other (possibly non-renewable) sources if its own supply is not sufficient to meet the deadlines. We formulate two stochastic optimization problems: The first seeks to minimize the time average cost of using the other sources (and hence strives for the most efficient utilization of the renewable source). The second allows the renewable source to dynamically set a price for its service, and seeks to maximize the resulting time average profit. These problems are solved via the Lyapunov optimization technique. Our resulting algorithms do not require knowledge of the statistics of the time-varying supply and demand processes and are robust to arbitrary sample path variations.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Gossip Algorithms for Distributed Signal Processing

Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This article presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rebuilding for Array Codes in Distributed Storage Systems

In distributed storage systems that use coding, the issue of minimizing the communication required to rebuild a storage node after a failure arises. We consider the problem of repairing an erased node in a distributed storage system that uses an EVENODD code. EVENODD codes are maximum distance separable (MDS) array codes that are used to protect against erasures, and only require XOR operations for encoding and decoding. We show that when there are two redundancy nodes, to rebuild one erased systematic node, only 3/4 of the information needs to be transmitted. Interestingly, in many cases, the required disk I/O is also minimized.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Security in Distributed Storage Systems by Communicating a Logarithmic Number of Bits

We investigate the problem of maintaining an encoded distributed storage system when some nodes contain adversarial errors. Using the error-correction capabilities that are built into the existing redundancy of the system, we propose a simple linear hashing scheme to detect errors in the storage nodes. Our main result is that for storing a data object of total size $\size$ using an $(n,k)$ MDS code over a finite field $\F_q$, up to $t_1=\lfloor(n-k)/2\rfloor$ errors can be detected, with probability of failure smaller than $1/ \size$, by communicating only $O(n(n-k)\log \size)$ bits to a trusted verifier. Our result constructs small projections of the data that preserve the errors with high probability and builds on a pseudorandom generator that fools linear functions. The transmission rate achieved by our scheme is asymptotically equal to the min-cut capacity between the source and any receiver.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Symmetric Allocations for Distributed Storage

We consider the problem of optimally allocating a given total storage budget in a distributed storage system. A source has a data object which it can code and store over a set of storage nodes; it is allowed to store any amount of coded data in each node, as long as the total amount of storage used does not exceed the given budget. A data collector subsequently attempts to recover the original data object by accessing each of the nodes independently with some constant probability. By using an appropriate code, successful recovery occurs when the total amount of data in the accessed nodes is at least the size of the original data object. The goal is to find an optimal storage allocation that maximizes the probability of successful recovery. This optimization problem is challenging because of its discrete nature and nonconvexity, despite its simple formulation. Symmetric allocations (in which all nonempty nodes store the same amount of data), though intuitive, may be suboptimal; the problem is nontrivial even if we optimize over only symmetric allocations. Our main result shows that the symmetric allocation that spreads the budget maximally over all nodes is asymptotically optimal in a regime of interest. Specifically, we derive an upper bound for the suboptimality of this allocation and show that the performance gap vanishes asymptotically in the specified regime. Further, we explicitly find the optimal symmetric allocation for a variety of cases. Our results can be applied to distributed storage systems and other problems dealing with reliability under uncertainty, including delay tolerant networks (DTNs) and content delivery networks (CDNs).

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Probabilistic Analysis of Linear Programming Decoding

We initiate the probabilistic analysis of linear programming (LP) decoding of low-density parity-check (LDPC) codes. Specifically, we show that for a random LDPC code ensemble, the linear programming decoder of Feldman et al. succeeds in correcting a constant fraction of errors with high probability. The fraction of correctable errors guaranteed by our analysis surpasses previous non-asymptotic results for LDPC codes, and in particular exceeds the best previous finite-length result on LP decoding by a factor greater than ten. This improvement stems in part from our analysis of probabilistic bit-flipping channels, as opposed to adversarial channels. At the core of our analysis is a novel combinatorial characterization of LP decoding success, based on the notion of a generalized matching. An interesting by-product of our analysis is to establish the existence of ``probabilistic expansion'' in random bipartite graphs, in which one requires only that almost every (as opposed to every) set of a certain size expands, for sets much larger than in the classical worst-case setting.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Decentralized Erasure Codes for Distributed Networked Storage

We consider the problem of constructing an erasure code for storage over a network when the data sources are distributed. Specifically, we assume that there are n storage nodes with limited memory and k<n sources generating the data. We want a data collector, who can appear anywhere in the network, to query any k storage nodes and be able to retrieve the data. We introduce Decentralized Erasure Codes, which are linear codes with a specific randomized structure inspired by network coding on random bipartite graphs. We show that decentralized erasure codes are optimally sparse, and lead to reduced communication, storage and computation cost over random linear coding.

0 citations0 reviewsNo code linkedOpen access