OpenRaiser/Intern-Atlas huggingface dataset:
Radix-2 Fast Hartley Transform Revisited
Venue: arXiv cs.DM 2015
Year: 2015

A Fast algorithm for the Discrete Hartley Transform (DHT) is presented, which resembles radix-2 fast Fourier Transform (FFT). Although fast DHTs are already known, this new approach bring some light about the deep relationship between fast DHT algorithms and a multiplication-free fast algorithm for the Hadamard Transform.
Satisfiability of Ordering CSPs Above Average
Venue: arXiv cs.DS 2015
Year: 2015

We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity $k$ is fixed-parameter tractable for every $k$. Previously, this was only known for $k=2$ and $k=3$. We also generalize this result to more general classes of CSPs, including CSPs with predicates defined by linear inequalities. To obtain our results, we prove a new Bonami-type inequality for the Efron-Stein decomposition. The inequality applies to functions defined on arbitrary product probability spaces. In contrast to other variants of the Bonami Inequality, it does not depend on the mass of the smallest atom in the probability space. We believe that this inequality is of independent interest.
Detection of Cyberbullying Incidents on the Instagram Social Network
Venue: arXiv cs.SI 2015
Year: 2015

Cyberbullying is a growing problem affecting more than half of all American teens. The main goal of this paper is to investigate fundamentally new approaches to understand and automatically detect incidents of cyberbullying over images in Instagram, a media-based mobile social network. To this end, we have collected a sample Instagram data set consisting of images and their associated comments, and designed a labeling study for cyberbullying as well as image content using human labelers at the crowd-sourced Crowdflower Web site. An analysis of the labeled data is then presented, including a study of correlations between different features and cyberbullying as well as cyberaggression. Using the labeled data, we further design and evaluate the accuracy of a classifier to automatically detect incidents of cyberbullying.
RAPTOR: Routing Attacks on Privacy in Tor
Venue: arXiv cs.NI 2015
Year: 2015

The Tor network is a widely used system for anonymous communication. However, Tor is known to be vulnerable to attackers who can observe traffic at both ends of the communication path. In this paper, we show that prior attacks are just the tip of the iceberg. We present a suite of new attacks, called Raptor, that can be launched by Autonomous Systems (ASes) to compromise user anonymity. First, AS-level adversaries can exploit the asymmetric nature of Internet routing to increase the chance of observing at least one direction of user traffic at both ends of the communication. Second, AS-level adversaries can exploit natural churn in Internet routing to lie on the BGP paths for more users over time. Third, strategic adversaries can manipulate Internet routing via BGP hijacks (to discover the users using specific Tor guard nodes) and interceptions (to perform traffic analysis). We demonstrate the feasibility of Raptor attacks by analyzing historical BGP data and Traceroute data as well as performing real-world attacks on the live Tor network, while ensuring that we do not harm real users. In addition, we outline the design of two monitoring frameworks to counter these attacks: BGP monitoring to detect control-plane attacks, and Traceroute monitoring to detect data-plane anomalies. Overall, our work motivates the design of anonymity systems that are aware of the dynamics of Internet routing.
Knowledge-based Query Expansion in Real-Time Microblog Search
Venue: arXiv cs.IR 2015
Year: 2015

Since the length of microblog texts, such as tweets, is strictly limited to 140 characters, traditional Information Retrieval techniques suffer from the vocabulary mismatch problem severely and cannot yield good performance in the context of microblogosphere. To address this critical challenge, in this paper, we propose a new language modeling approach for microblog retrieval by inferring various types of context information. In particular, we expand the query using knowledge terms derived from Freebase so that the expanded one can better reflect users' search intent. Besides, in order to further satisfy users' real-time information need, we incorporate temporal evidences into the expansion method, which can boost recent tweets in the retrieval results with respect to a given topic. Experimental results on two official TREC Twitter corpora demonstrate the significant superiority of our approach over baseline methods.
Dominance and Deficiency for Petri Nets and Chemical Reaction Networks
Venue: arXiv cs.DC 2015
Year: 2015

Inspired by Anderson et al. [J. R. Soc. Interface, 2014] we study the long-term behavior of discrete chemical reaction networks (CRNs). In particular, using techniques from both Petri net theory and CRN theory, we provide a powerful sufficient condition for a structurally-bounded CRN to have the property that none of the non-terminal reactions can fire for all its recurrent configurations. We compare this result and its proof with a related result of Anderson et al. and show its consequences for the case of CRNs with deficiency one.
On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
Venue: arXiv cs.FL 2015
Year: 2015

Does the trace language of a given vector addition system (VAS) intersect with a given context-free language? This question lies at the heart of several verification questions involving recursive programs with integer parameters. In particular, it is equivalent to the coverability problem for VAS that operate on a pushdown stack. We show decidability in dimension one, based on an analysis of a new model called grammar-controlled vector addition systems.
Bounding linear head reduction and visible interaction through skeletons
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we study the complexity of execution in higher-order programming languages. Our study has two facets: on the one hand we give an upper bound to the length of interactions between bounded P-visible strategies in Hyland-Ong game semantics. This result covers models of programming languages with access to computational effects like non-determinism, state or control operators, but its semantic formulation causes a loose connection to syntax. On the other hand we give a syntactic counterpart of our semantic study: a non-elementary upper bound to the length of the linear head reduction sequence (a low-level notion of reduction, close to the actual implementation of the reduction of higher-order programs by abstract machines) of simply-typed lambda-terms. In both cases our upper bounds are proved optimal by giving matching lower bounds. These two results, although different in scope, are proved using the same method: we introduce a simple reduction on finite trees of natural numbers, hereby called interaction skeletons. We study this reduction and give upper bounds to its complexity. We then apply this study by giving two simulation results: a semantic one measuring progress in game-theoretic interaction via interaction skeletons, and a syntactic one establishing a correspondence between linear head reduction of terms satisfying a locality condition called local scope and the reduction of interaction skeletons. This result is then generalized to arbitrary terms by a local scopization transformation.
GreenDelivery: Proactive Content Caching and Push with Energy-Harvesting-based Small Cells
Venue: arXiv cs.IT 2015
Year: 2015

The explosive growth of mobile multimedia traffic calls for scalable wireless access with high quality of service and low energy cost. Motivated by the emerging energy harvesting communications, and the trend of caching multimedia contents at the access edge and user terminals, we propose a paradigm-shift framework, namely GreenDelivery, enabling efficient content delivery with energy harvesting based small cells. To resolve the two-dimensional randomness of energy harvesting and content request arrivals, proactive caching and push are jointly optimized, with respect to the content popularity distribution and battery states. We thus develop a novel way of understanding the interplay between content and energy over time and space. Case studies are provided to show the substantial reduction of macro BS activities, and thus the related energy consumption from the power grid is reduced. Research issues of the proposed GreenDelivery framework are also discussed.
Outage Minimization for a Fading Wireless Link with Energy Harvesting Transmitter and Receiver
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies online power control policies for outage minimization in a fading wireless link with energy harvesting transmitter and receiver. The outage occurs when either the transmitter or the receiver does not have enough energy, or the channel is in outage, where the transmitter only has the channel distribution information. Under infinite battery capacity and without retransmission, we prove that threshold-based power control policies are optimal. We thus propose disjoint/joint threshold-based policies with and without battery state sharing between the transmitter and receiver, respectively. We also analyze the impact of practical receiver detection and processing on the outage performance. When retransmission is considered, policy with linear power levels is adopted to adapt the power thresholds per retransmission. With finite battery capacity, a three dimensional finite state Markov chain is formulated to calculate the optimal parameters and corresponding performance of proposed policies. The energy arrival correlation between the transmitter and receiver is addressed for both finite and infinite battery cases. Numerical results show the impact of battery capacity, energy arrival correlation and detection cost on the outage performance of the proposed policies, as well as the tradeoff between the outage probability and the average transmission times.
Using models to model-check recursive schemes
Venue: arXiv cs.LO 2015
Year: 2015

We propose a model-based approach to the model checking problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose the use of a model of lambda-Y-calculus to discriminate the terms that satisfy a given property. If a model is finite in every type, this gives a decision procedure. We provide a construction of such a model for every property expressed by automata with trivial acceptance conditions and divergence testing. Such properties pose already interesting challenges for model construction. Moreover, we argue that having models capturing some class of properties has several other virtues in addition to providing decidability of the model-checking problem. As an illustration, we show a very simple construction transforming a scheme to a scheme reflecting a property captured by a given model.
Optimization of Switch Keyboards
Venue: arXiv cs.HC 2015
Year: 2015

Patients with motor control difficulties often "type" on a computer using a switch keyboard to guide a scanning cursor to text elements. We show how to optimize some parts of the design of switch keyboards by casting the design problem as mixed integer programming. A new algorithm to find an optimized design solution is approximately 3600 times faster than a previous algorithm, which was also susceptible to finding a non-optimal solution. The optimization requires a model of the probability of an entry error, and we show how to build such a model from experimental data. Example optimized keyboards are demonstrated.
Making Availability as a Service in the Clouds
Venue: arXiv cs.DC 2015
Year: 2015

Cloud computing has achieved great success in modern IT industry as an excellent computing paradigm due to its flexible management and elastic resource sharing. To date, cloud computing takes an irrepalceable position in our socioeconomic system and influences almost every aspect of our daily life. However, it is still in its infancy, many problems still exist.Besides the hotly-debated security problem, availability is also an urgent issue.With the limited power of availability mechanisms provided in present cloud platform, we can hardly get detailed availability information of current applications such as the root causes of availability problem,mean time to failure, etc. Thus a new mechanism based on deep avaliability analysis is neccessary and benificial.Following the prevalent terminology 'XaaS',this paper proposes a new win-win concept for cloud users and providers in term of 'Availability as a Service' (abbreviated as 'AaaS').The aim of 'AaaS' is to provide comprehensive and aimspecific runtime avaliabilty analysis services for cloud users by integrating plent of data-driven and modeldriven approaches. To illustrate this concept, we realize a prototype named 'EagleEye' with all features of 'AaaS'. By subscribing corresponding services in 'EagleEye', cloud users could get specific availability information of their applications deployed in cloud platform. We envision this new kind of service will be merged into the cloud management mechanism in the near future.
Simulation of Genetic Algorithm: Traffic Light Efficiency
Venue: arXiv cs.NE 2015
Year: 2015

Traffic is a problem in many urban areas worldwide. Traffic flow is dictated by certain devices such as traffic lights. The traffic lights signal when each lane is able to pass through the intersection. Often, static schedules interfere with ideal traffic flow. The purpose of this project was to find a way to make intersections controlled with traffic lights more efficient. This goal was accomplished through the creation of a genetic algorithm, which enhances an input algorithm through genetic principles to produce the fittest algorithm. The program was comprised of two major elements: coding in Java and coding in Simulation of Urban Mobility (SUMO), which is an environment that simulates real traffic. The Java code called upon the SUMO simulation via a command prompt which ran the simulation, received the output, altered the algorithm, and looped. The SUMO component initialized a simulation in which a 1 x 1 street layout was created, each intersection with its own traffic light. Each loop enhanced the input algorithm by altering the scheduling string (dictates the light changes). After the looped simulations were executed, the data was then analyzed. This was accomplished by creating an algorithm based upon regular practice, timed traffic lights, and comparing the output which was comprised of the total time it took for all vehicles to exit the system and the average time it took each individual vehicle to exit the system. These different variables: the time it took the average vehicle to exit the system and total time for all vehicles to exit the system, where then graphed together to provide a visual aid. The genetic algorithm did improve traffic light and traffic flow efficiency in comparison to traditional scheduling methods.
The complexity of computing the minimum rank of a sign pattern matrix
Venue: arXiv cs.CC 2015
Year: 2015

We show that computing the minimum rank of a sign pattern matrix is NP hard. Our proof is based on a simple but useful connection between minimum ranks of sign pattern matrices and the stretchability problem for pseudolines arrangements. In fact, our hardness result shows that it is already hard to determine if the minimum rank of a sign pattern matrix is $\leq 3$. We complement this by giving a polynomial time algorithm for determining if a given sign pattern matrix has minimum rank $\leq 2$. Our result answers one of the open problems from Linial et al. [Combinatorica, 27(4):439--463, 2007].
The Least-core and Nucleolus of Path Cooperative Games
Venue: arXiv cs.GT 2015
Year: 2015

Cooperative games provide an appropriate framework for fair and stable profit distribution in multiagent systems. In this paper, we study the algorithmic issues on path cooperative games that arise from the situations where some commodity flows through a network. In these games, a coalition of edges or vertices is successful if it enables a path from the source to the sink in the network, and lose otherwise. Based on dual theory of linear programming and the relationship with flow games, we provide the characterizations on the CS-core, least-core and nucleolus of path cooperative games. Furthermore, we show that the least-core and nucleolus are polynomially solvable for path cooperative games defined on both directed and undirected network.
Autonomic Resource Management in Virtual Networks
Venue: arXiv cs.NI 2015
Year: 2015

Virtualization enables the building of multiple virtual networks over a shared substrate. One of the challenges to virtualisation is efficient resource allocation. This problem has been found to be NP hard. Therefore, most approaches to it have not only proposed static solutions, but have also made many assumptions to simplify it. In this paper, we propose a distributed, autonomic and artificial intelligence based solution to resource allocation. Our aim is to obtain self-configuring, selfoptimizing, self-healing and context aware virtual networks
Comparing Distance Bounding Protocols: a Critical Mission Supported by Decision Theory
Venue: arXiv cs.CR 2015
Year: 2015

Distance bounding protocols are security countermeasures designed to thwart relay attacks. Such attacks consist in relaying messages exchanged between two parties, making them believe they communicate directly with each other. Although distance bounding protocols have existed since the early nineties, this research topic resurrected with the deployment of contactless systems, against which relay attacks are particularly impactful. Given the impressive number of distance bounding protocols that are designed every year, it becomes urgent to provide researchers and engineers with a methodology to fairly compare the protocols in spite of their various properties. This paper introduces such a methodology based on concepts from the decision making field. The methodology allows for a multi-criteria comparison of distance bounding protocols, thereby identifying the most appropriate protocols once the context is provided. As a side effect, this paper clearly identifies the protocols that should no longer be considered, regardless of the considered scenario.
Enhanced Image Classification With a Fast-Learning Shallow Convolutional Neural Network
Venue: arXiv cs.NE 2015
Year: 2015

We present a neural network architecture and training method designed to enable very rapid training and low implementation complexity. Due to its training speed and very few tunable parameters, the method has strong potential for applications requiring frequent retraining or online training. The approach is characterized by (a) convolutional filters based on biologically inspired visual processing filters, (b) randomly-valued classifier-stage input weights, (c) use of least squares regression to train the classifier output weights in a single batch, and (d) linear classifier-stage output units. We demonstrate the efficacy of the method by applying it to image classification. Our results match existing state-of-the-art results on the MNIST (0.37% error) and NORB-small (2.2% error) image classification databases, but with very fast training times compared to standard deep network approaches. The network's performance on the Google Street View House Number (SVHN) (4% error) database is also competitive with state-of-the art methods.
PiMPeR: Piecewise Dense 3D Reconstruction from Multi-View and Multi-Illumination Images
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we address the problem of dense 3D reconstruction from multiple view images subject to strong lighting variations. In this regard, a new piecewise framework is proposed to explicitly take into account the change of illumination across several wide-baseline images. Unlike multi-view stereo and multi-view photometric stereo methods, this pipeline deals with wide-baseline images that are uncalibrated, in terms of both camera parameters and lighting conditions. Such a scenario is meant to avoid use of any specific imaging setup and provide a tool for normal users without any expertise. To the best of our knowledge, this paper presents the first work that deals with such unconstrained setting. We propose a coarse-to-fine approach, in which a coarse mesh is first created using a set of geometric constraints and, then, fine details are recovered by exploiting photometric properties of the scene. Augmenting the fine details on the coarse mesh is done via a final optimization step. Note that the method does not provide a generic solution for multi-view photometric stereo problem but it relaxes several common assumptions of this problem. The approach scales very well in size given its piecewise nature, dealing with large scale optimization and with severe missing data. Experiments on a benchmark dataset Robot data-set show the method performance against 3D ground truth.
Using Twitter to Predict Sales: A Case Study
Venue: arXiv cs.SI 2015
Year: 2015

This paper studies the relation between activity on Twitter and sales. While research exists into the relation between Tweets and movie and book sales, this paper shows that the same relations do not hold for products that receive less attention on social media. For such products, classification of Tweets is far more important to determine a relation. Also, for such products advanced statistical relations, in addition to correlation, are required to relate Twitter activity and sales. In a case study that involves Tweets and sales from a company in four countries, the paper shows how, by classifying Tweets, such relations can be identified. In particular, the paper shows evidence that positive Tweets by persons (as opposed to companies) can be used to forecast sales and that peaks in positive Tweets by persons are strongly related to an increase in sales. These results can be used to improve sales forecasts and to increase sales in marketing campaigns.
Logic BIST: State-of-the-Art and Open Problems
Venue: arXiv cs.AR 2015
Year: 2015

Many believe that in-field hardware faults are too rare in practice to justify the need for Logic Built-In Self-Test (LBIST) in a design. Until now, LBIST was primarily used in safety-critical applications. However, this may change soon. First, even if costly methods like burn-in are applied, it is no longer possible to get rid of all latent defects in devices at leading-edge technology. Second, demands for high reliability spread to consumer electronics as smartphones replace our wallets and IDs. However, today many ASIC vendors are reluctant to use LBIST. In this paper, we describe the needs for successful deployment of LBIST in the industrial practice and discuss how these needs can be addressed. Our work is hoped to attract a wider attention to this important research topic.
A Memcomputing Pascaline
Venue: arXiv cs.ET 2015
Year: 2015

The original Pascaline was a mechanical calculator able to sum and subtract integers. It encodes information in the angles of mechanical wheels and through a set of gears, and aided by gravity, could perform the calculations. Here, we show that such a concept can be realized in electronics using memory elements such as memristive systems. By using memristive emulators we have demonstrated experimentally the memcomputing version of the mechanical Pascaline, capable of processing and storing the numerical results in the multiple levels of each memristive element. Our result is the first experimental demonstration of multidigit arithmetics with multi-level memory devices that further emphasizes the versatility and potential of memristive systems for future massively-parallel high-density computing architectures.