OpenRaiser/Intern-Atlas huggingface dataset:
A Tractable Framework for Exact Probability of Node Isolation and Minimum Node Degree Distribution in Finite Multi-hop Networks
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a tractable analytical framework for the exact calculation of probability of node isolation and minimum node degree distribution when $N$ sensor nodes are independently and uniformly distributed inside a finite square region. The proposed framework can accurately account for the boundary effects by partitioning the square into subregions, based on the transmission range and the node location. We show that for each subregion, the probability that a random node falls inside a disk centered at an arbitrary node located in that subregion can be expressed analytically in closed-form. Using the results for the different subregions, we obtain the exact probability of node isolation and minimum node degree distribution that serves as an upper bound for the probability of $k$-connectivity. Our theoretical framework is validated by comparison with the simulation results and shows that the minimum node degree distribution serves as a tight upper bound for the probability of $k$-connectivity. The proposed framework provides a very useful tool to accurately account for the boundary effects in the design of finite wireless networks.
Exploring associations between micro-level models of innovation diffusion and emerging macro-level adoption patterns
Venue: arXiv cs.SI 2013
Year: 2013

A micro-level agent-based model of innovation diffusion was developed that explicitly combines (a) an individual's perception of the advantages or relative utility derived from adoption, and (b) social influence from members of the individual's social network. The micro-model was used to simulate macro-level diffusion patterns emerging from different configurations of micro-model parameters. Micro-level simulation results matched very closely the adoption patterns predicted by the widely-used Bass macro-level model (Bass, 1969). For a portion of the domain, results from micro-simulations were consistent with aggregate-level adoption patterns reported in the literature. Induced Bass macro-level parameters and responded to changes in micro-parameters: (1) increased with the number of innovators and with the rate at which innovators are introduced; (2) increased with the probability of rewiring in small-world networks, as the characteristic path length decreases; and (3) an increase in the overall perceived utility of an innovation caused a corresponding increase in induced and values. Understanding micro to macro linkages can inform the design and assessment of marketing interventions on micro-variables - or processes related to them - to enhance adoption of future products or technologies.
Runtime Optimizations for Prediction with Tree-Based Models
Venue: arXiv cs.DB 2013
Year: 2013

Tree-based models have proven to be an effective solution for web ranking as well as other problems in diverse domains. This paper focuses on optimizing the runtime performance of applying such models to make predictions, given an already-trained model. Although exceedingly simple conceptually, most implementations of tree-based models do not efficiently utilize modern superscalar processor architectures. By laying out data structures in memory in a more cache-conscious fashion, removing branches from the execution flow using a technique called predication, and micro-batching predictions using a technique called vectorization, we are able to better exploit modern processor architectures and significantly improve the speed of tree-based models over hard-coded if-else blocks. Our work contributes to the exploration of architecture-conscious runtime implementations of machine learning algorithms.
Network Coded TCP (CTCP)
Venue: arXiv cs.NI 2013
Year: 2013

We introduce CTCP, a reliable transport protocol using network coding. CTCP is designed to incorporate TCP features such as congestion control, reliability, and fairness while significantly improving on TCP's performance in lossy, interference-limited and/or dynamic networks. A key advantage of adopting a transport layer over a link layer approach is that it provides backward compatibility with wireless equipment installed throughout existing networks. We present a portable userspace implementation of CTCP and extensively evaluate its performance in both testbed and production wireless networks.
Spike and Tyke, the Quantized Neuron Model
Venue: arXiv cs.NE 2013
Year: 2013

Modeling spike firing assumes that spiking statistics are Poisson, but real data violates this assumption. To capture non-Poissonian features, in order to fix the inevitable inherent irregularity, researchers rescale the time axis with tedious computational overhead instead of searching for another distribution. Spikes or action potentials are precisely-timed changes in the ionic transport through synapses adjusting the synaptic weight, successfully modeled and developed as a memristor. Memristance value is multiples of initial resistance. This reminds us with the foundations of quantum mechanics. We try to quantize potential and resistance, as done with energy. After reviewing Planck curve for blackbody radiation, we propose the quantization equations. We introduce and prove a theorem that quantizes the resistance. Then we define the tyke showing its basic characteristics. Finally we give the basic transformations to model spiking and link an energy quantum to a tyke. Investigation shows how this perfectly models the neuron spiking, with over 97% match.
Taming the Infinite Chase: Query Answering under Expressive Integrity Constraints
Venue: arXiv cs.LO 2013
Year: 2013

The chase algorithm is a fundamental tool for query evaluation and query containment under constraints, where the constraints are (sub-classes of) tuple-generating dependencies (TGDs) and equality generating depencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates, with some notable exceptions. In this paper we take a general approach, and we propose large classes of TGDs under which the chase does not always terminate. Our languages, in particular, are inspired by guarded logic: we show that by enforcing syntactic properties on the form of the TGDs, we are able to ensure decidability of the problem of answering conjunctive queries despite the non-terminating chase. We provide tight complexity bounds for the problem of conjunctive query evaluation for several classes of TGDs. We then introduce EGDs, and provide a condition under which EGDs do not interact with TGDs, and therefore do not take part in query answering. We show applications of our classes of constraints to the problem of answering conjunctive queries under F-Logic Lite, a recently introduced ontology language, and under prominent tractable Description Logics languages. All the results in this paper immediately extend to the problem of conjunctive query containment.
A Tight Upper Bound for the Third-Order Asymptotics for Most Discrete Memoryless Channels
Venue: arXiv cs.IT 2013
Year: 2013

This paper shows that the logarithm of the epsilon-error capacity (average error probability) for n uses of a discrete memoryless channel is upper bounded by the normal approximation plus a third-order term that does not exceed 1/2 log n + O(1) if the epsilon-dispersion of the channel is positive. This matches a lower bound by Y. Polyanskiy (2010) for discrete memoryless channels with positive reverse dispersion. If the epsilon-dispersion vanishes, the logarithm of the epsilon-error capacity is upper bounded by the n times the capacity plus a constant term except for a small class of DMCs and epsilon >= 1/2.
Online Bin Packing with Advice
Venue: arXiv cs.DS 2013
Year: 2013

We consider the online bin packing problem under the advice complexity model where the 'online constraint' is relaxed and an algorithm receives partial information about the future requests. We provide tight upper and lower bounds for the amount of advice an algorithm needs to achieve an optimal packing. We also introduce an algorithm that, when provided with log n + o(log n) bits of advice, achieves a competitive ratio of 3/2 for the general problem. This algorithm is simple and is expected to find real-world applications. We introduce another algorithm that receives 2n + o(n) bits of advice and achieves a competitive ratio of 4/3 + ε. Finally, we provide a lower bound argument that implies that advice of linear size is required for an algorithm to achieve a competitive ratio better than 9/8.
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits
Venue: arXiv cs.CC 2013
Year: 2013

We give a nontrivial algorithm for the satisfiability problem for cn-wire threshold circuits of depth two which is better than exhaustive search by a factor 2^{sn} where s= 1/c^{O(c^2)}. We believe that this is the first nontrivial satisfiability algorithm for cn-wire threshold circuits of depth two. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination Problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most cn. One of our motivations is proving strong lower bounds for TC^0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.
Clustering Based Topology Control Protocol for Data Delivery in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

The issue of optimizing the limited and often non-renewable energy of sensor nodes due to its direct impact on network lifetime dominates every aspect of wireless sensor networks. Existing techniques for optimizing energy consumption are based on exploiting node redundancy, adaptive radio transmission power and topology control. Topology control protocols have a significant impact on network lifetime, available energy and connectivity. In this paper we classify sensor nodes as strong and weak nodes based on their residual energy as well as operational lifetime and propose a Clustering based topology control protocol (CTCP) which extends network lifetime while guarantying the minimum connectivity. Extensive simulations in Java-Simulator (J-Sim) show that our proposed protocol outperforms the existing protocols in terms of various performance metrics life network lifetime, average delay and minimizes energy utilization.
On Dynamics in Selfish Network Creation
Venue: arXiv cs.GT 2013
Year: 2013

We consider the dynamic behavior of several variants of the Network Creation Game, introduced by Fabrikant et al. [PODC'03]. Equilibrium networks in these models have desirable properties like low social cost and small diameter, which makes them attractive for the decentralized creation of overlay-networks. Unfortunately, due to the non-constructiveness of the Nash equilibrium, no distributed algorithm for finding such networks is known. We treat these games as sequential-move games and analyze whether (uncoordinated) selfish play eventually converges to an equilibrium state. Thus, we shed light on one of the most natural algorithms for this problem: distributed local search, where in each step some agent performs a myopic selfish improving move. We show that fast convergence is guaranteed for all versions of Swap Games, introduced by Alon et al. [SPAA'10], if the initial network is a tree, and show that this process can be sped up to an almost optimal number of moves. For non-tree networks we show the surprising result that even one non-tree edge suffices to destroy the convergence guarantee and no move policy can enforce convergence. This answers an open problem from Ehsani et al. [SPAA'11] in the negative. We extend our negative results to the well-studied original version and prove that there is no convergence guarantee -- even if all agents play optimally. Furthermore, we show the quite surprising result that employing cost-sharing yields even worse dynamic behavior. Finally, we contrast our mostly negative theoretical results by a careful empirical study. Our simulations indicate two positive facts: (1) The non-convergent behavior seems to be confined to a small set of pathological instances and is unlikely to show up in practice. (2) In all our simulations we observed a remarkably fast convergence towards a stable network in O(n) steps, where n is the number of agents.
Towards Trustworthy Mobile Social Networking Services for Disaster Response
Venue: arXiv cs.SI 2013
Year: 2013

Situational awareness is crucial for effective disaster management. However, obtaining information about the actual situation is usually difficult and time-consuming. While there has been some effort in terms of incorporating the affected population as a source of information, the issue of obtaining trustworthy information has not yet received much attention. Therefore, we introduce the concept of witness-based report verification, which enables users from the affected population to evaluate reports issued by other users. We present an extensive overview of the objectives to be fulfilled by such a scheme and provide a first approach considering security and privacy. Finally, we evaluate the performance of our approach in a simulation study. Our results highlight synergetic effects of group mobility patterns that are likely in disaster situations.
A New Approach to Output-Sensitive Voronoi Diagrams and Delaunay Triangulations
Venue: arXiv cs.CG 2013
Year: 2013

We describe a new algorithm for computing the Voronoi diagram of a set of $n$ points in constant-dimensional Euclidean space. The running time of our algorithm is $O(f \log n \log Δ)$ where $f$ is the output complexity of the Voronoi diagram and $Δ$ is the spread of the input, the ratio of largest to smallest pairwise distances. Despite the simplicity of the algorithm and its analysis, it improves on the state of the art for all inputs with polynomial spread and near-linear output size. The key idea is to first build the Voronoi diagram of a superset of the input points using ideas from Voronoi refinement mesh generation. Then, the extra points are removed in a straightforward way that allows the total work to be bounded in terms of the output complexity, yielding the output sensitive bound. The removal only involves local flips and is inspired by kinetic data structures.
Multi-attribute value functions in energy-aware network control
Venue: arXiv cs.NI 2013
Year: 2013

This paper evaluates and classifies existing and emerging energy-control technologies for computer networks based on their relative value functions. Using formal decision analysis methods, we demonstrate the impact of risk-benefit dimensions on technology certain equivalent and deployment perspective. We demonstrate how energy control solutions can be cost-effective or unsustainable depending on network type and operator risk tolerance.
Carrier Frequency Offset Estimation Approach for Multicarrier Transmission on Hexagonal Time-Frequency Lattice
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a novel carrier frequency offset estimation approach, including preamble structure, carrier frequency offset estimation algorithm, is proposed for hexagonal multi-carrier transmission (HMCT) system. The closed-form Cramer-Rao lower bound of the proposed carrier frequency offset estimation scheme is given. Theoretical analyses and simulation results show that the proposed preamble structure and carrier frequency offset estimation algorithm for HMCT system obtains an approximation to the Cramer-Rao lower bound mean square error (MSE) performance over the doubly dispersive (DD) propagation channel.
Universal point sets for planar three-tree
Venue: arXiv cs.CG 2013
Year: 2013

For every $n\in \mathbb{N}$, we present a set $S_n$ of $O(n^{3/2}\log n)$ points in the plane such that every planar 3-tree with $n$ vertices has a straight-line embedding in the plane in which the vertices are mapped to a subset of $S_n$. This is the first subquadratic upper bound on the size of universal point sets for planar 3-trees, as well as for the class of 2-trees and serial parallel graphs.
On an algorithm for multiperiodic words
Venue: arXiv cs.FL 2013
Year: 2013

We consider an algorithm by Tijdeman and Zamboni constructing a word of a given length that has a given set of periods, and the richest possible alphabet. We show that this algorithm can be easily stated and its correctness briefly proved using the class equivalence approach.
On Automation and Medical Image Interpretation, With Applications for Laryngeal Imaging
Venue: arXiv cs.CV 2013
Year: 2013

Indeed, these are exciting times. We are in the heart of a digital renaissance. Automation and computer technology allow engineers and scientists to fabricate processes that amalgamate quality of life. We anticipate much growth in medical image interpretation and understanding, due to the influx of computer technologies. This work should serve as a guide to introduce the reader to core themes in theoretical computer science, as well as imaging applications for understanding vocal-fold vibrations. In this work, we motivate the use of automation, review some mathematical models of computation. We present a proof of a classical problem in image analysis that cannot be automated by means of algorithms. Furthermore, discuss some applications for processing medical images of the vocal folds, and discuss some of the exhilarating directions the art of automation will take vocal-fold image interpretation and quite possibly other areas of biomedical image analysis.
Regular Cost Functions, Part I: Logic and Algebra over Words
Venue: arXiv cs.FL 2013
Year: 2013

The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the two values "inside" and "outside". This theory is a continuation of the works on distance automata and similar models. These models of automata have been successfully used for solving the star-height problem, the finite power property, the finite substitution problem, the relative inclusion star-height problem and the boundedness problem for monadic-second order logic over words. Our notion of regularity can be -- as in the classical theory of regular languages -- equivalently defined in terms of automata, expressions, algebraic recognisability, and by a variant of the monadic second-order logic. These equivalences are strict extensions of the corresponding classical results. The present paper introduces the cost monadic logic, the quantitative extension to the notion of monadic second-order logic we use, and show that some problems of existence of bounds are decidable for this logic. This is achieved by introducing the corresponding algebraic formalism: stabilisation monoids.
Zero-Delay and Causal Single-User and Multi-User Lossy Source Coding with Decoder Side Information
Venue: arXiv cs.IT 2013
Year: 2013

We consider zero-delay single-user and multi-user source coding with average distortion constraint and decoder side information. The zero-delay constraint translates into causal (sequential) encoder and decoder pairs as well as the use of instantaneous codes. For the single-user setting, we show that optimal performance is attained by time sharing at most two scalar encoder-decoder pairs, that use zero-error side information codes. Side information lookahead is shown to useless in this setting. We show that the restriction to causal encoding functions is the one that causes the performance degradation, compared to unrestricted systems, and not the sequential decoders or instantaneous codes. Furthermore, we show that even without delay constraints, if either the encoder or decoder are restricted a-priori to be scalar, the performance loss cannot be compensated by the other component, which can be scalar as well without further loss. Finally, we show that the multi-terminal source coding problem can be solved in the zero-delay regime and the rate-distortion region is given.
Policy Evaluation with Variance Related Risk Criteria in Markov Decision Processes
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we extend temporal difference policy evaluation algorithms to performance criteria that include the variance of the cumulative reward. Such criteria are useful for risk management, and are important in domains such as finance and process control. We propose both TD(0) and LSTD(lambda) variants with linear function approximation, prove their convergence, and demonstrate their utility in a 4-dimensional continuous state space problem.
Tree-based Arithmetic and Compressed Representations of Giant Numbers
Venue: arXiv cs.PL 2013
Year: 2013

Can we do arithmetic in a completely different way, with a radically different data structure? Could this approach provide practical benefits, like operations on giant numbers while having an average performance similar to traditional bitstring representations? While answering these questions positively, our tree based representation described in this paper comes with a few extra benefits: it compresses giant numbers such that, for instance, the largest known prime number as well as its related perfect number are represented as trees of small sizes. The same also applies to Fermat numbers and important computations like exponentiation of two become constant time operations. At the same time, succinct representations of sparse sets, multisets and sequences become possible through bijections to our tree-represented natural numbers.
Nonconvergent Electoral Equilibria under Scoring Rules: Beyond Plurality
Venue: arXiv cs.GT 2013
Year: 2013

We use Hotelling's spatial model of competition to investigate the position-taking behaviour of political candidates under a class of electoral systems known as scoring rules. In a scoring rule election, voters rank all the candidates running for office, following which the candidates are assigned points according to a vector of nonincreasing scores. Convergent Nash equilibria in which all candidates adopt the same policy were characterised by Cox (1987). Here, we investigate nonconvergent equilibria, where candidates adopt divergent policies. We identify a number of classes of scoring rules exhibiting a range of different equilibrium properties. For some of these, nonconvergent equilibria do not exist. For others, nonconvergent equilibria in which candidates cluster at positions spread across the issue space are observed. In particular, we prove that the class of convex rules does not have Nash equilibria (convergent or nonconvergent) with the exception of some derivatives of Borda rule. Finally, we examine the special cases of four-, five- and six- candidate elections. In the former two cases, we provide a complete characterisation of nonconvergent equilibria.