OpenRaiser/Intern-Atlas huggingface dataset:
Information Flow Control in WebKit's JavaScript Bytecode
Venue: arXiv cs.CR 2014
Year: 2014

Websites today routinely combine JavaScript from multiple sources, both trusted and untrusted. Hence, JavaScript security is of paramount importance. A specific interesting problem is information flow control (IFC) for JavaScript. In this paper, we develop, formalize and implement a dynamic IFC mechanism for the JavaScript engine of a production Web browser (specifically, Safari's WebKit engine). Our IFC mechanism works at the level of JavaScript bytecode and hence leverages years of industrial effort on optimizing both the source to bytecode compiler and the bytecode interpreter. We track both explicit and implicit flows and observe only moderate overhead. Working with bytecode results in new challenges including the extensive use of unstructured control flow in bytecode (which complicates lowering of program context taints), unstructured exceptions (which complicate the matter further) and the need to make IFC analysis permissive. We explain how we address these challenges, formally model the JavaScript bytecode semantics and our instrumentation, prove the standard property of termination-insensitive non-interference, and present experimental results on an optimized prototype.
Avoiding Serialization Effects in Data-Dependency aware Task Parallel Algorithms for Spatial Decomposition
Venue: arXiv cs.DC 2014
Year: 2014

Spatial decomposition is a popular basis for parallelising code. Cast in the frame of task parallelism, calculations on a spatial domain can be treated as a task. If neighbouring domains interact and share results, access to the specific data needs to be synchronized to avoid race conditions. This is the case for a variety of applications, like most molecular dynamics and many computational fluid dynamics codes. Here we present an unexpected problem which can occur in dependency-driven task parallelization models like StarSs: the tasks accessing a specific spatial domain are treated as interdependent, as dependencies are detected automatically via memory addresses. Thus, the order in which tasks are generated will have a severe impact on the dependency tree. In the worst case, a complete serialization is reached and no two tasks can be calculated in parallel. We present the problem in detail based on an example from molecular dynamics, and introduce a theoretical framework to calculate the degree of serialization. Furthermore, we present strategies to avoid this unnecessary problem. We recommend treating these strategies as best practice when using dependency-driven task parallel programming models like StarSs on such scenarios.
Solving reviewer assignment problem in software peer review: An approach based on preference matrix and asymmetric TSP model
Venue: arXiv cs.DL 2014
Year: 2014

Optimized reviewer assignment can effectively utilize limited intellectual resources and significantly assure review quality in various scenarios such as paper selection in conference or journal, proposal selection in funding agencies and so on. However, little research on reviewer assignment of software peer review has been found. In this study, an optimization approach is proposed based on students' preference matrix and the model of asymmetric traveling salesman problem (ATSP). Due to the most critical role of rule matrix in this approach, we conduct a questionnaire to obtain students' preference matrices and convert them to rule matrices. With the help of software ILOG CPLEX, the approach is accomplished by controlling the exit criterion of ATSP model. The comparative study shows that the assignment strategies with both reviewers' preference matrix and authors' preference matrix get better performance than the random assignment. Especially, it is found that the performance is just a little better than that of random assignment when the reviewers' and authors' preference matrices are merged. In other words, the majority of students have a strong wish of harmonious development even though high-level students are not willing to do that.
Government and Social Media: A Case Study of 31 Informational World Cities
Venue: arXiv cs.CY 2014
Year: 2014

Social media platforms are increasingly being used by governments to foster user interaction. Particularly in cities with enhanced ICT infrastructures (i.e., Informational World Cities) and high internet penetration rates, social media platforms are valuable tools for reaching high numbers of citizens. This empirical investigation of 31 Informational World Cities will provide an overview of social media services used for governmental purposes, of their popularity among governments, and of their usage intensity in broadcasting information online.
SAS+ Planning as Satisfiability
Venue: arXiv cs.AI 2014
Year: 2014

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.
Reformulating the Situation Calculus and the Event Calculus in the General Theory of Stable Models and in Answer Set Programming
Venue: arXiv cs.AI 2014
Year: 2014

Circumscription and logic programs under the stable model semantics are two well-known nonmonotonic formalisms. The former has served as a basis of classical logic based action formalisms, such as the situation calculus, the event calculus and temporal action logics; the latter has served as a basis of a family of action languages, such as language A and several of its descendants. Based on the discovery that circumscription and the stable model semantics coincide on a class of canonical formulas, we reformulate the situation calculus and the event calculus in the general theory of stable models. We also present a translation that turns the reformulations further into answer set programs, so that efficient answer set solvers can be applied to compute the situation calculus and the event calculus.
Computing All-Pairs Shortest Paths by Leveraging Low Treewidth
Venue: arXiv cs.DS 2014
Year: 2014

We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w_d) time, where w_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w_d^2 + n^2 s_d) on general graphs, where s_d andlt= w_d is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshalls as well as Johnsons algorithm, which represent the current state of the art with a run time of O(n^3) and O(nm + n^2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.
Local Consistency and SAT-Solvers
Venue: arXiv cs.AI 2014
Year: 2014

Local consistency techniques such as k-consistency are a key component of specialised solvers for constraint satisfaction problems. In this paper we show that the power of using k-consistency techniques on a constraint satisfaction problem is precisely captured by using a particular inference rule, which we call negative-hyper-resolution, on the standard direct encoding of the problem into Boolean clauses. We also show that current clause-learning SAT-solvers will discover in expected polynomial time any inconsistency that can be deduced from a given set of clauses using negative-hyper-resolvents of a fixed size. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all fixed values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of constraint problems which are challenging for conventional constraint-programming solvers.
The Capacity of String-Replication Systems
Venue: arXiv cs.IT 2014
Year: 2014

It is known that the majority of the human genome consists of repeated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from repeated sequences and has mutated to its current form. In this paper, we investigate the possibility of constructing an exponentially large number of sequences from a short initial sequence and simple replication rules, including those resembling genomic replication processes. In other words, our goal is to find out the capacity, or the expressive power, of these string-replication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-replication systems.
The Energy/Frequency Convexity Rule: Modeling and Experimental Validation on Mobile Devices
Venue: arXiv cs.OH 2014
Year: 2014

This paper provides both theoretical and experimental evidence for the existence of an Energy/Frequency Convexity Rule, which relates energy consumption and CPU frequency on mobile devices. We monitored a typical smartphone running a specific computing-intensive kernel of multiple nested loops written in C using a high-resolution power gauge. Data gathered during a week-long acquisition campaign suggest that energy consumed per input element is strongly correlated with CPU frequency, and, more interestingly, the curve exhibits a clear minimum over a 0.2 GHz to 1.6 GHz window. We provide and motivate an analytical model for this behavior, which fits well with the data. Our work should be of clear interest to researchers focusing on energy usage and minimization for mobile devices, and provide new insights for optimization opportunities.
A Three-Dimensional Voting System in Hong Kong
Venue: arXiv cs.GT 2014
Year: 2014

The voting system in the Legislative Council of Hong Kong (Legco) is sometimes unicameral and sometimes bicameral, depending on whether the bill is proposed by the Hong Kong government. Therefore, although without any representative within Legco, the Hong Kong government has certain degree of legislative power --- as if there is a virtual representative of the Hong Kong government within the Legco. By introducing such a virtual representative of the Hong Kong government, we show that Legco is a three-dimensional voting system. We also calculate two power indices of the Hong Kong government through this virtual representative and consider the $C$-dimension and the $W$-dimension of Legco. Finally, some implications of this Legco model to the current constitutional reform in Hong Kong will be given.
Termination of oblivious chase is undecidable
Venue: arXiv cs.DB 2014
Year: 2014

We show that all--instances termination of chase is undecidable. More precisely, there is no algorithm deciding, for a given set $\cal T$ consisting of Tuple Generating Dependencies (a.k.a. Datalog$^\exists$ program), whether the $\cal T$-chase on $D$ will terminate for every finite database instance $D$. Our method applies to Oblivious Chase, Semi-Oblivious Chase and -- after a slight modification -- also for Standard Chase. This means that we give a (negative) solution to the all--instances termination problem for all version of chase that are usually considered. The arity we need for our undecidability proof is three. We also show that the problem is EXPSPACE-hard for binary signatures, but decidability for this case is left open. Both the proofs -- for ternary and binary signatures -- are easy. Once you know them.
The critical factors affecting E-Government adoption: A Conceptual Framework in Vietnam
Venue: arXiv cs.CY 2014
Year: 2014

Electronic government (e-government) has established as an effective mechanism for increasing government productivity and efficiency and a key enabler of citizen- centric services. However, e-government implementation is surrounded by technological, governing and social issues, which have to be considered and treated carefully in order to facilitate this change. This research attempts to explore and investigate the key challenges that influence e-government implementation and the factors influencing citizen adoption in Vietnam. It develops a conceptual framework on the basis of existing experiences drawn from administrative reforms. Survey data from public employee will be used to test the proposed hypothesis and the model. Therefore, this research has identified factors that determine if the citizen will adopt E-government services and thereby aiding governments in accessing what is required to increase adoption. We will also highlight several research, practitioner and policy implications.
The existential fragment of S1S over element and successor is the co-Buchi languages
Venue: arXiv cs.FL 2014
Year: 2014

Buchi's theorem, in establishing the equivalence between languages definable in S1S over element and < and the omega-regular languages also demonstrated that S1S over element and < is no more expressive than its existential fragment. It is also easy to see that S1S over element and < is equi-expressive with S1S over element and successor. However, it is not immediately obvious whether it is possible to adapt Buchi's argument to establish equivalence between expressivity in S1S over element and successor and its existential fragment. In this paper we show that it is not: the existential fragment of S1S over element and successor is strictly less expressive, and is in fact equivalent to the co-Buchi languages.
Low-Complexity Robust Data-Adaptive Dimensionality Reduction Based on Joint Iterative Optimization of Parameters
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents a low-complexity robust data-dependent dimensionality reduction based on a modified joint iterative optimization (MJIO) algorithm for reduced-rank beamforming and steering vector estimation. The proposed robust optimization procedure jointly adjusts the parameters of a rank-reduction matrix and an adaptive beamformer. The optimized rank-reduction matrix projects the received signal vector onto a subspace with lower dimension. The beamformer/steering vector optimization is then performed in a reduced-dimension subspace. We devise efficient stochastic gradient and recursive least-squares algorithms for implementing the proposed robust MJIO design. The proposed robust MJIO beamforming algorithms result in a faster convergence speed and an improved performance. Simulation results show that the proposed MJIO algorithms outperform some existing full-rank and reduced-rank algorithms with a comparable complexity.
MRRR-based Eigensolvers for Multi-core Processors and Supercomputers
Venue: arXiv cs.MS 2014
Year: 2014

The real symmetric tridiagonal eigenproblem is of outstanding importance in numerical computations; it arises frequently as part of eigensolvers for standard and generalized dense Hermitian eigenproblems that are based on a reduction to tridiagonal form. For its solution, the algorithm of Multiple Relatively Robust Representations (MRRR or MR3 in short) - introduced in the late 1990s - is among the fastest methods. To compute k eigenpairs of a real n-by-n tridiagonal T, MRRR only requires O(kn) arithmetic operations; in contrast, all the other practical methods require O(k^2 n) or O(n^3) operations in the worst case. This thesis centers around the performance and accuracy of MRRR.
Stability Analysis and Design of a Network of Event-based Systems
Venue: arXiv cs.SY 2014
Year: 2014

We consider a network of event-based systems that use a shared wireless medium to communicate with their respective controllers. These systems use a contention resolution mechanism to arbitrate access to the shared network. We identify sufficient conditions for Lyapunov mean square stability of each control system in the network, and design event-based policies that guarantee it. Our stability analysis is based on a Markov model that removes the network-induced correlation between the states of the control systems in the network. Analyzing the stability of this Markov model remains a challenge, as the event-triggering policy renders the estimation error non-Gaussian. Hence, we identify an auxiliary system that furnishes an upper bound for the variance of the system states. Using the stability analysis, we design policies, such as the constant-probability policy, for adapting the event-triggering thresholds to the delay in accessing the network. Realistic wireless networked control examples illustrate the applicability of the presented approach.
Análisis e implementación de algoritmos evolutivos para la optimización de simulaciones en ingeniería civil. (draft)
Venue: arXiv cs.NE 2014
Year: 2014

This paper studies the applicability of evolutionary algorithms, particularly, the evolution strategies family in order to estimate a degradation parameter in the shear design of reinforced concrete members. This problem represents a great computational task and is highly relevant in the framework of the structural engineering that for the first time is solved using genetic algorithms. You are viewing a draft, the authors appreciate corrections, comments and suggestions to this work.
Over-constrained Weierstrass iteration and the nearest consistent system
Venue: arXiv cs.SC 2014
Year: 2014

We propose a generalization of the Weierstrass iteration for over-constrained systems of equations and we prove that the proposed method is the Gauss-Newton iteration to find the nearest system which has at least $k$ common roots and which is obtained via a perturbation of prescribed structure. In the univariate case we show the connection of our method to the optimization problem formulated by Karmarkar and Lakshman for the nearest GCD. In the multivariate case we generalize the expressions of Karmarkar and Lakshman, and give explicitly several iteration functions to compute the optimum. The arithmetic complexity of the iterations is detailed.
Distributed call-by-value machines
Venue: arXiv cs.PL 2014
Year: 2014

We present a new abstract machine, called DCESH, which describes the execution of higher-order programs running in distributed architectures. DCESH implements a generalised form of Remote Procedure Call that supports calling higher-order functions across node boundaries, without sending actual code. Our starting point is a variant of the SECD machine that we call the CES machine, which implements reduction for untyped call-by-value PCF. We successively add the features that we need for distributed execution and show the correctness of each addition. First we add heaps, forming the CESH machine, which provides features necessary for more efficient execution, and show that there is a bisimulation between the CES and the CESH machine. Then we construct a two-level operational semantics, where the high level is a network of communicating machines, and the low level is given by local machine transitions. Using these networks, we arrive at our final system, the distributed CESH machine (DCESH). We show that there is a bisimulation relation also between the CESH machine and the DCESH machine. All the technical results have been formalised and proved correct in Agda, and a prototype compiler has been developed.
A Stable Fountain Code Mechanism for Peer-to-Peer Content Distribution
Venue: arXiv cs.NI 2014
Year: 2014

Most peer-to-peer content distribution systems require the peers to privilege the welfare of the overall system over greedily maximizing their own utility. When downloading a file broken up into multiple pieces, peers are often asked to pass on some possible download opportunities of common pieces in order to favor rare pieces. This is to avoid the missing piece syndrome, which throttles the download rate of the peer-to-peer system to that of downloading the file straight from the server. In other situations, peers are asked to stay in the system even though they have collected all the file's pieces and have an incentive to leave right away. We propose a mechanism which allows peers to act greedily and yet stabilizes the peer-to-peer content sharing system. Our mechanism combines a fountain code at the server to generate innovative new pieces, and a prioritization for the server to deliver pieces only to new peers. While by itself, neither the fountain code nor the prioritization of new peers alone stabilizes the system, we demonstrate that their combination does, through both analytical and numerical evaluation.
Harmony Search Algorithm for Curriculum-Based Course Timetabling Problem
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, harmony search algorithm is applied to curriculum-based course timetabling. The implementation, specifically the process of improvisation consists of memory consideration, random consideration and pitch adjustment. In memory consideration, the value of the course number for new solution was selected from all other course number located in the same column of the Harmony Memory. This research used the highest occurrence of the course number to be scheduled in a new harmony. The remaining courses that have not been scheduled by memory consideration will go through random consideration, i.e. will select any feasible location available to be scheduled in the new harmony solution. Each course scheduled out of memory consideration is examined as to whether it should be pitch adjusted with probability of eight procedures. However, the algorithm produced results that were not comparatively better than those previously known as best solution. With proper modification in terms of the approach in this algorithm would make the algorithm perform better on curriculum-based course timetabling.
Skill Analysis with Time Series Image Data
Venue: arXiv cs.AI 2014
Year: 2014

We present a skill analysis with time series image data using data mining methods, focused on table tennis. We do not use body model, but use only hi-speed movies, from which time series data are obtained and analyzed using data mining methods such as C4.5 and so on. We identify internal models for technical skills as evaluation skillfulness for the forehand stroke of table tennis, and discuss mono and meta-functional skills for improving skills.