OpenRaiser/Intern-Atlas huggingface dataset:
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
Venue: arXiv cs.CC 2016
Year: 2016

Given a fixed constraint language $Γ$, the conservative CSP over $Γ$ (denoted by c-CSP($Γ$)) is a variant of CSP($Γ$) where the domain of each variable can be restricted arbitrarily. A dichotomy is known for conservative CSP: for every fixed language $Γ$, c-CSP($Γ$) is either in P or NP-complete. However, the characterization of conservatively tractable languages is of algebraic nature and the naive recognition algorithm is super-exponential in the domain size. The main contribution of this paper is a polynomial-time algorithm that, given a constraint language $Γ$ as input, decides if c-CSP($Γ$) is tractable. In addition, if $Γ$ is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of $Γ$.
Stochastic Variance-Reduced ADMM
Venue: arXiv cs.LG 2016
Year: 2016

The alternating direction method of multipliers (ADMM) is a powerful optimization solver in machine learning. Recently, stochastic ADMM has been integrated with variance reduction methods for stochastic gradient, leading to SAG-ADMM and SDCA-ADMM that have fast convergence rates and low iteration complexities. However, their space requirements can still be high. In this paper, we propose an integration of ADMM with the method of stochastic variance reduced gradient (SVRG). Unlike another recent integration attempt called SCAS-ADMM, the proposed algorithm retains the fast convergence benefits of SAG-ADMM and SDCA-ADMM, but is more advantageous in that its storage requirement is very low, even independent of the sample size $n$. We also extend the proposed method for nonconvex problems, and obtain a convergence rate of $O(1/T)$. Experimental results demonstrate that it is as fast as SAG-ADMM and SDCA-ADMM, much faster than SCAS-ADMM, and can be used on much bigger data sets.
Smart Shires: The Revenge of Countrysides (Extended Version)
Venue: arXiv cs.CY 2016
Year: 2016

This paper discusses the need to devise novel strategies to create smart services specifically designed to non-metropolitan areas, i.e. countrysides. These solutions must be viable, cheap an should take into consideration the different nature of countrysides, that cannot afford the deployment of services designed for smart cities. These solutions would have an important social impact for people leaving in these countrysides, and might slow down the constant migration of citizens towards metropolis. In this work, we focus on communication technologies and practical technological/software distributed architectures. An important aspect for the real deployment of these smart shires is their simulation. We show that priority-based broadcast schemes over ad-hoc networks can represent an effective communication substrate to be used in a software middleware promoting the creation of applications for smart shire scenarios.
Voronoi Choice Games
Venue: arXiv cs.GT 2016
Year: 2016

We study novel variations of Voronoi games and associated random processes that we call Voronoi choice games. These games provide a rich framework for studying questions regarding the power of small numbers of choices in multi-player, competitive scenarios, and they further lead to many interesting, non-trivial random processes that appear worthy of study. As an example of the type of problem we study, suppose a group of $n$ miners are staking land claims through the following process: each miner has $m$ associated points independently and uniformly distributed on an underlying space, so the $k$th miner will have associated points $p_{k1},p_{k2},\ldots,p_{km}$. Each miner chooses one of these points as the base point for their claim. Each miner obtains mining rights for the area of the square that is closest to their chosen base, that is, they obtain the Voronoi cell corresponding to their chosen point in the Voronoi diagram of the $n$ chosen points. Each player's goal is simply to maximize the amount of land under their control. What can we say about the players' strategy and the equilibria of such games? In our main result, we derive bounds on the expected number of pure Nash equilibria for a variation of the 1-dimensional game on the circle where a player owns the arc starting from their point and moving clockwise to the next point. This result uses interesting properties of random arc lengths on circles, and demonstrates the challenges in analyzing these kinds of problems. We also provide several other related results. In particular, for the 1-dimensional game on the circle, we show that a pure Nash equilibrium always exists when each player owns the part of the circle nearest to their point, but it is NP-hard to determine whether a pure Nash equilibrium exists in the variant when each player owns the arc starting from their point clockwise to the next point.
Modeling the Evolution of Gene-Culture Divergence
Venue: arXiv cs.NE 2016
Year: 2016

We present a model for evolving agents using both genetic and cultural inheritance mechanisms. Within each agent our model maintains two distinct information stores we call the genome and the memome. Processes of adaptation are modeled as evolutionary processes at each level of adaptation (phylogenetic, ontogenetic, sociogenetic). We review relevant competing models and we show how our model improves on previous attempts to model genetic and cultural evolutionary processes. In particular we argue our model can achieve divergent gene-culture co-evolution.
On the Grundy number of Cameron graphs
Venue: arXiv cs.DM 2016
Year: 2016

The Grundy number of a graph is the maximal number of colors attained by a first-fit coloring of the graph. The class of Cameron graphs is the Seidel switching class of cographs. In this paper we show that the Grundy number is computable in polynomial time for Cameron graphs.
Leveraging Multiple Channels in Ad Hoc Networks
Venue: arXiv cs.DC 2016
Year: 2016

We examine the utility of multiple channels of communication in wireless networks under the SINR model of interference. The central question is whether the use of multiple channels can result in linear speedup, up to some fundamental limit. We answer this question affirmatively for the data aggregation problem, perhaps the most fundamental problem in sensor networks. To achieve this, we form a hierarchical structure of independent interest, and illustrate its versatility by obtaining a new algorithm with linear speedup for the node coloring problem.
Generalized Homogeneous Polynomials for Efficient Template-Based Nonlinear Invariant Synthesis
Venue: arXiv cs.PL 2016
Year: 2016

The template-based method is one of the most successful approaches to algebraic invariant synthesis. In this method, an algorithm designates a template polynomial p over program variables, generates constraints for p=0 to be an invariant, and solves the generated constraints. However, this approach often suffers from an increasing template size if the degree of a template polynomial is too high. We propose a technique to make template-based methods more efficient. Our technique is based on the following finding: If an algebraic invariant exists, then there is a specific algebraic invariant that we call a generalized homogeneous algebraic invariant that is often smaller. This finding justifies using only a smaller template that corresponds to a generalized homogeneous algebraic invariant. Concretely, we state our finding above formally based on the abstract semantics of an imperative program proposed by Cachera et al. Then, we modify their template-based invariant synthesis so that it generates only generalized homogeneous algebraic invariants. This modification is proved to be sound. Furthermore, we also empirically demonstrate the merit of the restriction to generalized homogeneous algebraic invariants. Our implementation outperforms that of Cachera et al. for programs that require a higher-degree template.
Semi-supervised Dictionary Learning Based on Hilbert-Schmidt Independence Criterion
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, a novel semi-supervised dictionary learning and sparse representation (SS-DLSR) is proposed. The proposed method benefits from the supervisory information by learning the dictionary in a space where the dependency between the data and class labels is maximized. This maximization is performed using Hilbert-Schmidt independence criterion (HSIC). On the other hand, the global distribution of the underlying manifolds were learned from the unlabeled data by minimizing the distances between the unlabeled data and the corresponding nearest labeled data in the space of the dictionary learned. The proposed SS-DLSR algorithm has closed-form solutions for both the dictionary and sparse coefficients, and therefore does not have to learn the two iteratively and alternately as is common in the literature of the DLSR. This makes the solution for the proposed algorithm very fast. The experiments confirm the improvement in classification performance on benchmark datasets by including the information from both labeled and unlabeled data, particularly when there are many unlabeled data.
Predictive No-Reference Assessment of Video Quality
Venue: arXiv cs.MM 2016
Year: 2016

Among the various means to evaluate the quality of video streams, No-Reference (NR) methods have low computation and may be executed on thin clients. Thus, NR algorithms would be perfect candidates in cases of real-time quality assessment, automated quality control and, particularly, in adaptive mobile streaming. Yet, existing NR approaches are often inaccurate, in comparison to Full-Reference (FR) algorithms, especially under lossy network conditions. In this work, we present an NR method that combines machine learning with simple NR metrics to achieve a quality index comparably as accurate as the Video Quality Metric (VQM) Full-Reference algorithm. Our method is tested in an extensive dataset (960 videos), under lossy network conditions and considering nine different machine learning algorithms. Overall, we achieve an over 97% correlation with VQM, while allowing real-time assessment of video quality of experience in realistic streaming scenarios.
NRSSPrioritize: Associating Protein Complex and Disease Similarity Information to Prioritize Disease Candidate Genes
Venue: arXiv cs.CE 2016
Year: 2016

The identification of disease-associated genes has recently gathered much attention for uncovering disease complex mechanisms that could lead to new insights into the treatment of diseases. For exploring disease-susceptible genes, not only experimental approaches such as genome-wide association studies (GWAS) have been used, but also computational methods. Since experimental approaches are both time-consuming and expensive, numerous studies have utilized computational techniques to explore disease genes. These methods use various biological data sources and known disease genes to prioritize disease candidate genes. In this paper, we propose a gene prioritization method (NRSSPrioritize), which benefits from both local and global measures of a protein-protein interaction (PPI) network and also from disease similarity knowledge to suggest candidate genes for colorectal cancer (CRC) susceptibility. Network Propagation, Random Walk with Restart, and Shortest Paths are three network analysis tools that are applied to a PPI network for the purpose of scoring candidate genes. Also, by looking through diseases with similar symptoms to CRC and obtaining their causing genes, candidate genes are scored in a different way. Finally, to integrate these four different scoring schemes, Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) and Analytic Network Process (ANP) methods are applied to obtain appropriate weights for the above four quantified measures and the weighted summation of these measures are used to calculate the final score of each candidate gene. NRSSPrioritize was validated by cross-validation analysis and its results were compared with other prioritization tools, which gave the best performance when using our proposed method.
Deep Multi-fidelity Gaussian Processes
Venue: arXiv cs.LG 2016
Year: 2016

We develop a novel multi-fidelity framework that goes far beyond the classical AR(1) Co-kriging scheme of Kennedy and O'Hagan (2000). Our method can handle general discontinuous cross-correlations among systems with different levels of fidelity. A combination of multi-fidelity Gaussian Processes (AR(1) Co-kriging) and deep neural networks enables us to construct a method that is immune to discontinuities. We demonstrate the effectiveness of the new technology using standard benchmark problems designed to resemble the outputs of complicated high- and low-fidelity codes.
Sleeping Beauties in Meme Diffusion
Venue: arXiv cs.SI 2016
Year: 2016

A sleeping beauty in diffusion indicates that the information, can be ideas or innovations, will experience a hibernation before a sudden spike of popularity and it is widely found in citation history of scientific publications. However, in this study, we demonstrate that the sleeping beauty is an interesting and unexceptional phenomenon in information diffusion and even more inspiring, there exist two consecutive sleeping beauties in the entire lifetime of propagation, suggesting that the information, including scientific topics, search queries or Wikipedia entries, which we call memes, will go unnoticed for a period and suddenly attracts some attention, and then it falls asleep again and later wakes up with another unexpected popularity peak. Further explorations on this phenomenon show that intervals between two wake ups follow an exponential distribution and the second wake up generally reaches its peak at a higher velocity. In addition, higher volume of the first wake up will lead to even much higher popularity of the second wake up with great odds. Taking these findings into consideration, an upgraded Bass model is presented to well describe the diffusion dynamics of memes on different media. Our results can help understand the common mechanism behind propagation of different memes and are instructive to locate the tipping point in marketing or find innovative publications in science.
The $p$-Center Problem in Tree Networks Revisited
Venue: arXiv cs.DS 2016
Year: 2016

We present two improved algorithms for weighted discrete $p$-center problem for tree networks with $n$ vertices. One of our proposed algorithms runs in $O(n \log n + p \log^2 n \log(n/p))$ time. For all values of $p$, our algorithm thus runs as fast as or faster than the most efficient $O(n\log^2 n)$ time algorithm obtained by applying Cole's speed-up technique [cole1987] to the algorithm due to Megiddo and Tamir [megiddo1983], which has remained unchallenged for nearly 30 years. Our other algorithm, which is more practical, runs in $O(n \log n + p^2 \log^2(n/p))$ time, and when $p=O(\sqrt{n})$ it is faster than Megiddo and Tamir's $O(n \log^2n \log\log n)$ time algorithm [megiddo1983].
Towards Miss Universe Automatic Prediction: The Evening Gown Competition
Venue: arXiv cs.CV 2016
Year: 2016

Can we predict the winner of Miss Universe after watching how they stride down the catwalk during the evening gown competition? Fashion gurus say they can! In our work, we study this question from the perspective of computer vision. In particular, we want to understand whether existing computer vision approaches can be used to automatically extract the qualities exhibited by the Miss Universe winners during their catwalk. This study can pave the way towards new vision-based applications for the fashion industry. To this end, we propose a novel video dataset, called the Miss Universe dataset, comprising 10 years of the evening gown competition selected between 1996-2010. We further propose two ranking-related problems: (1) Miss Universe Listwise Ranking and (2) Miss Universe Pairwise Ranking. In addition, we also develop an approach that simultaneously addresses the two proposed problems. To describe the videos we employ the recently proposed Stacked Fisher Vectors in conjunction with robust local spatio-temporal features. From our evaluation we found that although the addressed problems are extremely challenging, the proposed system is able to rank the winner in the top 3 best predicted scores for 5 out of 10 Miss Universe competitions.
A Retraction Theorem for Distributed Synthesis
Venue: arXiv cs.DC 2016
Year: 2016

We present a general theorem for distributed synthesis problems in coordination games with $ω$-regular objectives of the form: If there exists a winning strategy for the coalition, then there exists an "essential" winning strategy, that is obtained by a retraction of the given one. In general, this does not lead to finite-state winning strategies, but when the knowledge of agents remains bounded, we can solve the synthesis problem. Our study is carried out in a setting where objectives are expressed in terms of events that may \emph{not} be observable. This is natural in games of imperfect information, rather than the common assumption that objectives are expressed in terms of events that are observable to all agents. We characterise decidable distributed synthesis problems in terms of finiteness of knowledge states and finite congruence classes induced by them.
Online Influence Maximization in Non-Stationary Social Networks
Venue: arXiv cs.SI 2016
Year: 2016

Social networks have been popular platforms for information propagation. An important use case is viral marketing: given a promotion budget, an advertiser can choose some influential users as the seed set and provide them free or discounted sample products; in this way, the advertiser hopes to increase the popularity of the product in the users' friend circles by the world-of-mouth effect, and thus maximizes the number of users that information of the production can reach. There has been a body of literature studying the influence maximization problem. Nevertheless, the existing studies mostly investigate the problem on a one-off basis, assuming fixed known influence probabilities among users, or the knowledge of the exact social network topology. In practice, the social network topology and the influence probabilities are typically unknown to the advertiser, which can be varying over time, i.e., in cases of newly established, strengthened or weakened social ties. In this paper, we focus on a dynamic non-stationary social network and design a randomized algorithm, RSB, based on multi-armed bandit optimization, to maximize influence propagation over time. The algorithm produces a sequence of online decisions and calibrates its explore-exploit strategy utilizing outcomes of previous decisions. It is rigorously proven to achieve an upper-bounded regret in reward and applicable to large-scale social networks. Practical effectiveness of the algorithm is evaluated using both synthetic and real-world datasets, which demonstrates that our algorithm outperforms previous stationary methods under non-stationary conditions.
Smart Multihoming in Smart Shires: Mobility and Communication Management for Smart Services in Countrysides
Venue: arXiv cs.NI 2016
Year: 2016

This paper discusses on the need to focus on effective and cheap communication solutions for the deployment of smart services in countrysides. We present the main wireless technologies, software architectures and protocols that need to be exploited, such as multihop, multipath communication and mobility support through multihoming. We present Always Best Packet Switching (ABPS), an operation mode to perform network handover in a seamless way without the need to change the current network infrastructure and configuration. This is in accordance with the need of having cheap solutions that may work in a smart shire scenario. A simulation assessment confirms the effectiveness of our approach.
An Enhanced Deep Feature Representation for Person Re-identification
Venue: arXiv cs.CV 2016
Year: 2016

Feature representation and metric learning are two critical components in person re-identification models. In this paper, we focus on the feature representation and claim that hand-crafted histogram features can be complementary to Convolutional Neural Network (CNN) features. We propose a novel feature extraction model called Feature Fusion Net (FFN) for pedestrian image representation. In FFN, back propagation makes CNN features constrained by the handcrafted features. Utilizing color histogram features (RGB, HSV, YCbCr, Lab and YIQ) and texture features (multi-scale and multi-orientation Gabor features), we get a new deep feature representation that is more discriminative and compact. Experiments on three challenging datasets (VIPeR, CUHK01, PRID450s) validates the effectiveness of our proposal.
High-Level System Design of IEEE 802.11b Standard-Compliant Link Layer for MATLAB-Based SDR
Venue: arXiv cs.NI 2016
Year: 2016

Software defined radio (SDR) allows unprecedented levels of flexibility by transitioning the radio communication system from a rigid hardware platform to a more user-controlled software paradigm. However, it can still be time consuming to design and implement such SDRs as they typically require thorough knowledge of the operating environment and a careful tuning of the program. In this work, our contribution is the design of a bidirectional transceiver that runs on the commonly used USRP platform and implemented in MATLAB using standard tools like MATLAB Coder and MEX to speed up the processing steps. We outline strategies on how to create a state-action based design, wherein the same node switches between transmitter and receiver functions. Our design allows optimal selection of the parameters towards meeting the timing requirements set forth by various processing blocks associated with a DBPSK physical layer and CSMA/CA/ACK MAC layer so that all operations remain functionally compliant with the IEEE 802.11b standard for the 1 Mbps specification. The code base of the system is enabled through the Communications System Toolbox and incorporates channel sensing and exponential random back-off for contention resolution. The current work provides an experimental testbed that enables creation of new MAC protocols starting from the fundamental IEEE 802.11b standard. Our design approach guarantees consistent performance of the bi-directional link, and the three node experimental results demonstrate the robustness of the system in mitigating packet collisions and enforcing fairness among nodes, making it a feasible framework in higher layer protocol design.
Fundamental Green Tradeoffs: Progresses, Challenges, and Impacts on 5G Networks
Venue: arXiv cs.IT 2016
Year: 2016

With years of tremendous traffic and energy consumption growth, green radio has been valued not only for theoretical research interests but also for the operational expenditure reduction and the sustainable development of wireless communications. Fundamental green tradeoffs, served as an important framework for analysis, include four basic relationships: spectrum efficiency (SE) versus energy efficiency (EE), deployment efficiency (DE) versus energy efficiency (EE), delay (DL) versus power (PW), and bandwidth (BW) versus power (PW). In this paper, we first provide a comprehensive overview on the extensive on-going research efforts and categorize them based on the fundamental green tradeoffs. We will then focus on research progresses of 4G and 5G communications, such as orthogonal frequency division multiplexing (OFDM) and non-orthogonal aggregation (NOA), multiple input multiple output (MIMO), and heterogeneous networks (HetNets). We will also discuss potential challenges and impacts of fundamental green tradeoffs, to shed some light on the energy efficient research and design for future wireless networks.