OpenRaiser/Intern-Atlas huggingface dataset:
Better Optimism By Bayes: Adaptive Planning with Rich Models
Venue: arXiv cs.AI 2014
Year: 2014

The computational costs of inference and planning have confined Bayesian model-based reinforcement learning to one of two dismal fates: powerful Bayes-adaptive planning but only for simplistic models, or powerful, Bayesian non-parametric models but using simple, myopic planning strategies such as Thompson sampling. We ask whether it is feasible and truly beneficial to combine rich probabilistic models with a closer approximation to fully Bayesian planning. First, we use a collection of counterexamples to show formal problems with the over-optimism inherent in Thompson sampling. Then we leverage state-of-the-art techniques in efficient Bayes-adaptive planning and non-parametric Bayesian methods to perform qualitatively better than both existing conventional algorithms and Thompson sampling on two contextual bandit-like problems.
Generating Logical Specifications from Requirements Models for Deduction-based Formal Verification
Venue: arXiv cs.SE 2014
Year: 2014

The work concerns automatic generation of logical specifications from requirements models. Logical specifications obtained in such a way can be subjected to formal verification using deductive reasoning. Formal verification concerns correctness of a model behaviour. Reliability of the requirements engineering is essential for all phases of software development processes. Deductive reasoning is an important alternative among other formal methods. However, logical specifications, considered as sets of temporal logic formulas, are difficult to specify manually by inexperienced users and this fact can be regarded as a significant obstacle to practical use of deduction-based verification tools. A method of building requirements models using some UML diagrams, including their logical specifications, is presented step by step. Organizing activity diagrams into predefined workflow patterns enables automated extraction of logical specifications. The crucial aspect of the presented approach is integrating the requirements engineering phase and the automatic generation of logical specifications. A system of the deduction-based verification is proposed. The reasoning process could be based on the semantic tableaux method. A simple yet illustrative example of the requirements elicitation and verification is provided.
A New Approach to Reporting Archaeological Surveys: Connecting Rough Cilicia, Visible Past and Open Context through loose coupling and 3d codes
Venue: arXiv cs.DL 2014
Year: 2014

The project presents the strategy adopted by the Rough Cilicia Archaeological Survey team for publishing its primary data and reports via three potentially transformative strategies for digital humanities: Loose coupling of digital data curation and publishing platforms. In loosely coupled systems, components share only a limited set of simple assumptions, which enables systems to evolve dynamically. Collaborative creation of map based narrative content. Connecting print scholarship (book, reports, article) to online resources via two-dimensional barcodes (2D codes) that can be printed on paper and can call up hyperlinks when scanned with a Smartphone. The three strategies are made possible by loosely coupling two autonomous services: Visible Past, dedicated to web collaboration and digital-print publishing and Open Context, which is a geo-historical data archiving and publishing service. The Rough Cilicia Archaeological Survey, Visible Past, and Open Context work together to illustrate a new genre of scholarship, which combine qualitative narratives and quantitative representations of space and social phenomena. The project provides tools for collaborative creation of rich scholarly narratives that are spatially located and for connecting print publications to the digital realm. The project is a case study for utilizing the three new strategies for creating and publishing spatial humanities scholarship more broadly for ancient historians.
Leveraging Long-Term Predictions and Online-Learning in Agent-based Multiple Person Tracking
Venue: arXiv cs.CV 2014
Year: 2014

We present a multiple-person tracking algorithm, based on combining particle filters and RVO, an agent-based crowd model that infers collision-free velocities so as to predict pedestrian's motion. In addition to position and velocity, our tracking algorithm can estimate the internal goals (desired destination or desired velocity) of the tracked pedestrian in an online manner, thus removing the need to specify this information beforehand. Furthermore, we leverage the longer-term predictions of RVO by deriving a higher-order particle filter, which aggregates multiple predictions from different prior time steps. This yields a tracker that can recover from short-term occlusions and spurious noise in the appearance model. Experimental results show that our tracking algorithm is suitable for predicting pedestrians' behaviors online without needing scene priors or hand-annotated goal information, and improves tracking in real-world crowded scenes under low frame rates.
Freedom From Restriction, Freedom Of A Restriction: A Comparison Of Some Open Source Software Licenses
Venue: arXiv cs.CY 2014
Year: 2014

There is a multitude of licenses out there for a software developer to choose from, but a lot of programmers would prefer to not have to have a legal degree in order to understand them and would rather just have their code out in the public being used. This paper examines a few of the more popular and common software licenses available and compares their conditions from the perspective that a developer wanted to scratch their proverbial itch, have their code be used and maybe even get credit for it. This paper attempts to clarify which license a developer would benefit from the most if they just want to have their code used, have their name out there and not be sued if anything breaks.
We Are Impatient: Algorithms for Geographically Distributed Load Balancing with (Almost) Arbitrary Load Functions
Venue: arXiv cs.DC 2014
Year: 2014

In geographically-distributed systems, communication latencies are non-negligible. The perceived processing time of a request is thus composed of the time needed to route the request to the server and the true processing time. Once a request reaches a target server, the processing time depends on the total load of that server; this dependency is described by a load function. We consider a broad class of load functions; we just require that they are convex and two times differentiable. In particular our model can be applied to heterogeneous systems in which every server has a different load function. This approach allows us not only to generalize results for queuing theory and for batches of requests, but also to use empirically-derived load functions, measured in a system under stress-testing. The optimal assignment of requests to servers is communication-balanced, i.e. for any pair of non perfectly-balanced servers, the reduction of processing time resulting from moving a single request from the overloaded to underloaded server is smaller than the additional communication latency. We present a centralized and a decentralized algorithm for optimal load balancing. We prove bounds on the algorithms' convergence. To the best of our knowledge these bounds were not known even for the special cases studied previously (queuing theory and batches of requests). Both algorithms are any-time algorithms. In the decentralized algorithm, each server balances the load with a randomly chosen peer. Such algorithm is very robust to failures. We prove that the decentralized algorithm performs locally-optimal steps. Our work extends the currently known results by considering a broad class of load functions and by establishing theoretical bounds on the algorithms' convergence. These results are applicable for servers whose characteristics under load cannot be described by a standard mathematical models.
Deciding Entailments in Inductive Separation Logic with Tree Automata
Venue: arXiv cs.LO 2014
Year: 2014

Separation Logic (SL) with inductive definitions is a natural formalism for specifying complex recursive data structures, used in compositional verification of programs manipulating such structures. The key ingredient of any automated verification procedure based on SL is the decidability of the entailment problem. In this work, we reduce the entailment problem for a non-trivial subset of SL describing trees (and beyond) to the language inclusion of tree automata (TA). Our reduction provides tight complexity bounds for the problem and shows that entailment in our fragment is EXPTIME-complete. For practical purposes, we leverage from recent advances in automata theory, such as inclusion checking for non-deterministic TA avoiding explicit determinization. We implemented our method and present promising preliminary experimental results.
Characterizing the Sample Complexity of Private Learners
Venue: arXiv cs.CR 2014
Year: 2014

In 2008, Kasiviswanathan et al. defined private learning as a combination of PAC learning and differential privacy. Informally, a private learner is applied to a collection of labeled individual information and outputs a hypothesis while preserving the privacy of each individual. Kasiviswanathan et al. gave a generic construction of private learners for (finite) concept classes, with sample complexity logarithmic in the size of the concept class. This sample complexity is higher than what is needed for non-private learners, hence leaving open the possibility that the sample complexity of private learning may be sometimes significantly higher than that of non-private learning. We give a combinatorial characterization of the sample size sufficient and necessary to privately learn a class of concepts. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure RepDim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies RepDim(C)=O(m), and that there exists a private learning algorithm with sample complexity m=O(RepDim(C)). We further demonstrate that a similar characterization holds for the database size needed for privately computing a large class of optimization problems and also for the well studied problem of private data release.
Design of an Amplifier through Second Generation Current Conveyor
Venue: arXiv cs.ET 2014
Year: 2014

This paper describes the architecture of first and second generation current conveyor (CCI and CCII respectively) and designing an amplifier using second generation current conveyor. The designed amplifier through CCII+ can be used in various analog computation circuits and is superior in performance than the classical opamp. It provides better gain with higher accuracy.
Significance of Coupling and Cohesion on Design Quality
Venue: arXiv cs.SE 2014
Year: 2014

In recent years, the complexity of the software is increasing due to automation of every segment of application. Software is nowhere remained as one-time development product since its architectural dimension is increasing with addition of new requirements over a short duration. Object Oriented Development (OOD) methodology is a popular development approach for such systems which perceives and models the requirements as real world entities. Classes and Objects logically represent the entities in the solution space and quality of the software is directly depending on the design quality of these logical entities. Cohesion and Coupling (C&C) are two major design decisive factors in OOD which impacts the design of a class and dependency between them in complex software. It is also most significant to measure C&C for software to control the complexity level as requirements increases. Several metrics are in practice to quantify C&C which plays a major role in measuring the design quality. The software industries are focusing on increasing and measuring the quality of the product through quality design to continue their market image in the competitive world. As a part of our research, this paper highlights on the impact of C&C on design quality of a complex system and its measures to quantify the overall quality of software.
Prediction of Human Performance Capability during Software Development using Classification
Venue: arXiv cs.SE 2014
Year: 2014

The quality of human capital is crucial for software companies to maintain competitive advantages in knowledge economy era. Software companies recognize superior talent as a business advantage. They increasingly recognize the critical linkage between effective talent and business success. However, software companies suffering from high turnover rates often find it hard to recruit the right talents. There is an urgent need to develop a personnel selection mechanism to find the talents who are the most suitable for their software projects. Data mining techniques assures exploring the information from the historical projects depending on which the project manager can make decisions for producing high quality software. This study aims to fill the gap by developing a data mining framework based on decision tree and association rules to refocus on criteria for personnel selection. An empirical study was conducted in a software company to support their hiring decision for project members. The results demonstrated that there is a need to refocus on selection criteria for quality objectives. Better selection criteria was identified by patterns obtained from data mining models by integrating knowledge from software project database and authors research techniques.
Validation Experiments for LBM Simulations of Electron Beam Melting
Venue: arXiv cs.CE 2014
Year: 2014

This paper validates 3D simulation results of electron beam melting (EBM) processes comparing experimental and numerical data. The physical setup is presented which is discretized by a three dimensional (3D) thermal lattice Boltzmann method (LBM). An experimental process window is used for the validation depending on the line energy injected into the metal powder bed and the scan velocity of the electron beam. In the process window the EBM products are classified into the categories, porous, good and swelling, depending on the quality of the surface. The same parameter sets are used to generate a numerical process window. A comparison of numerical and experimental process windows shows a good agreement. This validates the EBM model and justifies simulations for future improvements of EBM processes. In particular numerical simulations can be used to explain future process window scenarios and find the best parameter set for a good surface quality and dense products.
Network flow-based simultaneous retiming and slack budgeting for low power design
Venue: arXiv cs.AR 2014
Year: 2014

Low power design has become one of the most significant requirements when CMOS technology entered the nanometer era. Therefore, timing budget is often performed to slow down as many components as possible so that timing slacks can be applied to reduce the power consumption while maintaining the performance of the whole design. Retiming is a procedure that involves the relocation of flip-flops (FFs) across logic gates to achieve faster clocking speed. In this paper we show that the retiming and slack budgeting problem can be formulated to a convex cost dual network flow problem. Both the theoretical analysis and experimental results show the efficiency of our approach which can not only reduce power consumption by 8.9%, but also speedup previous work by 500 times.
Materialized View Replacement using Markovs Analysis
Venue: arXiv cs.DB 2014
Year: 2014

Materialized view is used in large data centric applications to expedite query processing. The efficiency of materialized view depends on degree of result found against the queries over the existing materialized views. Materialized views are constructed following different methodologies. Thus the efficacy of the materialized views depends on the methodology based on which these are formed. Construction of materialized views are often time consuming and moreover after a certain time the performance of the materialized views degrade when the nature of queries change. In this situation either new materialized views could be constructed from scratch or the existing views could be upgraded. Fresh construction of materialized views has higher time complexity hence the modification of the existing views is a better solution.Modification process of materialized view is classified under materialized view maintenance scheme. Materialized view maintenance is a continuous process and the system could be tuned to ensure a constant rate of performance. If a materialized view construction process is not supported by materialized view maintenance scheme that system would suffer from performance degradation. In this paper a new materialized view maintenance scheme is proposed using markovs analysis to ensure consistent performance. Markovs analysis is chosen here to predict steady state probability over initial probability.
Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction
Venue: arXiv cs.DC 2014
Year: 2014

Motivated by applications to sensor networks, as well as to many other areas, this paper studies the construction of minimum-degree spanning trees. We consider the classical node-register state model, with a weakly fair scheduler, and we present a space-optimal \emph{silent} self-stabilizing construction of minimum-degree spanning trees in this model. Computing a spanning tree with minimum degree is NP-hard. Therefore, we actually focus on constructing a spanning tree whose degree is within one from the optimal. Our algorithm uses registers on $O(\log n)$ bits, converges in a polynomial number of rounds, and performs polynomial-time computation at each node. Specifically, the algorithm constructs and stabilizes on a special class of spanning trees, with degree at most $OPT+1$. Indeed, we prove that, unless NP $=$ coNP, there are no proof-labeling schemes involving polynomial-time computation at each node for the whole family of spanning trees with degree at most $OPT+1$. Up to our knowledge, this is the first example of the design of a compact silent self-stabilizing algorithm constructing, and stabilizing on a subset of optimal solutions to a natural problem for which there are no time-efficient proof-labeling schemes. On our way to design our algorithm, we establish a set of independent results that may have interest on their own. In particular, we describe a new space-optimal silent self-stabilizing spanning tree construction, stabilizing on \emph{any} spanning tree, in $O(n)$ rounds, and using just \emph{one} additional bit compared to the size of the labels used to certify trees. We also design a silent loop-free self-stabilizing algorithm for transforming a tree into another tree. Last but not least, we provide a silent self-stabilizing algorithm for computing and certifying the labels of a NCA-labeling scheme.
Local Approximability of Minimum Dominating Set on Planar Graphs
Venue: arXiv cs.DC 2014
Year: 2014

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-ε)$-approximation of a minimum dominating set on planar graphs, for any positive constant $ε$. In prior work, the best lower bound on the approximation ratio has been $5-ε$; there is also an upper bound of $52$.
Modeling European Options
Venue: arXiv cs.CE 2014
Year: 2014

Option contracts can be valued by using the Black-Scholes equation, a partial differential equation with initial conditions. An exact solution for European style options is known. The computation time and the error need to be minimized simultaneously. In this paper, the authors have solved the Black-Scholes equation by employing a reasonably accurate implicit method. Options with known analytic solutions have been evaluated. Furthermore, an overall second order accurate space and time discretization has been accomplished in this paper.
Coordinated Output Regulation of Heterogeneous Linear Systems under Switching Topologies
Venue: arXiv cs.SY 2014
Year: 2014

This paper constructs a framework to describe and study the coordinated output regulation problem for multiple heterogeneous linear systems. Each agent is modeled as a general linear multiple-input multiple-output system with an autonomous exosystem which represents the individual offset from the group reference for the agent. The multi-agent system as a whole has a group exogenous state which represents the tracking reference for the whole group. Under the constraints that the group exogenous output is only locally available to each agent and that the agents have only access to their neighbors' information, we propose observer-based feedback controllers to solve the coordinated output regulation problem using output feedback information. A high-gain approach is used and the information interactions are allowed to be switched over a finite set of fixed networks containing both graphs that have a directed spanning tree and graphs that do not. The fundamental relationship between the information interactions, the dwell time, the non-identical dynamics of different agents, and the high-gain parameters is given. Simulations are shown to validate the theoretical results.
Quality-aware Approach for Engineering Self-adaptive Software Systems
Venue: arXiv cs.SE 2014
Year: 2014

Self-adaptivity allows software systems to autonomously adjust their behavior during run-time to reduce the cost complexities caused by manual maintenance. In this paper, an approach for building an external adaptation engine for self-adaptive software systems is proposed. In order to improve the quality of self-adaptive software systems, this research addresses two challenges in self-adaptive software systems. The first challenge is managing the complexity of the adaptation space efficiently and the second is handling the run-time uncertainty that hinders the adaptation process. This research utilizes Case-based Reasoning as an adaptation engine along with utility functions for realizing the managed system's requirements and handling uncertainty.
Methodology for standard cell compliance and detailed placement for triple patterning lithography
Venue: arXiv cs.AR 2014
Year: 2014

As the feature size of semiconductor process further scales to sub-16nm technology node, triple patterning lithography (TPL) has been regarded one of the most promising lithography candidates. M1 and contact layers, which are usually deployed within standard cells, are most critical and complex parts for modern digital designs. Traditional design flow that ignores TPL in early stages may limit the potential to resolve all the TPL conflicts. In this paper, we propose a coherent framework, including standard cell compliance and detailed placement to enable TPL friendly design. Considering TPL constraints during early design stages, such as standard cell compliance, improves the layout decomposability. With the pre-coloring solutions of standard cells, we present a TPL aware detailed placement, where the layout decomposition and placement can be resolved simultaneously. Our experimental results show that, with negligible impact on critical path delay, our framework can resolve the conflicts much more easily, compared with the traditional physical design flow and followed layout decomposition.