OpenRaiser/Intern-Atlas huggingface dataset:
Three Variables Suffice for Real-Time Specification
Venue: arXiv cs.LO 2015
Year: 2015

A natural framework for real-time specification is monadic first-order logic over the structure $(\mathbb{R},<,+1)$---the ordered real line with unary $+1$ function. Our main result is that $(\mathbb{R},<,+1)$ has the 3-variable property: every monadic first-order formula with at most 3 free variables is equivalent over this structure to one that uses 3 variables in total. As a corollary we obtain also the 3-variable property for the structure $(\mathbb{R},<,f)$ for any fixed linear function $f:\mathbb{R}\rightarrow\mathbb{R}$. On the other hand, we exhibit a countable dense linear order $(E,<)$ and a bijection $f:E\rightarrow E$ such that $(E,<,f)$ does not have the $k$-variable property for any $k$.
Secrecy Wireless Information and Power Transfer in Fading Wiretap Channel
Venue: arXiv cs.IT 2015
Year: 2015

Simultaneous wireless information and power transfer (SWIPT) has recently drawn significant interests for its dual use of radio signals to provide wireless data and energy access at the same time. However, a challenging secrecy communication issue arises as the messages sent to the information receivers (IRs) may be eavesdropped by the energy receivers (ERs), which are presumed to harvest energy only from the received signals. To tackle this problem, we propose in this paper an artificial noise (AN) aided transmission scheme to facilitate the secrecy information transmission to IRs and yet meet the energy harvesting requirement for ERs, under the assumption that the AN can be cancelled at IRs but not at ERs. Specifically, the proposed scheme splits the transmit power into two parts, to send the confidential message to the IR and an AN to interfere with the ER, respectively. Under a simplified three-node wiretap channel setup, the transmit power allocations and power splitting ratios over fading channels are jointly optimized to minimize the outage probability for delay-limited secrecy information transmission, or to maximize the average rate for no-delay-limited secrecy information transmission, subject to a combination of average and peak power constraints at the transmitter as well as an average energy harvesting constraint at the ER. Both the secrecy outage probability minimization and average rate maximization problems are shown to be non-convex, for each of which we propose the optimal solution based on the dual decomposition as well as suboptimal solution based on the alternating optimization. Furthermore, two benchmark schemes are introduced for comparison. Finally, the performances of proposed schemes are evaluated by simulations in terms of various trade-offs for wireless (secrecy) information versus energy transmissions.
Fuzzy inequational logic
Venue: arXiv cs.LO 2015
Year: 2015

We present a logic for reasoning about graded inequalities which generalizes the ordinary inequational logic used in universal algebra. The logic deals with atomic predicate formulas of the form of inequalities between terms and formalizes their semantic entailment and provability in graded setting which allows to draw partially true conclusions from partially true assumptions. We follow the Pavelka approach and define general degrees of semantic entailment and provability using complete residuated lattices as structures of truth degrees. We prove the logic is Pavelka-style complete. Furthermore, we present a logic for reasoning about graded if-then rules which is obtained as particular case of the general result.
Computing with Coloured Tangles
Venue: arXiv cs.CC 2015
Year: 2015

We suggest a diagrammatic model of computation based on an axiom of distributivity. A diagram of a decorated coloured tangle, similar to those that appear in low dimensional topology, plays the role of a circuit diagram. Equivalent diagrams represent bisimilar computations. We prove that our model of computation is Turing complete, and that with bounded resources it can moreover decide any language in complexity class IP, sometimes with better performance parameters than corresponding classical protocols.
Convex Calibration Dimension for Multiclass Loss Matrices
Venue: arXiv cs.LG 2015
Year: 2015

We study consistency properties of surrogate loss functions for general multiclass learning problems, defined by a general multiclass loss matrix. We extend the notion of classification calibration, which has been studied for binary and multiclass 0-1 classification problems (and for certain other specific learning problems), to the general multiclass setting, and derive necessary and sufficient conditions for a surrogate loss to be calibrated with respect to a loss matrix in this setting. We then introduce the notion of convex calibration dimension of a multiclass loss matrix, which measures the smallest `size' of a prediction space in which it is possible to design a convex surrogate that is calibrated with respect to the loss matrix. We derive both upper and lower bounds on this quantity, and use these results to analyze various loss matrices. In particular, we apply our framework to study various subset ranking losses, and use the convex calibration dimension as a tool to show both the existence and non-existence of various types of convex calibrated surrogates for these losses. Our results strengthen recent results of Duchi et al. (2010) and Calauzenes et al. (2012) on the non-existence of certain types of convex calibrated surrogates in subset ranking. We anticipate the convex calibration dimension may prove to be a useful tool in the study and design of surrogate losses for general multiclass learning problems.
Algorithm xxx: RIDC Methods -- A Family of Parallel Time-Integrators
Venue: arXiv cs.MS 2015
Year: 2015

Revisionist integral deferred correction (RIDC) methods are a family of parallel--in--time methods to solve systems of initial values problems. The approach is able to bootstrap lower order time integrators to provide high order approximations in approximately the same wall clock time, hence providing a multiplicative increase in the number of compute cores utilized. Here we provide a C++ framework which automatically produces a parallel--in--time solution of a system of initial value problems given user supplied code for the right hand side of the system and a sequential code for a first-order time step. The user supplied time step routine may be explicit or implicit and may make use of any auxiliary libraries which take care of the solution of any nonlinear algebraic systems which may arise or the numerical linear algebra required. The code contains six examples of increasing complexity which also serve as templates to solve user defined problems.
Limits on Fundamental Limits to Computation
Venue: arXiv cs.ET 2015
Year: 2015

An indispensable part of our lives, computing has also become essential to industries and governments. Steady improvements in computer hardware have been supported by periodic doubling of transistor densities in integrated circuits over the last fifty years. Such Moore scaling now requires increasingly heroic efforts, stimulating research in alternative hardware and stirring controversy. To help evaluate emerging technologies and enrich our understanding of integrated-circuit scaling, we review fundamental limits to computation: in manufacturing, energy, physical space, design and verification effort, and algorithms. To outline what is achievable in principle and in practice, we recall how some limits were circumvented, compare loose and tight limits. We also point out that engineering difficulties encountered by emerging technologies may indicate yet-unknown limits.
Optimal Joint User Association and Resource Allocation in Heterogeneous Networks via Sparsity Pursuit
Venue: arXiv cs.NI 2015
Year: 2015

This paper studies the joint user association and resource allocation in heterogeneous networks (HetNets) from a novel perspective, motivated by and generalizing the idea of fractional frequency reuse. By treating the multi-cell multi-user resource allocation as resource partitioning among multiple reuse patterns, we propose a unified framework to analyze and compare a wide range of user association and resource allocation strategies for HetNets, and provide an optimal benchmark for network performance. The enabling mechanisms are a novel formulation to consider all possible interference patterns or any pre-defined subset of patterns, and efficient sparsity-pursuit algorithms to find the solution. A notable feature of this formulation is that the patterns remain fixed during the resource optimization process. This creates a favorable opportunity for convex formulations while still considering interference coupling. More importantly, in view of the fact that multi-cell resource allocation is very computational demanding, our framework provides a systematic way to trade off performance for the reduction of computational complexity by restricting the candidate patterns to a small number of feature patterns. Relying on the sparsity-pursuit capability of the proposed algorithms, we develop a practical guideline to identify the feature patterns. Numerical results show that the identified feature patterns can significantly improve the existing strategies, and jointly optimizing the user association and resource allocation indeed brings considerable gain.
Massive MIMO with Non-Ideal Arbitrary Arrays: Hardware Scaling Laws and Circuit-Aware Design
Venue: arXiv cs.IT 2015
Year: 2015

Massive multiple-input multiple-output (MIMO) systems are cellular networks where the base stations (BSs) are equipped with unconventionally many antennas, deployed on co-located or distributed arrays. Huge spatial degrees-of-freedom are achieved by coherent processing over these massive arrays, which provide strong signal gains, resilience to imperfect channel knowledge, and low interference. This comes at the price of more infrastructure; the hardware cost and circuit power consumption scale linearly/affinely with the number of BS antennas $N$. Hence, the key to cost-efficient deployment of large arrays is low-cost antenna branches with low circuit power, in contrast to today's conventional expensive and power-hungry BS antenna branches. Such low-cost transceivers are prone to hardware imperfections, but it has been conjectured that the huge degrees-of-freedom would bring robustness to such imperfections. We prove this claim for a generalized uplink system with multiplicative phase-drifts, additive distortion noise, and noise amplification. Specifically, we derive closed-form expressions for the user rates and a scaling law that shows how fast the hardware imperfections can increase with $N$ while maintaining high rates. The connection between this scaling law and the power consumption of different transceiver circuits is rigorously exemplified. This reveals that one can make the circuit power increase as $\sqrt{N}$, instead of linearly, by careful circuit-aware system design.
On Characterizing the Local Pooling Factor of Greedy Maximal Scheduling in Random Graphs
Venue: arXiv cs.IT 2015
Year: 2015

The study of the optimality of low-complexity greedy scheduling techniques in wireless communications networks is a very complex problem. The Local Pooling (LoP) factor provides a single-parameter means of expressing the achievable capacity region (and optimality) of one such scheme, greedy maximal scheduling (GMS). The exact LoP factor for an arbitrary network graph is generally difficult to obtain, but may be evaluated or bounded based on the network graph's particular structure. In this paper, we provide rigorous characterizations of the LoP factor in large networks modeled as Erdős-Rényi (ER) and random geometric (RG) graphs under the primary interference model. We employ threshold functions to establish critical values for either the edge probability or communication radius to yield useful bounds on the range and expectation of the LoP factor as the network grows large. For sufficiently dense random graphs, we find that the LoP factor is between 1/2 and 2/3, while sufficiently sparse random graphs permit GMS optimality (the LoP factor is 1) with high probability. We then place LoP within a larger context of commonly studied random graph properties centered around connectedness. We observe that edge densities permitting connectivity generally admit cycle subgraphs which forms the basis for the LoP factor upper bound of 2/3. We conclude with simulations to explore the regime of small networks, which suggest the probability that an ER or RG graph satisfies LoP and is connected decays quickly in network size.
A New IEEE 802.15.4 Simulation Model for OMNeT++ / INET
Venue: arXiv cs.NI 2015
Year: 2015

This paper introduces a new IEEE 802.15.4 simulation model for OMNeT++ / INET. 802.15.4 is an important underlying standard for wireless sensor networks and Internet of Things scenarios. The presented implementation is designed to be compatible with OMNeT++ 4.x and INET 2.x and laid-out to be expandable for newer revisions of the 802.15.4 standard. The source code is available online https://github.com/michaelkirsche/IEEE802154INET-Standalone
Maximizing k-Submodular Functions and Beyond
Venue: arXiv cs.DS 2015
Year: 2015

We consider the maximization problem in the value oracle model of functions defined on $k$-tuples of sets that are submodular in every orthant and $r$-wise monotone, where $k\geq 2$ and $1\leq r\leq k$. We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of $1/(1+r)$. For $r=k$, we give an analysis of a randomised greedy algorithm that shows that any such function can be approximated to a factor of $1/(1+\sqrt{k/2})$. In the case of $k=r=2$, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of $1/2$. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that $NP\neq RP$. Extending a result of Ando et al., we show that for any $k\geq 3$ submodularity in every orthant and pairwise monotonicity (i.e. $r=2$) precisely characterize $k$-submodular functions. Consequently, we obtain an approximation guarantee of $1/3$ (and thus independent of $k$) for the maximization problem of $k$-submodular functions.
The Evolution of First Person Vision Methods: A Survey
Venue: arXiv cs.CV 2015
Year: 2015

The emergence of new wearable technologies such as action cameras and smart-glasses has increased the interest of computer vision scientists in the First Person perspective. Nowadays, this field is attracting attention and investments of companies aiming to develop commercial devices with First Person Vision recording capabilities. Due to this interest, an increasing demand of methods to process these videos, possibly in real-time, is expected. Current approaches present a particular combinations of different image features and quantitative methods to accomplish specific objectives like object detection, activity recognition, user machine interaction and so on. This paper summarizes the evolution of the state of the art in First Person Vision video analysis between 1997 and 2014, highlighting, among others, most commonly used features, methods, challenges and opportunities within the field.
Lyapunov Functions Family Approach to Transient Stability Assessment
Venue: arXiv cs.SY 2015
Year: 2015

Analysis of transient stability of strongly nonlinear post-fault dynamics is one of the most computationally challenging parts of Dynamic Security Assessment. This paper proposes a novel approach for assessment of transient stability of the system. The approach generalizes the idea of energy methods, and extends the concept of energy function to a more general Lyapunov Functions Family (LFF) constructed via Semi-Definite-Programming techniques. Unlike the traditional energy function and its variations, the constructed Lyapunov functions are proven to be decreasing only in a finite neighborhood of the equilibrium point. However, we show that they can still certify stability of a broader set of initial conditions in comparison to the traditional energy function in the closest-UEP method. Moreover, the certificates of stability can be constructed via a sequence of convex optimization problems that are tractable even for large scale systems. We also propose specific algorithms for adaptation of the Lyapunov functions to specific initial conditions and demonstrate the effectiveness of the approach on a number of IEEE test cases.
Computing the coefficients for the power series solution of the Lane-Emden equation with the Python library SymPy
Venue: arXiv cs.MS 2015
Year: 2015

It is shown how the Python library Sympy can be used to compute symbolically the coefficients of the power series solution of the Lane-Emden equation (LEE). Sympy is an open source Python library for symbolic mathematics. The power series solutions are compared to the numerically computed solutions using matplotlib. The results of a run time measurement of the implemented algorithm are discussed at the end.
Statics and dynamics of selfish interactions in distributed service systems
Venue: arXiv cs.GT 2015
Year: 2015

We study a class of games which model the competition among agents to access some service provided by distributed service units and which exhibit congestion and frustration phenomena when service units have limited capacity. We propose a technique, based on the cavity method of statistical physics, to characterize the full spectrum of Nash equilibria of the game. The analysis reveals a large variety of equilibria, with very different statistical properties. Natural selfish dynamics, such as best-response, usually tend to large-utility equilibria, even though those of smaller utility are exponentially more numerous. Interestingly, the latter actually can be reached by selecting the initial conditions of the best-response dynamics close to the saturation limit of the service unit capacities. We also study a more realistic stochastic variant of the game by means of a simple and effective approximation of the average over the random parameters, showing that the properties of the average-case Nash equilibria are qualitatively similar to the deterministic ones.
Far-Field Compression for Fast Kernel Summation Methods in High Dimensions
Venue: arXiv cs.LG 2015
Year: 2015

We consider fast kernel summations in high dimensions: given a large set of points in $d$ dimensions (with $d \gg 3$) and a pair-potential function (the {\em kernel} function), we compute a weighted sum of all pairwise kernel interactions for each point in the set. Direct summation is equivalent to a (dense) matrix-vector multiplication and scales quadratically with the number of points. Fast kernel summation algorithms reduce this cost to log-linear or linear complexity. Treecodes and Fast Multipole Methods (FMMs) deliver tremendous speedups by constructing approximate representations of interactions of points that are far from each other. In algebraic terms, these representations correspond to low-rank approximations of blocks of the overall interaction matrix. Existing approaches require an excessive number of kernel evaluations with increasing $d$ and number of points in the dataset. To address this issue, we use a randomized algebraic approach in which we first sample the rows of a block and then construct its approximate, low-rank interpolative decomposition. We examine the feasibility of this approach theoretically and experimentally. We provide a new theoretical result showing a tighter bound on the reconstruction error from uniformly sampling rows than the existing state-of-the-art. We demonstrate that our sampling approach is competitive with existing (but prohibitively expensive) methods from the literature. We also construct kernel matrices for the Laplacian, Gaussian, and polynomial kernels -- all commonly used in physics and data analysis. We explore the numerical properties of blocks of these matrices, and show that they are amenable to our approach. Depending on the data set, our randomized algorithm can successfully compute low rank approximations in high dimensions. We report results for data sets with ambient dimensions from four to 1,000.
Massive MIMO with Optimal Power and Training Duration Allocation
Venue: arXiv cs.IT 2015
Year: 2015

We consider the uplink of massive multicell multiple-input multiple-output systems, where the base stations (BSs), equipped with massive arrays, serve simultaneously several terminals in the same frequency band. We assume that the BS estimates the channel from uplink training, and then uses the maximum ratio combining technique to detect the signals transmitted from all terminals in its own cell. We propose an optimal resource allocation scheme which jointly selects the training duration, training signal power, and data signal power in order to maximize the sum spectral efficiency, for a given total energy budget spent in a coherence interval. Numerical results verify the benefits of the optimal resource allocation scheme. Furthermore, we show that more training signal power should be used at low signal-to-noise ratio (SNRs), and vice versa at high SNRs. Interestingly, for the entire SNR regime, the optimal training duration is equal to the number of terminals.
A Ruin Theoretic Design Approach for Wireless Cellular Network Sharing with Facilities
Venue: arXiv cs.CY 2015
Year: 2015

With the rise of cheap small-cells in wireless cellular networks, there are new opportunities for third party providers to service local regions via sharing arrangements with traditional operators. In fact, such arrangements are highly desirable for large facilities---such as stadiums, universities, and mines---as they already need to cover property costs, and often have fibre backhaul and efficient power infrastructure. In this paper, we propose a new network sharing arrangement between large facilities and traditional operators. Our facility network sharing arrangement consists of two aspects: leasing of core network access and spectrum from traditional operators; and service agreements with users. Importantly, our incorporation of a user service agreement into the arrangement means that resource allocation must account for financial as well as physical resource constraints. This introduces a new non-trivial dimension into wireless network resource allocation, which requires a new evaluation framework---the data rate is no longer the only main performance metric. Moreover, despite clear economic incentives to adopt network sharing for facilities, a business case is lacking. As such, we develop a general socio-technical evaluation framework based on ruin-theory, where the key metric for the sharing arrangement is the probability that the facility has less than zero revenue surplus. We then use our framework to evaluate our facility network sharing arrangement, which offers guidance for leasing and service agreement negotiations, as well as design of the wireless network architecture, taking into account network revenue streams.
Algorithmic complexity for psychology: A user-friendly implementation of the coding theorem method
Venue: arXiv cs.CC 2015
Year: 2015

Kolmogorov-Chaitin complexity has long been believed to be impossible to approximate when it comes to short sequences (e.g. of length 5-50). However, with the newly developed \emph{coding theorem method} the complexity of strings of length 2-11 can now be numerically estimated. We present the theoretical basis of algorithmic complexity for short strings (ACSS) and describe an R-package providing functions based on ACSS that will cover psychologists' needs and improve upon previous methods in three ways: (1) ACSS is now available not only for binary strings, but for strings based on up to 9 different symbols, (2) ACSS no longer requires time-consuming computing, and (3) a new approach based on ACSS gives access to an estimation of the complexity of strings of any length. Finally, three illustrative examples show how these tools can be applied to psychology.