OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Storage Allocations
Venue: arXiv cs.IT 2012
Year: 2012

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.
Counting in Graph Covers: A Combinatorial Characterization of the Bethe Entropy Function
Venue: arXiv cs.IT 2012
Year: 2012

We present a combinatorial characterization of the Bethe entropy function of a factor graph, such a characterization being in contrast to the original, analytical, definition of this function. We achieve this combinatorial characterization by counting valid configurations in finite graph covers of the factor graph. Analogously, we give a combinatorial characterization of the Bethe partition function, whose original definition was also of an analytical nature. As we point out, our approach has similarities to the replica method, but also stark differences. The above findings are a natural backdrop for introducing a decoder for graph-based codes that we will call symbolwise graph-cover decoding, a decoder that extends our earlier work on blockwise graph-cover decoding. Both graph-cover decoders are theoretical tools that help towards a better understanding of message-passing iterative decoding, namely blockwise graph-cover decoding links max-product (min-sum) algorithm decoding with linear programming decoding, and symbolwise graph-cover decoding links sum-product algorithm decoding with Bethe free energy function minimization at temperature one. In contrast to the Gibbs entropy function, which is a concave function, the Bethe entropy function is in general not concave everywhere. In particular, we show that every code picked from an ensemble of regular low-density parity-check codes with minimum Hamming distance growing (with high probability) linearly with the block length has a Bethe entropy function that is convex in certain regions of its domain.
URSA: A System for Uniform Reduction to SAT
Venue: arXiv cs.AI 2012
Year: 2012

There are a huge number of problems, from various areas, being solved by reducing them to SAT. However, for many applications, translation into SAT is performed by specialized, problem-specific tools. In this paper we describe a new system for uniform solving of a wide class of problems by reducing them to SAT. The system uses a new specification language URSA that combines imperative and declarative programming paradigms. The reduction to SAT is defined precisely by the semantics of the specification language. The domain of the approach is wide (e.g., many NP-complete problems can be simply specified and then solved by the system) and there are problems easily solvable by the proposed system, while they can be hardly solved by using other programming languages or constraint programming systems. So, the system can be seen not only as a tool for solving problems by reducing them to SAT, but also as a general-purpose constraint solving system (for finite domains). In this paper, we also describe an open-source implementation of the described approach. The performed experiments suggest that the system is competitive to state-of-the-art related modelling systems.
Tight Cell-Probe Bounds for Online Integer Multiplication and Convolution
Venue: arXiv cs.DS 2012
Year: 2012

We show tight bounds for both online integer multiplication and convolution in the cell-probe model with word size w. For the multiplication problem, one pair of digits, each from one of two n digit numbers that are to be multiplied, is given as input at step i. The online algorithm outputs a single new digit from the product of the numbers before step i+1. We give a Theta((d/w)*log n) bound on average per output digit for this problem where 2^d is the maximum value of a digit. In the convolution problem, we are given a fixed vector V of length n and we consider a stream in which numbers arrive one at a time. We output the inner product of V and the vector that consists of the last n numbers of the stream. We show a Theta((d/w)*log n) bound for the number of probes required per new number in the stream. All the bounds presented hold under randomisation and amortisation. Multiplication and convolution are central problems in the study of algorithms which also have the widest range of practical applications.
Secret Writing on Dirty Paper: A Deterministic View
Venue: arXiv cs.IT 2012
Year: 2012

Recently there has been a lot of success in using the deterministic approach to provide approximate characterization of Gaussian network capacity. In this paper, we take a deterministic view and revisit the problem of wiretap channel with side information. A precise characterization of the secrecy capacity is obtained for a linear deterministic model, which naturally suggests a coding scheme which we show to achieve the secrecy capacity of the degraded Gaussian model (dubbed as "secret writing on dirty paper") to within half a bit.
Multi-Level Steganography: Improving Hidden Communication in Networks
Venue: arXiv cs.CR 2012
Year: 2012

The paper presents Multi-Level Steganography (MLS), which defines a new concept for hidden communication in telecommunication networks. In MLS, at least two steganographic methods are utilised simultaneously, in such a way that one method (called the upper-level) serves as a carrier for the second one (called the lower-level). Such a relationship between two (or more) information hiding solutions has several potential benefits. The most important is that the lower-level method steganographic bandwidth can be utilised to make the steganogram unreadable even after the detection of the upper-level method: e.g., it can carry a cryptographic key that deciphers the steganogram carried by the upper-level one. It can also be used to provide the steganogram with integrity. Another important benefit is that the lower-layer method may be used as a signalling channel in which to exchange information that affects the way that the upper-level method functions, thus possibly making the steganographic communication harder to detect. The prototype of MLS for IP networks was also developed, and the experimental results are included in this paper.
NP has log-space verifiers with fixed-size public quantum registers
Venue: arXiv cs.CC 2012
Year: 2012

In classical Arthur-Merlin games, the class of languages whose membership proofs can be verified by Arthur using logarithmic space (AM(log-space)) coincides with the class P \cite{Co89}. In this note, we show that if Arthur has a fixed-size quantum register (the size of the register does not depend on the length of the input) instead of another source of random bits, membership in any language in NP can be verified with any desired error bound.
Computing pseudotriangulations via branched coverings
Venue: arXiv cs.CG 2012
Year: 2012

We describe an efficient algorithm to compute a pseudotriangulation of a finite planar family of pairwise disjoint convex bodies presented by its chirotope. The design of the algorithm relies on a deepening of the theory of visibility complexes and on the extension of that theory to the setting of branched coverings. The problem of computing a pseudotriangulation that contains a given set of bitangent line segments is also examined.
Limit Theorems in Hidden Markov Models
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, under mild assumptions, we derive a law of large numbers, a central limit theorem with an error estimate, an almost sure invariance principle and a variant of Chernoff bound in finite-state hidden Markov models. These limit theorems are of interest in certain ares in statistics and information theory. Particularly, we apply the limit theorems to derive the rate of convergence of the maximum likelihood estimator in finite-state hidden Markov models.
Ranking-Based Black-Box Complexity
Venue: arXiv cs.NE 2012
Year: 2012

Randomized search heuristics such as evolutionary algorithms, simulated annealing, and ant colony optimization are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. While several strong runtime analysis results have appeared in the last 20 years, a powerful complexity theory for such algorithms is yet to be developed. We enrich the existing notions of black-box complexity by the additional restriction that not the actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the black-box algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems. For example, the class of all binary-value functions has a black-box complexity of $O(\log n)$ in the previous black-box models, but has a ranking-based complexity of $Θ(n)$. For the class of all OneMax functions, we present a ranking-based black-box algorithm that has a runtime of $Θ(n / \log n)$, which shows that the OneMax problem does not become harder with the additional ranking-basedness restriction.
Diversity of MMSE MIMO Receivers
Venue: arXiv cs.IT 2012
Year: 2012

In most MIMO systems, the family of waterfall error curves, calculated at different spectral efficiencies, are asymptotically parallel at high SNR. In other words, most MIMO systems exhibit a single diversity value for all fixed rates. The MIMO MMSE receiver does not follow this pattern and exhibits a varying diversity in its family of error curves. This work analyzes this interesting behavior of the MMSE MIMO receiver and produces the MMSE MIMO diversity at all rates. The diversity of the quasi-static flat-fading MIMO channel consisting of any arbitrary number of transmit and receive antennas is fully characterized, showing that full spatial diversity is possible if and only if the rate is within a certain bound which is a function of the number of antennas. For other rates, the available diversity is fully characterized. At sufficiently low rates, the MMSE receiver has a diversity similar to the maximum likelihood receiver (maximal diversity), while at high rates it performs similarly to the zero-forcing receiver (minimal diversity). Linear receivers are also studied in the context of the MIMO multiple access channel (MAC). Then, the quasi-static frequency selective MIMO channel is analyzed under zero-padding (ZP) and cyclic-prefix (CP) block transmissions and MMSE reception, and lower and upper bounds on diversity are derived. For the special case of SIMO under CP, it is shown that the above-mentioned bounds are tight.
Codes and Designs Related to Lifted MRD Codes
Venue: arXiv cs.IT 2012
Year: 2012

Lifted maximum rank distance (MRD) codes, which are constant dimension codes, are considered. It is shown that a lifted MRD code can be represented in such a way that it forms a block design known as a transversal design. A slightly different representation of this design makes it similar to a $q-$analog of a transversal design. The structure of these designs is used to obtain upper bounds on the sizes of constant dimension codes which contain a lifted MRD code. Codes which attain these bounds are constructed. These codes are the largest known codes for the given parameters. These transversal designs can be also used to derive a new family of linear codes in the Hamming space. Bounds on the minimum distance and the dimension of such codes are given.
Minimizing interference in ad-hoc networks with bounded communication radius
Venue: arXiv cs.CG 2012
Year: 2012

We consider a topology control problem in which we are given a set of $n$ sensors in the plane and we would like to assign a communication radius to each of them. The radii assignment must generate a strongly connected network and have low receiver-based interference (i.e., we minimize the largest in-degree of the network). We give an algorithm that generates a network with $O(\log Δ)$ interference, where $Δ$ is the interference of a uniform-radius ad-hoc network. We then adapt the construction to the case in which no sensor can have a communication radius larger than $R_{\min}$, the minimum value needed to obtain connectivity. We also show that $\log Δ$ interference is needed for some instances, making our algorithms asymptotically optimal.
Decoding by Embedding: Correct Decoding Radius and DMT Optimality
Venue: arXiv cs.IT 2012
Year: 2012

The closest vector problem (CVP) and shortest (nonzero) vector problem (SVP) are the core algorithmic problems on Euclidean lattices. They are central to the applications of lattices in many problems of communications and cryptography. Kannan's \emph{embedding technique} is a powerful technique for solving the approximate CVP, yet its remarkable practical performance is not well understood. In this paper, the embedding technique is analyzed from a \emph{bounded distance decoding} (BDD) viewpoint. We present two complementary analyses of the embedding technique: We establish a reduction from BDD to Hermite SVP (via unique SVP), which can be used along with any Hermite SVP solver (including, among others, the Lenstra, Lenstra and Lovász (LLL) algorithm), and show that, in the special case of LLL, it performs at least as well as Babai's nearest plane algorithm (LLL-aided SIC). The former analysis helps to explain the folklore practical observation that unique SVP is easier than standard approximate SVP. It is proven that when the LLL algorithm is employed, the embedding technique can solve the CVP provided that the noise norm is smaller than a decoding radius $λ_1/(2γ)$, where $λ_1$ is the minimum distance of the lattice, and $γ\approx O(2^{n/4})$. This substantially improves the previously best known correct decoding bound $γ\approx {O}(2^{n})$. Focusing on the applications of BDD to decoding of multiple-input multiple-output (MIMO) systems, we also prove that BDD of the regularized lattice is optimal in terms of the diversity-multiplexing gain tradeoff (DMT), and propose practical variants of embedding decoding which require no knowledge of the minimum distance of the lattice and/or further improve the error performance.
Duals of Orphan-Free Anisotropic Voronoi Diagrams are Triangulations
Venue: arXiv cs.CG 2012
Year: 2012

We show that, under mild conditions on the underlying metric, duals of appropriately defined anisotropic Voronoi diagrams are embedded triangulations. Furthermore, they always triangulate the convex hull of the vertices, and have other properties that parallel those of ordinary Delaunay triangulations. These results apply to the duals of anisotropic Voronoi diagrams of any set of vertices, so long as the diagram is orphan-free.
Support of Interactive 3D/4D Presentations by the Very First Ever Made Virtual Laboratories of Antennas
Venue: arXiv cs.OH 2012
Year: 2012

Based on the experience we have gained so far, as independent reviewers of Radioengineering journal, we thought that may be proved useful to publicly share with the interested author, especially the young one, some practical implementations of our ideas for the interactive representation of data using 3D/4D movement and animation, in an attempt to motivate and support her/him in the development of similar dynamic presentations, when s/he is looking for a way to locate the stronger aspects of her/his research results in order to prepare a clear, most appropriate for publication, static presentation figure. For this purpose, we selected to demonstrate a number of presentations, from the simplest to the most complicated, concerning well-known antenna issues with rather hard to imagine details, as it happens perhaps in cases involving Spherical Coordinates and Polarization, which we created to enrich the very first ever made Virtual Laboratories of Antennas, that we distribute over the Open Internet through our website Virtual Antennas. These presentations were developed in a general way, without using antenna simulators, to handle output text and image data from third-party CAS Computer Algebra Systems, such as the Mathematica commercial software we use or the Maxima FLOSS we track its evolution.
The AWGN Red Alert Problem
Venue: arXiv cs.IT 2012
Year: 2012

Consider the following unequal error protection scenario. One special message, dubbed the "red alert" message, is required to have an extremely small probability of missed detection. The remainder of the messages must keep their average probability of error and probability of false alarm below a certain threshold. The goal then is to design a codebook that maximizes the error exponent of the red alert message while ensuring that the average probability of error and probability of false alarm go to zero as the blocklength goes to infinity. This red alert exponent has previously been characterized for discrete memoryless channels. This paper completely characterizes the optimal red alert exponent for additive white Gaussian noise channels with block power constraints.
Neighbor Oblivious and Finite-State Algorithms for Circumventing Local Minima in Geographic Forwarding
Venue: arXiv cs.NI 2012
Year: 2012

We propose distributed link reversal algorithms to circumvent communication voids in geographic routing. We also solve the attendant problem of integer overflow in these algorithms. These are achieved in two steps. First, we derive partial and full link reversal algorithms that do not require one-hop neighbor information, and convert a destination-disoriented directed acyclic graph (DAG) to a destination-oriented DAG. We embed these algorithms in the framework of Gafni and Bertsekas ("Distributed algorithms for generating loop-free routes in networks with frequently changing topology", 1981) in order to establish their termination properties. We also analyze certain key properties exhibited by our neighbor oblivious link reversal algorithms, e.g., for any two neighbors, their t-states are always consecutive integers, and for any node, its t-state size is upper bounded by log(N). In the second step, we resolve the integer overflow problem by analytically deriving one-bit full link reversal and two-bit partial link reversal versions of our neighbor oblivious link reversal algorithms.
Modeling and Analysis of K-Tier Downlink Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2012
Year: 2012

Cellular networks are in a major transition from a carefully planned set of large tower-mounted base-stations (BSs) to an irregular deployment of heterogeneous infrastructure elements that often additionally includes micro, pico, and femtocells, as well as distributed antennas. In this paper, we develop a tractable, flexible, and accurate model for a downlink heterogeneous cellular network (HCN) consisting of K tiers of randomly located BSs, where each tier may differ in terms of average transmit power, supported data rate and BS density. Assuming a mobile user connects to the strongest candidate BS, the resulting Signal-to-Interference-plus-Noise-Ratio (SINR) is greater than 1 when in coverage, Rayleigh fading, we derive an expression for the probability of coverage (equivalently outage) over the entire network under both open and closed access, which assumes a strikingly simple closed-form in the high SINR regime and is accurate down to -4 dB even under weaker assumptions. For external validation, we compare against an actual LTE network (for tier 1) with the other K-1 tiers being modeled as independent Poisson Point Processes. In this case as well, our model is accurate to within 1-2 dB. We also derive the average rate achieved by a randomly located mobile and the average load on each tier of BSs. One interesting observation for interference-limited open access networks is that at a given SINR, adding more tiers and/or BSs neither increases nor decreases the probability of coverage or outage when all the tiers have the same target-SINR.
Precoding for Outage Probability Minimization on Block Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

The outage probability limit is a fundamental and achievable lower bound on the word error rate of coded communication systems affected by fading. This limit is mainly determined by two parameters: the diversity order and the coding gain. With linear precoding, full diversity on a block fading channel can be achieved without error-correcting code. However, the effect of precoding on the coding gain is not well known, mainly due to the complicated expression of the outage probability. Using a geometric approach, this paper establishes simple upper bounds on the outage probability, the minimization of which yields to precoding matrices that achieve very good performance. For discrete alphabets, it is shown that the combination of constellation expansion and precoding is sufficient to closely approach the minimum possible outage achieved by an i.i.d. Gaussian input distribution, thus essentially maximizing the coding gain.
Synthesis and Analysis of Product-form Petri Nets
Venue: arXiv cs.DM 2012
Year: 2012

For a large Markovian model, a "product form" is an explicit description of the steady-state behaviour which is otherwise generally untractable. Being first introduced in queueing networks, it has been adapted to Markovian Petri nets. Here we address three relevant issues for product-form Petri nets which were left fully or partially open: (1) we provide a sound and complete set of rules for the synthesis; (2) we characterise the exact complexity of classical problems like reachability; (3) we introduce a new subclass for which the normalising constant (a crucial value for product-form expression) can be efficiently computed.
Complexity of Model Checking for Modal Dependence Logic
Venue: arXiv cs.LO 2012
Year: 2012

Modal dependence logic (MDL) was introduced recently by Väänänen. It enhances the basic modal language by an operator =(). For propositional variables p_1,...,p_n the atomic formula =(p_1,...,p_(n-1),p_n) intuitively states that the value of p_n is determined solely by those of p_1,...,p_(n-1). We show that model checking for MDL formulae over Kripke structures is NP-complete and further consider fragments of MDL obtained by restricting the set of allowed propositional and modal connectives. It turns out that several fragments, e.g., the one without modalities or the one without propositional connectives, remain NP-complete. We also consider the restriction of MDL where the length of each single dependence atom is bounded by a number that is fixed for the whole logic. We show that the model checking problem for this bounded MDL is still NP-complete. We additionally extend MDL by allowing classical disjunction - introduced by Sevenster - besides dependence disjunction and show that classical disjunction is always at least as computationally bad as bounded arity dependence atoms and in some cases even worse, e.g., the fragment with nothing but the two disjunctions is NP-complete. Furthermore we almost completely classifiy the computational complexity of the model checking problem for all restrictions of propositional and modal operators for both unbounded as well as bounded MDL.