OpenRaiser/Intern-Atlas huggingface dataset:
Ensemble of Thermostatically Controlled Loads: Statistical Physics Approach
Venue: arXiv cs.SY 2017
Year: 2017

Thermostatically Controlled Loads (TCL), e.g. air-conditioners and heaters, are by far the most wide-spread consumers of electricity. Normally the devices are calibrated to provide the so-called bang-bang control of temperature -- changing from on to off, and vice versa, depending on temperature. Aggregation of a large group of similar devices into a statistical ensemble is considered, where the devices operate following the same dynamics subject to stochastic perturbations and randomized, Poisson on/off switching policy. We analyze, using theoretical and computational tools of statistical physics, how the ensemble relaxes to a stationary distribution and establish relation between the relaxation and statistics of the probability flux, associated with devices' cycling in the mixed (discrete, switch on/off, and continuous, temperature) phase space. This allowed us to derive and analyze spectrum of the non-equilibrium (detailed balance broken) statistical system and uncover how switching policy affects oscillatory trend and speed of the relaxation. Relaxation of the ensemble is of a practical interest because it describes how the ensemble recovers from significant perturbations, e.g. forceful temporary switching off aimed at utilizing flexibility of the ensemble in providing "demand response" services relieving consumption temporarily to balance larger power grid. We discuss how the statistical analysis can guide further development of the emerging demand response technology.
Ontology based system to guide internship assignment process
Venue: arXiv cs.AI 2017
Year: 2017

Internship assignment is a complicated process for universities since it is necessary to take into account a multiplicity of variables to establish a compromise between companies' requirements and student competencies acquired during the university training. These variables build up a complex relations map that requires the formulation of an exhaustive and rigorous conceptual scheme. In this research a domain ontological model is presented as support to the student's decision making for opportunities of University studies level of the University Lumiere Lyon 2 (ULL) education system. The ontology is designed and created using methodological approach offering the possibility of improving the progressive creation, capture and knowledge articulation. In this paper, we draw a balance taking the demands of the companies across the capabilities of the students. This will be done through the establishment of an ontological model of an educational learners' profile and the internship postings which are written in a free text and using uncontrolled vocabulary. Furthermore, we outline the process of semantic matching which improves the quality of query results.
Algorithms For Longest Chains In Pseudo- Transitive Graphs
Venue: arXiv cs.CG 2017
Year: 2017

A directed acyclic graph G = (V, E) is pseudo-transitive with respect to a given subset of edges E1, if for any edge ab in E1 and any edge bc in E, we have ac in E. We give algorithms for computing longest chains and demonstrate geometric applications that unify and improves some important past results. (For specific applications see the introduction.)
Non-Iterative SLAM
Venue: arXiv cs.RO 2017
Year: 2017

The goal of this paper is to create a new framework for dense SLAM that is light enough for micro-robot systems based on depth camera and inertial sensor. Feature-based and direct methods are two mainstreams in visual SLAM. Both methods minimize photometric or reprojection error by iterative solutions, which are computationally expensive. To overcome this problem, we propose a non-iterative framework to reduce computational requirement. First, the attitude and heading reference system (AHRS) and axonometric projection are utilized to decouple the 6 Degree-of-Freedom (DoF) data, so that point clouds can be matched in independent spaces respectively. Second, based on single key-frame training, the matching process is carried out in frequency domain by Fourier transformation, which provides a closed-form non-iterative solution. In this manner, the time complexity is reduced to $\mathcal{O}(n \log{n})$, where $n$ is the number of matched points in each frame. To the best of our knowledge, this method is the first non-iterative and online trainable approach for data association in visual SLAM. Compared with the state-of-the-arts, it runs at a faster speed and obtains 3-D maps with higher resolution yet still with comparable accuracy.
Intersection Types and Counting
Venue: arXiv cs.LO 2017
Year: 2017

We present a new approach to the following meta-problem: given a quantitative property of trees, design a type system such that the desired property for the tree generated by an infinitary ground $λ$-term corresponds to some property of a derivation of a type for this $λ$-term, in this type system. Our approach is presented in the particular case of the language finiteness problem for nondeterministic higher-order recursion schemes (HORSes): given a nondeterministic HORS, decide whether the set of all finite trees generated by this HORS is finite. We give a type system such that the HORS can generate a tree of an arbitrarily large finite size if and only if in the type system we can obtain derivations that are arbitrarily large, in an appropriate sense; the latter condition can be easily decided.
Finding low-tension communities
Venue: arXiv cs.SI 2017
Year: 2017

Motivated by applications that arise in online social media and collaboration networks, there has been a lot of work on community-search and team-formation problems. In the former class of problems, the goal is to find a subgraph that satisfies a certain connectivity requirement and contains a given collection of seed nodes. In the latter class of problems, on the other hand, the goal is to find individuals who collectively have the skills required for a task and form a connected subgraph with certain properties. In this paper, we extend both the community-search and the team-formation problems by associating each individual with a profile. The profile is a numeric score that quantifies the position of an individual with respect to a topic. We adopt a model where each individual starts with a latent profile and arrives to a conformed profile through a dynamic conformation process, which takes into account the individual's social interaction and the tendency to conform with one's social environment. In this framework, social tension arises from the differences between the conformed profiles of neighboring individuals as well as from differences between individuals' conformed and latent profiles. Given a network of individuals, their latent profiles and this conformation process, we extend the community-search and the team-formation problems by requiring the output subgraphs to have low social tension. From the technical point of view, we study the complexity of these problems and propose algorithms for solving them effectively. Our experimental evaluation in a number of social networks reveals the efficacy and efficiency of our methods.
Profiling of OCR'ed Historical Texts Revisited
Venue: arXiv cs.CV 2017
Year: 2017

In the absence of ground truth it is not possible to automatically determine the exact spectrum and occurrences of OCR errors in an OCR'ed text. Yet, for interactive postcorrection of OCR'ed historical printings it is extremely useful to have a statistical profile available that provides an estimate of error classes with associated frequencies, and that points to conjectured errors and suspicious tokens. The method introduced in Reffle (2013) computes such a profile, combining lexica, pattern sets and advanced matching techniques in a specialized Expectation Maximization (EM) procedure. Here we improve this method in three respects: First, the method in Reffle (2013) is not adaptive: user feedback obtained by actual postcorrection steps cannot be used to compute refined profiles. We introduce a variant of the method that is open for adaptivity, taking correction steps of the user into account. This leads to higher precision with respect to recognition of erroneous OCR tokens. Second, during postcorrection often new historical patterns are found. We show that adding new historical patterns to the linguistic background resources leads to a second kind of improvement, enabling even higher precision by telling historical spellings apart from OCR errors. Third, the method in Reffle (2013) does not make any active use of tokens that cannot be interpreted in the underlying channel model. We show that adding these uninterpretable tokens to the set of conjectured errors leads to a significant improvement of the recall for error detection, at the same time improving precision.
Privacy Preserving Stream Analytics: The Marriage of Randomized Response and Approximate Computing
Venue: arXiv cs.DC 2017
Year: 2017

How to preserve users' privacy while supporting high-utility analytics for low-latency stream processing? To answer this question: we describe the design, implementation, and evaluation of PRIVAPPROX, a data analytics system for privacy-preserving stream processing. PRIVAPPROX provides three properties: (i) Privacy: zero-knowledge privacy guarantees for users, a privacy bound tighter than the state-of-the-art differential privacy; (ii) Utility: an interface for data analysts to systematically explore the trade-offs between the output accuracy (with error-estimation) and query execution budget; (iii) Latency: near real-time stream processing based on a scalable "synchronization-free" distributed architecture. The key idea behind our approach is to marry two existing techniques together: namely, sampling (used in the context of approximate computing) and randomized response (used in the context of privacy-preserving analytics). The resulting marriage is complementary - it achieves stronger privacy guarantees and also improves performance, a necessary ingredient for achieving low-latency stream analytics.
Block-wise Lensless Compressive Camera
Venue: arXiv cs.CV 2017
Year: 2017

The existing lensless compressive camera ($\text{L}^2\text{C}^2$)~\cite{Huang13ICIP} suffers from low capture rates, resulting in low resolution images when acquired over a short time. In this work, we propose a new regime to mitigate these drawbacks. We replace the global-based compressive sensing used in the existing $\text{L}^2\text{C}^2$ by the local block (patch) based compressive sensing. We use a single sensor for each block, rather than for the entire image, thus forming a multiple but spatially parallel sensor $\text{L}^2\text{C}^2$. This new camera retains the advantages of existing $\text{L}^2\text{C}^2$ while leading to the following additional benefits: 1) Since each block can be very small, {\em e.g.}$~8\times 8$ pixels, we only need to capture $\sim 10$ measurements to achieve reasonable reconstruction. Therefore the capture time can be reduced significantly. 2) The coding patterns used in each block can be the same, therefore the sensing matrix is only of the block size compared to the entire image size in existing $\text{L}^2\text{C}^2$. This saves the memory requirement of the sensing matrix as well as speeds up the reconstruction. 3) Patch based image reconstruction is fast and since real time stitching algorithms exist, we can perform real time reconstruction. 4) These small blocks can be integrated to any desirable number, leading to ultra high resolution images while retaining fast capture rate and fast reconstruction. We develop multiple geometries of this block-wise $\text{L}^2\text{C}^2$ in this paper. We have built prototypes of the proposed block-wise $\text{L}^2\text{C}^2$ and demonstrated excellent results of real data.
Moving to VideoKifu: the last steps toward a fully automatic record-keeping of a Go game
Venue: arXiv cs.CV 2017
Year: 2017

In a previous paper [ arXiv:1508.03269 ] we described the techniques we successfully employed for automatically reconstructing the whole move sequence of a Go game by means of a set of pictures. Now we describe how it is possible to reconstruct the move sequence by means of a video stream (which may be provided by an unattended webcam), possibly in real-time. Although the basic algorithms remain the same, we will discuss the new problems that arise when dealing with videos, with special care for the ones that could block a real-time analysis and require an improvement of our previous techniques or even a completely brand new approach. Eventually we present a number of preliminary but positive experimental results supporting the effectiveness of the software we are developing, built on the ideas here outlined.
Irrational Guards are Sometimes Needed
Venue: arXiv cs.CG 2017
Year: 2017

In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon such that the guards together can see the whole polygon. We say that a guard at position $x$ sees a point $y$ if the line segment $xy$ is fully contained in the polygon. Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every $n$, there is polygon which can be guarded by $3n$ guards with irrational coordinates but need $4n$ guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.
Metric Reasoning About $λ$-Terms: The General Case (Long Version)
Venue: arXiv cs.LO 2017
Year: 2017

In any setting in which observable properties have a quantitative flavour, it is natural to compare computational objects by way of \emph{metrics} rather than equivalences or partial orders. This holds, in particular, for probabilistic higher-order programs. A natural notion of comparison, then, becomes context distance, the metric analogue of Morris' context equivalence. In this paper, we analyze the main properties of the context distance in fully-fledged probabilistic $λ$-calculi, this way going beyond the state of the art, in which only affine calculi were considered. We first of all study to which extent the context distance trivializes, giving a sufficient condition for trivialization. We then characterize context distance by way of a coinductively defined, tuple-based notion of distance in one of those calculi, called $Λ^\oplus_!$. We finally derive pseudometrics for call-by-name and call-by-value probabilistic $λ$-calculi, and prove them fully-abstract.
Capacity and Normalized Optimal Detection Error in Gaussian Channels
Venue: arXiv cs.IT 2017
Year: 2017

For vector Gaussian channels, a precise differential connection between channel capacity and a quantity termed normalized optimal detection error (NODE) is presented. Then, this C-NODE relationship is extended to continuous-time Gaussian channels drawing on a waterfilling characterization recently found for the capacity of continuous-time linear time-varying channels. In the latter case, the C-NODE relationship becomes asymptotic in nature. In either case, the C-NODE relationship is compared with the I-MMSE relationship due to Guo et al. connecting mutual information in Gaussian channels with the minimum mean-square error (MMSE) of estimation theory.
Using LLVM-based JIT Compilation in Genetic Programming
Venue: arXiv cs.NE 2017
Year: 2017

The paper describes an approach to implementing genetic programming, which uses the LLVM library to just-in-time compile/interpret the evolved abstract syntax trees. The solution is described in some detail, including a parser (based on FlexC++ and BisonC++) that can construct the trees from a simple toy language with C-like syntax. The approach is compared with a previous implementation (based on direct execution of trees using polymorphic functors) in terms of execution speed.
Index appearance record for transforming Rabin automata into parity automata
Venue: arXiv cs.LO 2017
Year: 2017

Transforming deterministic $ω$-automata into deterministic parity automata is traditionally done using variants of appearance records. We present a more efficient variant of this approach, tailored to Rabin automata, and several optimizations applicable to all appearance records. We compare the methods experimentally and find out that our method produces smaller automata than previous approaches. Moreover, the experiments demonstrate the potential of our method for LTL synthesis, using LTL-to-Rabin translators. It leads to significantly smaller parity automata when compared to state-of-the-art approaches on complex formulae.
On the Performance of X-Duplex Relaying
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we study a X-duplex relay system with one source, one amplify-and-forward (AF) relay and one destination, where the relay is equipped with a shared antenna and two radio frequency (RF) chains used for transmission or reception. X-duplex relay can adaptively configure the connection between its RF chains and antenna to operate in either HD or FD mode, according to the instantaneous channel conditions. We first derive the distribution of the signal to interference plus noise ratio (SINR), based on which we then analyze the outage probability, average symbol error rate (SER), and average sum rate. We also investigate the X-duplex relay with power allocation and derive the lower bound and upper bound of the corresponding outage probability. Both analytical and simulated results show that the X-duplex relay achieves a better performance over pure FD and HD schemes in terms of SER, outage probability and average sum rate, and the performance floor caused by the residual self interference can be eliminated using flexible RF chain configurations.
User-guided free-form asset modelling
Venue: arXiv cs.GR 2017
Year: 2017

In this paper a new system for piecewise primitive surface recovery on point clouds is presented, which allows a novice user to sketch areas of interest in order to guide the fitting process. The algorithm is demonstrated against a benchmark technique for autonomous surface fitting, and, contrasted against existing literature in user guided surface recovery, with empirical evidence. It is concluded that the system is an improvement to the current documented literature for its visual quality when modelling objects which are composed of piecewise primitive shapes, and, in its ability to fill large holes on occluded surfaces using free-form input.
Consequences of Unhappiness While Developing Software
Venue: arXiv cs.SE 2017
Year: 2017

The growing literature on affect among software developers mostly reports on the linkage between happiness, software quality, and developer productivity. Understanding the positive side of happiness -- positive emotions and moods -- is an attractive and important endeavor. Scholars in industrial and organizational psychology have suggested that also studying the negative side -- unhappiness -- could lead to cost-effective ways of enhancing working conditions, job performance, and to limiting the occurrence of psychological disorders. Our comprehension of the consequences of (un)happiness among developers is still too shallow, and is mainly expressed in terms of development productivity and software quality. In this paper, we attempt to uncover the experienced consequences of unhappiness among software developers. Using qualitative data analysis of the responses given by 181 questionnaire participants, we identified 49 consequences of unhappiness while doing software development. We found detrimental consequences on developers' mental well-being, the software development process, and the produced artifacts. Our classification scheme, available as open data, will spawn new happiness research opportunities of cause-effect type, and it can act as a guideline for practitioners for identifying damaging effects of unhappiness and for fostering happiness on the job.
Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
Venue: arXiv cs.DM 2017
Year: 2017

A graph is said to be well-dominated if all its minimal dominating sets are of the same size. The class of well-dominated graphs forms a subclass of the well studied class of well-covered graphs. While the recognition problem for the class of well-covered graphs is known to be co-NP-complete, the recognition complexity of well-dominated graphs is open. In this paper we introduce the notion of an irreducible dominating set, a variant of dominating set generalizing both minimal dominating sets and minimal total dominating sets. Based on this notion, we characterize the family of minimal dominating sets in a lexicographic product of two graphs and derive a characterization of the well-dominated lexicographic product graphs. As a side result motivated by this study, we give a polynomially testable characterization of well-dominated graphs with domination number two, and show, more generally, that well-dominated graphs can be recognized in polynomial time in any class of graphs with bounded domination number. Our results include a characterization of dominating sets in lexicographic product graphs, which generalizes the expression for the domination number of such graphs following from works of Zhang et al. (2011) and of Šumenjak et al. (2012).
What makes a gesture a gesture? Neural signatures involved in gesture recognition
Venue: arXiv cs.HC 2017
Year: 2017

Previous work in the area of gesture production, has made the assumption that machines can replicate "human-like" gestures by connecting a bounded set of salient points in the motion trajectory. Those inflection points were hypothesized to also display cognitive saliency. The purpose of this paper is to validate that claim using electroencephalography (EEG). That is, this paper attempts to find neural signatures of gestures (also referred as placeholders) in human cognition, which facilitate the understanding, learning and repetition of gestures. Further, it is discussed whether there is a direct mapping between the placeholders and kinematic salient points in the gesture trajectories. These are expressed as relationships between inflection points in the gestures' trajectories with oscillatory mu rhythms (8-12 Hz) in the EEG. This is achieved by correlating fluctuations in mu power during gesture observation with salient motion points found for each gesture. Peaks in the EEG signal at central electrodes (motor cortex) and occipital electrodes (visual cortex) were used to isolate the salient events within each gesture. We found that a linear model predicting mu peaks from motion inflections fits the data well. Increases in EEG power were detected 380 and 500ms after inflection points at occipital and central electrodes, respectively. These results suggest that coordinated activity in visual and motor cortices is sensitive to motion trajectories during gesture observation, and it is consistent with the proposal that inflection points operate as placeholders in gesture recognition.