OpenRaiser/Intern-Atlas huggingface dataset:
Structure Based Extended Resolution for Constraint Programming
Venue: arXiv cs.AI 2013
Year: 2013

Nogood learning is a powerful approach to reducing search in Constraint Programming (CP) solvers. The current state of the art, called Lazy Clause Generation (LCG), uses resolution to derive nogoods expressing the reasons for each search failure. Such nogoods can prune other parts of the search tree, producing exponential speedups on a wide variety of problems. Nogood learning solvers can be seen as resolution proof systems. The stronger the proof system, the faster it can solve a CP problem. It has recently been shown that the proof system used in LCG is at least as strong as general resolution. However, stronger proof systems such as \emph{extended resolution} exist. Extended resolution allows for literals expressing arbitrary logical concepts over existing variables to be introduced and can allow exponentially smaller proofs than general resolution. The primary problem in using extended resolution is to figure out exactly which literals are useful to introduce. In this paper, we show that we can use the structural information contained in a CP model in order to introduce useful literals, and that this can translate into significant speedups on a range of problems.
Which percentile-based approach should be preferred for calculating normalized citation impact values? An empirical comparison of five approaches including a newly developed citation-rank approach (P100)
Venue: arXiv cs.DL 2013
Year: 2013

Percentile-based approaches have been proposed as a non-parametric alternative to parametric central-tendency statistics to normalize observed citation counts. Percentiles are based on an ordered set of citation counts in a reference set, whereby the fraction of papers at or below the citation counts of a focal paper is used as an indicator for its relative citation impact in the set. In this study, we pursue two related objectives: (1) although different percentile-based approaches have been developed, an approach is hitherto missing that satisfies a number of criteria such as scaling of the percentile ranks from zero (all other papers perform better) to 100 (all other papers perform worse), and solving the problem with tied citation ranks unambiguously. We introduce a new citation-rank approach having these properties, namely P100. (2) We compare the reliability of P100 empirically with other percentile-based approaches, such as the approaches developed by the SCImago group, the Centre for Science and Technology Studies (CWTS), and Thomson Reuters (InCites), using all papers published in 1980 in Thomson Reuters Web of Science (WoS). How accurately can the different approaches predict the long-term citation impact in 2010 (in year 31) using citation impact measured in previous time windows (years 1 to 30)? The comparison of the approaches shows that the method used by InCites overestimates citation impact (because of using the highest percentile rank when papers are assigned to more than a single subject category) whereas the SCImago indicator shows higher power in predicting the long-term citation impact on the basis of citation rates in early years. Since the results show a disadvantage in this predictive ability for P100 against the other approaches, there is still room for further improvements.
Implementing a Wall-In Building Placement in StarCraft with Declarative Programming
Venue: arXiv cs.AI 2013
Year: 2013

In real-time strategy games like StarCraft, skilled players often block the entrance to their base with buildings to prevent the opponent's units from getting inside. This technique, called "walling-in", is a vital part of player's skill set, allowing him to survive early aggression. However, current artificial players (bots) do not possess this skill, due to numerous inconveniences surfacing during its implementation in imperative languages like C++ or Java. In this text, written as a guide for bot programmers, we address the problem of finding an appropriate building placement that would block the entrance to player's base, and present a ready to use declarative solution employing the paradigm of answer set programming (ASP). We also encourage the readers to experiment with different declarative approaches to this problem.
New upper bound on block sensitivity and certificate complexity in terms of sensitivity
Venue: arXiv cs.CC 2013
Year: 2013

Sensitivity \cite{CD82,CDR86} and block sensitivity \cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexity, the "Sensitivity versus Block Sensitivity" question, proposed by Nisan and Szegedy \cite{Nisan94} in 1992, is whether these two complexity measures are polynomially related, i.e., whether $bs(f)=O(s(f)^{O(1)})$. We prove an new upper bound on block sensitivity in terms of sensitivity: $bs(f) \leq 2^{s(f)-1} s(f)$. Previously, the best upper bound on block sensitivity was $bs(f) \leq (\frac{e}{\sqrt{2π}}) e^{s(f)} \sqrt{s(f)}$ by Kenyon and Kutin \cite{KK}. We also prove that if $\min\{s_0(f),s_1(f)\}$ is a constant, then sensitivity and block sensitivity are linearly related, i.e. $bs(f)=O(s(f))$.
Empirical Evaluation of the Parallel Distribution Sweeping Framework on Multicore Architectures
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we perform an empirical evaluation of the Parallel External Memory (PEM) model in the context of geometric problems. In particular, we implement the parallel distribution sweeping framework of Ajwani, Sitchinava and Zeh to solve batched 1-dimensional stabbing max problem. While modern processors consist of sophisticated memory systems (multiple levels of caches, set associativity, TLB, prefetching), we empirically show that algorithms designed in simple models, that focus on minimizing the I/O transfers between shared memory and single level cache, can lead to efficient software on current multicore architectures. Our implementation exhibits significantly fewer accesses to slow DRAM and, therefore, outperforms traditional approaches based on plane sweep and two-way divide and conquer.
Dynamic Code Coverage with Progressive Detail Levels
Venue: arXiv cs.SE 2013
Year: 2013

Nowadays, locating software components responsible for observed failures is one of the most expensive and error-prone tasks in the software development process. To improve the debugging process efficiency, some effort was already made to automatically assist the detection and location of software faults. This led to the creation of statistical debugging tools such as Tarantula, Zoltar and GZoltar. These tools use information gathered from code coverage data and the result of test executions to return a list of potential faulty locations. Although helpful, fault localization tools have some scaling problems because of the fine-grained coverage data they need to perform the fault localization analysis. Instrumentation overhead, which in some cases can be as high as 50% is the main cause for their inefficiency. This thesis proposes a new approach to this problem, avoiding as much as possible the high level of coverage detail, while still using the proven techniques these fault localization tools employ. This approach, named DCC, consists of using a coarser initial instrumentation, obtaining only coverage traces for large components. Then, the instrumentation detail of certain components is progressively increased, based on the intermediate results provided by the same techniques employed in current fault localization tools. To assess the validity of our proposed approach, an empirical evaluation was performed, injecting faults in four real-world software projects. The empirical evaluation demonstrates that the DCC approach reduces the execution overhead that exists in spectrum-based fault localization, and even presents a more concise potential fault ranking to the user. We have observed execution time reductions of 27% on average and diagnostic report size reductions of 63% on average.
Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

Suppose that the collection $\{e_i\}_{i=1}^m$ forms a frame for $\R^k$, where each entry of the vector $e_i$ is a sub-Gaussian random variable. We consider expansions in such a frame, which are then quantized using a Sigma-Delta scheme. We show that an arbitrary signal in $\R^k$ can be recovered from its quantized frame coefficients up to an error which decays root-exponentially in the oversampling rate $m/k$. Here the quantization scheme is assumed to be chosen appropriately depending on the oversampling rate and the quantization alphabet can be coarse. The result holds with high probability on the draw of the frame uniformly for all signals. The crux of the argument is a bound on the extreme singular values of the product of a deterministic matrix and a sub-Gaussian frame. For fine quantization alphabets, we leverage this bound to show polynomial error decay in the context of compressed sensing. Our results extend previous results for structured deterministic frame expansions and Gaussian compressed sensing measurements.
An Advanced Survey on Secure Energy-Efficient Hierarchical Routing Protocols in Wireless Sensor Networks
Venue: arXiv cs.CR 2013
Year: 2013

Wireless Sensor Networks (WSNs) are often deployed in hostile environments, which make such networks highly vulnerable and increase the risk of attacks against this type of network. WSN comprise of large number of sensor nodes with different hardware abilities and functions. Due to the limited memory resources and energy constraints, complex security algorithms cannot be used in sensor networks. Therefore, it is necessary to balance between the security level and the associated energy consumption overhead to mitigate the security risks. Hierarchical routing protocol is more energy-efficient than other routing protocols in WSNs. Many secure cluster-based routing protocols have been proposed in the literature to overcome these constraints. In this paper, we discuss Secure Energy-Efficient Hierarchical Routing Protocols in WSNs and compare them in terms of security, performance and efficiency. Security issues for WSNs and their solutions are also discussed.
Automated Certification of Authorisation Policy Resistance
Venue: arXiv cs.CR 2013
Year: 2013

Attribute-based Access Control (ABAC) extends traditional Access Control by considering an access request as a set of pairs attribute name-value, making it particularly useful in the context of open and distributed systems, where security relevant information can be collected from different sources. However, ABAC enables attribute hiding attacks, allowing an attacker to gain some access by withholding information. In this paper, we first introduce the notion of policy resistance to attribute hiding attacks. We then propose the tool ATRAP (Automatic Term Rewriting for Authorisation Policies), based on the recent formal ABAC language PTaCL, which first automatically searches for resistance counter-examples using Maude, and then automatically searches for an Isabelle proof of resistance. We illustrate our approach with two simple examples of policies and propose an evaluation of ATRAP performances.
Methods of Repairing Virus Infected Files, A TRIZ based Analysis
Venue: arXiv cs.CR 2013
Year: 2013

Most viruses are capable of fixing up the first few bytes and repair the original program because they have to return the control back to the infected program. This fact is used by a heuristic cleaner to clean the infected file. As the virus knows how to repair the it uses the same virus to repair the infected file. There are some infections where parts of the files are damaged by the virus. These types of infections are caused by 'file modifying viruses'. In these cases, the chance of recovery is less, but the anti-virus has to apply various methods with hope. The virus cleaner must know the characteristics of a virus in order to remove that virus. It cannot remove an unknown virus whose methods of infection are not known. If a virus is wrongly detected to be a different virus, then the cleaner will do wrong operations and build a garbage file.
From Principles to Practice with Class in the First Year
Venue: arXiv cs.PL 2013
Year: 2013

We propose a bridge between functional and object-oriented programming in the first-year curriculum. Traditionally, curricula that begin with functional programming transition to a professional, usually object-oriented, language in the second course. This transition poses obstacles for students, and often results in confusing the details of development environments, syntax, and libraries with the fundamentals of OO programming that the course should focus on. Instead, we propose to begin the second course with a sequence of custom teaching languages which minimize the transition from the first course, and allow students to focus on core ideas. After working through the sequence of pedagogical languages, we then transition to Java, at which point students have a strong command of the basic principles. We have 3 years of experience with this course, with notable success.
Galerkin Methods for Complementarity Problems and Variational Inequalities
Venue: arXiv cs.LG 2013
Year: 2013

Complementarity problems and variational inequalities arise in a wide variety of areas, including machine learning, planning, game theory, and physical simulation. In all of these areas, to handle large-scale problem instances, we need fast approximate solution methods. One promising idea is Galerkin approximation, in which we search for the best answer within the span of a given set of basis functions. Bertsekas proposed one possible Galerkin method for variational inequalities. However, this method can exhibit two problems in practice: its approximation error is worse than might be expected based on the ability of the basis to represent the desired solution, and each iteration requires a projection step that is not always easy to implement efficiently. So, in this paper, we present a new Galerkin method with improved behavior: our new error bounds depend directly on the distance from the true solution to the subspace spanned by our basis, and the only projections we require are onto the feasible region or onto the span of our basis.
A generalization of bounds for cyclic codes, including the HT and BS bounds
Venue: arXiv cs.IT 2013
Year: 2013

We use the algebraic structure of cyclic codes and some properties of the discrete Fourier transform to give a reformulation of several classical bounds for the distance of cyclic codes, by extending techniques of linear algebra. We propose a bound, whose computational complexity is polynomial bounded, which is a generalization of the Hartmann-Tzeng bound and the Betti-Sala bound. In the majority of computed cases, our bound is the tightest among all known polynomial-time bounds, including the Roos bound.
A Multi-Engine Approach to Answer Set Programming
Venue: arXiv cs.AI 2013
Year: 2013

Answer Set Programming (ASP) is a truly-declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, that has been recently employed in many applications. The development of efficient ASP systems is, thus, crucial. Having in mind the task of improving the solving methods for ASP, there are two usual ways to reach this goal: $(i)$ extending state-of-the-art techniques and ASP solvers, or $(ii)$ designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the "best" available solver on a per-instance basis. In this paper we pursue this latter direction. We first define a set of cheap-to-compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a {\sl training} set and the solvers' performance on these instances, inductively learn algorithm selection strategies to be applied to a {\sl test} set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the "System Track" of the 3rd ASP Competition. Our analysis shows that, by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve more instances compared with any solver that entered the 3rd ASP Competition. (To appear in Theory and Practice of Logic Programming (TPLP).)
Minimizing Convergence Error in Multi-Agent Systems via Leader Selection: A Supermodular Optimization Approach
Venue: arXiv cs.SY 2013
Year: 2013

In a leader-follower multi-agent system (MAS), the leader agents act as control inputs and influence the states of the remaining follower agents. The rate at which the follower agents converge to their desired states, as well as the errors in the follower agent states prior to convergence, are determined by the choice of leader agents. In this paper, we study leader selection in order to minimize convergence errors experienced by the follower agents, which we define as a norm of the distance between the follower agents' intermediate states and the convex hull of the leader agent states. By introducing a novel connection to random walks on the network graph, we show that the convergence error has an inherent supermodular structure as a function of the leader set. Supermodularity enables development of efficient discrete optimization algorithms that directly approximate the optimal leader set, provide provable performance guarantees, and do not rely on continuous relaxations. We formulate two leader selection problems within the supermodular optimization framework, namely, the problem of selecting a fixed number of leader agents in order to minimize the convergence error, as well as the problem of selecting the minimum-size set of leader agents to achieve a given bound on the convergence error. We introduce algorithms for approximating the optimal solution to both problems in static networks, dynamic networks with known topology distributions, and dynamic networks with unknown and unpredictable topology distributions. Our approach is shown to provide significantly lower convergence errors than existing random and degree-based leader selection methods in a numerical study.
Cloud-Based Augmentation for Mobile Devices: Motivation, Taxonomies, and Open Challenges
Venue: arXiv cs.DC 2013
Year: 2013

Recently, Cloud-based Mobile Augmentation (CMA) approaches have gained remarkable ground from academia and industry. CMA is the state-of-the-art mobile augmentation model that employs resource-rich clouds to increase, enhance, and optimize computing capabilities of mobile devices aiming at execution of resource-intensive mobile applications. Augmented mobile devices envision to perform extensive computations and to store big data beyond their intrinsic capabilities with least footprint and vulnerability. Researchers utilize varied cloud-based computing resources (e.g., distant clouds and nearby mobile nodes) to meet various computing requirements of mobile users. However, employing cloud-based computing resources is not a straightforward panacea. Comprehending critical factors that impact on augmentation process and optimum selection of cloud-based resource types are some challenges that hinder CMA adaptability. This paper comprehensively surveys the mobile augmentation domain and presents taxonomy of CMA approaches. The objectives of this study is to highlight the effects of remote resources on the quality and reliability of augmentation processes and discuss the challenges and opportunities of employing varied cloud-based resources in augmenting mobile devices. We present augmentation definition, motivation, and taxonomy of augmentation types, including traditional and cloud-based. We critically analyze the state-of-the-art CMA approaches and classify them into four groups of distant fixed, proximate fixed, proximate mobile, and hybrid to present a taxonomy. Vital decision making and performance limitation factors that influence on the adoption of CMA approaches are introduced and an exemplary decision making flowchart for future CMA approaches are presented. Impacts of CMA approaches on mobile computing is discussed and open challenges are presented as the future research directions.
Breaking Symmetry with Different Orderings
Venue: arXiv cs.AI 2013
Year: 2013

We can break symmetry by eliminating solutions within each symmetry class. For instance, the Lex-Leader method eliminates all but the smallest solution in the lexicographical ordering. Unfortunately, the Lex-Leader method is intractable in general. We prove that, under modest assumptions, we cannot reduce the worst case complexity of breaking symmetry by using other orderings on solutions. We also prove that a common type of symmetry, where rows and columns in a matrix of decision variables are interchangeable, is intractable to break when we use two promising alternatives to the lexicographical ordering: the Gray code ordering (which uses a different ordering on solutions), and the Snake-Lex ordering (which is a variant of the lexicographical ordering that re-orders the variables). Nevertheless, we show experimentally that using other orderings like the Gray code to break symmetry can be beneficial in practice as they may better align with the objective function and branching heuristic.
The Complexity of Clausal Fragments of LTL
Venue: arXiv cs.LO 2013
Year: 2013

We introduce and investigate a number of fragments of propo- sitional temporal logic LTL over the flow of time (Z, <). The fragments are defined in terms of the available temporal operators and the structure of the clausal normal form of the temporal formulas. We determine the computational complexity of the satisfiability problem for each of the fragments, which ranges from NLogSpace to PTime, NP and PSpace.
Low-Density Parity-Check Codes From Transversal Designs With Improved Stopping Set Distributions
Venue: arXiv cs.IT 2013
Year: 2013

This paper examines the construction of low-density parity-check (LDPC) codes from transversal designs based on sets of mutually orthogonal Latin squares (MOLS). By transferring the concept of configurations in combinatorial designs to the level of Latin squares, we thoroughly investigate the occurrence and avoidance of stopping sets for the arising codes. Stopping sets are known to determine the decoding performance over the binary erasure channel and should be avoided for small sizes. Based on large sets of simple-structured MOLS, we derive powerful constraints for the choice of suitable subsets, leading to improved stopping set distributions for the corresponding codes. We focus on LDPC codes with column weight 4, but the results are also applicable for the construction of codes with higher column weights. Finally, we show that a subclass of the presented codes has quasi-cyclic structure which allows low-complexity encoding.
Cryptocat: Adopting Accessibility and Ease of Use as Security Properties
Venue: arXiv cs.CR 2013
Year: 2013

Cryptocat is a Free and Open Source Software (FL/OSS) browser extension that makes use of web technologies in order to provide easy to use, accessible, encrypted instant messaging to the general public. We aim to investigate how to best leverage the accessibility and portability offered by web technologies in order to allow encrypted instant messaging an opportunity to better permeate on a social level. We have found that encrypted communications, while in many cases technically well-implemented, suffer from a lack of usage due to their being unappealing and inaccessible to the "average end-user". Our position is that accessibility and ease of use must be treated as security properties. Even if a cryptographic system is technically highly qualified, securing user privacy is not achieved without addressing the problem of accessibility. Our goal is to investigate the feasibility of implementing cryptographic systems in highly accessible mediums, and to address the technical and social challenges of making encrypted instant messaging accessible and portable.