OpenRaiser/Intern-Atlas huggingface dataset:
Stability and Queueing Analysis of IEEE 802.11 Distributed Coordination Function
Venue: arXiv cs.NI 2012
Year: 2012

A widely adopted two-dimensional Markov chain model of the IEEE 802.11 DCF was introduced by Bianchi to characterize the backoff behavior of a single node under a saturated traffic condition. Using this approach, we propose a queuing model for the 802.11 DCF under a non-saturated traffic environment. The input buffer of each node is modeled as a Geo/G/1 queue, and the packet service time distribution is derived from Markov state space of 802.11 DCF with the underlying scheduling algorithm. The DCF defines two access mechanisms, namely the Basic access mechanism and the request-to-send/clear-to-send (RTS/CTS) access mechanism. Based on our model, performance analyses of both schemes are studied with probabilistic exponential backoff scheduling. We obtain the characteristic equation of network throughput and expressions of packet queueing delay. Specifically, we obtain the stable throughput and bounded delay regions with respect to the retransmission factor according to the basic queueing analysis. For both access schemes, the bounded delay region is a subset of the stable throughput region. Our results show that the RTS/CTS access mechanism is more stable and performs better than the Basic access mechanism. The analysis in this paper is verified by simulation results.
Control Complexity in Bucklin and Fallback Voting
Venue: arXiv cs.CC 2012
Year: 2012

Electoral control models ways of changing the outcome of an election via such actions as adding/deleting/partitioning either candidates or voters. To protect elections from such control attempts, computational complexity has been investigated and the corresponding NP-hardness results are termed "resistance." It has been a long-running project of research in this area to classify the major voting systems in terms of their resistance properties. We show that fallback voting, an election system proposed by Brams and Sanver (2009) to combine Bucklin with approval voting, is resistant to each of the common types of control except to destructive control by either adding or deleting voters. Thus fallback voting displays the broadest control resistance currently known to hold among natural election systems with a polynomial-time winner problem. We also study the control complexity of Bucklin voting and show that it performs at least almost as well as fallback voting in terms of control resistance. As Bucklin voting is a special case of fallback voting, each resistance shown for Bucklin voting strengthens the corresponding resistance for fallback voting. Such worst-case complexity analysis is at best an indication of security against control attempts, rather than a proof. In practice, the difficulty of control will depend on the structure of typical instances. We investigate the parameterized control complexity of Bucklin and fallback voting, according to several parameters that are often likely to be small for typical instances. Our results, though still in the worst-case complexity model, can be interpreted as significant strengthenings of the resistance demonstrations based on NP-hardness.
PyDEC: Software and Algorithms for Discretization of Exterior Calculus
Venue: arXiv cs.NA 2012
Year: 2012

This paper describes the algorithms, features and implementation of PyDEC, a Python library for computations related to the discretization of exterior calculus. PyDEC facilitates inquiry into both physical problems on manifolds as well as purely topological problems on abstract complexes. We describe efficient algorithms for constructing the operators and objects that arise in discrete exterior calculus, lowest order finite element exterior calculus and in related topological problems. Our algorithms are formulated in terms of high-level matrix operations which extend to arbitrary dimension. As a result, our implementations map well to the facilities of numerical libraries such as NumPy and SciPy. The availability of such libraries makes Python suitable for prototyping numerical methods. We demonstrate how PyDEC is used to solve physical and topological problems through several concise examples.
Decoding square-free Goppa codes over $\F_p$
Venue: arXiv cs.CR 2012
Year: 2012

We propose a new, efficient non-deterministic decoding algorithm for square-free Goppa codes over $\F_p$ for any prime $p$. If the code in question has degree $t$ and the average distance to the closest codeword is at least $(4/p)t + 1$, the proposed decoder can uniquely correct up to $(2/p)t$ errors with high probability. The correction capability is higher if the distribution of error magnitudes is not uniform, approaching or reaching $t$ errors when any particular error value occurs much more often than others or exclusively. This makes the method interesting for (semantically secure) cryptosystems based on the decoding problem for permuted and punctured Goppa codes.
An ER-based Framework for Declarative Web Programming
Venue: arXiv cs.PL 2012
Year: 2012

We describe a framework to support the implementation of web-based systems intended to manipulate data stored in relational databases. Since the conceptual model of a relational database is often specified as an entity-relationship (ER) model, we propose to use the ER model to generate a complete implementation in the declarative programming language Curry. This implementation contains operations to create and manipulate entities of the data model, supports authentication, authorization, session handling, and the composition of individual operations to user processes. Furthermore, the implementation ensures the consistency of the database w.r.t. the data dependencies specified in the ER model, i.e., updates initiated by the user cannot lead to an inconsistent state of the database. In order to generate a high-level declarative implementation that can be easily adapted to individual customer requirements, the framework exploits previous works on declarative database programming and web user interface construction in Curry.
Cooperative Strategies for Simultaneous and Broadcast Relay Channels
Venue: arXiv cs.IT 2012
Year: 2012

Consider the \emph{simultaneous relay channel} (SRC) which consists of a set of relay channels where the source wishes to transmit common and private information to each of the destinations. This problem is recognized as being equivalent to that of sending common and private information to several destinations in presence of helper relays where each channel outcome becomes a branch of the \emph{broadcast relay channel} (BRC). Cooperative schemes and capacity region for a set with two memoryless relay channels are investigated. The proposed coding schemes, based on \emph{Decode-and-Forward} (DF) and \emph{Compress-and-Forward} (CF) must be capable of transmitting information simultaneously to all destinations in such set. Depending on the quality of source-to-relay and relay-to-destination channels, inner bounds on the capacity of the general BRC are derived. Three cases of particular interest are considered: cooperation is based on DF strategy for both users --referred to as DF-DF region--, cooperation is based on CF strategy for both users --referred to as CF-CF region--, and cooperation is based on DF strategy for one destination and CF for the other --referred to as DF-CF region--. These results can be seen as a generalization and hence unification of previous works. An outer-bound on the capacity of the general BRC is also derived. Capacity results are obtained for the specific cases of semi-degraded and degraded Gaussian simultaneous relay channels. Rates are evaluated for Gaussian models where the source must guarantee a minimum amount of information to both users while additional information is sent to each of them.
Optimal Energy Allocation for Wireless Communications with Energy Harvesting Constraints
Venue: arXiv cs.IT 2012
Year: 2012

We consider the use of energy harvesters, in place of conventional batteries with fixed energy storage, for point-to-point wireless communications. In addition to the challenge of transmitting in a channel with time selective fading, energy harvesters provide a perpetual but unreliable energy source. In this paper, we consider the problem of energy allocation over a finite horizon, taking into account channel conditions and energy sources that are time varying, so as to maximize the throughput. Two types of side information (SI) on the channel conditions and harvested energy are assumed to be available: causal SI (of the past and present slots) or full SI (of the past, present and future slots). We obtain structural results for the optimal energy allocation, via the use of dynamic programming and convex optimization techniques. In particular, if unlimited energy can be stored in the battery with harvested energy and the full SI is available, we prove the optimality of a water-filling energy allocation solution where the so-called water levels follow a staircase function.
Interference Channels with Rate-Limited Feedback
Venue: arXiv cs.IT 2012
Year: 2012

We consider the two-user interference channel with rate-limited feedback. Related prior works focus on the case where feedback links have infinite capacity, while no research has been done for the rate-limited feedback problem. Several new challenges arise due to the capacity limitations of the feedback links, both in deriving inner-bounds and outer-bounds. We study this problem under three different interference models: the El Gamal-Costa deterministic model, the linear deterministic model, and the Gaussian model. For the first two models, we develop an achievable scheme that employs three techniques: Han-Kobayashi message splitting, quantize-and-binning, and decode-and-forward. We also derive new outer-bounds for all three models and we show the optimality of our scheme under the linear deterministic model. In the Gaussian case, we propose a transmission strategy that incorporates lattice codes, inspired by the ideas developed in the first two models. For symmetric channel gains, we prove that the gap between the achievable sum-rate of the proposed scheme and our new outer-bounds is bounded by a constant number of bits, independent of the channel gains.
Causal Rate Distortion Function and Relations to Filtering Theory
Venue: arXiv cs.IT 2012
Year: 2012

A causal rate distortion function is defined, its solution is described, and its relation to filtering theory is discussed. The relation to filtering is obtained via a causal constraint imposed on the reconstruction kernel to be realizable.
Information Storage and Retrieval for Probe Storage using Optical Diffraction Patterns
Venue: arXiv cs.IT 2012
Year: 2012

A novel method for fast information retrieval from a probe storage device is considered. It is shown that information can be stored and retrieved using the optical diffraction patterns obtained by the illumination of a large array of cantilevers by a monochromatic light source. In thermo-mechanical probe storage, the information is stored as a sequence of indentations on the polymer medium. To retrieve the information, the array of probes is actuated by applying a bending force to the cantilevers. Probes positioned over indentations experience deflection by the depth of the indentation, probes over the flat media remain un-deflected. Thus the array of actuated probes can be viewed as an irregular optical grating, which creates a data-dependent diffraction pattern when illuminated by laser light. We develop a low complexity modulation scheme, which allows the extraction of information stored in the pattern of indentations on the media from Fourier coefficients of the intensity of the diffraction pattern. We then derive a low-complexity maximum likelihood sequence detection algorithm for retrieving the user information from the Fourier coefficients. The derivation of both the modulation and the detection schemes is based on the Fraunhofer formula for data-dependent diffraction patterns. We show that for as long as the Fresnel number F<0.1, the optimal channel detector derived from Fraunhofer diffraction theory does not suffer any significant performance degradation.
On Secrecy Rate Analysis of MIMO Wiretap Channels Driven by Finite-Alphabet Input
Venue: arXiv cs.IT 2012
Year: 2012

This work investigates the effect of finite-alphabet source input on the secrecy rate of a multi-antenna wiretap system. Existing works have characterized maximum achievable secrecy rate or secrecy capacity for single and multiple antenna systems based on Gaussian source signals and secrecy code. Despite the impracticality of Gaussian sources, the compact closed-form expression of mutual information between linear channel Gaussian input and corresponding output has led to broad application of Gaussian input assumption in physical secrecy analysis. For practical considerations, we study the effect of finite discrete-constellation on the achievable secrecy rate of multiple-antenna wire-tap channels. Our proposed precoding scheme converts the multi-antenna system into a bank of parallel channels. Based on this precoding strategy, we propose a decentralized power allocation algorithm based on dual decomposition for maximizing the achievable secrecy rate. In addition, we analyze the achievable secrecy rate for finite-alphabet inputs in low and high SNR cases. Our results demonstrate substantial difference in secrecy rate between systems given finite-alphabet inputs and systems with Gaussian inputs.
On Conditions for Linearity of Optimal Estimation
Venue: arXiv cs.IT 2012
Year: 2012

When is optimal estimation linear? It is well known that, when a Gaussian source is contaminated with Gaussian noise, a linear estimator minimizes the mean square estimation error. This paper analyzes, more generally, the conditions for linearity of optimal estimators. Given a noise (or source) distribution, and a specified signal to noise ratio (SNR), we derive conditions for existence and uniqueness of a source (or noise) distribution for which the $L_p$ optimal estimator is linear. We then show that, if the noise and source variances are equal, then the matching source must be distributed identically to the noise. Moreover, we prove that the Gaussian source-channel pair is unique in the sense that it is the only source-channel pair for which the mean square error (MSE) optimal estimator is linear at more than one SNR values. Further, we show the asymptotic linearity of MSE optimal estimators for low SNR if the channel is Gaussian regardless of the source and, vice versa, for high SNR if the source is Gaussian regardless of the channel. The extension to the vector case is also considered where besides the conditions inherited from the scalar case, additional constraints must be satisfied to ensure linearity of the optimal estimator.
Deciding the Value 1 Problem of Probabilistic Leaktight Automata
Venue: arXiv cs.FL 2012
Year: 2012

The value 1 problem is a decision problem for probabilistic automata over finite words: given a probabilistic automaton A, are there words accepted by A with probability arbitrarily close to 1? This problem was proved undecidable recently. We sharpen this result, showing that the undecidability result holds even if the probabilistic automata have only one probabilistic transition. Our main contribution is to introduce a new class of probabilistic automata, called leaktight automata, for which the value 1 problem is shown decidable (and PSPACE-complete). We construct an algorithm based on the computation of a monoid abstracting the behaviours of the automaton, and rely on algebraic techniques developed by Simon for the correctness proof. The class of leaktight automata is decidable in PSPACE, subsumes all subclasses of probabilistic automata whose value 1 problem is known to be decidable (in particular deterministic automata), and is closed under two natural composition operators.
Optimal strategies for a game on amenable semigroups
Venue: arXiv cs.GT 2012
Year: 2012

The semigroup game is a two-person zero-sum game defined on a semigroup S as follows: Players 1 and 2 choose elements x and y in S, respectively, and player 1 receives a payoff f(xy) defined by a function f from S to [-1,1]. If the semigroup is amenable in the sense of Day and von Neumann, one can extend the set of classical strategies, namely countably additive probability measures on S, to include some finitely additive measures in a natural way. This extended game has a value and the players have optimal strategies. This theorem extends previous results for the multiplication game on a compact group or on the positive integers with a specific payoff. We also prove that the procedure of extending the set of allowed strategies preserves classical solutions: if a semigroup game has a classical solution, this solution solves also the extended game.
K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance
Venue: arXiv cs.DS 2012
Year: 2012

We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m = O(k log(n/k)) and a 1 + epsilon approximation factor, which matches the best achievable bound for other error measures, such as the L_1 norm. Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems.
Robust Monotonic Optimization Framework for Multicell MISO Systems
Venue: arXiv cs.IT 2012
Year: 2012

The performance of multiuser systems is both difficult to measure fairly and to optimize. Most resource allocation problems are non-convex and NP-hard, even under simplifying assumptions such as perfect channel knowledge, homogeneous channel properties among users, and simple power constraints. We establish a general optimization framework that systematically solves these problems to global optimality. The proposed branch-reduce-and-bound (BRB) algorithm handles general multicell downlink systems with single-antenna users, multiantenna transmitters, arbitrary quadratic power constraints, and robustness to channel uncertainty. A robust fairness-profile optimization (RFO) problem is solved at each iteration, which is a quasi-convex problem and a novel generalization of max-min fairness. The BRB algorithm is computationally costly, but it shows better convergence than the previously proposed outer polyblock approximation algorithm. Our framework is suitable for computing benchmarks in general multicell systems with or without channel uncertainty. We illustrate this by deriving and evaluating a zero-forcing solution to the general problem.
Context-Oriented Programming: A Programming Paradigm for Autonomic Systems
Venue: arXiv cs.PL 2012
Year: 2012

Dynamic software adaptability is one of the central features leveraged by autonomic computing. However, developing software that changes its behavior at run time adapting to the operational conditions is a challenging task. Several approaches have been proposed in the literature to attack this problem at different and complementary abstraction levels: software architecture, middleware, and programming level. We focus on the support that ad-hoc programming language constructs may provide to support dynamically adaptive behaviors. We introduce context-oriented programming languages and we present a framework that positions the supported paradigm in the MAPE-K autonomic loop. We discuss the advantages of using context-oriented programming languages instead of other mainstream approaches based on dynamic aspect oriented programming languages and present a case study that shows how the proposed programming style naturally fits dynamic adaptation requirements. Finally, we discuss some known problems and outline a number of open research challenges.
The parameterized complexity of k-edge induced subgraphs
Venue: arXiv cs.DS 2012
Year: 2012

We prove that finding a $k$-edge induced subgraph is fixed-parameter tractable, thereby answering an open problem of Leizhen Cai. Our algorithm is based on several combinatorial observations, Gauss' famous \emph{Eureka} theorem [Andrews, 86], and a generalization of the well-known fpt-algorithm for the model-checking problem for first-order logic on graphs with locally bounded tree-width due to Frick and Grohe [Frick and Grohe, 01]. On the other hand, we show that two natural counting versions of the problem are hard. Hence, the $k$-edge induced subgraph problem is one of the rare known examples in parameterized complexity that are easy for decision while hard for counting.
Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes
Venue: arXiv cs.IT 2012
Year: 2012

Linear programming (LP) decoding approximates maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of box constraints together with a set of linear inequalities called "parity inequalities" that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or "cut," at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding.
Equilibrium strategy and population-size effects in lowest unique bid auctions
Venue: arXiv cs.GT 2012
Year: 2012

In lowest unique bid auctions, $N$ players bid for an item. The winner is whoever places the \emph{lowest} bid, provided that it is also unique. We use a grand canonical approach to derive an analytical expression for the equilibrium distribution of strategies. We then study the properties of the solution as a function of the mean number of players, and compare them with a large dataset of internet auctions. The theory agrees with the data with striking accuracy for small population size $N$, while for larger $N$ a qualitatively different distribution is observed. We interpret this result as the emergence of two different regimes, one in which adaptation is feasible and one in which it is not. Our results question the actual possibility of a large population to adapt and find the optimal strategy when participating in a collective game.