OpenRaiser/Intern-Atlas huggingface dataset:
Uni-MUMAC: A Unified Down/Up-link MU-MIMO MAC Protocol for IEEE 802.11ac WLANs
Venue: arXiv cs.NI 2014
Year: 2014

Due to the dominance of the downlink traffic in Wireless Local Area Networks (WLANs), a large number of previous research efforts have been put to enhance the transmission from the Access Point (AP) to stations (STAs). The downlink Multi-User Multiple-Input Multiple-Output (MU-MIMO) technique, supported by the latest IEEE amendment-802.11ac, is considered as one of the key enhancements leading WLANs to the Gigabit era. However, as cloud uploading services, Peer-to-Peer (P2P) and telepresence applications get popular, the need for a higher uplink capacity becomes inevitable. In this paper, a unified down/up-link Medium Access Control (MAC) protocol called Uni-MUMAC is proposed to enhance the performance of IEEE 802.11ac WLANs by exploring the multi-user spatial multiplexing technique. Specifically, in the downlink, we implement an IEEE 802.11ac-compliant MU-MIMO transmission scheme to allow the AP to simultaneously send frames to a group of STAs. In the uplink, we extend the traditional one round channel access contention to two rounds, which coordinate multiple STAs to transmit frames to the AP simultaneously. 2-nd round Contention Window (CW2nd), a parameter that makes the length of the 2-nd contention round elastic according to the traffic condition, is introduced. Uni-MUMAC is evaluated through simulations in saturated and non-saturated conditions when both downlink and uplink traffic are present in the system. We also propose an analytic saturation model to validate the simulation results. By properly setting CW2nd and other parameters, Uni-MUMAC is compared to a prominent multi-user transmission scheme in the literature. The results exhibit that Uni-MUMAC not only performs well in the downlink-dominant scenario, but it is also able to balance both the downlink and uplink throughput in the emerging uplink bandwidth-hungry scenario.
Subspace identification of large-scale interconnected systems
Venue: arXiv cs.SY 2014
Year: 2014

We propose a decentralized subspace algorithm for identification of large-scale, interconnected systems that are described by sparse (multi) banded state-space matrices. First, we prove that the state of a local subsystem can be approximated by a linear combination of inputs and outputs of the local subsystems that are in its neighborhood. Furthermore, we prove that for interconnected systems with well-conditioned, finite-time observability Gramians (or observability matrices), the size of this neighborhood is relatively small. On the basis of these results, we develop a subspace identification algorithm that identifies a state-space model of a local subsystem from the local input-output data. Consequently, the developed algorithm is computationally feasible for interconnected systems with a large number of local subsystems. Numerical results confirm the effectiveness of the new identification algorithm.
The Rooster and the Syntactic Bracket
Venue: arXiv cs.LO 2014
Year: 2014

We propose an extension of pure type systems with an algebraic presentation of inductive and co-inductive type families with proper indices. This type theory supports coercions toward from smaller sorts to bigger sorts via explicit type construction, as well as impredicative sorts. Type families in impredicative sorts are constructed with a bracketing operation. The necessary restrictions of pattern-matching from impredicative sorts to types are confined to the bracketing construct. This type theory gives an alternative presentation to the calculus of inductive constructions on which the Coq proof assistant is an implementation.
Order-preserving pattern matching with k mismatches
Venue: arXiv cs.DS 2014
Year: 2014

We study a generalization of the recently introduced order-preserving pattern matching, where instead of looking for an exact copy of the pattern, we only require that the relative order between the elements is the same. In our variant, we additionally allow up to k mismatches between the pattern and the text, and the goal is to construct an efficient algorithm for small values of k. For a pattern of length m and a text of length n, our algorithm detects an order-preserving occurrence with up to k mismatches in O(n(loglogm + kloglogk)) time.
Loop Calculus for Non-Binary Alphabets using Concepts from Information Geometry
Venue: arXiv cs.IT 2014
Year: 2014

The Bethe approximation is a well-known approximation of the partition function used in statistical physics. Recently, an equality relating the partition function and its Bethe approximation was obtained for graphical models with binary variables by Chertkov and Chernyak. In this equality, the multiplicative error in the Bethe approximation is represented as a weighted sum over all generalized loops in the graphical model. In this paper, the equality is generalized to graphical models with non-binary alphabet using concepts from information geometry.
Blind pilot decontamination
Venue: arXiv cs.IT 2014
Year: 2014

A subspace projection to improve channel estimation in massive multi-antenna systems is proposed and analyzed. Together with power-controlled hand-off, it can mitigate the pilot contamination problem without the need for coordination among cells. The proposed method is blind in the sense that it does not require pilot data to find the appropriate subspace. It is based on the theory of large random matrices that predicts that the eigenvalue spectra of large sample covariance matrices can asymptotically decompose into disjoint bulks as the matrix size grows large. Random matrix and free probability theory are utilized to predict under which system parameters such a bulk decomposition takes place. Simulation results are provided to confirm that the proposed method outperforms conventional linear channel estimation if bulk separation occurs.
Polylogarithmic Supports are required for Approximate Well-Supported Nash Equilibria below 2/3
Venue: arXiv cs.GT 2014
Year: 2014

In an epsilon-approximate Nash equilibrium, a player can gain at most epsilon in expectation by unilateral deviation. An epsilon well-supported approximate Nash equilibrium has the stronger requirement that every pure strategy used with positive probability must have payoff within epsilon of the best response payoff. Daskalakis, Mehta and Papadimitriou conjectured that every win-lose bimatrix game has a 2/3-well-supported Nash equilibrium that uses supports of cardinality at most three. Indeed, they showed that such an equilibrium will exist subject to the correctness of a graph-theoretic conjecture. Regardless of the correctness of this conjecture, we show that the barrier of a 2/3 payoff guarantee cannot be broken with constant size supports; we construct win-lose games that require supports of cardinality at least Omega((log n)^(1/3)) in any epsilon-well supported equilibrium with epsilon < 2/3. The key tool in showing the validity of the construction is a proof of a bipartite digraph variant of the well-known Caccetta-Haggkvist conjecture. A probabilistic argument shows that there exist epsilon-well-supported equilibria with supports of cardinality O(log n/(epsilon^2)), for any epsilon> 0; thus, the polylogarithmic cardinality bound presented cannot be greatly improved. We also show that for any delta > 0, there exist win-lose games for which no pair of strategies with support sizes at most two is a (1-delta)-well-supported Nash equilibrium. In contrast, every bimatrix game with payoffs in [0,1] has a 1/2-approximate Nash equilibrium where the supports of the players have cardinality at most two.
Alpha-Concave Hull, a Generalization of Convex Hull
Venue: arXiv cs.CG 2014
Year: 2014

Bounding hull, such as convex hull, concave hull, alpha shapes etc. has vast applications in different areas especially in computational geometry. Alpha shape and concave hull are generalizations of convex hull. Unlike the convex hull, they construct non-convex enclosure on a set of points. In this paper, we introduce another generalization of convex hull, named alpha-concave hull, and compare this concept with convex hull and alpha shape. We show that the alpha-concave hull is also a generalization of an NP-complete problem named min-area TSP. We prove that computing the alpha-concave hull is NP-hard on a set of points.
A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
Venue: arXiv cs.IT 2014
Year: 2014

Low-density parity-check (LDPC) convolutional codes (or spatially-coupled codes) were recently shown to approach capacity on the binary erasure channel (BEC) and binary-input memoryless symmetric channels. The mechanism behind this spectacular performance is now called threshold saturation via spatial coupling. This new phenomenon is characterized by the belief-propagation threshold of the spatially-coupled ensemble increasing to an intrinsic noise threshold defined by the uncoupled system. In this paper, we present a simple proof of threshold saturation that applies to a wide class of coupled scalar recursions. Our approach is based on constructing potential functions for both the coupled and uncoupled recursions. Our results actually show that the fixed point of the coupled recursion is essentially determined by the minimum of the uncoupled potential function and we refer to this phenomenon as Maxwell saturation. A variety of examples are considered including the density-evolution equations for: irregular LDPC codes on the BEC, irregular low-density generator matrix codes on the BEC, a class of generalized LDPC codes with BCH component codes, the joint iterative decoding of LDPC codes on intersymbol-interference channels with erasure noise, and the compressed sensing of random vectors with i.i.d. components.
Online Approximate Optimal Station Keeping of an Autonomous Underwater Vehicle
Venue: arXiv cs.SY 2014
Year: 2014

Online approximation of an optimal station keeping strategy for a fully actuated six degrees-of-freedom autonomous underwater vehicle is considered. The developed controller is an approximation of the solution to a two player zero-sum game where the controller is the minimizing player and an external disturbance is the maximizing player. The solution is approximated using a reinforcement learning-based actor-critic framework. The result guarantees uniformly ultimately bounded (UUB) convergence of the states and UUB convergence of the approximated policies to the optimal polices without the requirement of persistence of excitation.
A Survey on Device-to-Device Communication in Cellular Networks
Venue: arXiv cs.GT 2014
Year: 2014

Device-to-Device (D2D) communication was initially proposed in cellular networks as a new paradigm to enhance network performance. The emergence of new applications such as content distribution and location-aware advertisement introduced new use-cases for D2D communications in cellular networks. The initial studies showed that D2D communication has advantages such as increased spectral efficiency and reduced communication delay. However, this communication mode introduces complications in terms of interference control overhead and protocols that are still open research problems. The feasibility of D2D communications in LTE-A is being studied by academia, industry, and the standardization bodies. To date, there are more than 100 papers available on D2D communications in cellular networks and, there is no survey on this field. In this article, we provide a taxonomy based on the D2D communicating spectrum and review the available literature extensively under the proposed taxonomy. Moreover, we provide new insights to the over-explored and under-explored areas which lead us to identify open research problems of D2D communication in cellular networks.
Improved Battery Models of an Aggregation of Thermostatically Controlled Loads for Frequency Regulation
Venue: arXiv cs.SY 2014
Year: 2014

Recently it has been shown that an aggregation of Thermostatically Controlled Loads (TCLs) can be utilized to provide fast regulating reserve service for power grids and the behavior of the aggregation can be captured by a stochastic battery with dissipation. In this paper, we address two practical issues associated with the proposed battery model. First, we address clustering of a heterogeneous collection and show that by finding the optimal dissipation parameter for a given collection, one can divide these units into few clusters and improve the overall battery model. Second, we analytically characterize the impact of imposing a no-short-cycling requirement on TCLs as constraints on the ramping rate of the regulation signal. We support our theorems by providing simulation results.
Linear Precoding Based on Polynomial Expansion: Reducing Complexity in Massive MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Large-scale multi-user multiple-input multiple-output (MIMO) techniques have the potential to bring tremendous improvements for future communication systems. Counter-intuitively, the practical issues of having uncertain channel knowledge, high propagation losses, and implementing optimal non-linear precoding are solved more-or-less automatically by enlarging system dimensions. However, the computational precoding complexity grows with the system dimensions. For example, the close-to-optimal regularized zero-forcing (RZF) precoding is very complicated to implement in practice, since it requires fast inversions of large matrices in every coherence period. Motivated by the high performance of RZF, we propose to replace the matrix inversion by a truncated polynomial expansion (TPE), thereby obtaining the new TPE precoding scheme which is more suitable for real-time hardware implementation. The degree of the matrix polynomial can be adapted to the available hardware resources and enables smooth transition between simple maximum ratio transmission (MRT) and more advanced RZF. By deriving new random matrix results, we obtain a deterministic expression for the asymptotic signal-to-interference-and-noise ratio (SINR) achieved by TPE precoding in large-scale MIMO systems. Furthermore, we provide a closed-form expression for the polynomial coefficients that maximizes this SINR. To maintain a fixed per-user rate loss as compared to RZF, the polynomial degree does not need to scale with the system, but it should be increased with the quality of the channel knowledge and the signal-to-noise ratio (SNR).
Source-Channel Matching for Sources with Memory
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we analyze the probabilistic matching of sources with memory to channels with memory so that symbol-by-symbol code with memory without anticipation are optimal, with respect to an average distortion and excess distortion probability. We show achievability of such a symbolby- symbol code with memory without anticipation, and we show matching for the Binary Symmetric Markov source (BSMS(p)) over a first-order symmetric channel with a cost constraint.
Competition vs. Cooperation: A Game-Theoretic Decision Analysis for MIMO HetNets
Venue: arXiv cs.GT 2014
Year: 2014

This paper addresses the problem of competition vs. cooperation in the downlink, between base stations (BSs), of a multiple input multiple output (MIMO) interference, heterogeneous wireless network (HetNet). This research presents a scenario where a macrocell base station (MBS) and a cochannel femtocell base station (FBS) each simultaneously serving their own user equipment (UE), has to choose to act as individual systems or to cooperate in coordinated multipoint transmission (CoMP). The paper employes both the theories of non-cooperative and cooperative games in a unified procedure to analyze the decision making process. The BSs of the competing system are assumed to operate at the\emph{}maximum expected sum rate\emph{}(MESR)\emph{}correlated equilibrium\emph{}(CE), which is compared against the value of CoMP to establish the stability of the coalition. It is proven that there exists a threshold geographical separation, $d_{\text{th}}$, between the macrocell user equipment (MUE) and FBS, under which the region of coordination is non-empty. Theoretical results are verified through simulations.
One Quantifier Alternation in First-Order Logic with Modular Predicates
Venue: arXiv cs.FL 2014
Year: 2014

Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[<,MOD] with order comparison $x<y$ and predicates for $x \equiv i \mod n$ has been investigated by Barrington, Compton, Straubing and Therien. The study of FO[<,MOD]-fragments was initiated by Chaubard, Pin and Straubing. More recently, Dartois and Paperman showed that definability in the two-variable fragment FO2[<,MOD] is decidable. In this paper we continue this line of work. We give an effective algebraic characterization of the word languages in Sigma2[<,MOD]. The fragment Sigma2 consists of first-order formulas in prenex normal form with two blocks of quantifiers starting with an existential block. In addition we show that Delta2[<,MOD], the largest subclass of Sigma2[<,MOD] which is closed under negation, has the same expressive power as two-variable logic FO2[<,MOD]. This generalizes the result FO2[<] = Delta2[<] of Therien and Wilke to modular predicates. As a byproduct, we obtain another decidable characterization of FO2[<,MOD].
PPF - A Parallel Particle Filtering Library
Venue: arXiv cs.DC 2014
Year: 2014

We present the parallel particle filtering (PPF) software library, which enables hybrid shared-memory/distributed-memory parallelization of particle filtering (PF) algorithms combining the Message Passing Interface (MPI) with multithreading for multi-level parallelism. The library is implemented in Java and relies on OpenMPI's Java bindings for inter-process communication. It includes dynamic load balancing, multi-thread balancing, and several algorithmic improvements for PF, such as input-space domain decomposition. The PPF library hides the difficulties of efficient parallel programming of PF algorithms and provides application developers with the necessary tools for parallel implementation of PF methods. We demonstrate the capabilities of the PPF library using two distributed PF algorithms in two scenarios with different numbers of particles. The PPF library runs a 38 million particle problem, corresponding to more than 1.86 GB of particle data, on 192 cores with 67% parallel efficiency. To the best of our knowledge, the PPF library is the first open-source software that offers a parallel framework for PF applications.
Computation with No Memory, and Rearrangeable Multicast Networks
Venue: arXiv cs.DM 2014
Year: 2014

We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n - 1 component modifications, that is by a program of length 2n - 1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinement of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g. Z/sZ for any integer s), we build a program with maximal length 2n - 1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z.
Spider covers for prize-collecting network activation problem
Venue: arXiv cs.DS 2014
Year: 2014

In the network activation problem, each edge in a graph is associated with an activation function, that decides whether the edge is activated from node-weights assigned to its end-nodes. The feasible solutions of the problem are the node-weights such that the activated edges form graphs of required connectivity, and the objective is to find a feasible solution minimizing its total weight. In this paper, we consider a prize-collecting version of the network activation problem, and present first non- trivial approximation algorithms. Our algorithms are based on a new LP relaxation of the problem. They round optimal solutions for the relaxation by repeatedly computing node-weights activating subgraphs called spiders, which are known to be useful for approximating the network activation problem.
A Study of Truck Platooning Incentives Using a Congestion Game
Venue: arXiv cs.GT 2014
Year: 2014

We introduce an atomic congestion game with two types of agents, cars and trucks, to model the traffic flow on a road over various time intervals of the day. Cars maximize their utility by finding a trade-off between the time they choose to use the road, the average velocity of the flow at that time, and the dynamic congestion tax that they pay for using the road. In addition to these terms, the trucks have an incentive for using the road at the same time as their peers because they have platooning capabilities, which allow them to save fuel. The dynamics and equilibria of this game-theoretic model for the interaction between car traffic and truck platooning incentives are investigated. We use traffic data from Stockholm to validate parts of the modeling assumptions and extract reasonable parameters for the simulations. We use joint strategy fictitious play and average strategy fictitious play to learn a pure strategy Nash equilibrium of this game. We perform a comprehensive simulation study to understand the influence of various factors, such as the drivers' value of time and the percentage of the trucks that are equipped with platooning devices, on the properties of the Nash equilibrium.
Parameterized algorithm for weighted independent set problem in bull-free graphs
Venue: arXiv cs.DM 2014
Year: 2014

The maximum stable set problem is NP-hard, even when restricted to triangle-free graphs. In particular, one cannot expect a polynomial time algorithm deciding if a bull-free graph has a stable set of size $k$, when $k$ is part of the instance. Our main result in this paper is to show the existence of an FPT algorithm when we parameterize the problem by the solution size $k$. A polynomial kernel is unlikely to exist for this problem. We show however that our problem has a polynomial size Turing-kernel. More precisely, the hard cases are instances of size $O(k^5)$. As a byproduct, if we forbid odd holes in addition to the bull, we show the existence of a polynomial time algorithm for the stable set problem. We also prove that the chromatic number of a bull-free graph is bounded by a function of its clique number and the maximum chromatic number of its triangle-free induced subgraphs. All our results rely on a decomposition theorem of bull-free graphs due to Chudnovsky which is modified here, allowing us to provide extreme decompositions, adapted to our computational purpose.