OpenRaiser/Intern-Atlas huggingface dataset:
MoM-SO: a Complete Method for Computing the Impedance of Cable Systems Including Skin, Proximity, and Ground Return Effects
Venue: arXiv cs.CE 2015
Year: 2015

The availability of accurate and broadband models for underground and submarine cable systems is of paramount importance for the correct prediction of electromagnetic transients in power grids. Recently, we proposed the MoM-SO method for extracting the series impedance of power cables while accounting for skin and proximity effect in the conductors. In this paper, we extend the method to include ground return effects and to handle cables placed inside a tunnel. Numerical tests show that the proposed method is more accurate than widely-used analytic formulas, and is much faster than existing proximity-aware approaches like finite elements. For a three-phase cable system in a tunnel, the proposed method requires only 0.3 seconds of CPU time per frequency point, against the 8.3 minutes taken by finite elements, for a speed up beyond 1000 X.
Variance-Constrained Actor-Critic Algorithms for Discounted and Average Reward MDPs
Venue: arXiv cs.LG 2015
Year: 2015

In many sequential decision-making problems we may want to manage risk by minimizing some measure of variability in rewards in addition to maximizing a standard criterion. Variance related risk measures are among the most common risk-sensitive criteria in finance and operations research. However, optimizing many such criteria is known to be a hard problem. In this paper, we consider both discounted and average reward Markov decision processes. For each formulation, we first define a measure of variability for a policy, which in turn gives us a set of risk-sensitive criteria to optimize. For each of these criteria, we derive a formula for computing its gradient. We then devise actor-critic algorithms that operate on three timescales - a TD critic on the fastest timescale, a policy gradient (actor) on the intermediate timescale, and a dual ascent for Lagrange multipliers on the slowest timescale. In the discounted setting, we point out the difficulty in estimating the gradient of the variance of the return and incorporate simultaneous perturbation approaches to alleviate this. The average setting, on the other hand, allows for an actor update using compatible features to estimate the gradient of the variance. We establish the convergence of our algorithms to locally risk-sensitive optimal policies. Finally, we demonstrate the usefulness of our algorithms in a traffic signal control application.
The matching polytope does not admit fully-polynomial size relaxation schemes
Venue: arXiv cs.CC 2015
Year: 2015

The groundbreaking work of Rothvoß [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the matching polytope has exponential extension complexity). We generalize this result by deriving strong bounds on the polyhedral inapproximability of the matching polytope: for fixed $0 < \varepsilon < 1$, every polyhedral $(1 + \varepsilon / n)$-approximation requires an exponential number of inequalities, where $n$ is the number of vertices. This is sharp given the well-known $ρ$-approximation of size $O(\binom{n}{ρ/(ρ-1)})$ provided by the odd-sets of size up to $ρ/(ρ-1)$. Thus matching is the first problem in $P$, whose natural linear encoding does not admit a fully polynomial-size relaxation scheme (the polyhedral equivalent of an FPTAS), which provides a sharp separation from the polynomial-size relaxation scheme obtained e.g., via constant-sized odd-sets mentioned above. Our approach reuses ideas from Rothvoß [arxiv:1311.2369], however the main lower bounding technique is different. While the original proof is based on the hyperplane separation bound (also called the rectangle corruption bound), we employ the information-theoretic notion of common information as introduced in Braun and Pokutta [http://eccc.hpi-web.de/report/2013/056/], which allows to analyze perturbations of slack matrices. It turns out that the high extension complexity for the matching polytope stem from the same source of hardness as for the correlation polytope: a direct sum structure.
Abstraction of Elementary Hybrid Systems by Variable Transformation
Venue: arXiv cs.SY 2015
Year: 2015

Elementary hybrid systems (EHSs) are those hybrid systems (HSs) containing elementary functions such as exp, ln, sin, cos, etc. EHSs are very common in practice, especially in safety-critical domains. Due to the non-polynomial expressions which lead to undecidable arithmetic, verification of EHSs is very hard. Existing approaches based on partition of state space or over-approximation of reachable sets suffer from state explosion or inflation of numerical errors. In this paper, we propose a symbolic abstraction approach that reduces EHSs to polynomial hybrid systems (PHSs), by replacing all non-polynomial terms with newly introduced variables. Thus the verification of EHSs is reduced to the one of PHSs, enabling us to apply all the well-established verification techniques and tools for PHSs to EHSs. In this way, it is possible to avoid the limitations of many existing methods. We illustrate the abstraction approach and its application in safety verification of EHSs by several real world examples.
Tight Bounds for Symmetric Divergence Measures and a Refined Bound for Lossless Source Coding
Venue: arXiv cs.IT 2015
Year: 2015

Tight bounds for several symmetric divergence measures are derived in terms of the total variation distance. It is shown that each of these bounds is attained by a pair of 2 or 3-element probability distributions. An application of these bounds for lossless source coding is provided, refining and improving a certain bound by Csiszár. Another application of these bounds has been recently introduced by Yardi. et al. for channel-code detection.
Lattice Codes for Many-to-One Interference Channels With and Without Cognitive Messages
Venue: arXiv cs.IT 2015
Year: 2015

A new achievable rate region is given for the Gaussian cognitive many-to-one interference channel. The proposed novel coding scheme is based on the compute-and-forward approach with lattice codes. Using the idea of decoding sums of codewords, our scheme improves considerably upon the conventional coding schemes which treat interference as noise or decode messages simultaneously. Our strategy also extends directly to the usual many-to-one interference channels without cognitive messages. Comparing to the usual compute-and-forward scheme where a fixed lattice is used for the code construction, the novel scheme employs scaled lattices and also encompasses key ingredients of the existing schemes for the cognitive interference channel. With this new component, our scheme achieves a larger rate region in general. For some symmetric channel settings, new constant gap or capacity results are established, which are independent of the number of users in the system.
Multi-Linear Interactive Matrix Factorization
Venue: arXiv cs.IR 2015
Year: 2015

Recommender systems, which can significantly help users find their interested items from the information era, has attracted an increasing attention from both the scientific and application society. One of the widest applied recommendation methods is the Matrix Factorization (MF). However, most of MF based approaches focus on the user-item rating matrix, but ignoring the ingredients which may have significant influence on users' preferences on items. In this paper, we propose a multi-linear interactive MF algorithm (MLIMF) to model the interactions between the users and each event associated with their final decisions. Our model considers not only the user-item rating information but also the pairwise interactions based on some empirically supported factors. In addition, we compared the proposed model with three typical other methods: user-based collaborative filtering (UCF), item-based collaborative filtering (ICF) and regularized MF (RMF). Experimental results on two real-world datasets, \emph{MovieLens} 1M and \emph{MovieLens} 100k, show that our method performs much better than other three methods in the accuracy of recommendation. This work may shed some light on the in-depth understanding of modeling user online behaviors and the consequent decisions.
Thou Shalt is not You Will
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we discuss some reasons why temporal logic might not be suitable to model real life norms. To show this, we present a novel deontic logic contrary-to-duty/derived permission paradox based on the interaction of obligations, permissions and contrary-to-duty obligations. The paradox is inspired by real life norms.
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
Venue: arXiv cs.GT 2015
Year: 2015

We study combinatorial auctions where each item is sold separately but simultaneously via a second price auction. We ask whether it is possible to efficiently compute in this game a pure Nash equilibrium with social welfare close to the optimal one. We show that when the valuations of the bidders are submodular, in many interesting settings (e.g., constant number of bidders, budget additive bidders) computing an equilibrium with good welfare is essentially as easy as computing, completely ignoring incentives issues, an allocation with good welfare. On the other hand, for subadditive valuations, we show that computing an equilibrium requires exponential communication. Finally, for XOS (a.k.a. fractionally subadditive) valuations, we show that if there exists an efficient algorithm that finds an equilibrium, it must use techniques that are very different from our current ones.
Batch Arrival Multiserver Queue with Setup Time
Venue: arXiv cs.PF 2015
Year: 2015

Queues with setup time are extensively studied because they have application in performance evaluation of power-saving data centers. In a data center, there are a huge number of servers which consume a large amount of energy. In the current technology, an idle server still consumes about 60\% of its peak processing a job. Thus, the only way to save energy is to turn off servers which are not processing a job. However, when there are some waiting jobs, we have to turn on the OFF servers. A server needs some setup time to be active during which it consumes energy but cannot process a job. Therefore, there exists a trade-off between power consumption and delay performance. Gandhi et al. \cite{Gandhi10a,Gandhi10} analyze this trade-off using an M/M/$c$ queue with staggered setup (one server in setup at a time). In this paper, using an alternative approach, we obtain generating functions for the joint stationary distribution of the number of active servers and that of jobs in the system for a more general model with batch arrivals and state-dependent setup time. We further obtain moments for the queue size. Numerical results reveal that keeping the same traffic intensity, the mean power consumption decreases with the mean batch size for the case of fixed batch size. One of the main theoretical contribution is a new conditional decomposition formula showing that the number of waiting customers under the condition that all servers are busy can be decomposed to the sum of two independent random variables where the first is the same quantity in the corresponding model without setup time while the second is the number of waiting customers before an arbitrary customer.
Transparallel mind: Classical computing with quantum power
Venue: arXiv cs.AI 2015
Year: 2015

Inspired by the extraordinary computing power promised by quantum computers, the quantum mind hypothesis postulated that quantum mechanical phenomena are the source of neuronal synchronization, which, in turn, might underlie consciousness. Here, I present an alternative inspired by a classical computing method with quantum power. This method relies on special distributed representations called hyperstrings. Hyperstrings are superpositions of up to an exponential number of strings, which -- by a single-processor classical computer -- can be evaluated in a transparallel fashion, that is, simultaneously as if only one string were concerned. Building on a neurally plausible model of human visual perceptual organization, in which hyperstrings are formal counterparts of transient neural assemblies, I postulate that synchronization in such assemblies is a manifestation of transparallel information processing. This accounts for the high combinatorial capacity and speed of human visual perceptual organization and strengthens ideas that self-organizing cognitive architecture bridges the gap between neurons and consciousness.
Minimal Output Unstable Configurations in Chemical Reaction Networks and Deciders
Venue: arXiv cs.CC 2015
Year: 2015

We study the set of output stable configurations of chemical reaction deciders (CRDs). It turns out that CRDs with only bimolecular reactions (which are almost equivalent to population protocols) have a special structure that allows for an algorithm to efficiently compute their finite set of minimal output unstable configurations. As a consequence, a relatively large set of configurations may be efficiently checked for output stability. We also provide a number of observations regarding the semilinearity result of Angluin et al. [Distrib. Comput., 2007] from the context of population protocols (which is a central result for output stable CRDs). In particular, we observe that the computation-friendly class of totally stable CRDs has equal expressive power as the larger class of output stable CRDs.
Harvest-Then-Cooperate: Wireless-Powered Cooperative Communications
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a wireless-powered cooperative communication network consisting of one hybrid access-point (AP), one source, and one relay. In contrast to conventional cooperative networks, the source and relay in the considered network have no embedded energy supply. They need to rely on the energy harvested from the signals broadcasted by the AP for their cooperative information transmission. Based on this three-node reference model, we propose a harvest-then-cooperate (HTC) protocol, in which the source and relay harvest energy from the AP in the downlink and work cooperatively in the uplink for the source's information transmission. Considering a delay-limited transmission mode, the approximate closed-form expression for the average throughput of the proposed protocol is derived over Rayleigh fading channels. Subsequently, this analysis is extended to the multi-relay scenario, where the approximate throughput of the HTC protocol with two popular relay selection schemes is derived. The asymptotic analyses for the throughput performance of the considered schemes at high signal-to-noise radio are also provided. All theoretical results are validated by numerical simulations. The impacts of the system parameters, such as time allocation, relay number, and relay position, on the throughput performance are extensively investigated.
Parallel Graph Partitioning for Complex Networks
Venue: arXiv cs.DC 2015
Year: 2015

Processing large complex networks like social networks or web graphs has recently attracted considerable interest. In order to do this in parallel, we need to partition them into pieces of about equal size. Unfortunately, previous parallel graph partitioners originally developed for more regular mesh-like networks do not work well for these networks. This paper addresses this problem by parallelizing and adapting the label propagation technique originally developed for graph clustering. By introducing size constraints, label propagation becomes applicable for both the coarsening and the refinement phase of multilevel graph partitioning. We obtain very high quality by applying a highly parallel evolutionary algorithm to the coarsened graph. The resulting system is both more scalable and achieves higher quality than state-of-the-art systems like ParMetis or PT-Scotch. For large complex networks the performance differences are very big. For example, our algorithm can partition a web graph with 3.3 billion edges in less than sixteen seconds using 512 cores of a high performance cluster while producing a high quality partition -- none of the competing systems can handle this graph on our system.
Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
Venue: arXiv cs.CV 2015
Year: 2015

We propose a Branch-and-Cut (B&C) method for solving general MAP-MRF inference problems. The core of our method is a very efficient bounding procedure, which combines scalable semidefinite programming (SDP) and a cutting-plane method for seeking violated constraints. In order to further speed up the computation, several strategies have been exploited, including model reduction, warm start and removal of inactive constraints. We analyze the performance of the proposed method under different settings, and demonstrate that our method either outperforms or performs on par with state-of-the-art approaches. Especially when the connectivities are dense or when the relative magnitudes of the unary costs are low, we achieve the best reported results. Experiments show that the proposed algorithm achieves better approximation than the state-of-the-art methods within a variety of time budgets on challenging non-submodular MAP-MRF inference problems.
Forward - Backward Greedy Algorithms for Atomic Norm Regularization
Venue: arXiv cs.DS 2015
Year: 2015

In many signal processing applications, the aim is to reconstruct a signal that has a simple representation with respect to a certain basis or frame. Fundamental elements of the basis known as "atoms" allow us to define "atomic norms" that can be used to formulate convex regularizations for the reconstruction problem. Efficient algorithms are available to solve these formulations in certain special cases, but an approach that works well for general atomic norms, both in terms of speed and reconstruction accuracy, remains to be found. This paper describes an optimization algorithm called CoGEnT that produces solutions with succinct atomic representations for reconstruction problems, generally formulated with atomic-norm constraints. CoGEnT combines a greedy selection scheme based on the conditional gradient approach with a backward (or "truncation") step that exploits the quadratic nature of the objective to reduce the basis size. We establish convergence properties and validate the algorithm via extensive numerical experiments on a suite of signal processing applications. Our algorithm and analysis also allow for inexact forward steps and for occasional enhancements of the current representation to be performed. CoGEnT can outperform the basic conditional gradient method, and indeed many methods that are tailored to specific applications, when the enhancement and truncation steps are defined appropriately. We also introduce several novel applications that are enabled by the atomic-norm framework, including tensor completion, moment problems in signal processing, and graph deconvolution.
Distributed Channel Assignment in Cognitive Radio Networks: Stable Matching and Walrasian Equilibrium
Venue: arXiv cs.IT 2015
Year: 2015

We consider a set of secondary transmitter-receiver pairs in a cognitive radio setting. Based on channel sensing and access performances, we consider the problem of assigning channels orthogonally to secondary users through distributed coordination and cooperation algorithms. Two economic models are applied for this purpose: matching markets and competitive markets. In the matching market model, secondary users and channels build two agent sets. We implement a stable matching algorithm in which each secondary user, based on his achievable rate, proposes to the coordinator to be matched with desirable channels. The coordinator accepts or rejects the proposals based on the channel preferences which depend on interference from the secondary user. The coordination algorithm is of low complexity and can adapt to network dynamics. In the competitive market model, channels are associated with prices and secondary users are endowed with monetary budget. Each secondary user, based on his utility function and current channel prices, demands a set of channels. A Walrasian equilibrium maximizes the sum utility and equates the channel demand to their supply. We prove the existence of Walrasian equilibrium and propose a cooperative mechanism to reach it. The performance and complexity of the proposed solutions are illustrated by numerical simulations.
Content Caching and Delivery over Heterogeneous Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

Emerging heterogeneous wireless architectures consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). We design a coded caching-and-delivery scheme for such architectures that equips APs with storage, enabling content pre-fetching prior to knowing user demands. Users requesting content are served by connecting to local APs with cached content, as well as by listening to a BS broadcast transmission. For any given content popularity profile, the goal is to design the caching-and-delivery scheme so as to optimally trade off the transmission cost at the BS against the storage cost at the APs and the user cost of connecting to multiple APs. We design a coded caching scheme for non-uniform content popularity that dynamically allocates user access to APs based on requested content. We demonstrate the approximate optimality of our scheme with respect to information-theoretic bounds. We numerically evaluate it on a YouTube dataset and quantify the trade-off between transmission rate, storage, and access cost. Our numerical results also suggest the intriguing possibility that, to gain most of the benefits of coded caching, it suffices to divide the content into a small number of popularity classes.
Coded Caching for Multi-level Popularity and Access
Venue: arXiv cs.IT 2015
Year: 2015

To address the exponentially rising demand for wireless content, use of caching is emerging as a potential solution. It has been recently established that joint design of content delivery and storage (coded caching) can significantly improve performance over conventional caching. Coded caching is well suited to emerging heterogeneous wireless architectures which consist of a dense deployment of local-coverage wireless access points (APs) with high data rates, along with sparsely-distributed, large-coverage macro-cell base stations (BS). This enables design of coded caching-and-delivery schemes that equip APs with storage, and place content in them in a way that creates coded-multicast opportunities for combining with macro-cell broadcast to satisfy users even with different demands. Such coded-caching schemes have been shown to be order-optimal with respect to the BS transmission rate, for a system with single-level content, i.e., one where all content is uniformly popular. In this work, we consider a system with non-uniform popularity content which is divided into multiple levels, based on varying degrees of popularity. The main contribution of this work is the derivation of an order-optimal scheme which judiciously shares cache memory among files with different popularities. To show order-optimality we derive new information-theoretic lower bounds, which use a sliding-window entropy inequality, effectively creating a non-cutset bound. We also extend the ideas to when users can access multiple caches along with the broadcast. Finally we consider two extreme cases of user distribution across caches for the multi-level popularity model: a single user per cache (single-user setup) versus a large number of users per cache (multi-user setup), and demonstrate a dichotomy in the order-optimal strategies for these two extreme cases.