OpenRaiser/Intern-Atlas huggingface dataset:
Toward Recovering Complete SRS for Softbody Simulation System and a Sample Application - a Team 4 SOEN6481-W13 Project Report
Venue: arXiv cs.SE 2013
Year: 2013

This document gathers high-level users requirements and describes the system features. It provides a detailed explanation of the main functionalities of the system with a more emphasis on the stakeholders needs and wants. Indeed, the document goes through design constraints that may restrict various aspects of the design and implementation.
Identifying Communities and Key Vertices by Reconstructing Networks from Samples
Venue: arXiv cs.SI 2013
Year: 2013

Sampling techniques such as Respondent-Driven Sampling (RDS) are widely used in epidemiology to sample "hidden" populations, such that properties of the network can be deduced from the sample. We consider how similar techniques can be designed that allow the discovery of the structure, especially the community structure, of networks. Our method involves collecting samples of a network by random walks and reconstructing the network by probabilistically coalescing vertices, using vertex attributes to determine the probabilities. Even though our method can only approximately reconstruct a part of the original network, it can recover its community structure relatively well. Moreover, it can find the key vertices which, when immunized, can effectively reduce the spread of an infection through the original network.
Graph Reconstruction via Distance Oracles
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of reconstructing a hidden graph given access to a distance oracle. We design randomized algorithms for the following problems: reconstruction of a degree bounded graph with query complexity $\tilde{O}(n^{3/2})$; reconstruction of a degree bounded outerplanar graph with query complexity $\tilde{O}(n)$; and near-optimal approximate reconstruction of a general graph.
Robust 1-bit Compressive Sensing via Gradient Support Pursuit
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies a formulation of 1-bit Compressed Sensing (CS) problem based on the maximum likelihood estimation framework. In order to solve the problem we apply the recently proposed Gradient Support Pursuit algorithm, with a minor modification. Assuming the proposed objective function has a Stable Restricted Hessian, the algorithm is shown to accurately solve the 1-bit CS problem. Furthermore, the algorithm is compared to the state-of-the-art 1-bit CS algorithms through numerical simulations. The results suggest that the proposed method is robust to noise and at mid to low input SNR regime it achieves the best reconstruction SNR vs. execution time trade-off.
Technical report- Evaluation methodology in the REVIT project
Venue: arXiv cs.CY 2013
Year: 2013

The purpose of this technical report is to present a methodological approach for evaluating the REVIT (http://revit.cti.gr) educational venture as a whole and assessing the learning effectiveness of the resulting collaborative e-courses.
Designing the W3C Open Annotation Data Model
Venue: arXiv cs.DL 2013
Year: 2013

The Open Annotation Core Data Model specifies an interoperable framework for creating associations between related resources, called annotations, using a methodology that conforms to the Architecture of the World Wide Web. Open Annotations can easily be shared between platforms, with sufficient richness of expression to satisfy complex requirements while remaining simple enough to also allow for the most common use cases, such as attaching a piece of text to a single web resource. This paper presents the W3C Open Annotation Community Group specification and the rationale behind the scoping and technical decisions that were made. It also motivates interoperable Annotations via use cases, and provides a brief analysis of the advantages over previous specifications.
Separating regular languages by piecewise testable and unambiguous languages
Venue: arXiv cs.FL 2013
Year: 2013

Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation problem for regular languages. We give a Ptime algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a $BΣ1(<)$ sentence can witness that the languages are disjoint. The proof refines an algebraic argument from Almeida and the third author. When separation is possible, we also express a separator by saturating one of the original languages by a suitable congruence. Following the same line, we show that one can as well decide whether two regular languages can be separated by an unambiguous language, albeit with a higher complexity.
On the mixed $f$-divergence for multiple pairs of measures
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the concept of the classical $f$-divergence (for a pair of measures) is extended to the mixed $f$-divergence (for multiple pairs of measures). The mixed $f$-divergence provides a way to measure the difference between multiple pairs of (probability) measures. Properties for the mixed $f$-divergence are established, such as permutation invariance and symmetry in distributions. An Alexandrov-Fenchel type inequality and an isoperimetric type inequality for the mixed $f$-divergence will be proved and applications in the theory of convex bodies are given.
Approximation Hardness of Graphic TSP on Cubic Graphs
Venue: arXiv cs.CC 2013
Year: 2013

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used in the paper could be also of independent interest.
The Power and Limitations of Static Binary Search Trees with Lazy Finger
Venue: arXiv cs.DS 2013
Year: 2013

A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed---where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.
Decision Problems for Additive Regular Functions
Venue: arXiv cs.FL 2013
Year: 2013

Additive Cost Register Automata (ACRA) map strings to integers using a finite set of registers that are updated using assignments of the form "x := y + c" at every step. The corresponding class of additive regular functions has multiple equivalent characterizations, appealing closure properties, and a decidable equivalence problem. In this paper, we solve two decision problems for this model. First, we define the register complexity of an additive regular function to be the minimum number of registers that an ACRA needs to compute it. We characterize the register complexity by a necessary and sufficient condition regarding the largest subset of registers whose values can be made far apart from one another. We then use this condition to design a PSPACE algorithm to compute the register complexity of a given ACRA, and establish a matching lower bound. Our results also lead to a machine-independent characterization of the register complexity of additive regular functions. Second, we consider two-player games over ACRAs, where the objective of one of the players is to reach a target set while minimizing the cost. We show the corresponding decision problem to be EXPTIME-complete when costs are non-negative integers, but undecidable when costs are integers.
An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
Venue: arXiv cs.DS 2013
Year: 2013

We design a new LP-based algorithm for the graphic $s$-$t$ path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the idea of narrow cuts due to An, Kleinberg, and Shmoys. It partly answers an open question of Sebő.
Detecting regularities on grammar-compressed strings
Venue: arXiv cs.DS 2013
Year: 2013

We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size $n$ that represents a string $s$ of length $N$, our algorithm compute all runs and squares in $s$ in $O(n^3h)$ time and $O(n^2)$ space, where $h$ is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in $O(n^3h + gnh\log N)$ time and $O(n^2)$ space, where $g$ is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in $O(n^2 h)$ time and $O(nh(n+\log^2 N))$ time, respectively.
Lower bounds on the Münchhausen problem
Venue: arXiv cs.IT 2013
Year: 2013

"The Baron's omni-sequence", B(n), first defined by Khovanova and Lewis (2011), is a sequence that gives for each n the minimum number of weighings on balance scales that can verify the correct labeling of n identically-looking coins with distinct integer weights between 1 gram and n grams. A trivial lower bound on B(n) is log_3(n), and it has been shown that B(n) is log_3(n) + O(log log n). In this paper we give a first nontrivial lower bound to the Münchhausen problem, showing that there is an infinite number of n values for which B(n) does not equal ceil(log_3 n). Furthermore, we show that if N(k) is the number of n values for which k = ceil(log_3 n) and B(n) does not equal k, then N(k) is an unbounded function of k.
Filament and Flare Detection in Hα image sequences
Venue: arXiv cs.CV 2013
Year: 2013

Solar storms can have a major impact on the infrastructure of the earth. Some of the causing events are observable from ground in the Hα spectral line. In this paper we propose a new method for the simultaneous detection of flares and filaments in Hα image sequences. Therefore we perform several preprocessing steps to enhance and normalize the images. Based on the intensity values we segment the image by a variational approach. In a final postprecessing step we derive essential properties to classify the events and further demonstrate the performance by comparing our obtained results to the data annotated by an expert. The information produced by our method can be used for near real-time alerts and the statistical analysis of existing data by solar physicists.
Non Deterministic Logic Programs
Venue: arXiv cs.AI 2013
Year: 2013

Non deterministic applications arise in many domains, including, stochastic optimization, multi-objectives optimization, stochastic planning, contingent stochastic planning, reinforcement learning, reinforcement learning in partially observable Markov decision processes, and conditional planning. We present a logic programming framework called non deterministic logic programs, along with a declarative semantics and fixpoint semantics, to allow representing and reasoning about inherently non deterministic real-world applications. The language of non deterministic logic programs framework is extended with non-monotonic negation, and two alternative semantics are defined: the stable non deterministic model semantics and the well-founded non deterministic model semantics as well as their relationship is studied. These semantics subsume the deterministic stable model semantics and the deterministic well-founded semantics of deterministic normal logic programs, and they reduce to the semantics of deterministic definite logic programs without negation. We show the application of the non deterministic logic programs framework to a conditional planning problem.
Bounded Model Checking of an MITL Fragment for Timed Automata
Venue: arXiv cs.LO 2013
Year: 2013

Timed automata (TAs) are a common formalism for modeling timed systems. Bounded model checking (BMC) is a verification method that searches for runs violating a property using a SAT or SMT solver. MITL is a real-time extension of the linear time logic LTL. Originally, MITL was defined for traces of non-overlapping time intervals rather than the "super-dense" time traces allowing for intervals overlapping in single points that are employed by the nowadays common semantics of timed automata. In this paper we extend the semantics of a fragment of MITL to super-dense time traces and devise a bounded model checking encoding for the fragment. We prove correctness and completeness in the sense that using a sufficiently large bound a counter-example to any given non-holding property can be found. We have implemented the proposed bounded model checking approach and experimentally studied the efficiency and scalability of the implementation.
Lay-up Optimization of Laminated Composites: Mixed Approach with Exact Feasibility Bounds on Lamination Parameters
Venue: arXiv cs.CE 2013
Year: 2013

We suggest modified bi-level approach for finding the best stacking sequence of laminated composite structures subject to mechanical, blending and manufacturing constraints. We propose to use both the number of plies laid up at predefined angles and lamination parameters as independent variables at outer (global) stage of bi-level scheme aimed to satisfy buckling, strain and percentage constraints. Our formulation allows precise definition of the feasible region of lamination parameters and greatly facilitates the solution of inner level problem of finding the optimal stacking sequence.
Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
Venue: arXiv cs.DS 2013
Year: 2013

We show that the shadow vertex algorithm can be used to compute a short path between a given pair of vertices of a polytope P = {x : Ax \leq b} along the edges of P, where A \in R^{m \times n} is a real-valued matrix. Both, the length of the path and the running time of the algorithm, are polynomial in m, n, and a parameter 1/delta that is a measure for the flatness of the vertices of P. For integer matrices A \in Z^{m \times n} we show a connection between delta and the largest absolute value Delta of any sub-determinant of A, yielding a bound of O(Delta^4 m n^4) for the length of the computed path. This bound is expressed in the same parameter Delta as the recent non-constructive bound of O(Delta^2 n^4 \log (n Delta)) by Bonifas et al. For the special case of totally unimodular matrices, the length of the computed path simplifies to O(m n^4), which significantly improves the previously best known constructive bound of O(m^{16} n^3 \log^3(mn)) by Dyer and Frieze.
Solution of System of Linear Equations - A Neuro-Fuzzy Approach
Venue: arXiv cs.AI 2013
Year: 2013

Neuro-Fuzzy Modeling has been applied in a wide variety of fields such as Decision Making, Engineering and Management Sciences etc. In particular, applications of this Modeling technique in Decision Making by involving complex Systems of Linear Algebraic Equations have remarkable significance. In this Paper, we present Polak-Ribiere Conjugate Gradient based Neural Network with Fuzzy rules to solve System of Simultaneous Linear Algebraic Equations. This is achieved using Fuzzy Backpropagation Learning Rule. The implementation results show that the proposed Neuro-Fuzzy Network yields effective solutions for exactly determined, underdetermined and over-determined Systems of Linear Equations. This fact is demonstrated by the Computational Complexity analysis of the Neuro-Fuzzy Algorithm. The proposed Algorithm is simulated effectively using MATLAB software. To the best of our knowledge this is the first work of the Systems of Linear Algebraic Equations using Neuro-Fuzzy Modeling.
Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
Venue: arXiv cs.CG 2013
Year: 2013

We study the \LowerBoundedCenter (\lbc) problem, which is a clustering problem that can be viewed as a variant of the \kCenter problem. In the \lbc problem, we are given a set of points P in a metric space and a lower bound λ, and the goal is to select a set C \subseteq P of centers and an assignment that maps each point in P to a center of C such that each center of C is assigned at least λpoints. The price of an assignment is the maximum distance between a point and the center it is assigned to, and the goal is to find a set of centers and an assignment of minimum price. We give a constant factor approximation algorithm for the \lbc problem that runs in O(n \log n) time when the input points lie in the d-dimensional Euclidean space R^d, where d is a constant. We also prove that this problem cannot be approximated within a factor of 1.8-εunless P = \NP even if the input points are points in the Euclidean plane R^2.
SOA Embedded in BPM: A High Level View of Object Oriented Paradigm
Venue: arXiv cs.SE 2013
Year: 2013

The trends of design and development of information systems have undergone a variety of ongoing phases and stages. These variations have been evolved due to brisk changes in user requirements and business needs. To meet these requirements and needs, a flexible and agile business solution was required to come up with the latest business trends and styles. Another obstacle in agility of information systems was typically different treatment of same diseases of two patients: business processes and information services. After the emergence of information technology, the business processes and information systems have become counterparts. But these two business halves have been treated under totally different standards. There is need to streamline the boundaries of these both pillars that are equally sharing information system's burdens and liabilities. In last decade, the object orientation has evolved into one of the major solutions for modern business needs and now, SOA is the solution to shift business on ranks of electronic platform. BPM is another modern business solution that assists to regularize optimization of business processes. This paper discusses how object orientation can be conformed to incorporate or embed SOA in BPM for improved information systems.
Uniform generation of RNA pseudoknot structures with genus filtration
Venue: arXiv cs.CE 2013
Year: 2013

In this paper we present a sampling framework for RNA structures of fixed topological genus. We introduce a novel, linear time, uniform sampling algorithm for RNA structures of fixed topological genus $g$, for arbitrary $g>0$. Furthermore we develop a linear time sampling algorithm for RNA structures of fixed topological genus $g$ that are weighted by a simplified, loop-based energy functional. For this process the partition function of the energy functional has to be computed once, which has $O(n^2)$ time complexity.
Cross-site Scripting Attacks on Android WebView
Venue: arXiv cs.CR 2013
Year: 2013

WebView is an essential component in Android and iOS. It enables applications to display content from on-line resources. It simplifies task of performing a network request, parsing the data and rendering it. WebView uses a number of APIs which can interact with the web contents inside WebView. In the current paper, Cross-site scripting attacks or XSS attacks specific to Android WebView are discussed. Cross site scripting (XSS) is a type of vulnerability commonly found in web applications. This vulnerability makes it possible for attackers to run malicious code into victim's WebView,through HttpClient APIs. Using this malicious code, the attackers can steal the victim's credentials, such as cookies. The access control policies (that is,the same origin policy) employed by the browser to protect those credentials can be bypassed by exploiting the XSS vulnerability.
On the Effect of Correlated Measurements on the Performance of Distributed Estimation
Venue: arXiv cs.IT 2013
Year: 2013

We address the distributed estimation of an unknown scalar parameter in Wireless Sensor Networks (WSNs). Sensor nodes transmit their noisy observations over multiple access channel to a Fusion Center (FC) that reconstructs the source parameter. The received signal is corrupted by noise and channel fading, so that the FC objective is to minimize the Mean-Square Error (MSE) of the estimate. In this paper, we assume sensor node observations to be correlated with the source signal and correlated with each other as well. The correlation coefficient between two observations is exponentially decaying with the distance separation. The effect of the distance-based correlation on the estimation quality is demonstrated and compared with the case of unity correlated observations. Moreover, a closed-form expression for the outage probability is derived and its dependency on the correlation coefficients is investigated. Numerical simulations are provided to verify our analytic results.
Lobby index as a network centrality measure
Venue: arXiv cs.SI 2013
Year: 2013

We study the lobby index (l-index for short) as a local node centrality measure for complex networks. The l-inde is compared with degree (a local measure), betweenness and Eigenvector centralities (two global measures) in the case of biological network (Yeast interaction protein-protein network) and a linguistic network (Moby Thesaurus II). In both networks, the l-index has poor correlation with betweenness but correlates with degree and Eigenvector. Being a local measure, one can take advantage by using the l-index because it carries more information about its neighbors when compared with degree centrality, indeed it requires less time to compute when compared with Eigenvector centrality. Results suggests that l-index produces better results than degree and Eigenvector measures for ranking purposes, becoming suitable as a tool to perform this task.
Learning Geo-Temporal Non-Stationary Failure and Recovery of Power Distribution
Venue: arXiv cs.SY 2013
Year: 2013

Smart energy grid is an emerging area for new applications of machine learning in a non-stationary environment. Such a non-stationary environment emerges when large-scale failures occur at power distribution networks due to external disturbances such as hurricanes and severe storms. Power distribution networks lie at the edge of the grid, and are especially vulnerable to external disruptions. Quantifiable approaches are lacking and needed to learn non-stationary behaviors of large-scale failure and recovery of power distribution. This work studies such non-stationary behaviors in three aspects. First, a novel formulation is derived for an entire life cycle of large-scale failure and recovery of power distribution. Second, spatial-temporal models of failure and recovery of power distribution are developed as geo-location based multivariate non-stationary GI(t)/G(t)/Infinity queues. Third, the non-stationary spatial-temporal models identify a small number of parameters to be learned. Learning is applied to two real-life examples of large-scale disruptions. One is from Hurricane Ike, where data from an operational network is exact on failures and recoveries. The other is from Hurricane Sandy, where aggregated data is used for inferring failure and recovery processes at one of the impacted areas. Model parameters are learned using real data. Two findings emerge as results of learning: (a) Failure rates behave similarly at the two different provider networks for two different hurricanes but differently at the geographical regions. (b) Both rapid- and slow-recovery are present for Hurricane Ike but only slow recovery is shown for a regional distribution network from Hurricane Sandy.