OpenRaiser/Intern-Atlas huggingface dataset:
Online Packet Scheduling with Bounded Delay and Lookahead
Venue: arXiv cs.DS 2016
Year: 2016

We study the online bounded-delay packet scheduling problem (BDPS), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is $1.828$, still quite far from the best lower bound of $ϕ\approx 1.618$. In the variant of BDPS with $s$-bounded instances, each packet can be scheduled in at most $s$ consecutive slots, starting at its release time. The lower bound of $ϕ$ applies even to the special case of $2$-bounded instances, and a $ϕ$-competitive algorithm for $3$-bounded instances was given in Chin et al. Improving that result, and addressing a question posed by Goldwasser, we present a $ϕ$-competitive algorithm for $4$-bounded instances. We also study a variant of BDPS where an online algorithm has the additional power of $1$-lookahead, knowing at time $t$ which packets will arrive at time $t+1$. For BDPS with $1$-lookahead restricted to $2$-bounded instances, we present an online algorithm with competitive ratio $(\sqrt{13} - 1)/2 \approx 1.303$ and we prove a nearly tight lower bound of $(1 + \sqrt{17})/4 \approx 1.281$.
Clique-Width and Directed Width Measures for Answer-Set Programming
Venue: arXiv cs.AI 2016
Year: 2016

Disjunctive Answer Set Programming (ASP) is a powerful declarative programming paradigm whose main decision problems are located on the second level of the polynomial hierarchy. Identifying tractable fragments and developing efficient algorithms for such fragments are thus important objectives in order to complement the sophisticated ASP systems available to date. Hard problems can become tractable if some problem parameter is bounded by a fixed constant; such problems are then called fixed-parameter tractable (FPT). While several FPT results for ASP exist, parameters that relate to directed or signed graphs representing the program at hand have been neglected so far. In this paper, we first give some negative observations showing that directed width measures on the dependency graph of a program do not lead to FPT results. We then consider the graph parameter of signed clique-width and present a novel dynamic programming algorithm that is FPT w.r.t. this parameter. Clique-width is more general than the well-known treewidth, and, to the best of our knowledge, ours is the first FPT algorithm for bounded clique-width for reasoning problems beyond SAT.
Ordering as privileged information
Venue: arXiv cs.AI 2016
Year: 2016

We propose to accelerate the rate of convergence of the pattern recognition task by directly minimizing the variance diameters of certain hypothesis spaces, which are critical quantities in fast-convergence results.We show that the variance diameters can be controlled by dividing hypothesis spaces into metric balls based on a new order metric. This order metric can be minimized as an ordinal regression problem, leading to a LUPI (Learning Using Privileged Information) application where we take the privileged information as some desired ordering, and construct a faster-converging hypothesis space by empirically restricting some larger hypothesis space according to that ordering. We give a risk analysis of the approach. We discuss the difficulties with model selection and give an innovative technique for selecting multiple model parameters. Finally, we provide some data experiments.
Minimizing the Total Movement for Movement to Independence Problem on a Line
Venue: arXiv cs.CG 2016
Year: 2016

Given a positive real value $δ$, a set $P$ of points along a line and a distance function $d$, in the movement to independence problem, we wish to move the points to new positions on the line such that for every two points $p_{i},p_{j} \in P$, we have $d(p_{i},p_{j}) \geq δ$ while minimizing the sum of movements of all points. This measure of the cost for moving the points was previously unsolved in this setting. However for different cost measures there are algorithms of $O(n \log(n))$ or of $O(n)$. We present an $O(n \log(n))$ algorithm for the points on a line and thus conclude the setting in one dimension.
Geometric Learning and Topological Inference with Biobotic Networks: Convergence Analysis
Venue: arXiv cs.RO 2016
Year: 2016

In this study, we present and analyze a framework for geometric and topological estimation for mapping of unknown environments. We consider agents mimicking motion behaviors of cyborg insects, known as biobots, and exploit coordinate-free local interactions among them to infer geometric and topological information about the environment, under minimal sensing and localization constraints. Local interactions are used to create a graphical representation referred to as the encounter graph. A metric is estimated over the encounter graph of the agents in order to construct a geometric point cloud using manifold learning techniques. Topological data analysis (TDA), in particular persistent homology, is used in order to extract topological features of the space and a classification method is proposed to infer robust features of interest (e.g. existence of obstacles). We examine the asymptotic behavior of the proposed metric in terms of the convergence to the geodesic distances in the underlying manifold of the domain, and provide stability analysis results for the topological persistence. The proposed framework and its convergences and stability analysis are demonstrated through numerical simulations and experiments.
Detecting Algebraic Manipulation in Leaky Storage Systems
Venue: arXiv cs.IT 2016
Year: 2016

Algebraic Manipulation Detection (AMD) Codes detect adversarial noise that is added to a coded message and stored in a storage that is opaque to the adversary. We study AMD codes when the storage can leak up to ρ\log|G| bits of information about the stored codeword, where G is the group in which the stored codeword lives and ρis a constant. We propose ρ-AMD codes that provide protection in this new setting, and define weak and strong ρ-AMD codes that provide security for a random and an arbitrary message, respectively. We derive concrete and asymptotic bounds for the efficiency of these codes featuring a rate upper bound of 1-ρfor the strong codes. We also define the class of ρ^{LV}-AMD codes that provide protection when leakage is in the form of a number of codeword components, and give constructions featuring a strong ρ^{LV}-AMD codes that asymptotically achieve the rate 1-ρ. We describe applications of ρ-AMD codes to, (i) robust ramp secret sharing scheme and, (ii) wiretap II channel when the adversary can eavesdrop a ρfraction of codeword components and tamper with all components of the codeword.
Efficient and Consistent Robust Time Series Analysis
Venue: arXiv cs.LG 2016
Year: 2016

We study the problem of robust time series analysis under the standard auto-regressive (AR) time series model in the presence of arbitrary outliers. We devise an efficient hard thresholding based algorithm which can obtain a consistent estimate of the optimal AR model despite a large fraction of the time series points being corrupted. Our algorithm alternately estimates the corrupted set of points and the model parameters, and is inspired by recent advances in robust regression and hard-thresholding methods. However, a direct application of existing techniques is hindered by a critical difference in the time-series domain: each point is correlated with all previous points rendering existing tools inapplicable directly. We show how to overcome this hurdle using novel proof techniques. Using our techniques, we are also able to provide the first efficient and provably consistent estimator for the robust regression problem where a standard linear observation model with white additive noise is corrupted arbitrarily. We illustrate our methods on synthetic datasets and show that our methods indeed are able to consistently recover the optimal parameters despite a large fraction of points being corrupted.
On the Control of Energy Storage Systems for Electric Vehicles Fast Charging in Service Areas
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents a real time control strategy for energy storage systems integration in electric vehicles fast charging applications combined with generation from intermittent renewable energy sources. A two steps approach taking advantage of the model predictive control methodology is designed on purpose to optimally allocate the reference charging power while managing the priority among the plugged vehicles and then control the storage for efficiently sustaining the charging process. Two different use cases are considered: in the former the charging area is disconnected from the grid, so that the objective is to minimize the deviation of electric vehicles charging power from the nominal value; in the latter the focus is on the point of connection to the grid and the need of mitigating the related power flow. In both cases the fundamental requirement for feasible control system operation is to guarantee stability of the storage's state of charge over the time. Simulation results are provided and discussed in detail, showing the effectiveness of the proposed approach.
The Art of DNA Strings: Sixteen Years of DNA Coding Theory
Venue: arXiv cs.IT 2016
Year: 2016

The idea of computing with DNA was given by Tom Head in 1987, however in 1994 in a seminal paper, the actual successful experiment for DNA computing was performed by Adleman. The heart of the DNA computing is the DNA hybridization, however, it is also the source of errors. Thus the success of the DNA computing depends on the error control techniques. The classical coding theory techniques have provided foundation for the current information and communication technology (ICT). Thus it is natural to expect that coding theory will be the foundational subject for the DNA computing paradigm. For the successful experiments with DNA computing usually we design DNA strings which are sufficiently dissimilar. This leads to the construction of a large set of DNA strings which satisfy certain combinatorial and thermodynamic constraints. Over the last 16 years, many approaches such as combinatorial, algebraic, computational have been used to construct such DNA strings. In this work, we survey this interesting area of DNA coding theory by providing key ideas of the area and current known results.
Formal Definition of QoE Metrics
Venue: arXiv cs.MM 2016
Year: 2016

This technical report formally defines the QoE metrics which are introduced and discussed in the article "QoE Beyond the MOS: An In-Depth Look at QoE via Better Metrics and their Relation to MOS" by Tobias Hoßfeld, Poul E. Heegaard, Martin Varela, Sebastian Möller, accepted for publication in the Springer journal "Quality and User Experience". Matlab scripts for computing the QoE metrics for given data sets are available in GitHub.
Moving Toward High Precision Dynamical Modelling in Hidden Markov Models
Venue: arXiv cs.CL 2016
Year: 2016

Hidden Markov Model (HMM) is often regarded as the dynamical model of choice in many fields and applications. It is also at the heart of most state-of-the-art speech recognition systems since the 70's. However, from Gaussian mixture models HMMs (GMM-HMM) to deep neural network HMMs (DNN-HMM), the underlying Markovian chain of state-of-the-art models did not changed much. The "left-to-right" topology is mostly always employed because very few other alternatives exist. In this paper, we propose that finely-tuned HMM topologies are essential for precise temporal modelling and that this approach should be investigated in state-of-the-art HMM system. As such, we propose a proof-of-concept framework for learning efficient topologies by pruning down complex generic models. Speech recognition experiments that were conducted indicate that complex time dependencies can be better learned by this approach than with classical "left-to-right" models.
Efficient Timeout Synthesis in Fixed-Delay CTMC Using Policy Iteration
Venue: arXiv cs.PF 2016
Year: 2016

We consider the fixed-delay synthesis problem for continuous-time Markov chains extended with fixed-delay transitions (fdCTMC). The goal is to synthesize concrete values of the fixed-delays (timeouts) that minimize the expected total cost incurred before reaching a given set of target states. The same problem has been considered and solved in previous works by computing an optimal policy in a certain discrete-time Markov decision process (MDP) with a huge number of actions that correspond to suitably discretized values of the timeouts. In this paper, we design a symbolic fixed-delay synthesis algorithm which avoids the explicit construction of large action spaces. Instead, the algorithm computes a small sets of "promising" candidate actions on demand. The candidate actions are selected by minimizing a certain objective function by computing its symbolic derivative and extracting a univariate polynomial whose roots are precisely the points where the derivative takes zero value. Since roots of high degree univariate polynomials can be isolated very efficiently using modern mathematical software, we achieve not only drastic memory savings but also speedup by three orders of magnitude compared to the previous methods.
NIST: An Image Classification Network to Image Semantic Retrieval
Venue: arXiv cs.CV 2016
Year: 2016

This paper proposes a classification network to image semantic retrieval (NIST) framework to counter the image retrieval challenge. Our approach leverages the successful classification network GoogleNet based on Convolutional Neural Networks to obtain the semantic feature matrix which contains the serial number of classes and corresponding probabilities. Compared with traditional image retrieval using feature matching to compute the similarity between two images, NIST leverages the semantic information to construct semantic feature matrix and uses the semantic distance algorithm to compute the similarity. Besides, the fusion strategy can significantly reduce storage and time consumption due to less classes participating in the last semantic distance computation. Experiments demonstrate that our NIST framework produces state-of-the-art results in retrieval experiments on MIRFLICKR-25K dataset.
Model Checking of BPMN Models for Reconfigurable Workflows
Venue: arXiv cs.SE 2016
Year: 2016

Nowadays, business enterprises often need to dynamically reconfigure their internal processes in order to improve the efficiency of the business flow. However, modifications of the workflow usually lead to several problems in terms of deadlock freedom, completeness and security. A solid solution to these problems consists in the application of model checking techniques in order to verify if specific properties of the workflow are preserved by the change in configuration. Our goal in this work is to develop a formal verification procedure to deal with these problems. The first step consists in developing a formal definition of a BPMN model of a business workflow. Then, a given BPMN model is translated into a formal model specified in Promela. Finally, by using the SPIN model checker, the correctness of the reconfigured workflow is verified.
Threshold Decoding for Disjunctive Group Testing
Venue: arXiv cs.IT 2016
Year: 2016

Let $1 \le s < t$, $N \ge 1$ be integers and a complex electronic circuit of size $t$ is said to be an $s$-active, $\; s \ll t$, and can work as a system block if not more than $s$ elements of the circuit are defective. Otherwise, the circuit is said to be an $s$-defective and should be replaced by a similar $s$-active circuit. Suppose that there exists a possibility to run $N$ non-adaptive group tests to check the $s$-activity of the circuit. As usual, we say that a (disjunctive) group test yields the positive response if the group contains at least one defective element. Along with the conventional decoding algorithm based on disjunctive $s$-codes, we consider a threshold decision rule with the minimal possible decoding complexity, which is based on the simple comparison of a fixed threshold $T$, $1 \le T \le N - 1$, with the number of positive responses $p$, $0 \le p \le N$. For the both of decoding algorithms we discuss upper bounds on the $α$-level of significance of the statistical test for the null hypothesis $\left\{ H_0 \,:\, \text{the circuit is $s$-active} \right\}$ verse the alternative hypothesis $\left\{ H_1 \,:\, \text{the circuit is $s$-defective} \right\}$.
Completely Reachable Automata
Venue: arXiv cs.FL 2016
Year: 2016

We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.
Visualizing Natural Language Descriptions: A Survey
Venue: arXiv cs.CL 2016
Year: 2016

A natural language interface exploits the conceptual simplicity and naturalness of the language to create a high-level user-friendly communication channel between humans and machines. One of the promising applications of such interfaces is generating visual interpretations of semantic content of a given natural language that can be then visualized either as a static scene or a dynamic animation. This survey discusses requirements and challenges of developing such systems and reports 26 graphical systems that exploit natural language interfaces and addresses both artificial intelligence and visualization aspects. This work serves as a frame of reference to researchers and to enable further advances in the field.
Complexity and Computation of Connected Zero Forcing
Venue: arXiv cs.DM 2016
Year: 2016

Zero forcing is an iterative graph coloring process whereby a colored vertex with a single uncolored neighbor forces that neighbor to be colored. It is NP-hard to find a minimum zero forcing set - a smallest set of initially colored vertices which forces the entire graph to be colored. We show that the problem remains NP-hard when the initially colored set induces a connected subgraph. We also give structural results about the connected zero forcing sets of a graph related to the graph's density, separating sets, and certain induced subgraphs, and we characterize the cardinality of the minimum connected zero forcing sets of unicyclic graphs and variants of cactus and block graphs. Finally, we identify several families of graphs whose connected zero forcing sets define greedoids and matroids.
Formal analysis of HTM Spatial Pooler performance under predefined operation conditions
Venue: arXiv cs.AI 2016
Year: 2016

This paper introduces mathematical formalism for Spatial (SP) of Hierarchical Temporal Memory (HTM) with a spacial consideration for its hardware implementation. Performance of HTM network and its ability to learn and adjust to a problem at hand is governed by a large set of parameters. Most of parameters are codependent which makes creating efficient HTM-based solutions challenging. It requires profound knowledge of the settings and their impact on the performance of system. Consequently, this paper introduced a set of formulas which are to facilitate the design process by enhancing tedious trial-and-error method with a tool for choosing initial parameters which enable quick learning convergence. This is especially important in hardware implementations which are constrained by the limited resources of a platform. The authors focused especially on a formalism of Spatial Pooler and derive at the formulas for quality and convergence of the model. This may be considered as recipes for designing efficient HTM models for given input patterns.
Honey Sheets: What Happens to Leaked Google Spreadsheets?
Venue: arXiv cs.CR 2016
Year: 2016

Cloud-based documents are inherently valuable, due to the volume and nature of sensitive personal and business content stored in them. Despite the importance of such documents to Internet users, there are still large gaps in the understanding of what cybercriminals do when they illicitly get access to them by for example compromising the account credentials they are associated with. In this paper, we present a system able to monitor user activity on Google spreadsheets. We populated 5 Google spreadsheets with fake bank account details and fake funds transfer links. Each spreadsheet was configured to report details of accesses and clicks on links back to us. To study how people interact with these spreadsheets in case they are leaked, we posted unique links pointing to the spreadsheets on a popular paste site. We then monitored activity in the accounts for 72 days, and observed 165 accesses in total. We were able to observe interesting modifications to these spreadsheets performed by illicit accesses. For instance, we observed deletion of some fake bank account information, in addition to insults and warnings that some visitors entered in some of the spreadsheets. Our preliminary results show that our system can be used to shed light on cybercriminal behavior with regards to leaked online documents.
Preventing Malware Pandemics in Mobile Devices by Establishing Response-time Bounds
Venue: arXiv cs.CR 2016
Year: 2016

We study the propagation of a malicious software in a network of mobile devices, which are moving in a specific city area, and establish time bounds for the activation of a counter-measure, i.e., an antivirus or a cleaner in order to prevent pandemic. More precisely, given an initial infected population (mobile devices), we establish upper bounds on the time needed for a counter-measure to take effect after infection (response-time), in order to prevent the rest susceptible devices to get infected. Thus, within a period of time, we guarantee that not all the susceptible devices in the city get infected and the infected ones get sanitized. In our work, we first propose a malware propagation model along with a device mobility model and then, utilizing these models, we develop a simulator that we use to study the spread of malware in such networks. Finally, we provide experimental results for the pandemic prevention taken by our simulator for various response-time intervals.
Encoding Cryptographic Functions to SAT Using Transalg System
Venue: arXiv cs.AI 2016
Year: 2016

In this paper we propose the technology for constructing propositional encodings of discrete functions. It is aimed at solving inversion problems of considered functions using state-of-the-art SAT solvers. We implemented this technology in the form of the software system called Transalg, and used it to construct SAT encodings for a number of cryptanalysis problems. By applying SAT solvers to these encodings we managed to invert several cryptographic functions. In particular, we used the SAT encodings produced by Transalg to construct the family of two-block MD5 collisions in which the first 10 bytes are zeros. Also we used Transalg encoding for the widely known A5/1 keystream generator to solve several dozen of its cryptanalysis instances in a distributed computing environment. In the paper we compare in detail the functionality of Transalg with that of similar software systems.