OpenRaiser/Intern-Atlas huggingface dataset:
A Multiple Search Operator Heuristic for the Max-k-cut Problem
Venue: arXiv cs.DM 2015
Year: 2015

The max-k-cut problem is to partition the vertices of a weighted graph $G = (V,E)$ into $k\geq2$ disjoint subsets such that the weight sum of the edges crossing the different subsets is maximized. The problem is referred as the max-cut problem when $k=2$. In this work, we present a multiple operator heuristic (MOH) for the general max-k-cut problem. MOH employs five distinct search operators organized into three search phases to effectively explore the search space. Experiments on two sets of 91 well-known benchmark instances show that the proposed algorithm is highly effective on the max-k-cut problem and improves the current best known results (new lower bounds) of most of the tested instances. For the popular special case $k=2$ (i.e., the max-cut problem), MOH also performs remarkably well by discovering 6 improved best known results. We provide additional studies to shed light on the alternative combinations of the employed search operators.
Quantifying the Cognitive Extent of Science
Venue: arXiv cs.DL 2015
Year: 2015

While the modern science is characterized by an exponential growth in scientific literature, the increase in publication volume clearly does not reflect the expansion of the cognitive boundaries of science. Nevertheless, most of the metrics for assessing the vitality of science or for making funding and policy decisions are based on productivity. Similarly, the increasing level of knowledge production by large science teams, whose results often enjoy greater visibility, does not necessarily mean that "big science" leads to cognitive expansion. Here we present a novel, big-data method to quantify the extents of cognitive domains of different bodies of scientific literature independently from publication volume, and apply it to 20 million articles published over 60-130 years in physics, astronomy, and biomedicine. The method is based on the lexical diversity of titles of fixed quotas of research articles. Owing to large size of quotas, the method overcomes the inherent stochasticity of article titles to achieve <1% precision. We show that the periods of cognitive growth do not necessarily coincide with the trends in publication volume. Furthermore, we show that the articles produced by larger teams cover significantly smaller cognitive territory than (the same quota of) articles from smaller teams. Our findings provide a new perspective on the role of small teams and individual researchers in expanding the cognitive boundaries of science. The proposed method of quantifying the extent of the cognitive territory can also be applied to study many other aspects of "science of science."
CarPed -- A Hybrid and Macroscopic Traffic and Pedestrian Simulator
Venue: arXiv cs.MA 2015
Year: 2015

Dense human flow has been a concern for the safety of public events for a long time. Macroscopic pedestrian models, which are mainly based on fluid dynamics, are often used to simulate huge crowds due to their low computational costs (Columbo & Rosini 2005). Similar approaches are used in the field of traffic simulations (Lighthill & Whitham 1955). A combined macroscopic simulation of vehicles and pedestrians is extremely helpful for all-encompassing traffic control. Therefore, we developed a hybrid model that contains networks for vehicular traffic and human flow. This comprehensive model supports concurrent multi-modal simulations of traffic and pedestrians.
Sketch-based Image Retrieval from Millions of Images under Rotation, Translation and Scale Variations
Venue: arXiv cs.CV 2015
Year: 2015

Proliferation of touch-based devices has made sketch-based image retrieval practical. While many methods exist for sketch-based object detection/image retrieval on small datasets, relatively less work has been done on large (web)-scale image retrieval. In this paper, we present an efficient approach for image retrieval from millions of images based on user-drawn sketches. Unlike existing methods for this problem which are sensitive to even translation or scale variations, our method handles rotation, translation, scale (i.e. a similarity transformation) and small deformations. The object boundaries are represented as chains of connected segments and the database images are pre-processed to obtain such chains that have a high chance of containing the object. This is accomplished using two approaches in this work: a) extracting long chains in contour segment networks and b) extracting boundaries of segmented object proposals. These chains are then represented by similarity-invariant variable length descriptors. Descriptor similarities are computed by a fast Dynamic Programming-based partial matching algorithm. This matching mechanism is used to generate a hierarchical k-medoids based indexing structure for the extracted chains of all database images in an offline process which is used to efficiently retrieve a small set of possible matched images for query chains. Finally, a geometric verification step is employed to test geometric consistency of multiple chain matches to improve results. Qualitative and quantitative results clearly demonstrate superiority of the approach over existing methods.
Topological chaos and chaotic iterations. Application to Hash functions
Venue: arXiv cs.CR 2015
Year: 2015

This paper introduces a new notion of chaotic algorithms. These algorithms are iterative and are based on so-called chaotic iterations. Contrary to all existing studies on chaotic iterations, we are not interested in stable states of such iterations but in their possible unpredictable behaviors. By establishing a link between chaotic iterations and the notion of Devaney's topological chaos, we give conditions ensuring that these kind of algorithms produce topological chaos. This leads to algorithms that are highly unpredictable. After presenting the theoretical foundations of our approach, we are interested in its practical aspects. We show how the theoretical algorithms give rise to computer programs that produce true topological chaos, then we propose applications in the area of information security.
A Unified Tagging Solution: Bidirectional LSTM Recurrent Neural Network with Word Embedding
Venue: arXiv cs.CL 2015
Year: 2015

Bidirectional Long Short-Term Memory Recurrent Neural Network (BLSTM-RNN) has been shown to be very effective for modeling and predicting sequential data, e.g. speech utterances or handwritten documents. In this study, we propose to use BLSTM-RNN for a unified tagging solution that can be applied to various tagging tasks including part-of-speech tagging, chunking and named entity recognition. Instead of exploiting specific features carefully optimized for each task, our solution only uses one set of task-independent features and internal representations learnt from unlabeled text for all tasks.Requiring no task specific knowledge or sophisticated feature engineering, our approach gets nearly state-of-the-art performance in all these three tagging tasks.
LM-CMA: an Alternative to L-BFGS for Large Scale Black-box Optimization
Venue: arXiv cs.NE 2015
Year: 2015

The limited memory BFGS method (L-BFGS) of Liu and Nocedal (1989) is often considered to be the method of choice for continuous optimization when first- and/or second- order information is available. However, the use of L-BFGS can be complicated in a black-box scenario where gradient information is not available and therefore should be numerically estimated. The accuracy of this estimation, obtained by finite difference methods, is often problem-dependent that may lead to premature convergence of the algorithm. In this paper, we demonstrate an alternative to L-BFGS, the limited memory Covariance Matrix Adaptation Evolution Strategy (LM-CMA) proposed by Loshchilov (2014). The LM-CMA is a stochastic derivative-free algorithm for numerical optimization of non-linear, non-convex optimization problems. Inspired by the L-BFGS, the LM-CMA samples candidate solutions according to a covariance matrix reproduced from $m$ direction vectors selected during the optimization process. The decomposition of the covariance matrix into Cholesky factors allows to reduce the memory complexity to $O(mn)$, where $n$ is the number of decision variables. The time complexity of sampling one candidate solution is also $O(mn)$, but scales as only about 25 scalar-vector multiplications in practice. The algorithm has an important property of invariance w.r.t. strictly increasing transformations of the objective function, such transformations do not compromise its ability to approach the optimum. The LM-CMA outperforms the original CMA-ES and its large scale versions on non-separable ill-conditioned problems with a factor increasing with problem dimension. Invariance properties of the algorithm do not prevent it from demonstrating a comparable performance to L-BFGS on non-trivial large scale smooth and nonsmooth optimization problems.
Shortest Reconfiguration of Sliding Tokens on a Caterpillar
Venue: arXiv cs.DS 2015
Year: 2015

Suppose that we are given two independent sets I_b and I_r of a graph such that |I_b|=|I_r|, and imagine that a token is placed on each vertex in |I_b|. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms I_b into I_r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. The reconfiguration problems tend to be PSPACE-complete in general, and some polynomial time algorithms are shown in restricted cases. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. For the 3SAT problem, a trichotomy for the complexity of finding the shortest sequence has been shown, that is, it is in P, NP-complete, or PSPACE-complete in certain conditions. In general, even if it is polynomial time solvable to decide whether two instances are reconfigured with each other, it can be NP-complete to find a shortest sequence between them. Namely, finding a shortest sequence between two independent sets can be more difficult than the decision problem of reconfigurability between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs. More precisely, we can find a shortest sequence between two independent sets on a graph G in polynomial time if either G is a proper interval graph, a trivially perfect graph, or a caterpillar. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours.
A Construction of Binary Linear Codes from Boolean Functions
Venue: arXiv cs.IT 2015
Year: 2015

Boolean functions have important applications in cryptography and coding theory. Two famous classes of binary codes derived from Boolean functions are the Reed-Muller codes and Kerdock codes. In the past two decades, a lot of progress on the study of applications of Boolean functions in coding theory has been made. Two generic constructions of binary linear codes with Boolean functions have been well investigated in the literature. The objective of this paper is twofold. The first is to provide a survey on recent results, and the other is to propose open problems on one of the two generic constructions of binary linear codes with Boolean functions. These open problems are expected to stimulate further research on binary linear codes from Boolean functions.
Six Potential Game-Changers in Cyber Security: Towards Priorities in Cyber Science and Engineering
Venue: arXiv cs.CR 2015
Year: 2015

The fields of study encompassed by cyber science and engineering are broad and poorly defined at this time. As national governments and research communities increase their recognition of the importance, urgency and technical richness of these disciplines, a question of priorities arises: what specific sub-areas of research should be the foci of attention and funding? In this paper we point to an approach to answering this question. We explore results of a recent workshop that postulated possible game-changers or disruptive changes that might occur in cyber security within the next 15 years. We suggest that such game-changers may be useful in focusing attention of research communities on high-priority topics. Indeed, if a drastic, important change is likely to occur, should we not focus our research efforts on the nature and ramifications of the phenomena pertaining to that change? We illustrate each of the game-changers examples of related current research, and then offer recommendations for advancement of cyber science and engineering with respect to each of the six game-changers.
Optimizing the Deployment of Electric Vehicle Charging Stations Using Pervasive Mobility Data
Venue: arXiv cs.SY 2015
Year: 2015

With recent advances in battery technology and the resulting decrease in the charging times, public charging stations are becoming a viable option for Electric Vehicle (EV) drivers. Concurrently, wide-spread use of location-tracking devices in mobile phones and wearable devices makes it possible to track individual-level human movements to an unprecedented spatial and temporal grain. Motivated by these developments, we propose a novel methodology to perform data-driven optimization of EV charging stations location. We formulate the problem as a discrete optimization problem on a geographical grid, with the objective of covering the entire demand region while minimizing a measure of drivers' discomfort. Since optimally solving the problem is computationally infeasible, we present computationally efficient, near-optimal solutions based on greedy and genetic algorithms. We then apply the proposed methodology to optimize EV charging stations location in the city of Boston, starting from a massive cellular phone data sets covering 1 million users over 4 months. Results show that genetic algorithm based optimization provides the best solutions in terms of drivers' discomfort and the number of charging stations required, which are both reduced about 10 percent as compared to a randomized solution. We further investigate robustness of the proposed data-driven methodology, showing that, building upon well-known regularity of aggregate human mobility patterns, the near-optimal solution computed using single day movements preserves its properties also in later months. When collectively considered, the results presented in this paper clearly indicate the potential of data-driven approaches for optimally locating public charging facilities at the urban scale.
Coherent Detection of Turbo-Coded OFDM Signals Transmitted through Frequency Selective Rayleigh Fading Channels with Receiver Diversity and Increased Throughput
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we discuss techniques for coherently detecting turbo coded orthogonal frequency division multiplexed (OFDM) signals, transmitted through frequency selective Rayleigh (the magnitude of each channel tap is Rayleigh distributed) fading channels having a uniform power delay profile. The channel output is further distorted by a carrier frequency and phase offset, besides additive white Gaussian noise (AWGN). A new frame structure for OFDM, consisting of a known preamble, cyclic prefix, data and known postamble is proposed, which has a higher throughput compared to the earlier work. A robust turbo decoder is proposed, which functions effectively over a wide range of signal-to-noise ratio (SNR). The key contribution to the good performance of the practical coherent receiver is due to the use of a long preamble (512 QPSK symbols), which is perhaps not specified in any of the current wireless communication standards. We have also shown from computer simulations that, it is possible to obtain even better BER performance, using a better code. A simple and approximate Cramer-Rao bound on the variance of the frequency offset estimation error for coherent detection, is derived. The proposed algorithms are well suited for implementation on a DSP-platform.
Three Stories on a Two-sided Coin: Index Coding, Locally Recoverable Distributed Storage, and Guessing Games on Graphs
Venue: arXiv cs.IT 2015
Year: 2015

Three science and engineering problems of recent interests -index coding, locally recoverable distributed storage, and guessing games on graphs- are discussed and the connection between their optimal solutions is elucidated. By generalizing recent results by Shanmugam and Dimakis and by Mazumdar on the complementarity between the optimal broadcast rate of an index coding problem on a directed graph and the normalized rate of a locally recoverable distributed storage problem on the same graph, it is shown that the capacity region and the optimal rate region of these two problems are complementary. The main ingredients in establishing this result are the notion of confusion graph introduced by Alon et al. (2008), the vertex transitivity of a confusion graph, the characterization of the index coding capacity region via the fractional chromatic number of confusion graphs, and the characterization of the optimal rate region of the locally recoverable distributed storage via the independence number of confusion graphs. As the third and final facet of the complementarity, guessing games on graphs by Riis are discussed as special cases of the locally recoverable distributed storage problem, and it is shown that the winning probability of the optimal strategy for a guessing game and the ratio between the winning probabilities of the optimal strategy and a random guess can be characterized, respectively, by the capacity region for index coding and the optimal rate region for distributed storage.
Towards a Consumer-Centric Grid: A Behavioral Perspective
Venue: arXiv cs.SY 2015
Year: 2015

Active consumer participation is seen as an integral part of the emerging smart grid. Examples include demand-side management programs, incorporation of consumer-owned energy storage or renewable energy units, and active energy trading. However, despite the foreseen technological benefits of such consumer-centric grid features, to date, their widespread adoption in practice remains modest. To shed light on this challenge, this paper explores the potential of prospect theory, a Nobel-prize winning theory, as a decision-making framework that can help understand how risk and uncertainty can impact the decisions of smart grid consumers. After introducing the basic notions of prospect theory, several examples drawn from a number of smart grid applications are developed. These results show that a better understanding of the role of human decision-making within the smart grid is paramount for optimizing its operation and expediting the deployment of its various technologies.
Adapting Real Quantifier Elimination Methods for Conflict Set Computation
Venue: arXiv cs.LO 2015
Year: 2015

The satisfiability problem in real closed fields is decidable. In the context of satisfiability modulo theories, the problem restricted to conjunctive sets of literals, that is, sets of polynomial constraints, is of particular importance. One of the central problems is the computation of good explanations of the unsatisfiability of such sets, i.e.\ obtaining a small subset of the input constraints whose conjunction is already unsatisfiable. We adapt two commonly used real quantifier elimination methods, cylindrical algebraic decomposition and virtual substitution, to provide such conflict sets and demonstrate the performance of our method in practice.
Improved Polynomial Remainder Sequences for Ore Polynomials
Venue: arXiv cs.SC 2015
Year: 2015

Polynomial remainder sequences contain the intermediate results of the Euclidean algorithm when applied to (non-)commutative polynomials. The running time of the algorithm is dependent on the size of the coefficients of the remainders. Different ways have been studied to make these as small as possible. The subresultant sequence of two polynomials is a polynomial remainder sequence in which the size of the coefficients is optimal in the generic case, but when taking the input from applications, the coefficients are often larger than necessary. We generalize two improvements of the subresultant sequence to Ore polynomials and derive a new bound for the minimal coefficient size. Our approach also yields a new proof for the results in the commutative case, providing a new point of view on the origin of the extraneous factors of the coefficients.
Full abstraction for probabilistic PCF
Venue: arXiv cs.LO 2015
Year: 2015

We present a probabilistic version of PCF, a well-known simply typed universal functional language. The type hierarchy is based on a single ground type of natural numbers. Even if the language is globally call-by-name, we allow a call-by-value evaluation for ground type arguments in order to provide the language with a suitable algorithmic expressiveness. We describe a denotational semantics based on probabilistic coherence spaces, a model of classical Linear Logic developed in previous works. We prove an adequacy and an equational full abstraction theorem showing that equality in the model coincides with a natural notion of observational equivalence.
Demo: Non-classic Interference Alignment for Downlink Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

Our demo aims at proving the concept of a recent proposed interference management scheme that reduces the inter-cell interference in downlink without complex coordination, known as non-classic interference alignment (IA) scheme. We assume a case where one main Base Station (BS) needs to serve three users equipments (UE) while another BS is causing interference. The primary goal is to construct the alignment scheme ; i.e. each UE estimates the main and interfered channel coefficients, calculates the optimal interference free directions dropped by the interfering BS and feeds them back to the main BS which in turn applies a scheduling to select the best free inter-cell interference directions. Once the scheme is build, we are able to measure the total capacity of the downlink interference channel. We run the scheme in CorteXlab ; a controlled hardware facility located in Lyon, France with remotely programmable radios and multi-node processing capabilities, and we illustrate the achievable capacity gain for different channel realizations.
Study of a bias in the offline evaluation of a recommendation algorithm
Venue: arXiv cs.IR 2015
Year: 2015

Recommendation systems have been integrated into the majority of large online systems to filter and rank information according to user profiles. It thus influences the way users interact with the system and, as a consequence, bias the evaluation of the performance of a recommendation algorithm computed using historical data (via offline evaluation). This paper describes this bias and discuss the relevance of a weighted offline evaluation to reduce this bias for different classes of recommendation algorithms.
Geometry on the Utility Space
Venue: arXiv cs.GT 2015
Year: 2015

We study the geometrical properties of the utility space (the space of expected utilities over a finite set of options), which is commonly used to model the preferences of an agent in a situation of uncertainty. We focus on the case where the model is neutral with respect to the available options, i.e. treats them, a priori, as being symmetrical from one another. Specifically, we prove that the only Riemannian metric that respects the geometrical properties and the natural symmetries of the utility space is the round metric. This canonical metric allows to define a uniform probability over the utility space and to naturally generalize the Impartial Culture to a model with expected utilities.