OpenRaiser/Intern-Atlas huggingface dataset:
A Novel Chaotic Image Encryption using Generalized Threshold Function
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, after reviewing the main points of image encryption and threshold function, we introduce the methods of chaotic image encryption based on pseudorandom bit padding that the bits be generated by the novel generalized threshold function (segmentation and self-similarity) methods. These methods decrease periodic effect of the ergodic dynamical systems in randomness of the chaotic image encryption. The essential idea of this paper is that given threshold functions of the ergodic dynamical systems. To evaluate the security of the cipher image of this scheme, the key space analysis, the correlation of two adjacent pixels and differential attack were performed. This scheme tries to improve the problem of failure of encryption such as small key space and level of security.
Strongly Convex Programming for Exact Matrix Completion and Robust Principal Component Analysis
Venue: arXiv cs.IT 2012
Year: 2012

The common task in matrix completion (MC) and robust principle component analysis (RPCA) is to recover a low-rank matrix from a given data matrix. These problems gained great attention from various areas in applied sciences recently, especially after the publication of the pioneering works of Cand`es et al.. One fundamental result in MC and RPCA is that nuclear norm based convex optimizations lead to the exact low-rank matrix recovery under suitable conditions. In this paper, we extend this result by showing that strongly convex optimizations can guarantee the exact low-rank matrix recovery as well. The result in this paper not only provides sufficient conditions under which the strongly convex models lead to the exact low-rank matrix recovery, but also guides us on how to choose suitable parameters in practical algorithms.
epsilon-Samples of Kernels
Venue: arXiv cs.CG 2012
Year: 2012

We study the worst case error of kernel density estimates via subset approximation. A kernel density estimate of a distribution is the convolution of that distribution with a fixed kernel (e.g. Gaussian kernel). Given a subset (i.e. a point set) of the input distribution, we can compare the kernel density estimates of the input distribution with that of the subset and bound the worst case error. If the maximum error is eps, then this subset can be thought of as an eps-sample (aka an eps-approximation) of the range space defined with the input distribution as the ground set and the fixed kernel representing the family of ranges. Interestingly, in this case the ranges are not binary, but have a continuous range (for simplicity we focus on kernels with range of [0,1]); these allow for smoother notions of range spaces. It turns out, the use of this smoother family of range spaces has an added benefit of greatly decreasing the size required for eps-samples. For instance, in the plane the size is O((1/eps^{4/3}) log^{2/3}(1/eps)) for disks (based on VC-dimension arguments) but is only O((1/eps) sqrt{log (1/eps)}) for Gaussian kernels and for kernels with bounded slope that only affect a bounded domain. These bounds are accomplished by studying the discrepancy of these "kernel" range spaces, and here the improvement in bounds are even more pronounced. In the plane, we show the discrepancy is O(sqrt{log n}) for these kernels, whereas for balls there is a lower bound of Omega(n^{1/4}).
Dependent Types for JavaScript
Venue: arXiv cs.PL 2012
Year: 2012

We present Dependent JavaScript (DJS), a statically-typed dialect of the imperative, object-oriented, dynamic language. DJS supports the particularly challenging features such as run-time type-tests, higher-order functions, extensible objects, prototype inheritance, and arrays through a combination of nested refinement types, strong updates to the heap, and heap unrolling to precisely track prototype hierarchies. With our implementation of DJS, we demonstrate that the type system is expressive enough to reason about a variety of tricky idioms found in small examples drawn from several sources, including the popular book JavaScript: The Good Parts and the SunSpider benchmark suite.
Error Correcting Codes for Distributed Control
Venue: arXiv cs.IT 2012
Year: 2012

The problem of stabilizing an unstable plant over a noisy communication link is an increasingly important one that arises in applications of networked control systems. Although the work of Schulman and Sahai over the past two decades, and their development of the notions of "tree codes"\phantom{} and "anytime capacity", provides the theoretical framework for studying such problems, there has been scant practical progress in this area because explicit constructions of tree codes with efficient encoding and decoding did not exist. To stabilize an unstable plant driven by bounded noise over a noisy channel one needs real-time encoding and real-time decoding and a reliability which increases exponentially with decoding delay, which is what tree codes guarantee. We prove that linear tree codes occur with high probability and, for erasure channels, give an explicit construction with an expected decoding complexity that is constant per time instant. We give novel sufficient conditions on the rate and reliability required of the tree codes to stabilize vector plants and argue that they are asymptotically tight. This work takes an important step towards controlling plants over noisy channels, and we demonstrate the efficacy of the method through several examples.
What is an OS?
Venue: arXiv cs.OS 2012
Year: 2012

While the engineering of operating systems is well understood, their formal structure and properties are not. The latter needs a clear definition of the purpose of an OS and an identification of the core. In this paper I offer definitions of the OS, processes and files, and present a few useful principles. The principles allow us to identify work like closure and continuation algorithms, in programming languages that is useful for the OS problem. The definitions and principles should yield a symbolic, albeit semiquantitative, framework that encompasses practice. Towards that end I specialise the definitions to describe conventional OSes and identify the core operations for a single computer OS that can be used to express their algorithms. The assumptions underlying the algorithms offer the design space framework. The paging and segmentation algorithms for conventional OSes are extracted from the framework as a check. Among the insights the emerge is that an OS is a constructive proof of equivalence between models of computation. Clear and useful definitions and principles are the first step towards a fully quantitative structure of an OS.
3D Finite Element Analysis of HMA Overlay Mix Design to Control Reflective Cracking
Venue: arXiv cs.CE 2012
Year: 2012

This study examines the effectiveness of HMA overlay design strategies for the purpose of controlling the development of reflective cracking. A parametric study was conducted using a 3D Finite Element (FE) model of a rigid pavement section including Linear Viscoelastic (LVE) material properties for the Hot Mix Asphalt (HMA) overlay and non-uniform tire-pavement contact stresses. Several asphalt mixtures were tested in the surface, intermediate, and leveling course of the HMA overlay. Results obtained show that no benefits can be anticipated by using either Polymer-Modified (PM) or Dense-Graded (DG) mixtures instead of Standard Binder (SB) mixtures in the surface or intermediate course. For the leveling course, the use of a PM asphalt binder was found beneficial in terms of mitigating reflective cracking. As compared to the SB mix, the use of PM asphalt mixture in the leveling course reduced the level of longitudinal tensile stress at the bottom of the HMA overlay above the PCC joint by approximately 30%.
Solving simple stochastic games with few coin toss positions
Venue: arXiv cs.GT 2012
Year: 2012

Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4^r r^{O(1)} n^{O(1)}. In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2^r (r log r + n)), thus improving both time bounds. While the algorithm is simple, the analysis leading to this time bound is involved, using techniques of extremal combinatorics to identify worst case instances for the algorithm.
Cache-Oblivious Implicit Predecessor Dictionaries with the Working Set Property
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we present an implicit dynamic dictionary with the working-set property, supporting insert(e) and delete(e) in O(log n) time, predecessor(e) in O(log l_{p(e)}) time, successor(e) in O(log l_{s(e)}) time and search(e) in O(log min(l_{p(e)},l_{e}, l_{s(e)})) time, where n is the number of elements stored in the dictionary, l_{e} is the number of distinct elements searched for since element e was last searched for and p(e) and s(e) are the predecessor and successor of e, respectively. The time-bounds are all worst-case. The dictionary stores the elements in an array of size n using no additional space. In the cache-oblivious model the log is base B and the cache-obliviousness is due to our black box use of an existing cache-oblivious implicit dictionary. This is the first implicit dictionary supporting predecessor and successor searches in the working-set bound. Previous implicit structures required O(log n) time.
Learning Smooth Pattern Transformation Manifolds
Venue: arXiv cs.CV 2012
Year: 2012

Manifold models provide low-dimensional representations that are useful for processing and analyzing data in a transformation-invariant way. In this paper, we study the problem of learning smooth pattern transformation manifolds from image sets that represent observations of geometrically transformed signals. In order to construct a manifold, we build a representative pattern whose transformations accurately fit various input images. We examine two objectives of the manifold building problem, namely, approximation and classification. For the approximation problem, we propose a greedy method that constructs a representative pattern by selecting analytic atoms from a continuous dictionary manifold. We present a DC (Difference-of-Convex) optimization scheme that is applicable to a wide range of transformation and dictionary models, and demonstrate its application to transformation manifolds generated by rotation, translation and anisotropic scaling of a reference pattern. Then, we generalize this approach to a setting with multiple transformation manifolds, where each manifold represents a different class of signals. We present an iterative multiple manifold building algorithm such that the classification accuracy is promoted in the learning of the representative patterns. Experimental results suggest that the proposed methods yield high accuracy in the approximation and classification of data compared to some reference methods, while the invariance to geometric transformations is achieved due to the transformation manifold model.
Reasoning About Strategies: On the Model-Checking Problem
Venue: arXiv cs.LO 2012
Year: 2012

In open systems verification, to formally check for reliability, one needs an appropriate formalism to model the interaction between agents and express the correctness of the system no matter how the environment behaves. An important contribution in this context is given by modal logics for strategic ability, in the setting of multi-agent games, such as ATL, ATL\star, and the like. Recently, Chatterjee, Henzinger, and Piterman introduced Strategy Logic, which we denote here by CHP-SL, with the aim of getting a powerful framework for reasoning explicitly about strategies. CHP-SL is obtained by using first-order quantifications over strategies and has been investigated in the very specific setting of two-agents turned-based games, where a non-elementary model-checking algorithm has been provided. While CHP-SL is a very expressive logic, we claim that it does not fully capture the strategic aspects of multi-agent systems. In this paper, we introduce and study a more general strategy logic, denoted SL, for reasoning about strategies in multi-agent concurrent games. We prove that SL includes CHP-SL, while maintaining a decidable model-checking problem. In particular, the algorithm we propose is computationally not harder than the best one known for CHP-SL. Moreover, we prove that such a problem for SL is NonElementarySpace-hard. This negative result has spurred us to investigate here syntactic fragments of SL, strictly subsuming ATL\star, with the hope of obtaining an elementary model-checking problem. Among the others, we study the sublogics SL[NG], SL[BG], and SL[1G]. They encompass formulas in a special prenex normal form having, respectively, nested temporal goals, Boolean combinations of goals and, a single goal at a time. About these logics, we prove that the model-checking problem for SL[1G] is 2ExpTime-complete, thus not harder than the one for ATL\star.
Liquid-gas-solid flows with lattice Boltzmann: Simulation of floating bodies
Venue: arXiv cs.CE 2012
Year: 2012

This paper presents a model for the simulation of liquid-gas-solid flows by means of the lattice Boltzmann method. The approach is built upon previous works for the simulation of liquid-solid particle suspensions on the one hand, and on a liquid-gas free surface model on the other. We show how the two approaches can be unified by a novel set of dynamic cell conversion rules. For evaluation, we concentrate on the rotational stability of non-spherical rigid bodies floating on a plane water surface - a classical hydrostatic problem known from naval architecture. We show the consistency of our method in this kind of flows and obtain convergence towards the ideal solution for the measured heeling stability of a floating box.
Empirical study of performance of data binding in ASP.NET web applications
Venue: arXiv cs.SE 2012
Year: 2012

Most developers use default properties of ASP.NET server controls when developing web applications. ASP.NET web applications typically employ server controls to provide dynamic web pages, and data-bound server controls to display and maintain database data. Though the default properties allow for fast creation of workable applications, creating a high-performance, multi-user, and scalable web application requires careful configuring of server controls and their enhancement using custom-made code. In providing commonly required functionality in data-driven ASP.NET web applications such as paging, sorting and filtering, our empirical study evaluated the impact of various technical approaches: automatic data binding in web server controls; data paging and sorting on web server; paging and sorting on database server; indexed and non-indexed database columns; clustered vs. non-clustered indices. The study observed significant performance differences between various technical approaches.
2D Barcode for DNA Encoding
Venue: arXiv cs.IT 2012
Year: 2012

The paper presents a solution for endcoding/decoding DNA information in 2D barcodes. First part focuses on the existing techniques and symbologies in 2D barcodes field. The 2D barcode PDF417 is presented as starting point. The adaptations and optimizations on PDF417 and on DataMatrix lead to the solution - DNA2DBC - DeoxyriboNucleic Acid Two Dimensional Barcode. The second part shows the DNA2DBC encoding/decoding process step by step. In conclusions are enumerated the most important features of 2D barcode implementation for DNA.
Code Design for the Noisy Slepian-Wolf Problem
Venue: arXiv cs.IT 2012
Year: 2012

We consider a noisy Slepian-Wolf problem where two correlated sources are separately encoded (using codes of fixed rate) and transmitted over two independent binary memoryless symmetric channels. The capacity of each channel is characterized by a single parameter which is not known at the transmitter. The goal is to design systems that retain near-optimal performance without channel knowledge at the transmitter. It was conjectured that it may be hard to design codes that perform well for symmetric channel conditions. In this work, we present a provable capacity-achieving sequence of LDGM ensembles for the erasure Slepian-Wolf problem with symmetric channel conditions. We also introduce a staggered structure which enables codes optimized for single user channels to perform well for symmetric channel conditions. We provide a generic framework for analyzing the performance of joint iterative decoding, using density evolution. Using differential evolution, we design punctured systematic LDPC codes to maximize the region of achievable channel conditions. The resulting codes are then staggered to further increase the region of achievable parameters. The main contribution of this paper is to demonstrate that properly designed irregular LDPC codes can perform well simultaneously over a wide range of channel parameters.
A Task Based Sensor-Centeric Model for overall Energy Consumption
Venue: arXiv cs.NI 2012
Year: 2012

Sensors have limited resources so it is important to manage the resources efficiently to maximize their use. A sensor's battery is a crucial resource as it singly determines the lifetime of sensor network applications. Since these devices are useful only when they are able to communicate with the world, radio transceiver of a sensor as an I/O and a costly unit plays a key role in its lifetime. This resource often consumes a big portion of the sensor's energy as it must be active most of the time to announce the existence of the sensor in the network. As such the radio component has to deal with its embedded sensor network whose parameters and operations have significant effects on the sensor's lifetime. In existing energy models, hardware is considered, but the environment and the network's parameters did not receive adequate attention. Energy consumption components of traditional network architecture are often considered individually and separately, and their influences on each other have not been considered in these approaches. In this paper we consider all possible tasks of a sensor in its embedded network and propose an energy management model. We categorize these tasks in five energy consuming constituents. The sensor's Energy Consumption (EC) is modeled on its energy consuming constituents and their input parameters and tasks. The sensor's EC can thus be reduced by managing and executing efficiently the tasks of its constituents. The proposed approach can be effective for power management, and it also can be used to guide the design of energy efficient wireless sensor networks through network parameterization and optimization.
Testing Substitutability of Weak Preferences
Venue: arXiv cs.GT 2012
Year: 2012

In many-to-many matching models, substitutable preferences constitute the largest domain for which a pairwise stable matching is guaranteed to exist. In this note, we extend the recently proposed algorithm of Hatfield et al. [3] to test substitutability of weak preferences. Interestingly, the algorithm is faster than the algorithm of Hatfield et al. by a linear factor on the domain of strict preferences.
Computing Critical $k$-tuples in Power Networks
Venue: arXiv cs.CE 2012
Year: 2012

In this paper the problem of finding the sparsest (i.e., minimum cardinality) critical $k$-tuple including one arbitrarily specified measurement is considered. The solution to this problem can be used to identify weak points in the measurement set, or aid the placement of new meters. The critical $k$-tuple problem is a combinatorial generalization of the critical measurement calculation problem. Using topological network observability results, this paper proposes an efficient and accurate approximate solution procedure for the considered problem based on solving a minimum-cut (Min-Cut) problem and enumerating all its optimal solutions. It is also shown that the sparsest critical $k$-tuple problem can be formulated as a mixed integer linear programming (MILP) problem. This MILP problem can be solved exactly using available solvers such as CPLEX and Gurobi. A detailed numerical study is presented to evaluate the efficiency and the accuracy of the proposed Min-Cut and MILP calculations.
Technical Note: Exploring Σ^P_2 / Π^P_2-hardness for Argumentation Problems with fixed distance to tractable classes
Venue: arXiv cs.AI 2012
Year: 2012

We study the complexity of reasoning in abstracts argumentation frameworks close to graph classes that allow for efficient reasoning methods, i.e.\ to one of the classes of acyclic, noeven, biparite and symmetric AFs. In this work we show that certain reasoning problems on the second level of the polynomial hierarchy still maintain their full complexity when restricted to instances of fixed distance to one of the above graph classes.
Noise vs computational intractability in dynamics
Venue: arXiv cs.CC 2012
Year: 2012

Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces -- unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to "destroy" Turing-completeness, and to make the system's long-term behavior computationally predictable. On a more technical level, we deal with long-term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. We also obtain some insight into the computational complexity of predicting systems affected by random noise.
A Novel Data-Aided Channel Estimation with Reduced Complexity for TDS-OFDM Systems
Venue: arXiv cs.NI 2012
Year: 2012

In contrast to the classical cyclic prefix (CP)-OFDM, the time domain synchronous (TDS)-OFDM employs a known pseudo noise (PN) sequence as guard interval (GI). Conventional channel estimation methods for TDS-OFDM are based on the exploitation of the PN sequence and consequently suffer from intersymbol interference (ISI). This paper proposes a novel dataaided channel estimation method which combines the channel estimates obtained from the PN sequence and, most importantly, additional channel estimates extracted from OFDM data symbols. Data-aided channel estimation is carried out using the rebuilt OFDM data symbols as virtual training sequences. In contrast to the classical turbo channel estimation, interleaving and decoding functions are not included in the feedback loop when rebuilding OFDM data symbols thereby reducing the complexity. Several improved techniques are proposed to refine the data-aided channel estimates, namely one-dimensional (1-D)/two-dimensional (2-D) moving average and Wiener filtering. Finally, the MMSE criteria is used to obtain the best combination results and an iterative process is proposed to progressively refine the estimation. Both MSE and BER simulations using specifications of the DTMB system are carried out to prove the effectiveness of the proposed algorithm even in very harsh channel conditions such as in the single frequency network (SFN) case.