OpenRaiser/Intern-Atlas huggingface dataset:
Balancing Scalability and Uniformity in SAT Witness Generator
Venue: arXiv cs.LO 2014
Year: 2014

Constrained-random simulation is the predominant approach used in the industry for functional verification of complex digital designs. The effectiveness of this approach depends on two key factors: the quality of constraints used to generate test vectors, and the randomness of solutions generated from a given set of constraints. In this paper, we focus on the second problem, and present an algorithm that significantly improves the state-of-the-art of (almost-)uniform generation of solutions of large Boolean constraints. Our algorithm provides strong theoretical guarantees on the uniformity of generated solutions and scales to problems involving hundreds of thousands of variables.
Capturing and Recognizing Objects Appearance Employing Eigenspace
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a method of capturing objects appearances from its environment and it also describes how to recognize unknown appearances creating an eigenspace. This representation and recognition can be done automatically taking objects various appearances by using robotic vision from a defined environment. This technique also allows extracting objects from some sort of complicated scenes. In this case, some of object appearances are taken with defined occlusions and eigenspaces are created by accepting both of non-occluded and occluded appearances together. Eigenspace is constructed successfully every times when a new object appears, and various appearances accumulated gradually. A sequence of appearances is generated from its accumulated shapes, which is used for recognition of the unknown objects appearances. Various objects environments are shown in the experiment to capture objects appearances and experimental results show effectiveness of the proposed approach.
Distributed Edge Partitioning for Graph Processing
Venue: arXiv cs.DC 2014
Year: 2014

The availability of larger and larger graph datasets, growing exponentially over the years, has created several new algorithmic challenges to be addressed. Sequential approaches have become unfeasible, while interest on parallel and distributed algorithms has greatly increased. Appropriately partitioning the graph as a preprocessing step can improve the degree of parallelism of its analysis. A number of heuristic algorithms have been developed to solve this problem, but many of them subdivide the graph on its vertex set, thus obtaining a vertex-partitioned graph. Aim of this paper is to explore a completely different approach based on edge partitioning, in which edges, rather than vertices, are partitioned into disjoint subsets. Contribution of this paper is twofold: first, we introduce a graph processing framework based on edge partitioning, that is flexible enough to be applied to several different graph problems. Second, we show the feasibility of these ideas by presenting a distributed edge partitioning algorithm called d-fep. Our framework is thoroughly evaluated, using both simulations and an Hadoop implementation running on the Amazon EC2 cloud. The experiments show that d-fep is efficient, scalable and obtains consistently good partitions. The resulting edge-partitioned graph can be exploited to obtain more efficient implementations of graph analysis algorithms.
A Framework for Hybrid Systems with Denial-of-Service Security Attack
Venue: arXiv cs.LO 2014
Year: 2014

Hybrid systems are integrations of discrete computation and continuous physical evolution. The physical components of such systems introduce safety requirements, the achievement of which asks for the correct monitoring and control from the discrete controllers. However, due to denial-of-service security attack, the expected information from the controllers is not received and as a consequence the physical systems may fail to behave as expected. This paper proposes a formal framework for expressing denial-of-service security attack in hybrid systems. As a virtue, a physical system is able to plan for reasonable behavior in case the ideal control fails due to unreliable communication, in such a way that the safety of the system upon denial-of-service is still guaranteed. In the context of the modeling language, we develop an inference system for verifying safety of hybrid systems, without putting any assumptions on how the environments behave. Based on the inference system, we implement an interactive theorem prover and have applied it to check an example taken from train control system.
Evaluating topic coherence measures
Venue: arXiv cs.LG 2014
Year: 2014

Topic models extract representative word sets - called topics - from word counts in documents without requiring any semantic annotations. Topics are not guaranteed to be well interpretable, therefore, coherence measures have been proposed to distinguish between good and bad topics. Studies of topic coherence so far are limited to measures that score pairs of individual words. For the first time, we include coherence measures from scientific philosophy that score pairs of more complex word subsets and apply them to topic scoring.
Transmit Power Minimization for MIMO Systems of Exponential Average BER with Fixed Outage Probability
Venue: arXiv cs.IT 2014
Year: 2014

This paper is concerned with a wireless system operating in MIMO fading channels with channel state information being known at both transmitter and receiver. By spatiotemporal subchannel selection and power control, it aims to minimize the average transmit power (ATP) of the MIMO system while achieving an exponential type of average bit error rate (BER) for each data stream. Under the constraints of a given fixed individual outage probability (OP) and average BER for each subchannel, based on a traditional upper bound and a dynamic upper bound of Q function, two closed-form ATP expressions are derived, respectively, and they correspond to two different power allocation schemes. Numerical results are provided to validate the theoretical analysis, and show that the power allocation scheme with the dynamic upper bound can achieve more power savings than the one with the traditional upper bound.
Lost Again in Shibuya: Exploration and Awareness in a Labyrinth
Venue: arXiv cs.HC 2014
Year: 2014

Existing digital technologies in urban settings tend to focus narrowly on concerns around wayfinding, safety, and consumption. In this paper, we examine pedestrian experiences based on the data collected through field observations as well as intensive interviews with nine pedestrians in the Shibuya area of Tokyo, and suggest an alternative approach to blending technologies and urban activities. Our focus is on social and cognitive aspects of pedestrians who get lost and explore a labyrinth of sidewalks. We use the data to discuss the activities that are often ignored or inadequately supported by existing systems.
ChromaPhy - A Living Wearable Connecting Humans and Their Environment
Venue: arXiv cs.HC 2014
Year: 2014

This research presents an artistic project aiming to make cyberfiction become reality and exemplifying a current trend in art and science collaborations. Chroma+Phy is a speculative design for a living wearable that combines the protoplasmic structure of the amoeboid acellular organism Physarum polycephalum and the chromatophores of the reptile Chameleon. The underpin-ning idea is that in a future far away or close, on planet earth or in outer space, humans will need some tools to help them in their social life and day-to-day routine. Chroma+Phy enhances the body aiming at humans in extreme habitats for an aggression-free and healthy life. Our approach will address actual issues of scientific discovery for society and catalyse idea translation through art and design experiments at frontiers of science.
Online Learning of k-CNF Boolean Functions
Venue: arXiv cs.LG 2014
Year: 2014

This paper revisits the problem of learning a k-CNF Boolean function from examples in the context of online learning under the logarithmic loss. In doing so, we give a Bayesian interpretation to one of Valiant's celebrated PAC learning algorithms, which we then build upon to derive two efficient, online, probabilistic, supervised learning algorithms for predicting the output of an unknown k-CNF Boolean function. We analyze the loss of our methods, and show that the cumulative log-loss can be upper bounded, ignoring logarithmic factors, by a polynomial function of the size of each example.
A modified ziggurat algorithm for generating exponentially- and normally-distributed pseudorandom numbers
Venue: arXiv cs.MS 2014
Year: 2014

The Ziggurat Algorithm is a very fast rejection sampling method for generating PseudoRandom Numbers (PRNs) from common statistical distributions. The algorithm divides a distribution into rectangular layers that stack on top of each other (resembling a Ziggurat), subsuming the desired distribution. Random values within these rectangular layers are then sampled by rejection. This implementation splits layers into two types: those constituting the majority that fall completely under the distribution and can be sampled extremely fast without a rejection test, and a few additional layers that encapsulate the fringe of the distribution and require a rejection test. This method offers speedups of 65% for exponentially- and 82% for normally-distributed PRNs when compared to the best available C implementations of these generators. Even greater speedups are obtained when the algorithm is extended to the Python and MATLAB/OCTAVE programming environments.
Automatic Segmentation of Broadcast News Audio using Self Similarity Matrix
Venue: arXiv cs.SD 2014
Year: 2014

Generally audio news broadcast on radio is com- posed of music, commercials, news from correspondents and recorded statements in addition to the actual news read by the newsreader. When news transcripts are available, automatic segmentation of audio news broadcast to time align the audio with the text transcription to build frugal speech corpora is essential. We address the problem of identifying segmentation in the audio news broadcast corresponding to the news read by the newsreader so that they can be mapped to the text transcripts. The existing techniques produce sub-optimal solutions when used to extract newsreader read segments. In this paper, we propose a new technique which is able to identify the acoustic change points reliably using an acoustic Self Similarity Matrix (SSM). We describe the two pass technique in detail and verify its performance on real audio news broadcast of All India Radio for different languages.
A Comparative Study of Load Balancing Algorithms in Cloud Computing Environment
Venue: arXiv cs.DC 2014
Year: 2014

Cloud Computing is a new trend emerging in IT environment with huge requirements of infrastructure and resources. Load Balancing is an important aspect of cloud computing environment. Efficient load balancing scheme ensures efficient resource utilization by provisioning of resources to cloud users on demand basis in pay as you say manner. Load Balancing may even support prioritizing users by applying appropriate scheduling criteria. This paper presents various load balancing schemes in different cloud environment based on requirements specified in Service Level Agreement (SLA).
The NUbots Team Description Paper 2014
Venue: arXiv cs.RO 2014
Year: 2014

The NUbots team, from The University of Newcastle, Australia, has had a strong record of success in the RoboCup Standard Platform League since first entering in 2002. The team has also competed within the RoboCup Humanoid Kid-Size League since 2012. The 2014 team brings a renewed focus on software architecture, modularity, and the ability to easily share code. This paper summarizes the history of the NUbots team, describes the roles and research of the team members, gives an overview of the NUbots' robots and software system, and addresses relevant research projects within the the Newcastle Robotics Laboratory.
Applications Oriented Input Design in Time-Domain Through Cyclic Methods
Venue: arXiv cs.SY 2014
Year: 2014

In this paper we propose a method for applications oriented input design for linear systems under time-domain constraints on the amplitude of input and output signals. The method guarantees a desired control performance for the estimated model in minimum time, by imposing some lower bound on the information matrix. The problem is formulated as a time domain optimization problem, which is non-convex. This is addressed through an alternating method, where we separate the problem into two steps and at each step we optimize the cost function with respect to one of two variables. We alternate between these two steps until convergence. A time recursive input design algorithm is performed, which enables us to use the algorithm with control. Therefore, a receding horizon framework is used to solve each optimization problem. Finally, we illustrate the method with two numerical examples which show the good ability of the proposed approach in generating an optimal input signal.
Hierarchical Coded Caching
Venue: arXiv cs.IT 2014
Year: 2014

Caching of popular content during off-peak hours is a strategy to reduce network loads during peak hours. Recent work has shown significant benefits of designing such caching strategies not only to deliver part of the content locally, but also to provide coded multicasting opportunities even among users with different demands. Exploiting both of these gains was shown to be approximately optimal for caching systems with a single layer of caches. Motivated by practical scenarios, we consider in this work a hierarchical content delivery network with two layers of caches. We propose a new caching scheme that combines two basic approaches. The first approach provides coded multicasting opportunities within each layer; the second approach provides coded multicasting opportunities across multiple layers. By striking the right balance between these two approaches, we show that the proposed scheme achieves the optimal communication rates to within a constant multiplicative and additive gap. We further show that there is no tension between the rates in each of the two layers up to the aforementioned gap. Thus, both layers can simultaneously operate at approximately the minimum rate.
The Sketching Complexity of Graph Cuts
Venue: arXiv cs.DS 2014
Year: 2014

We study the problem of sketching an input graph, so that given the sketch, one can estimate the weight of any cut in the graph within factor $1+ε$. We present lower and upper bounds on the size of a randomized sketch, focusing on the dependence on the accuracy parameter $ε>0$. First, we prove that for every $ε> 1/\sqrt n$, every sketch that succeeds (with constant probability) in estimating the weight of all cuts $(S,\bar S)$ in an $n$-vertex graph (simultaneously), must be of size $Ω(n/ε^2)$ bits. In the special case where the sketch is itself a weighted graph (which may or may not be a subgraph) and the estimator is the sum of edge weights across the cut in the sketch, i.e., a cut sparsifier, we show the sketch must have $Ω(n/ε^2)$ edges, which is optimal. Despite the long sequence of work on graph sparsification, no such lower bound was known on the size of a cut sparsifier. We then design a randomized sketch that, given $ε\in(0,1)$ and an edge-weighted $n$-vertex graph, produces a sketch of size $\tilde O(n/ε)$ bits, from which the weight of any cut $(S,\bar S)$ can be reported, with high probability, within factor $1+ε$. The previous upper bound is $\tilde O(n/ε^2)$ bits, which follows by storing a cut sparsifier (Bencz{ú}r and Karger, 1996). To obtain this improvement, we critically use both that the sketch need only be correct on each fixed cut with high probability (rather than on all cuts), and that the estimation procedure of the data structure can be arbitrary (rather than a weighted subgraph). We also show a lower bound of $Ω(n/ε)$ bits for the space requirement of any data structure achieving this guarantee.
Offshore Wind Farm Layout Optimization Using Adapted Genetic Algorithm: A different perspective
Venue: arXiv cs.NE 2014
Year: 2014

In this paper we study the problem of optimal layout of an offshore wind farm to minimize the wake effect impacts. Considering the specific requirements of concerned offshore wind farm, we propose an adaptive genetic algorithm (AGA) which introduces location swaps to replace random crossovers in conventional GAs. That way the total number of turbines in the resulting layout will be effectively kept to the initially specified value. We experiment the proposed AGA method on three cases with free wind speed of 12 m/s, 20 m/s, and a typical offshore wind distribution setting respectively. Numerical results verify the effectiveness of our proposed algorithm which achieves a much faster convergence compared to conventional GA algorithms.
Network Weirdness: Exploring the Origins of Network Paradoxes
Venue: arXiv cs.SI 2014
Year: 2014

Social networks have many counter-intuitive properties, including the "friendship paradox" that states, on average, your friends have more friends than you do. Recently, a variety of other paradoxes were demonstrated in online social networks. This paper explores the origins of these network paradoxes. Specifically, we ask whether they arise from mathematical properties of the networks or whether they have a behavioral origin. We show that sampling from heavy-tailed distributions always gives rise to a paradox in the mean, but not the median. We propose a strong form of network paradoxes, based on utilizing the median, and validate it empirically using data from two online social networks. Specifically, we show that for any user the majority of user's friends and followers have more friends, followers, etc. than the user, and that this cannot be explained by statistical properties of sampling. Next, we explore the behavioral origins of the paradoxes by using the shuffle test to remove correlations between node degrees and attributes. We find that paradoxes for the mean persist in the shuffled network, but not for the median. We demonstrate that strong paradoxes arise due to the assortativity of user attributes, including degree, and correlation between degree and attribute.
Verifying Web Applications: From Business Level Specifications to Automated Model-Based Testing
Venue: arXiv cs.SE 2014
Year: 2014

One of reasons preventing a wider uptake of model-based testing in the industry is the difficulty which is encountered by developers when trying to think in terms of properties rather than linear specifications. A disparity has traditionally been perceived between the language spoken by customers who specify the system and the language required to construct models of that system. The dynamic nature of the specifications for commercial systems further aggravates this problem in that models would need to be rechecked after every specification change. In this paper, we propose an approach for converting specifications written in the commonly-used quasi-natural language Gherkin into models for use with a model-based testing tool. We have instantiated this approach using QuickCheck and demonstrate its applicability via a case study on the eHealth system, the national health portal for Maltese residents.
Coverage Criteria for Model-Based Testing using Property Patterns
Venue: arXiv cs.SE 2014
Year: 2014

We present in this paper a model-based testing approach aiming at generating test cases from a UML/OCL model and a given test property. The property is expressed using a dedicated formalism based on patterns, and automatically translated into an automaton. We propose new automata coverage criteria that are tailored to the property automata we consider. These criteria are based on the coverage of a relevant subset of the transitions related to the original property, aiming at producing test cases that illustrate the dynamics of the system described in the property. In addition, we propose to produce test cases that can ensure the robustness of the system w.r.t. the property, by mutating the property automaton, in order to try to provoke events that would be forbidden by the property. This approach has been implemented into a large tool set and it has been experimented on realistic case studies, in the context of industrial research projects.
Countermeasures against Bernstein's remote cache timing attack
Venue: arXiv cs.CR 2014
Year: 2014

Cache timing attack is a type of side channel attack where the leaking timing information due to the cache behaviour of a crypto system is used by an attacker to break the system. Advanced Encryption Standard (AES) was considered a secure encryption standard until 2005 when Daniel Bernstein claimed that the software implementation of AES is vulnerable to cache timing attack. Bernstein demonstrated a remote cache timing attack on a software implementation of AES. The original AES implementation can methodically be altered to prevent the cache timing attack by hiding the natural cache-timing pattern during the encryption while preserving its semantics. The alternations while preventing the attack should not make the implementation very slow. In this paper, we report outcomes of our experiments on designing and implementing a number of possible countermeasures.
Exploiting Delay Correlation for Multi-Antenna-Assisted High Speed Train Communications
Venue: arXiv cs.IT 2014
Year: 2014

In High Speed Train Communications (HSTC), the most challenging issue is coping with the extremely fast fading channel. Compared with its static counterpart, channel estimation on the move consumes excessive energy and spectrum to achieve similar performance. To address this issue, we exploit the delay correlation inherent in the linear spatial-temporal structure of multi-antenna array, based on which the rapid fading channel may be approximated by a virtual slow-fading channel. Subsequently, error probability and spectral efficiency are re-examined for this staticized channel. In particular, we formulate the quantitative tradeoff between the two metrics of interest, by adjusting the pilot percentage in each frame. Numerical results verify the good performance of the proposed scheme and elucidate the tradeoff.
DValue for Boolean games is EXP-complete
Venue: arXiv cs.GT 2014
Year: 2014

We show that the following problem is EXP-complete: given a rational v and a two player, zero-sum Boolean game G determine whether the value of G is at least v. The proof is via a translation of the proof of the same result for Boolean circuit games in Feigenbaum et al. (1995).
Approximate Decentralized Bayesian Inference
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents an approximate method for performing Bayesian inference in models with conditional independence over a decentralized network of learning agents. The method first employs variational inference on each individual learning agent to generate a local approximate posterior, the agents transmit their local posteriors to other agents in the network, and finally each agent combines its set of received local posteriors. The key insight in this work is that, for many Bayesian models, approximate inference schemes destroy symmetry and dependencies in the model that are crucial to the correct application of Bayes' rule when combining the local posteriors. The proposed method addresses this issue by including an additional optimization step in the combination procedure that accounts for these broken dependencies. Experiments on synthetic and real data demonstrate that the decentralized method provides advantages in computational performance and predictive test likelihood over previous batch and distributed methods.