OpenRaiser/Intern-Atlas huggingface dataset:
Robust Synchronization in Markov Decision Processes
Venue: arXiv cs.LO 2014
Year: 2014

We consider synchronizing properties of Markov decision processes (MDP), viewed as generators of sequences of probability distributions over states. A probability distribution is p-synchronizing if the probability mass is at least p in some state, and a sequence of probability distributions is weakly p-synchronizing, or strongly p-synchronizing if respectively infinitely many, or all but finitely many distributions in the sequence are p-synchronizing. For each synchronizing mode, an MDP can be (i) sure winning if there is a strategy that produces a 1-synchronizing sequence; (ii) almost-sure winning if there is a strategy that produces a sequence that is, for all ε > 0, a (1-ε)-synchronizing sequence; (iii) limit-sure winning if for all ε > 0, there is a strategy that produces a (1-ε)-synchronizing sequence. For each synchronizing and winning mode, we consider the problem of deciding whether an MDP is winning, and we establish matching upper and lower complexity bounds of the problems, as well as the optimal memory requirement for winning strategies: (a) for all winning modes, we show that the problems are PSPACE-complete for weakly synchronizing, and PTIME-complete for strongly synchronizing; (b) we show that for weakly synchronizing, exponential memory is sufficient and may be necessary for sure winning, and infinite memory is necessary for almost-sure winning; for strongly synchronizing, linear-size memory is sufficient and may be necessary in all modes; (c) we show a robustness result that the almost-sure and limit-sure winning modes coincide for both weakly and strongly synchronizing.
Sparse Estimation From Noisy Observations of an Overdetermined Linear System
Venue: arXiv cs.SY 2014
Year: 2014

This note studies a method for the efficient estimation of a finite number of unknown parameters from linear equations, which are perturbed by Gaussian noise. In case the unknown parameters have only few nonzero entries, the proposed estimator performs more efficiently than a traditional approach. The method consists of three steps: (1) a classical Least Squares Estimate (LSE), (2) the support is recovered through a Linear Programming (LP) optimization problem which can be computed using a soft-thresholding step, (3) a de-biasing step using a LSE on the estimated support set. The main contribution of this note is a formal derivation of an associated ORACLE property of the final estimate. That is, when the number of samples is large enough, the estimate is shown to equal the LSE based on the support of the {\em true} parameters.
Multi-Voltage and Level-Shifter Assignment Driven Floorplanning
Venue: arXiv cs.AR 2014
Year: 2014

As technology scales, low power design has become a significant requirement for SOC designers. Among the existing techniques, Multiple-Supply Voltage (MSV) is a popular and effective method to reduce both dynamic and static power. Besides, level shifters consume area and delay, and should be considered during floorplanning. In this paper, we present a new floorplanning system, called MVLSAF, to solve multi-voltage and level shifter assignment problem. We use a convex cost network flow algorithm to assign arbitrary number of legal working voltages and a minimum cost flow algorithm to handle level-shifter assignment. The experimental results show MVLSAF is effective.
The Power of Well-Structured Systems
Venue: arXiv cs.LO 2014
Year: 2014

Well-structured systems, aka WSTSs, are computational models where the set of possible configurations is equipped with a well-quasi-ordering which is compatible with the transition relation between configurations. This structure supports generic decidability results that are important in verification and several other fields. This paper recalls the basic theory underlying well-structured systems and shows how two classic decision algorithms can be formulated as an exhaustive search for some "bad" sequences. This lets us describe new powerful techniques for the complexity analysis of WSTS algorithms. Recently, these techniques have been successful in precisely characterising the power, in a complexity-theoretical sense, of several important WSTS models like unreliable channel systems, monotonic counter machines, or networks of timed systems.
Local Optima Networks: A New Model of Combinatorial Fitness Landscapes
Venue: arXiv cs.NE 2014
Year: 2014

This chapter overviews a recently introduced network-based model of combinatorial landscapes: Local Optima Networks (LON). The model compresses the information given by the whole search space into a smaller mathematical object that is a graph having as vertices the local optima and as edges the possible weighted transitions between them. Two definitions of edges have been proposed: basin-transition and escape-edges, which capture relevant topological features of the underlying search spaces. This network model brings a new set of metrics to characterize the structure of combinatorial landscapes, those associated with the science of complex networks. These metrics are described, and results are presented of local optima network extraction and analysis for two selected combinatorial landscapes: NK landscapes and the quadratic assignment problem. Network features are found to correlate with and even predict the performance of heuristic search algorithms operating on these problems.
Robot Training Under Conditions of Incomplete Information
Venue: arXiv cs.RO 2014
Year: 2014

The development of the works of the author about adaptive algorithms of teaching the robotic systems with the help of operator is described here. An operator is assumed to be an experience decision-maker and sane carrier of a target which the robotic system needs to achieve. The works characteristic is that the behavior of the robotic system is not specified a priori (as standard) but is formed adaptively based on the information about the situation and decisions made by a decision-maker. In this scheme the robotic system and the decision-maker can cooperate in the normal operation mode of the robotic system or in the time sharing mode with the possibility to plan actively the experiment on the robotic system. If the adaptive scheme is chosen, there are teaching stages and operating stages of the robotic system. At that the decision-maker can act slowly having the possibility to weigh the decision made. This way allows the robotic system reacting flexibly by switching between preset models and respond to the environment instability. The data integrity about the environment condition and about target preferences of an operator plays a very important role in robotic system work. The effective work of the robotic system depends on the effective settings of a preference model of the robotic system based on the decisions of the decision-maker and on the effective control. The influence of settings and control factors on the index of effectiveness of the robotic system is subject of this work. The uncertainty may be caused by the data flow limitation received by the operator on the stage of the model setting.
Optimal Alphabetic Ternary Trees
Venue: arXiv cs.DS 2014
Year: 2014

We give a new algorithm to construct optimal alphabetic ternary trees, where every internal node has at most three children. This algorithm generalizes the classic Hu-Tucker algorithm, though the overall computational complexity has yet to be determined.
Complexity Jumps In Multiagent Justification Logic Under Interacting Justifications
Venue: arXiv cs.LO 2014
Year: 2014

The Logic of Proofs, LP, and its successor, Justification Logic, is a refinement of the modal logic approach to epistemology in which proofs/justifications are taken into account. In 2000 Kuznets showed that satisfiability for LP is in the second level of the polynomial hierarchy, a result which has been successfully repeated for all other one-agent justification logics whose complexity is known. We introduce a family of multi-agent justification logics with interactions between the agents' justifications, by extending and generalizing the two-agent versions of the Logic of Proofs introduced by Yavorskaya in 2008. Known concepts and tools from the single-agent justification setting are adjusted for this multiple agent case. We present tableau rules and some preliminary complexity results. In several cases the satisfiability problem for these logics remains in the second level of the polynomial hierarchy, while for others it is PSPACE or EXP-hard. Furthermore, this problem becomes PSPACE-hard even for certain two-agent logics, while there are EXP-hard logics of three agents.
Software Requirement Specification Using Reverse Speech Technology
Venue: arXiv cs.CL 2014
Year: 2014

Speech analysis had been taken to a new level with the discovery of Reverse Speech (RS). RS is the discovery of hidden messages, referred as reversals, in normal speech. Works are in progress for exploiting the relevance of RS in different real world applications such as investigation, medical field etc. In this paper we represent an innovative method for preparing a reliable Software Requirement Specification (SRS) document with the help of reverse speech. As SRS act as the backbone for the successful completion of any project, a reliable method is needed to overcome the inconsistencies. Using RS such a reliable method for SRS documentation was developed.
Information Theoretical Cryptogenography
Venue: arXiv cs.CR 2014
Year: 2014

We consider problems where $n$ people are communicating and a random subset of them is trying to leak information, without making it clear who are leaking the information. We introduce a measure of suspicion, and show that the amount of leaked information will always be bounded by the expected increase in suspicion, and that this bound is tight. We ask the question: Suppose a large number of people have some information they want to leak, but they want to ensure that after the communication, an observer will assign probability at most $c$ to the events that each of them is trying to leak the information. How much information can they reliably leak, per person who is leaking? We show that the answer is $- \frac{\log(1-c)}{c} -\log(e)$ bits.
Modeling of Degradation Processes in Historical Mortars
Venue: arXiv cs.CE 2014
Year: 2014

The aim of presented paper is modeling of degradation processes in historical mortars exposed to moisture impact during freezing. Internal damage caused by ice crystallization in pores is one of the most important factors limiting the service life of historical structures. Coupling the transport processes with the mechanical part will allow us to address the impact of moisture on the durability, strength and stiffness of mortars. This should be accomplished with the help of a complex thermo-hygro-mechanical model representing one of the prime objectives of this work. The proposed formulation is based on the extension of the classical poroelasticity models with the damage mechanics. An example of two-dimensional moisture transport in the environment with temperature below freezing point is presented to support the theoretical derivations.
An evaluative baseline for geo-semantic relatedness and similarity
Venue: arXiv cs.CL 2014
Year: 2014

In geographic information science and semantics, the computation of semantic similarity is widely recognised as key to supporting a vast number of tasks in information integration and retrieval. By contrast, the role of geo-semantic relatedness has been largely ignored. In natural language processing, semantic relatedness is often confused with the more specific semantic similarity. In this article, we discuss a notion of geo-semantic relatedness based on Lehrer's semantic fields, and we compare it with geo-semantic similarity. We then describe and validate the Geo Relatedness and Similarity Dataset (GeReSiD), a new open dataset designed to evaluate computational measures of geo-semantic relatedness and similarity. This dataset is larger than existing datasets of this kind, and includes 97 geographic terms combined into 50 term pairs rated by 203 human subjects. GeReSiD is available online and can be used as an evaluation baseline to determine empirically to what degree a given computational model approximates geo-semantic relatedness and similarity.
From LTL to Deterministic Automata: A Safraless Compositional Approach
Venue: arXiv cs.LO 2014
Year: 2014

We present a new algorithm to construct a deterministic Rabin automaton for an LTL formula $φ$. The automaton is the product of a master automaton and an array of slave automata, one for each $G$-subformula of $φ$. The slave automaton for $Gψ$ is in charge of recognizing whether $FGψ$ holds. As opposed to standard determinization procedures, the states of all our automata have a clear logical structure, which allows to apply various optimizations. Our construction subsumes former algorithms for fragments of LTL. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.
Authorship Analysis based on Data Compression
Venue: arXiv cs.CL 2014
Year: 2014

This paper proposes to perform authorship analysis using the Fast Compression Distance (FCD), a similarity measure based on compression with dictionaries directly extracted from the written texts. The FCD computes a similarity between two documents through an effective binary search on the intersection set between the two related dictionaries. In the reported experiments the proposed method is applied to documents which are heterogeneous in style, written in five different languages and coming from different historical periods. Results are comparable to the state of the art and outperform traditional compression-based methods.
Welfare guarantees for proportional allocations
Venue: arXiv cs.GT 2014
Year: 2014

According to the proportional allocation mechanism from the network optimization literature, users compete for a divisible resource -- such as bandwidth -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of 26.8% on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to 50% over both equilibrium concepts. Our analysis is simpler and, furthermore, we argue that it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between 36% and 50%) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.
A subexponential parameterized algorithm for Interval Completion
Venue: arXiv cs.DS 2014
Year: 2014

In the Interval Completion problem we are given a graph G and an integer k, and the task is to turn G using at most k edge additions into an interval graph, i.e., a graph admitting an intersection model of intervals on a line. Motivated by applications in sparse matrix multiplication and molecular biology, Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] asked for a fixed-parameter algorithm solving this problem. This question was answer affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time $O(k^{2k}n^3m)$. We give the first subexponential parameterized algorithm solving Interval Completion in time $k^{O(\sqrt{k})} n^{O(1)}$. This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.
A Clockwork RNN
Venue: arXiv cs.NE 2014
Year: 2014

Sequence prediction and classification are ubiquitous and challenging problems in machine learning that can require identifying complex dependencies between temporally distant inputs. Recurrent Neural Networks (RNNs) have the ability, in theory, to cope with these temporal dependencies by virtue of the short-term memory implemented by their recurrent (feedback) connections. However, in practice they are difficult to train successfully when the long-term memory is required. This paper introduces a simple, yet powerful modification to the standard RNN architecture, the Clockwork RNN (CW-RNN), in which the hidden layer is partitioned into separate modules, each processing inputs at its own temporal granularity, making computations only at its prescribed clock rate. Rather than making the standard RNN models more complex, CW-RNN reduces the number of RNN parameters, improves the performance significantly in the tasks tested, and speeds up the network evaluation. The network is demonstrated in preliminary experiments involving two tasks: audio signal generation and TIMIT spoken word classification, where it outperforms both RNN and LSTM networks.
Finding Coordinated Paths for Multiple Holonomic Agents in 2-d Polygonal Environment
Venue: arXiv cs.AI 2014
Year: 2014

Avoiding collisions is one of the vital tasks for systems of autonomous mobile agents. We focus on the problem of finding continuous coordinated paths for multiple mobile disc agents in a 2-d environment with polygonal obstacles. The problem is PSPACE-hard, with the state space growing exponentially in the number of agents. Therefore, the state of the art methods include mainly reactive techniques and sampling-based iterative algorithms. We compare the performance of a widely-used reactive method ORCA with three variants of a popular planning algorithm RRT* applied to multi-agent path planning and find that an algorithm combining reactive collision avoidance and RRT* planning, which we call ORCA-RRT* can be used to solve instances that are out of the reach of either of the techniques. We experimentally show that: 1) the reactive part of the algorithm can efficiently solve many multi-agent path finding problems involving large number of agents, for which RRT* algorithm is often unable to find a solution in limited time and 2) the planning component of the algorithm is able to solve many instances containing local minima, where reactive techniques typically fail.
Analysis of Carrier Frequency Selective Offset Estimation - Using Zero-IF and ZCZIn MC-DS-CDMA
Venue: arXiv cs.NI 2014
Year: 2014

A new method for frequency synchronization based upon Zero-Intermediate Frequency Zero-IF receiver and characteristics of the received signal s power spectrum for MC-DSCDMA Up link system is proposed in this paper. In addition to this, employing Zero Correlation Zone (ZCZ) sequences, designed specifically for quasi synchronous up link transmissions, is proposed to exploit frequency and temporal diversity in frequency-selective block fading channels. The variance for Carrier Frequency Offset (CFO) estimators of MC DS CDMA Uplink is compared with that of an OFDM system to estimate the CFO. Our study and results show that the MC DS CDMA system is outperforming the OFDM method
A Narrative Vehicle Protection Representation for Vehicle Speed Regulator Under Driver Exhaustion -- A Study
Venue: arXiv cs.CV 2014
Year: 2014

Driver fatigue is one of the important factors that cause traffic accidents, and the ever-increasing number due to diminished drivers vigilance level has become a problem of serious concern to society. Drivers with a diminished vigilance level suffer from a marked decline in their abilities of perception, recognition, and vehicle control, and therefore pose serious danger to their own life and the lives of other people. Exhaustion resulting from sleep deprivation or sleep disorders is an important factor in the creasing number of accidents. In this projected work, we discuss the various methods of the existing and the proposed method based on a real time online safety prototype that controls the vehicle speed under driver fatigue. The purpose of such a model is to advance a system to detect fatigue symptoms in drivers and control the speed of vehicle to avoid accidents. This system was tested adequately with subjects of different technology of various researchers finally the validity of the proposed model for vehicle speed controller based on driver fatigue detection is shown.
Using of GPUs for cluster analysis of large data by K-means method
Venue: arXiv cs.DC 2014
Year: 2014

This problem was solved within the framework of the grant project "Solving of problems of cluster analysis with application of parallel algorithms and cloud technologies" in the Institute of Mathematics and Mathematical Modelling in Almaty. The problem of cluster analysis for the large amount of data is very important in different areas of science - genetics, biology, sociology etc. At the same time, such statistical known packages as STATISTICA, STADIA, SYSTAT and others do not allow to solve large problems. The new algorithm that uses the high processing power of GPUs for solving clustering problems by the K-means method was developed. This algorithm is implemented as a C++ application in Microsoft Visual Studio 2010 with using the GPU Nvidia GeForce 660. The developed software package for solving clustering problems by the method of K - means with using GPUs allows us to handle up to 2 million records with number of features up to 25. The gain in the computing time is in factor 5. We plan to increase this factor up to 20-30 after improving the algorithms.
Parallel algorithms for problems of cluster analysis with very large amount of data
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we solve on GPUs massive problems with large amount of data, which are not appropriate for solution with the SIMD technology. For the given problem we consider a three-level parallelization. The multithreading of CPU is used at the top level and graphic processors for massive computing. For solving problems of cluster analysis on GPUs the nearest neighbor method (NNM) is developed. This algorithm allows us to handle up to 2 millions records with number of features up to 25. Since sequential and parallel algorithms are fundamentally different, it is difficult to compare the computation times. However, some comparisons are made. The gain in the computing time is about 10 times. We plan to increase this factor up to 50-100 after fine tuning of algorithms.
On Heterogeneous Regenerating Codes and Capacity of Distributed Storage Systems
Venue: arXiv cs.IT 2014
Year: 2014

Heterogeneous Distributed Storage Systems (DSS) are close to real world applications for data storage. Internet caching system and peer-to-peer storage clouds are the examples of such DSS. In this work, we calculate the capacity formula for such systems where each node store different number of packets and each having a different repair bandwidth (node can be repaired by contacting a specific set of nodes). The tradeoff curve between storage and repair bandwidth is studied for such heterogeneous DSS. By analyzing the capacity formula new minimum bandwidth regenerating (MBR) and minimum storage regenerating (MBR) points are obtained on the curve. It is shown that in some cases these are better than the homogeneous DSS.