OpenRaiser/Intern-Atlas huggingface dataset:
Automorphism Groups of Comparability Graphs
Venue: arXiv cs.DM 2015
Year: 2015

Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension ${\rm dim}(X)$ of a comparability graph $X$ is the dimension of any transitive orientation of X, and by $k$-DIM we denote the class of comparability graphs $X$ with ${\rm dim}(X) \le k$. It is known that the complements of comparability graphs are exactly function graphs and permutation graphs equal 2-DIM. In this paper, we characterize the automorphism groups of permutation graphs similarly to Jordan's characterization for trees (1869). For permutation graphs, there is an extra operation, so there are some extra groups not realized by trees. For $k \ge 4$, we show that every finite group can be realized as the automorphism group of some graph in $k$-DIM, and testing graph isomorphism for $k$-DIM is GI-complete.
An Improved Distributed Algorithm for Maximal Independent Set
Venue: arXiv cs.DS 2015
Year: 2015

The Maximal Independent Set (MIS) problem is one of the basics in the study of locality in distributed graph algorithms. This paper presents an extremely simple randomized algorithm providing a near-optimal local complexity for this problem, which incidentally, when combined with some recent techniques, also leads to a near-optimal global complexity. Classical algorithms of Luby [STOC'85] and Alon, Babai and Itai [JALG'86] provide the global complexity guarantee that, with high probability, all nodes terminate after $O(\log n)$ rounds. In contrast, our initial focus is on the local complexity, and our main contribution is to provide a very simple algorithm guaranteeing that each particular node $v$ terminates after $O(\log \mathsf{deg}(v)+\log 1/ε)$ rounds, with probability at least $1-ε$. The guarantee holds even if the randomness outside $2$-hops neighborhood of $v$ is determined adversarially. This degree-dependency is optimal, due to a lower bound of Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Interestingly, this local complexity smoothly transitions to a global complexity: by adding techniques of Barenboim, Elkin, Pettie, and Schneider [FOCS'12, arXiv: 1202.1983v3], we get a randomized MIS algorithm with a high probability global complexity of $O(\log Δ) + 2^{O(\sqrt{\log \log n})}$, where $Δ$ denotes the maximum degree. This improves over the $O(\log^2 Δ) + 2^{O(\sqrt{\log \log n})}$ result of Barenboim et al., and gets close to the $Ω(\min\{\log Δ, \sqrt{\log n}\})$ lower bound of Kuhn et al. Corollaries include improved algorithms for MIS in graphs of upper-bounded arboricity, or lower-bounded girth, for Ruling Sets, for MIS in the Local Computation Algorithms (LCA) model, and a faster distributed algorithm for the Lovász Local Lemma.
Compressive channel estimation and tracking for large arrays in mm wave picocells
Venue: arXiv cs.IT 2015
Year: 2015

We propose and investigate a compressive architecture for estimation and tracking of sparse spatial channels in millimeter (mm) wave picocellular networks. The base stations are equipped with antenna arrays with a large number of elements (which can fit within compact form factors because of the small carrier wavelength) and employ radio frequency (RF) beamforming, so that standard least squares adaptation techniques (which require access to individual antenna elements) are not applicable. We focus on the downlink, and show that "compressive beacons," transmitted using pseudorandom phase settings at the base station array, and compressively processed using pseudorandom phase settings at the mobile array, provide information sufficient for accurate estimation of the two-dimensional (2D) spatial frequencies associated with the directions of departure of the dominant rays from the base station, and the associated complex gains. This compressive approach is compatible with coarse phase-only control, and is based on a near-optimal sequential algorithm for frequency estimation which can exploit the geometric continuity of the channel across successive beaconing intervals to reduce the overhead to less than 1% even for very large (32 x 32) arrays. Compressive beaconing is essentially omnidirectional, and hence does not enjoy the SNR and spatial reuse benefits of beamforming obtained during data transmission. We therefore discuss system level design considerations for ensuring that the beacon SNR is sufficient for accurate channel estimation, and that inter-cell beacon interference is controlled by an appropriate reuse scheme.
Robust Energy-Constrained Frequency Reserves from Aggregations of Commercial Buildings
Venue: arXiv cs.SY 2015
Year: 2015

It has been shown that the heating, ventilation, and air conditioning (HVAC) systems of commercial buildings can offer ancillary services to power systems without loss of comfort. In this paper, we propose a new control framework for reliable scheduling and provision of frequency reserves by aggregations of commercial buildings. The framework incorporates energy-constrained frequency signals, which are adopted by several transmission system operators for loads and storage devices. We use a hierarchical approach with three levels: (i) reserve capacities are allocated among buildings (e.g., on a daily basis) using techniques from robust optimization, (ii) a robust model predictive controller optimizes the HVAC system consumption typically every 30 minutes, and (iii) a feedback controller adjusts the consumption to provide reserves in real time. We demonstrate how the framework can be used to estimate the reserve capacities in simulations with typical Swiss office buildings and different reserve product characteristics. Our results show that an aggregation of approximately 100 buildings suffices to meet the 5 MW minimum bid size of the Swiss reserve market.
Editorial for the First Workshop on Mining Scientific Papers: Computational Linguistics and Bibliometrics
Venue: arXiv cs.CL 2015
Year: 2015

The workshop "Mining Scientific Papers: Computational Linguistics and Bibliometrics" (CLBib 2015), co-located with the 15th International Society of Scientometrics and Informetrics Conference (ISSI 2015), brought together researchers in Bibliometrics and Computational Linguistics in order to study the ways Bibliometrics can benefit from large-scale text analytics and sense mining of scientific papers, thus exploring the interdisciplinarity of Bibliometrics and Natural Language Processing (NLP). The goals of the workshop were to answer questions like: How can we enhance author network analysis and Bibliometrics using data obtained by text analytics? What insights can NLP provide on the structure of scientific writing, on citation networks, and on in-text citation analysis? This workshop is the first step to foster the reflection on the interdisciplinarity and the benefits that the two disciplines Bibliometrics and Natural Language Processing can drive from it.
Swing-twist decomposition in Clifford algebra
Venue: arXiv cs.RO 2015
Year: 2015

The swing-twist decomposition is a standard routine in motion planning for humanoid limbs. In this paper the decomposition formulas are derived and discussed in terms of Clifford algebra. With the decomposition one can express an arbitrary spinor as a product of a twist-free spinor and a swing-free spinor (or vice-versa) in 3-dimensional Euclidean space. It is shown that in the derived decomposition formula the twist factor is a generalized projection of a spinor onto a vector in Clifford algebra. As a practical application of the introduced theory an optimized decomposition algorithm is proposed. It favourably compares to existing swing-twist decomposition implementations.
Comparing and evaluating extended Lambek calculi
Venue: arXiv cs.CL 2015
Year: 2015

Lambeks Syntactic Calculus, commonly referred to as the Lambek calculus, was innovative in many ways, notably as a precursor of linear logic. But it also showed that we could treat our grammatical framework as a logic (as opposed to a logical theory). However, though it was successful in giving at least a basic treatment of many linguistic phenomena, it was also clear that a slightly more expressive logical calculus was needed for many other cases. Therefore, many extensions and variants of the Lambek calculus have been proposed, since the eighties and up until the present day. As a result, there is now a large class of calculi, each with its own empirical successes and theoretical results, but also each with its own logical primitives. This raises the question: how do we compare and evaluate these different logical formalisms? To answer this question, I present two unifying frameworks for these extended Lambek calculi. Both are proof net calculi with graph contraction criteria. The first calculus is a very general system: you specify the structure of your sequents and it gives you the connectives and contractions which correspond to it. The calculus can be extended with structural rules, which translate directly into graph rewrite rules. The second calculus is first-order (multiplicative intuitionistic) linear logic, which turns out to have several other, independently proposed extensions of the Lambek calculus as fragments. I will illustrate the use of each calculus in building bridges between analyses proposed in different frameworks, in highlighting differences and in helping to identify problems.
Query Expansion for Survey Question Retrieval in the Social Sciences
Venue: arXiv cs.DL 2015
Year: 2015

In recent years, the importance of research data and the need to archive and to share it in the scientific community have increased enormously. This introduces a whole new set of challenges for digital libraries. In the social sciences typical research data sets consist of surveys and questionnaires. In this paper we focus on the use case of social science survey question reuse and on mechanisms to support users in the query formulation for data sets. We describe and evaluate thesaurus- and co-occurrence-based approaches for query expansion to improve retrieval quality in digital libraries and research data archives. The challenge here is to translate the information need and the underlying sociological phenomena into proper queries. As we can show retrieval quality can be improved by adding related terms to the queries. In a direct comparison automatically expanded queries using extracted co-occurring terms can provide better results than queries manually reformulated by a domain expert and better results than a keyword-based BM25 baseline.
An O(m^2 log m)-Competitive Algorithm for Online Machine Minimization
Venue: arXiv cs.DS 2015
Year: 2015

We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines. Our main result is a general O(m^2 log m)-competitive algorithm for the preemptive online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an O(log (p_max/p_min))-competitive algorithm by Phillips et al. (STOC 1997), which was to date the best known algorithm even when m=2. Our algorithm is O(1)-competitive for any m that is bounded by a constant. To develop the algorithm, we investigate two complementary special cases of the problem, namely, laminar instances and agreeable instances, for which we provide an O(log m)-competitive and an O(1)-competitive algorithm, respectively. Our O(1)-competitive algorithm for agreeable instances actually produces a non-preemptive schedule, which is of its own interest as there exists a strong lower bound of n, the number of jobs, for the general non-preemptive online machine minimization problem by Saha (FSTTCS 2013), which even holds for laminar instances.
Detecting Abnormal Profiles in Collaborative Filtering Recommender Systems
Venue: arXiv cs.IR 2015
Year: 2015

Personalization collaborative filtering recommender systems (CFRSs) are the crucial components of popular e-commerce services. In practice, CFRSs are also particularly vulnerable to "shilling" attacks or "profile injection" attacks due to their openness. The attackers can carefully inject chosen attack profiles into CFRSs in order to bias the recommendation results to their benefits. To reduce this risk, various detection techniques have been proposed to detect such attacks, which use diverse features extracted from user profiles. However, relying on limited features to improve the detection performance is difficult seemingly, since the existing features can not fully characterize the attack profiles and genuine profiles. In this paper, we propose a novel detection method to make recommender systems resistant to the "shilling" attacks or "profile injection" attacks. The existing features can be briefly summarized as two aspects including rating behavior based and item distribution based. We firstly formulate the problem as finding a mapping model between rating behavior and item distribution by exploiting the least-squares approximate solution. Based on the trained model, we design a detector by employing a regressor to detect such attacks. Extensive experiments on both the MovieLens-100K and MovieLens-ml-latest-small datasets examine the effectiveness of our proposed detection method. Experimental results were included to validate the outperformance of our approach in comparison with benchmarked method including KNN.
Asymptotic Analysis for Reliable Data Dissemination in Shared loss Multicast Trees
Venue: arXiv cs.NI 2015
Year: 2015

The completion time for the dissemination (or alternatively, aggregation) of information from all nodes in a network plays a critical role in the design and analysis of communication systems, especially in real time applications for which delay is critical. In this work, we analyse the completion time of data dissemination in a shared loss (i.e., unreliable links) multicast tree, at the limit of large number of nodes. Specifically, analytic expressions for upper and lower bounds on the expected completion time are provided, and, in particular, it is shown that both these bounds scale as $α\log n$. For example, on a full binary tree with $n$ end users, and packet loss probability of $0.1$, we bound the expected completion time for disseminating one packet from below by $1.41 \log_2 n+o \left( \log n \right)$ and from above by $1.78 \log_2 n+o \left( \log n \right)$. Clearly, the completion time is determined by the last end user who receives the message, that is, a maximum over all arrival times. Hence, Extreme Value Theory (EVT) is an appropriate tool to explore this problem. However, since arrival times are correlated, non-stationary, and furthermore, time slots are discrete, a thorough study of EVT for Non-Stationary Integer Valued (NSIV) sequences is required. To the best of our knowledge, such processes were not studied before in the framework of EVT. Consequently, we derive the asymptotic distribution of the maxima of NSIV sequences satisfying certain conditions, and give EVT results which are applicable also beyond the scope of this work. These result are then used to derive tight bounds on the completion time. Finally, the results are validated by extensive simulations and numerical analysis.
An Iterative Convolutional Neural Network Algorithm Improves Electron Microscopy Image Segmentation
Venue: arXiv cs.NE 2015
Year: 2015

To build the connectomics map of the brain, we developed a new algorithm that can automatically refine the Membrane Detection Probability Maps (MDPM) generated to perform automatic segmentation of electron microscopy (EM) images. To achieve this, we executed supervised training of a convolutional neural network to recover the removed center pixel label of patches sampled from a MDPM. MDPM can be generated from other machine learning based algorithms recognizing whether a pixel in an image corresponds to the cell membrane. By iteratively applying this network over MDPM for multiple rounds, we were able to significantly improve membrane segmentation results.
To Know Where We Are: Vision-Based Positioning in Outdoor Environments
Venue: arXiv cs.CV 2015
Year: 2015

Augmented reality (AR) displays become more and more popular recently, because of its high intuitiveness for humans and high-quality head-mounted display have rapidly developed. To achieve such displays with augmented information, highly accurate image registration or ego-positioning are required, but little attention have been paid for out-door environments. This paper presents a method for ego-positioning in outdoor environments with low cost monocular cameras. To reduce the computational and memory requirements as well as the communication overheads, we formulate the model compression algorithm as a weighted k-cover problem for better preserving model structures. Specifically for real-world vision-based positioning applications, we consider the issues with large scene change and propose a model update algorithm to tackle these problems. A long- term positioning dataset with more than one month, 106 sessions, and 14,275 images is constructed. Based on both local and up-to-date models constructed in our approach, extensive experimental results show that high positioning accuracy (mean ~ 30.9cm, stdev. ~ 15.4cm) can be achieved, which outperforms existing vision-based algorithms.
A Genetically Modified Hoare Logic
Venue: arXiv cs.CE 2015
Year: 2015

An important problem when modeling gene networks lies in the identification of parameters, even if we consider a purely discrete framework as the one of René Thomas. Here we are interested in the exhaustive search of all parameter values that are consistent with observed behaviors of the gene network. We present in this article a new approach based on Hoare Logic and on a weakest precondition calculus to generate constraints on possible parameter values. Observed behaviors play the role of "programs" for the classical Hoare logic, and computed weakest preconditions represent the sets of all compatible parameterizations expressed as constraints on parameters. Finally we give a proof of correctness of our Hoare logic for gene networks as well as a proof of completeness based on the computation of the weakest precondition.
Deep Knowledge Tracing
Venue: arXiv cs.AI 2015
Year: 2015

Knowledge tracing---where a machine models the knowledge of a student as they interact with coursework---is a well established problem in computer supported education. Though effectively modeling student knowledge would have high educational impact, the task has many inherent challenges. In this paper we explore the utility of using Recurrent Neural Networks (RNNs) to model student learning. The RNN family of models have important advantages over previous methods in that they do not require the explicit encoding of human domain knowledge, and can capture more complex representations of student knowledge. Using neural networks results in substantial improvements in prediction performance on a range of knowledge tracing datasets. Moreover the learned model can be used for intelligent curriculum design and allows straightforward interpretation and discovery of structure in student tasks. These results suggest a promising new line of research for knowledge tracing and an exemplary application task for RNNs.
Fluid Model Checking of Timed Properties
Venue: arXiv cs.FL 2015
Year: 2015

We address the problem of verifying timed properties of Markovian models of large populations of interacting agents, modelled as finite state automata. In particular, we focus on time-bounded properties of (random) individual agents specified by Deterministic Timed Automata (DTA) endowed with a single clock. Exploiting ideas from fluid approximation, we estimate the satisfaction probability of the DTA properties by reducing it to the computation of the transient probability of a subclass of Time-Inhomogeneous Markov Renewal Processes with exponentially and deterministically-timed transitions, and a small state space. For this subclass of models, we show how to derive a set of Delay Differential Equations (DDE), whose numerical solution provides a fast and accurate estimate of the satisfaction probability. In the paper, we also prove the asymptotic convergence of the approach, and exemplify the method on a simple epidemic spreading model. Finally, we also show how to construct a system of DDEs to efficiently approximate the average number of agents that satisfy the DTA specification.
Solving Problems with Unknown Solution Length at (Almost) No Extra Cost
Venue: arXiv cs.NE 2015
Year: 2015

Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if \emph{no} a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the \textsc{OneMax} and \textsc{LeadingOnes} test functions, thus solving an open problem from Cathabard et al.
Indistinguishability and semantic security for quantum encryption scheme
Venue: arXiv cs.CR 2015
Year: 2015

We investigate the definition of security for encryption scheme in quantum context. We systematically define the indistinguishability and semantic security for quantum public-key and private-key encryption schemes, and for computational security, physical security and information-theoretic security. Based on our definition, we present a necessary and sufficient condition that leads to information-theoretic indistinguishability for quantum encryption scheme. The equivalence between the indistinguishability and semantic security of quantum encryption scheme is also proved.
Spectral Analysis of Symmetric and Anti-Symmetric Pairwise Kernels
Venue: arXiv cs.LG 2015
Year: 2015

We consider the problem of learning regression functions from pairwise data when there exists prior knowledge that the relation to be learned is symmetric or anti-symmetric. Such prior knowledge is commonly enforced by symmetrizing or anti-symmetrizing pairwise kernel functions. Through spectral analysis, we show that these transformations reduce the kernel's effective dimension. Further, we provide an analysis of the approximation properties of the resulting kernels, and bound the regularization bias of the kernels in terms of the corresponding bias of the original kernel.
Representation-Compatible Power Indices
Venue: arXiv cs.GT 2015
Year: 2015

This paper studies power indices based on average representations of a weighted game. If restricted to account for the lack of power of dummy voters, average representations become coherent measures of voting power, with power distributions being proportional to the distribution of weights in the average representation. This makes these indices representation-compatible, a property not fulfilled by classical power indices. Average representations can be tailored to reveal the equivalence classes of voters defined by the Isbell desirability relation, which leads to a pair of new power indices that ascribes equal power to all members of an equivalence class.