OpenRaiser/Intern-Atlas huggingface dataset:
Detecting change points in the large-scale structure of evolving networks
Venue: arXiv cs.SI 2014
Year: 2014

Interactions among people or objects are often dynamic in nature and can be represented as a sequence of networks, each providing a snapshot of the interactions over a brief period of time. An important task in analyzing such evolving networks is change-point detection, in which we both identify the times at which the large-scale pattern of interactions changes fundamentally and quantify how large and what kind of change occurred. Here, we formalize for the first time the network change-point detection problem within an online probabilistic learning framework and introduce a method that can reliably solve it. This method combines a generalized hierarchical random graph model with a Bayesian hypothesis test to quantitatively determine if, when, and precisely how a change point has occurred. We analyze the detectability of our method using synthetic data with known change points of different types and magnitudes, and show that this method is more accurate than several previously used alternatives. Applied to two high-resolution evolving social networks, this method identifies a sequence of change points that align with known external "shocks" to these networks.
Counting the Number of Minimum Roman Dominating Functions of a Graph
Venue: arXiv cs.DS 2014
Year: 2014

We provide two algorithms counting the number of minimum Roman dominating functions of a graph on n vertices in O(1.5673^n) time and polynomial space. We also show that the time complexity can be reduced to O(1.5014^n) if exponential space is used. Our result is obtained by transforming the Roman domination problem into other combinatorial problems on graphs for which exact algorithms already exist.
Automated analysis of security protocols with global state
Venue: arXiv cs.CR 2014
Year: 2014

Security APIs, key servers and protocols that need to keep the status of transactions, require to maintain a global, non-monotonic state, e.g., in the form of a database or register. However, most existing automated verification tools do not support the analysis of such stateful security protocols - sometimes because of fundamental reasons, such as the encoding of the protocol as Horn clauses, which are inherently monotonic. A notable exception is the recent tamarin prover which allows specifying protocols as multiset rewrite (msr) rules, a formalism expressive enough to encode state. As multiset rewriting is a "low-level" specification language with no direct support for concurrent message passing, encoding protocols correctly is a difficult and error-prone process. We propose a process calculus which is a variant of the applied pi calculus with constructs for manipulation of a global state by processes running in parallel. We show that this language can be translated to msr rules whilst preserving all security properties expressible in a dedicated first-order logic for security properties. The translation has been implemented in a prototype tool which uses the tamarin prover as a backend. We apply the tool to several case studies among which a simplified fragment of PKCS\#11, the Yubikey security token, and an optimistic contract signing protocol.
A proof challenge: multiple alignment and information compression
Venue: arXiv cs.AI 2014
Year: 2014

These notes pose a "proof challenge": a proof, or disproof, of the proposition that "For any given body of information, I, expressed as a one-dimensional sequence of atomic symbols, a multiple alignment concept, described in the document, provides a means of encoding all the redundancy that may exist in I. Aspects of the challenge are described.
Performance of ML Range Estimator in Radio Interferometric Positioning Systems
Venue: arXiv cs.IT 2014
Year: 2014

The radio interferometric positioning system (RIPS) is a novel positioning solution used in wireless sensor networks. This letter explores the ranging accuracy of RIPS in two configurations. In the linear step-frequency (LSF) configuration, we derive the mean square error (MSE) of the maximum likelihood (ML) estimator. In the random step-frequency (RSF) configuration, we introduce average MSE to characterize the performance of the ML estimator. The simulation results fit well with theoretical analysis. It is revealed that RSF is superior to LSF in that the former is more robust in a jamming environment with similar ranging accuracy.
Ubic: Bridging the gap between digital cryptography and the physical world
Venue: arXiv cs.CR 2014
Year: 2014

Advances in computing technology increasingly blur the boundary between the digital domain and the physical world. Although the research community has developed a large number of cryptographic primitives and has demonstrated their usability in all-digital communication, many of them have not yet made their way into the real world due to usability aspects. We aim to make another step towards a tighter integration of digital cryptography into real world interactions. We describe Ubic, a framework that allows users to bridge the gap between digital cryptography and the physical world. Ubic relies on head-mounted displays, like Google Glass, resource-friendly computer vision techniques as well as mathematically sound cryptographic primitives to provide users with better security and privacy guarantees. The framework covers key cryptographic primitives, such as secure identification, document verification using a novel secure physical document format, as well as content hiding. To make a contribution of practical value, we focused on making Ubic as simple, easily deployable, and user friendly as possible.
Architecting Information Centric ETSI-M2M systems
Venue: arXiv cs.NI 2014
Year: 2014

The European Telecommunications Standards Institute (ETSI) released a set of specifications to define a restful architecture for enabling seamless service provisioning across heterogeneous Machine-to-Machine (M2M) systems. The current version of this architecture is strongly centralized, thus requiring new enhancements to its scalability, fault tolerance, and flexibility. To bridge this gap, herein it is presented an Overlay Service Capability Layer, based on Information Centric Networking design. Key features, example use cases and preliminary performance assessments are also discussed to highlight the potential of our approach.
Cooperative Radar and Communications Signaling: The Estimation and Information Theory Odd Couple
Venue: arXiv cs.IT 2014
Year: 2014

We investigate cooperative radar and communications signaling. While each system typically considers the other system a source of interference, by considering the radar and communications operations to be a single joint system, the performance of both systems can, under certain conditions, be improved by the existence of the other. As an initial demonstration, we focus on the radar as relay scenario and present an approach denoted multiuser detection radar (MUDR). A novel joint estimation and information theoretic bound formulation is constructed for a receiver that observes communications and radar return in the same frequency allocation. The joint performance bound is presented in terms of the communication rate and the estimation rate of the system.
Linear usage of state
Venue: arXiv cs.PL 2014
Year: 2014

We investigate the phenomenon that "every monad is a linear state monad". We do this by studying a fully-complete state-passing translation from an impure call-by-value language to a new linear type theory: the enriched call-by-value calculus. The results are not specific to store, but can be applied to any computational effect expressible using algebraic operations, even to effects that are not usually thought of as stateful. There is a bijective correspondence between generic effects in the source language and state access operations in the enriched call-by-value calculus. From the perspective of categorical models, the enriched call-by-value calculus suggests a refinement of the traditional Kleisli models of effectful call-by-value languages. The new models can be understood as enriched adjunctions.
On the Sequence of State Configurations in the Garden of Eden
Venue: arXiv cs.NE 2014
Year: 2014

Autonomous threshold element circuit networks are used to investigate the structure of neural networks. With these circuits, as the transition functions are threshold functions, it is necessary to consider the existence of sequences of state configurations that cannot be transitioned. In this study, we focus on all logical functions of four or fewer variables, and we discuss the periodic sequences and transient series that transition from all sequences of state configurations. Furthermore, by using the sequences of state configurations in the Garden of Eden, we show that it is easy to obtain functions that determine the operation of circuit networks.
On the evolution and utility of annual citation indices
Venue: arXiv cs.DL 2014
Year: 2014

We study the statistics of citations made to the top ranked indexed journals for Science and Social Science databases in the Journal Citation Reports using different measures. Total annual citation and impact factor, as well as a third measure called the annual citation rate are used to make the detailed analysis. We observe that the distribution of the annual citation rate has an universal feature - it shows a maximum at the rate scaled by half the average, irrespective of how the journals are ranked, and even across Science and Social Science journals, and fits well to log-Gumbel distribution. Correlations between different quantities are studied and a comparative analysis of the three measures is presented. The newly introduced annual citation rate factor helps in understanding the effect of scaling the number of citation by the total number of publications. The effect of the impact factor on authors contributing to the journals as well as on editorial policies is also discussed.
Automatically finding atomic regions for fixing bugs in Concurrent programs
Venue: arXiv cs.SE 2014
Year: 2014

This paper presents a technique for automatically constructing a fix for buggy concurrent programs: given a concurrent program that does not satisfy user-provided assertions, we infer atomic blocks that fix the program. An atomic block protects a piece of code and ensures that it runs without interruption from other threads. Our technique uses a verification tool as a subroutine to find the smallest atomic regions that remove all bugs in a given program. Keeping the atomic regions small allows for maximum concurrency. We have implemented our approach in a tool called AtomicInf. A user of AtomicInf can choose between strong and weak atomicity semantics for the inferred fix. While the former is simpler to find, the latter provides more information about the bugs that got fixed. We ran AtomicInf on several benchmarks and came up with the smallest and the most precise atomic regions in all of them. We implemented an earlier technique to our setting and observed that AtomicInf is 1.7 times faster on an average as compared to an earlier approach.
An Expressive Model for the Web Infrastructure: Definition and Application to the BrowserID SSO System
Venue: arXiv cs.CR 2014
Year: 2014

The web constitutes a complex infrastructure and as demonstrated by numerous attacks, rigorous analysis of standards and web applications is indispensable. Inspired by successful prior work, in particular the work by Akhawe et al. as well as Bansal et al., in this work we propose a formal model for the web infrastructure. While unlike prior works, which aim at automatic analysis, our model so far is not directly amenable to automation, it is much more comprehensive and accurate with respect to the standards and specifications. As such, it can serve as a solid basis for the analysis of a broad range of standards and applications. As a case study and another important contribution of our work, we use our model to carry out the first rigorous analysis of the BrowserID system (a.k.a. Mozilla Persona), a recently developed complex real-world single sign-on system that employs technologies such as AJAX, cross-document messaging, and HTML5 web storage. Our analysis revealed a number of very critical flaws that could not have been captured in prior models. We propose fixes for the flaws, formally state relevant security properties, and prove that the fixed system in a setting with a so-called secondary identity provider satisfies these security properties in our model. The fixes for the most critical flaws have already been adopted by Mozilla and our findings have been rewarded by the Mozilla Security Bug Bounty Program.
On the Duality of Erasures and Defects
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, the duality of erasures and defects will be investigated by comparing the binary erasure channel (BEC) and the binary defect channel (BDC). The duality holds for channel capacities, capacity achieving schemes, minimum distances, and upper bounds on the probability of failure to retrieve the original message. Also, the binary defect and erasure channel (BDEC) will be introduced by combining the properties of the BEC and the BDC. It will be shown that the capacity of the BDEC can be achieved by the coding scheme that combines the encoding for the defects and the decoding for the erasures. This coding scheme for the BDEC has two separate redundancy parts for correcting erasures and masking defects. Thus, we will investigate the problem of redundancy allocation between these two parts.
Extraction of Core Contents from Web Pages
Venue: arXiv cs.IR 2014
Year: 2014

The information available on web pages mostly contains semi-structured text documents which are represented either in XML, or HTML, or XHTML format that lacks formatted document structure. The document does not discriminate between the text and the schema that represent the text. Also the amount of structure used to represent the text depends on the purpose and size of text document. No semantic is applied to semi-structured documents. This requires extracting core contents of text document to analyse words or sentences to generate useful knowledge. This paper discusses several techniques and approaches useful for extracting core content from semi-structured text documents and their merits and demerits
Algebraic properties of word equations
Venue: arXiv cs.FL 2014
Year: 2014

The question about maximal size of independent system of word equations is one of the most striking problems in combinatorics on words. Recently, Aleksi Saarela has introduced a new approach to the problem that is based on linear-algebraic properties of polynomials encoding the equations and their solutions. In this paper we develop further this approach and take into account other algebraic properties of polynomials, namely their factorization. This, in particular, allows to improve the bound for the number of independent equations with maximal rank from quadratic to linear.
Parameterized Edge Hamiltonicity
Venue: arXiv cs.DS 2014
Year: 2014

We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al. by showing that Edge Hamiltonian Path is FPT parameterized by vertex cover, and that it also admits a cubic kernel. We then show fixed-parameter tractability even for a generalization of the problem to arbitrary hypergraphs, parameterized by the size of a (supplied) hitting set. We also consider the problem parameterized by treewidth or clique-width. Surprisingly, we show that the problem is FPT for both of these standard parameters, in contrast to its vertex version, which is W-hard for clique-width. Our technique, which may be of independent interest, relies on a structural characterization of clique-width in terms of treewidth and complete bipartite subgraphs due to Gurski and Wanke.
Engineering Parallel String Sorting
Venue: arXiv cs.DS 2014
Year: 2014

We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we first propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Then we focus on NUMA architectures, and develop parallel multiway LCP-merge and -mergesort to reduce the number of random memory accesses to remote nodes. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations. Comprehensive experiments on five current multi-core platforms are then reported and discussed. The experiments show that our implementations scale very well on real-world inputs and modern machines.
Blind-friendly von Neumann's Heads or Tails
Venue: arXiv cs.DS 2014
Year: 2014

The toss of a coin is usually regarded as the epitome of randomness, and has been used for ages as a means to resolve disputes in a simple, fair way. Perhaps as ancient as consulting objects such as coins and dice is the art of maliciously biasing them in order to unbalance their outcomes. However, it is possible to employ a biased device to produce equiprobable results in a number of ways, the most famous of which is the method suggested by von Neumann back in 1951. This paper addresses how to extract uniformly distributed bits of information from a nonuniform source. We study some probabilities related to biased dice and coins, culminating in an interesting variation of von Neumann's mechanism that can be employed in a more restricted setting where the actual results of the coin tosses are not known to the contestants.
Generating Music from Literature
Venue: arXiv cs.CL 2014
Year: 2014

We present a system, TransProse, that automatically generates musical pieces from text. TransProse uses known relations between elements of music such as tempo and scale, and the emotions they evoke. Further, it uses a novel mechanism to determine sequences of notes that capture the emotional activity in the text. The work has applications in information visualization, in creating audio-visual e-books, and in developing music apps.
On the Harmonic Oscillation of High-order Linear Time Invariant Systems
Venue: arXiv cs.DM 2014
Year: 2014

Linear time invariant (LTI) systems are widely used for modeling system dynamics in science and engineering problems. Harmonic oscillation of LTI systems are widely used for modeling and analyses of periodic physical phenomenon. This study investigates sufficient conditions to obtain harmonic oscillation for high-order LTI systems. The paper presents a design procedure for controlling harmonic oscillation of singleinput single-output high-order LTI systems. LTI system coefficients are calculated by the solution of linear equation set, which imposes a stable sinusoidal oscillation solution for the characteristic polynomials of LTI systems. An example design is demonstrated for fourth-order LTI systems and the control of harmonic oscillations are discussed by illustrating Hilbert transform and spectrogram of oscillation signals.
Optimal Window and Lattice in Gabor Transform Application to Audio Analysis
Venue: arXiv cs.SD 2014
Year: 2014

This article deals with the use of optimal lattice and optimal window in Discrete Gabor Transform computation. In the case of a generalized Gaussian window, extending earlier contributions, we introduce an additional local window adaptation technique for non-stationary signals. We illustrate our approach and the earlier one by addressing three time-frequency analysis problems to show the improvements achieved by the use of optimal lattice and window: close frequencies distinction, frequency estimation and SNR estimation. The results are presented, when possible, with real world audio signals.
Querying Geometric Figures Using a Controlled Language, Ontological Graphs and Dependency Lattices
Venue: arXiv cs.CG 2014
Year: 2014

Dynamic geometry systems (DGS) have become basic tools in many areas of geometry as, for example, in education. Geometry Automated Theorem Provers (GATP) are an active area of research and are considered as being basic tools in future enhanced educational software as well as in a next generation of mechanized mathematics assistants. Recently emerged Web repositories of geometric knowledge, like TGTP and Intergeo, are an attempt to make the already vast data set of geometric knowledge widely available. Considering the large amount of geometric information already available, we face the need of a query mechanism for descriptions of geometric constructions. In this paper we discuss two approaches for describing geometric figures (declarative and procedural), and present algorithms for querying geometric figures in declaratively and procedurally described corpora, by using a DGS or a dedicated controlled natural language for queries.
SMML estimators for linear regression and tessellations of hyperbolic space
Venue: arXiv cs.IT 2014
Year: 2014

The strict minimum message length (SMML) principle links data compression with inductive inference. The corresponding estimators have many useful properties but they can be hard to calculate. We investigate SMML estimators for linear regression models and we show that they have close connections to hyperbolic geometry. When equipped with the Fisher information metric, the linear regression model with $p$ covariates and a sample size of $n$ becomes a Riemannian manifold, and we show that this is isometric to $(p+1)$-dimensional hyperbolic space $\mathbb{H}^{p+1}$ equipped with a metric tensor which is $2n$ times the usual metric tensor on $\mathbb{H}^{p+1}$. A natural identification then allows us to also view the set of sufficient statistics for the linear regression model as a hyperbolic space. We show that the partition of an SMML estimator corresponds to a tessellation of this hyperbolic space.
Some isomorphic classes for noncanonical hypercomplex number systems of dimension 2
Venue: arXiv cs.NA 2014
Year: 2014

Building of some isomorphic classes for noncanonical hypercomplex number systems o dimension 2 is described. In general case, such systems with specific constraints to structural constants can be isomorphic to complex, dual or double number system. Isomorphic transition between noncanonical hypercomplex number systems of the general form and diagonal form is built.
A Subquadratic Algorithm for Minimum Palindromic Factorization
Venue: arXiv cs.DS 2014
Year: 2014

We give an $\mathcal{O}(n \log n)$-time, $\mathcal{O}(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm returns the minimum number of palindromes $S_1,\ldots, S_\ell$ such that $S = S_1 \cdots S_\ell$. We also show that the time complexity is $\mathcal{O}(n)$ on average and $Ω(n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.