OpenRaiser/Intern-Atlas huggingface dataset:
Compositional Transient Stability Analysis of Multi-Machine Power Networks
Venue: arXiv cs.SY 2014
Year: 2014

During the normal operation of a power system all the voltages and currents are sinusoids with a frequency of 60 Hz in America and parts of Asia, or of 50Hz in the rest of the world. Forcing all the currents and voltages to be sinusoids with the right frequency is one of the most important problems in power systems. This problem is known as the transient stability problem in the power systems literature. The classical models used to study transient stability are based on several implicit assumptions that are violated when transients occur. One such assumption is the use of phasors to study transients. While phasors require sinusoidal waveforms to be well defined, there is no guarantee that waveforms will remain sinusoidal during transients. In this paper, we use energy-based models derived from first principles that are not subject to hard-to-justify classical assumptions. In addition to eliminate assumptions that are known not to hold during transient stages, we derive intuitive conditions ensuring the transient stability of power systems with lossy transmission lines. Furthermore, the conditions for transient stability are compositional in the sense that one infers transient stability of a large power system by checking simple conditions for individual generators.
Querying the Guarded Fragment
Venue: arXiv cs.LO 2014
Year: 2014

Evaluating a Boolean conjunctive query Q against a guarded first-order theory F is equivalent to checking whether "F and not Q" is unsatisfiable. This problem is relevant to the areas of database theory and description logic. Since Q may not be guarded, well known results about the decidability, complexity, and finite-model property of the guarded fragment do not obviously carry over to conjunctive query answering over guarded theories, and had been left open in general. By investigating finite guarded bisimilar covers of hypergraphs and relational structures, and by substantially generalising Rosati's finite chase, we prove for guarded theories F and (unions of) conjunctive queries Q that (i) Q is true in each model of F iff Q is true in each finite model of F and (ii) determining whether F implies Q is 2EXPTIME-complete. We further show the following results: (iii) the existence of polynomial-size conformal covers of arbitrary hypergraphs; (iv) a new proof of the finite model property of the clique-guarded fragment; (v) the small model property of the guarded fragment with optimal bounds; (vi) a polynomial-time solution to the canonisation problem modulo guarded bisimulation, which yields (vii) a capturing result for guarded bisimulation invariant PTIME.
Automation of Mathematical Induction as part of the History of Logic
Venue: arXiv cs.AI 2014
Year: 2014

We review the history of the automation of mathematical induction
Location, Location, Location: Data-Intensive Distributed Computing in the Cloud
Venue: arXiv cs.DC 2014
Year: 2014

When orchestrating highly distributed and data-intensive Web service workflows the geographical placement of the orchestration engine can greatly affect the overall performance of a workflow. Orchestration engines are typically run from within an organisations' network, and may have to transfer data across long geographical distances, which in turn increases execution time and degrades the overall performance of a workflow. In this paper we present CloudForecast: a Web service framework and analysis tool which given a workflow specification, computes the optimal Amazon EC2 Cloud region to automatically deploy the orchestration engine and execute the workflow. We use geographical distance of the workflow, network latency and HTTP round-trip time between Amazon Cloud regions and the workflow nodes to find a ranking of Cloud regions. This combined set of simple metrics effectively predicts where the workflow orchestration engine should be deployed in order to reduce overall execution time. We evaluate our approach by executing randomly generated data-intensive workflows deployed on the PlanetLab platform in order to rank Amazon EC2 Cloud regions. Our experimental results show that our proposed optimisation strategy, depending on the particular workflow, can speed up execution time on average by 82.25% compared to local execution. We also show that the standard deviation of execution time is reduced by an average of almost 65% using the optimisation strategy.
Capacity-aware back-pressure traffic signal control
Venue: arXiv cs.SY 2014
Year: 2014

The control of a network of signalized intersections is considered. Previous work demonstrates that the so-called back-pressure control provides stability guarantees, assuming infinite queues capacities. In this paper, we highlight the failing of current back-pressure control under finite capacities by identifying sources of non work-conservation and congestion propagation. We propose the use of a normalized pressure which guarantees work conservation and mitigates congestion propagation, while ensuring fairness at low traffic densities, and recovering original back-pressure as capacities grow to infinity. This capacity-aware back-pressure control allows to improve performance as congestion increases, as indicated by simulation results, and keeps the key benefits of back-pressure: ability to be distributed over intersections and O(1) complexity.
Continuous-time Proportional-Integral Distributed Optimization for Networked Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we explore the relationship between dual decomposition and the consensus-based method for distributed optimization. The relationship is developed by examining the similarities between the two approaches and their relationship to gradient-based constrained optimization. By formulating each algorithm in continuous-time, it is seen that both approaches use a gradient method for optimization with one using a proportional control term and the other using an integral control term to drive the system to the constraint set. Therefore, a significant contribution of this paper is to combine these methods to develop a continuous-time proportional-integral distributed optimization method. Furthermore, we establish convergence using Lyapunov stability techniques and utilizing properties from the network structure of the multi-agent system.
Distributed Online Learning in Social Recommender Systems
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we consider decentralized sequential decision making in distributed online recommender systems, where items are recommended to users based on their search query as well as their specific background including history of bought items, gender and age, all of which comprise the context information of the user. In contrast to centralized recommender systems, in which there is a single centralized seller who has access to the complete inventory of items as well as the complete record of sales and user information, in decentralized recommender systems each seller/learner only has access to the inventory of items and user information for its own products and not the products and user information of other sellers, but can get commission if it sells an item of another seller. Therefore the sellers must distributedly find out for an incoming user which items to recommend (from the set of own items or items of another seller), in order to maximize the revenue from own sales and commissions. We formulate this problem as a cooperative contextual bandit problem, analytically bound the performance of the sellers compared to the best recommendation strategy given the complete realization of user arrivals and the inventory of items, as well as the context-dependent purchase probabilities of each item, and verify our results via numerical examples on a distributed data set adapted based on Amazon data. We evaluate the dependence of the performance of a seller on the inventory of items the seller has, the number of connections it has with the other sellers, and the commissions which the seller gets by selling items of other sellers to its users.
A Note on Broadcast Channels with Stale State Information at the Transmitter
Venue: arXiv cs.IT 2014
Year: 2014

This paper shows that the Maddah-Ali--Tse (MAT) scheme which establishes the symmetric capacity of two example broadcast channels with strictly causal state information at the transmitter is a simple special case of the Shayevitz--Wigger scheme for the broadcast channel with generalized feedback, which involves block Markov coding, compression, superposition coding, Marton coding, and coded time sharing. Focusing on the class of symmetric broadcast channels with state, we derive an expression for the maximum achievable symmetric rate using the Shayevitz--Wigger scheme. We show that the MAT results can be recovered by evaluating this expression for the special case in which superposition coding and Marton coding are not used. We then introduce a new broadcast channel example that shares many features of the MAT examples. We show that another special case of our maximum symmetric rate expression in which superposition coding is also used attains a higher symmetric rate than the MAT scheme. The symmetric capacity of this example is not known, however.
Decompositions of Triangle-Dense Graphs
Venue: arXiv cs.DS 2014
Year: 2014

High triangle density -- the graph property stating that a constant fraction of two-hop paths belong to a triangle -- is a common signature of social networks. This paper studies triangle-dense graphs from a structural perspective. We prove constructively that significant portions of a triangle-dense graph are contained in a disjoint union of dense, radius 2 subgraphs. This result quantifies the extent to which triangle-dense graphs resemble unions of cliques. We also show that our algorithm recovers planted clusterings in approximation-stable k-median instances.
Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
Venue: arXiv cs.IT 2014
Year: 2014

Spatially-coupled low-density parity-check (LDPC) codes, which were first introduced as LDPC convolutional codes, have been shown to exhibit excellent performance under low-complexity belief-propagation decoding. This phenomenon is now termed threshold saturation via spatial coupling. Spatially-coupled codes have been successfully applied in numerous areas. In particular, it was proven that spatially-coupled regular LDPC codes universally achieve capacity over the class of binary memoryless symmetric (BMS) channels under belief-propagation decoding. Recently, potential functions have been used to simplify threshold saturation proofs for scalar and vector recursions. In this paper, potential functions are used to prove threshold saturation for irregular LDPC and low-density generator-matrix (LDGM) codes on BMS channels, extending the simplified proof technique to BMS channels. The corresponding potential functions are closely related to the average Bethe free entropy of the ensembles in the large-system limit. These functions also appear in statistical physics when the replica method is used to analyze optimal decoding.
Analysis of Amoeba Active Contours
Venue: arXiv cs.CV 2014
Year: 2014

Subject of this paper is the theoretical analysis of structure-adaptive median filter algorithms that approximate curvature-based PDEs for image filtering and segmentation. These so-called morphological amoeba filters are based on a concept introduced by Lerallut et al. They achieve similar results as the well-known geodesic active contour and self-snakes PDEs. In the present work, the PDE approximated by amoeba active contours is derived for a general geometric situation and general amoeba metric. This PDE is structurally similar but not identical to the geodesic active contour equation. It reproduces the previous PDE approximation results for amoeba median filters as special cases. Furthermore, modifications of the basic amoeba active contour algorithm are analysed that are related to the morphological force terms frequently used with geodesic active contours. Experiments demonstrate the basic behaviour of amoeba active contours and its similarity to geodesic active contours.
Building Programmable Wireless Networks: An Architectural Survey
Venue: arXiv cs.NI 2014
Year: 2014

In recent times, there have been a lot of efforts for improving the ossified Internet architecture in a bid to sustain unstinted growth and innovation. A major reason for the perceived architectural ossification is the lack of ability to program the network as a system. This situation has resulted partly from historical decisions in the original Internet design which emphasized decentralized network operations through co-located data and control planes on each network device. The situation for wireless networks is no different resulting in a lot of complexity and a plethora of largely incompatible wireless technologies. The emergence of "programmable wireless networks", that allow greater flexibility, ease of management and configurability, is a step in the right direction to overcome the aforementioned shortcomings of the wireless networks. In this paper, we provide a broad overview of the architectures proposed in literature for building programmable wireless networks focusing primarily on three popular techniques, i.e., software defined networks, cognitive radio networks, and virtualized networks. This survey is a self-contained tutorial on these techniques and its applications. We also discuss the opportunities and challenges in building next-generation programmable wireless networks and identify open research issues and future research directions.
Bijective Mappings Of Meshes With Boundary And The Degree In Mesh Processing
Venue: arXiv cs.CG 2014
Year: 2014

This paper introduces three sets of sufficient conditions, for generating bijective simplicial mappings of manifold meshes. A necessary condition for a simplicial mapping of a mesh to be injective is that it either maintains the orientation of all elements or flips all the elements. However, these conditions are known to be insufficient for injectivity of a simplicial map. In this paper we provide additional simple conditions that, together with the above mentioned necessary conditions guarantee injectivity of the simplicial map. The first set of conditions generalizes classical global inversion theorems to the mesh (piecewise-linear) case. That is, proves that in case the boundary simplicial map is bijective and the necessary condition holds then the map is injective and onto the target domain. The second set of conditions is concerned with mapping of a mesh to a polytope and replaces the (often hard) requirement of a bijective boundary map with a collection of linear constraints and guarantees that the resulting map is injective over the interior of the mesh and onto. These linear conditions provide a practical tool for optimizing a map of the mesh onto a given polytope while allowing the boundary map to adjust freely and keeping the injectivity property in the interior of the mesh. The third set of conditions adds to the second set the requirement that the boundary maps are orientation preserving as-well (with a proper definition of boundary map orientation). This set of conditions guarantees that the map is injective on the boundary of the mesh as-well as its interior. Several experiments using the sufficient conditions are shown for mapping triangular meshes. A secondary goal of this paper is to advocate and develop the tool of degree in the context of mesh processing.
New Conditions for Sparse Phase Retrieval
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of sparse phase retrieval, where a $k$-sparse signal ${\bf x} \in {\mathbb R}^n \textrm{ (or } {\mathbb C}^n\textrm{)}$ is measured as ${\bf y} = |{\bf Ax}|,$ where ${\bf A} \in {\mathbb R}^{m \times n} \textrm{ (or } {\mathbb C}^{m \times n}\textrm{ respectively)}$ is a measurement matrix and $|\cdot|$ is the element-wise absolute value. For a real signal and a real measurement matrix ${\bf A}$, we show that $m = 2k$ measurements are necessary and sufficient to recover ${\bf x}$ uniquely. For complex signal ${\bf x} \in {\mathbb C}^n$ and ${\bf A} \in {\mathbb C}^{m \times n}$, we show that $m = 4k-2$ phaseless measurements are sufficient to recover ${\bf x}$. It is known that the multiplying constant $4$ in $m = 4k-2$ cannot be improved.
Simple CHT: A New Derivation of the Weakest Failure Detector for Consensus
Venue: arXiv cs.DC 2014
Year: 2014

The paper proposes an alternative proof that Omega, an oracle that outputs a process identifier and guarantees that eventually the same correct process identifier is output at all correct processes, provides minimal information about failures for solving consensus in read-write shared-memory systems: every oracle that gives enough failure information to solve consensus can be used to implement Omega. Unlike the original proof by Chandra, Hadzilacos and Toueg (CHT), the proof presented in this paper builds upon the very fact that 2-process wait-free consensus is impossible. Also, since the oracle that is used to implement can solve consensus, the implementation is allowed to directly access consensus objects. As a result, the proposed proof is shorter and conceptually simpler than the original one.
Polytopic uncertainty for linear systems: New and old complexity results
Venue: arXiv cs.SY 2014
Year: 2014

We survey the problem of deciding the stability or stabilizability of uncertain linear systems whose region of uncertainty is a polytope. This natural setting has applications in many fields of applied science, from Control Theory to Systems Engineering to Biology. We focus on the algorithmic decidability of this property when one is given a particular polytope. This setting gives rise to several different algorithmic questions, depending on the nature of time (discrete/continuous), the property asked (stability/stabilizability), or the type of uncertainty (fixed/switching). Several of these questions have been answered in the literature in the last thirty years. We point out the ones that have remained open, and we answer all of them, except one which we raise as an open question. In all the cases, the results are negative in the sense that the questions are NP-hard. As a byproduct, we obtain complexity results for several other matrix problems in Systems and Control.
A Partial Derandomization of PhaseLift using Spherical Designs
Venue: arXiv cs.IT 2014
Year: 2014

The problem of retrieving phase information from amplitude measurements alone has appeared in many scientific disciplines over the last century. PhaseLift is a recently introduced algorithm for phase recovery that is computationally efficient, numerically stable, and comes with rigorous performance guarantees. PhaseLift is optimal in the sense that the number of amplitude measurements required for phase reconstruction scales linearly with the dimension of the signal. However, it specifically demands Gaussian random measurement vectors - a limitation that restricts practical utility and obscures the specific properties of measurement ensembles that enable phase retrieval. Here we present a partial derandomization of PhaseLift that only requires sampling from certain polynomial size vector configurations, called t-designs. Such configurations have been studied in algebraic combinatorics, coding theory, and quantum information. We prove reconstruction guarantees for a number of measurements that depends on the degree t of the design. If the degree is allowed to to grow logarithmically with the dimension, the bounds become tight up to polylog-factors. Beyond the specific case of PhaseLift, this work highlights the utility of spherical designs for the derandomization of data recovery schemes.
A Low-Complexity Graph-Based LMMSE Receiver Designed for Colored Noise Induced by FTN-Signaling
Venue: arXiv cs.IT 2014
Year: 2014

We propose a low complexity graph-based linear minimum mean square error (LMMSE) equalizer which considers both the intersymbol interference (ISI) and the effect of non-white noise inherent in Faster-than-Nyquist (FTN) signaling. In order to incorporate the statistics of noise signal into the factor graph over which the LMMSE algorithm is implemented, we suggest a method that models it as an autoregressive (AR) process. Furthermore, we develop a new mechanism for exchange of information between the proposed equalizer and the channel decoder through turbo iterations. Based on these improvements, we show that the proposed low complexity receiver structure performs close to the optimal decoder operating in ISI-free ideal scenario without FTN signaling through simulations.
Designing Multi-User MIMO for Energy Efficiency: When is Massive MIMO the Answer?
Venue: arXiv cs.IT 2014
Year: 2014

Assume that a multi-user multiple-input multiple-output (MIMO) communication system must be designed to cover a given area with maximal energy efficiency (bit/Joule). What are the optimal values for the number of antennas, active users, and transmit power? By using a new model that describes how these three parameters affect the total energy efficiency of the system, this work provides closed-form expressions for their optimal values and interactions. In sharp contrast to common belief, the transmit power is found to increase (not decrease) with the number of antennas. This implies that energy efficient systems can operate at high signal-to-noise ratio (SNR) regimes in which the use of interference-suppressing precoding schemes is essential. Numerical results show that the maximal energy efficiency is achieved by a massive MIMO setup wherein hundreds of antennas are deployed to serve relatively many users using interference-suppressing regularized zero-forcing precoding.
A Game Theoretic Analysis for Energy Efficient Heterogeneous Networks
Venue: arXiv cs.GT 2014
Year: 2014

Smooth and green future extension/scalability (e.g., from sparse to dense, from small-area dense to large-area dense, or from normal-dense to super-dense) is an important issue in heterogeneous networks. In this paper, we study energy efficiency of heterogeneous networks for both sparse and dense two-tier small cell deployments. We formulate the problem as a hierarchical (Stackelberg) game in which the macro cell is the leader whereas the small cell is the follower. Both players want to strategically decide on their power allocation policies in order to maximize the energy efficiency of their registered users. A backward induction method has been used to obtain a closed-form expression of the Stackelberg equilibrium. It is shown that the energy efficiency is maximized when only one sub-band is exploited for the players of the game depending on their fading channel gains. Simulation results are presented to show the effectiveness of the proposed scheme.
Topological Additive Numbering of Directed Acyclic Graphs
Venue: arXiv cs.CC 2014
Year: 2014

We propose to study a problem that arises naturally from both Topological Numbering of Directed Acyclic Graphs, and Additive Coloring (also known as Lucky Labeling). Let $D$ be a digraph and $f$ a labeling of its vertices with positive integers; denote by $S(v)$ the sum of labels over all neighbors of each vertex $v$. The labeling $f$ is called \emph{topological additive numbering} if $S(u) < S(v)$ for each arc $(u,v)$ of the digraph. The problem asks to find the minimum number $k$ for which $D$ has a topological additive numbering with labels belonging to $\{ 1, \ldots, k \}$, denoted by $η_t(D)$. We characterize when a digraph has topological additive numberings, give a lower bound for $η_t(D)$, and provide an integer programming formulation for our problem, characterizing when its coefficient matrix is totally unimodular. We also present some families for which $η_t(D)$ can be computed in polynomial time. Finally, we prove that this problem is \np-Hard even when its input is restricted to planar bipartite digraphs.