OpenRaiser/Intern-Atlas huggingface dataset:
Evolving a New Feature for a Working Program
Venue: arXiv cs.NE 2011
Year: 2011

A genetic programming system is created. A first fitness function f1 is used to evolve a program that implements a first feature. Then the fitness function is switched to a second function f2, which is used to evolve a program that implements a second feature while still maintaining the first feature. The median number of generations G1 and G2 needed to evolve programs that work as defined by f1 and f2 are measured. The behavior of G1 and G2 are observed as the difficulty of the problem is increased. In these systems, the density D1 of programs that work (for fitness function f1) is measured in the general population of programs. The relationship G1~1/sqrt(D1) is observed to approximately hold. Also, the density D2 of programs that work (for fitness function f2) is measured in the general population of programs. The relationship G2~1/sqrt(D2) is observed to approximately hold.
Determining Relevance of Accesses at Runtime (Extended Version)
Venue: arXiv cs.DB 2011
Year: 2011

Consider the situation where a query is to be answered using Web sources that restrict the accesses that can be made on backend relational data by requiring some attributes to be given as input of the service. The accesses provide lookups on the collection of attributes values that match the binding. They can differ in whether or not they require arguments to be generated from prior accesses. Prior work has focused on the question of whether a query can be answered using a set of data sources, and in developing static access plans (e.g., Datalog programs) that implement query answering. We are interested in dynamic aspects of the query answering problem: given partial information about the data, which accesses could provide relevant data for answering a given query? We consider immediate and long-term notions of "relevant accesses", and ascertain the complexity of query relevance, for both conjunctive queries and arbitrary positive queries. In the process, we relate dynamic relevance of an access to query containment under access limitations and characterize the complexity of this problem; we produce several complexity results about containment that are of interest by themselves.
Visual Concept Detection and Real Time Object Detection
Venue: arXiv cs.CV 2011
Year: 2011

Bag-of-words model is implemented and tried on 10-class visual concept detection problem. The experimental results show that "DURF+ERT+SVM" outperforms "SIFT+ERT+SVM" both in detection performance and computation efficiency. Besides, combining DURF and SIFT results in even better detection performance. Real-time object detection using SIFT and RANSAC is also tried on simple objects, e.g. drink can, and good result is achieved.
Modeling Internet Security Investments: The Case of Dealing with Information Uncertainty
Venue: arXiv cs.CR 2011
Year: 2011

Modern distributed communication networks like the Internet and censorship-resistant networks (also a part of the Internet) are characterized by nodes (users) interconnected with one another via communication links. In this regard, the security of individual nodes depend not only on their own efforts, but also on the efforts and underlying connectivity structure of neighboring network nodes. By the term 'effort', we imply the amount of investments made by a user in security mechanisms like antivirus softwares, firewalls, etc., to improve its security. However, often due to the large magnitude of such networks, it is not always possible for nodes to have complete effort and connectivity structure information about all their neighbor nodes. Added to this is the fact that in many applications, the Internet users are selfish and are not willing to co-operate with other users on sharing effort information. In this paper, we adopt a non-cooperative game-theoretic approach to analyze individual user security in a communication network by accounting for both, the partial information that a network node possess about its underlying neighborhood connectivity structure, as well as the presence of positive externalities arising from efforts exerted by neighboring nodes. We investigate the equilibrium behavior of nodes and show 1) the existence of symmetric Bayesian Nash equilibria of efforts and 2) better connected nodes choose lower efforts to exert but earn higher utilities with respect to security improvement irrespective of the nature of node degree correlations amongst the neighboring nodes. Our results provide ways for Internet users to appropriately invest in security mechanisms under realistic environments of information uncertainty.
Real-Time Video Streaming in Multi-hop Wireless Static Ad Hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

We deal with the problem of streaming multiple video streams between pairs of nodes in a multi-hop wireless ad hoc network. The nodes are static, know their locations, and are synchronized (via GPS). We introduce a new interference model that uses variable interference radiuses. We present an algorithm for computing a frequency assignment and a schedule whose goal is to maximize throughput over all the video streams. In addition, we developed a localized flow-control mechanism to stabilize the queue lengths. We simulated traffic scheduled by the algorithm using OMNET++/MixiM (i.e., physical SINR interference model with 802.11g) to test whether the computed throughput is achieved. The results of the simulation show that the computed solution is \SINR-feasible and achieves predictable stable throughputs.
Video Encryption: A Survey
Venue: arXiv cs.CR 2011
Year: 2011

Multimedia data security is becoming important with the continuous increase of digital communications on internet. The encryption algorithms developed to secure text data are not suitable for multimedia application because of the large data size and real time constraint. In this paper, classification and description of various video encryption algorithms are presented. Analysis and Comparison of these algorithms with respect to various parameters like visual degradation, encryption ratio, speed, compression friendliness, format compliance and cryptographic security is presented.
On the Degrees of Freedom Achievable Through Interference Alignment in a MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

Consider a K-user flat fading MIMO interference channel where the k-th transmitter (or receiver) is equipped with M_k (respectively N_k) antennas. If a large number of statistically independent channel extensions are allowed either across time or frequency, the recent work [1] suggests that the total achievable degrees of freedom (DoF) can be maximized via interference alignment, resulting in a total DoF that grows linearly with K even if M_k and N_k are bounded. In this work we consider the case where no channel extension is allowed, and establish a general condition that must be satisfied by any degrees of freedom tuple (d_1, d2, ..., d_K) achievable through linear interference alignment. For a symmetric system with M_k = M, N_k = N, d_k = d for all k, this condition implies that the total achievable DoF cannot grow linearly with K, and is in fact no more than K(M + N)=(K + 1). We also show that this bound is tight when the number of antennas at each transceiver is divisible by the number of data streams.
Evolution of Computer Virus Concealment and Anti-Virus Techniques: A Short Survey
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents a general overview on evolution of concealment methods in computer viruses and defensive techniques employed by anti-virus products. In order to stay far from the anti-virus scanners, computer viruses gradually improve their codes to make them invisible. On the other hand, anti-virus technologies continually follow the virus tricks and methodologies to overcome their threats. In this process, anti-virus experts design and develop new methodologies to make them stronger, more and more, every day. The purpose of this paper is to review these methodologies and outline their strengths and weaknesses to encourage those are interested in more investigation on these areas.
High-Rate Short-Block LDPC Codes for Iterative Decoding with Applications to High-Density Magnetic Recording Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the Triangle Single Parity Check (T/SPC) code, a novel class of high-rate low-complexity LDPC codes. T/SPC is a regular, soft decodable, linear-time encodable/decodable code. Compared to previous high-rate and low-complexity LDPC codes, such as the well-known Turbo Product Code / Single Parity Check (TPC/SPC), T/SPC provides higher code rates, shorter code words, and lower complexity. This makes T/SPC very attractive for practical implementation on integrated circuits. In addition, we analyze the performance of iterative decoders based on a soft-input soft-output (SISO) equalizer using T/SPC over high-density perpendicular magnetic recording channels. Computer simulations show that the proposed scheme is able to achieve a gain of up to 0.3 dB over TPC/SPC codes with a significant reduction of implementation complexity.
Benchmarking the Quality of Diffusion-Weighted Images
Venue: arXiv cs.CV 2011
Year: 2011

We present a novel method that allows for measuring the quality of diffusion-weighted MR images dependent on the image resolution and the image noise. For this purpose, we introduce a new thresholding technique so that noise and the signal can automatically be estimated from a single data set. Thus, no user interaction as well as no double acquisition technique, which requires a time-consuming proper geometrical registration, is needed. As a coarser image resolution or slice thickness leads to a higher signal-to-noise ratio (SNR), our benchmark determines a resolution-independent quality measure so that images with different resolutions can be adequately compared. To evaluate our method, a set of diffusion-weighted images from different vendors is used. It is shown that the quality can efficiently be determined and that the automatically computed SNR is comparable to the SNR which is measured manually in a manually selected region of interest.
Effective partitioning method for computing weighted Moore-Penrose inverse
Venue: arXiv cs.SC 2011
Year: 2011

We introduce a method and an algorithm for computing the weighted Moore-Penrose inverse of multiple-variable polynomial matrix and the related algorithm which is appropriated for sparse polynomial matrices. These methods and algorithms are generalizations of algorithms developed in [M.B. Tasic, P.S. Stanimirovic, M.D. Petkovic, Symbolic computation of weighted Moore-Penrose inverse using partitioning method, Appl. Math. Comput. 189 (2007) 615-640] to multiple-variable rational and polynomial matrices and improvements of these algorithms on sparse matrices. Also, these methods are generalizations of the partitioning method for computing the Moore-Penrose inverse of rational and polynomial matrices introduced in [P.S. Stanimirovic, M.B. Tasic, Partitioning method for rational and polynomial matrices, Appl. Math. Comput. 155 (2004) 137-163; M.D. Petkovic, P.S. Stanimirovic, Symbolic computation of the Moore-Penrose inverse using partitioning method, Internat. J. Comput. Math. 82 (2005) 355-367] to the case of weighted Moore-Penrose inverse. Algorithms are implemented in the symbolic computational package MATHEMATICA.
About the generalized LM-inverse and the weighted Moore-Penrose inverse
Venue: arXiv cs.SC 2011
Year: 2011

The recursive method for computing the generalized LM-inverse of a constant rectangular matrix augmented by a column vector is proposed in Udwadia and Phohomsiri (2007) [16] and [17]. The corresponding algorithm for the sequential determination of the generalized LM-inverse is established in the present paper. We prove that the introduced algorithm for computing the generalized LM-inverse and the algorithm for the computation of the weighted Moore-Penrose inverse developed by Wang and Chen (1986) in [23] are equivalent algorithms. Both of the algorithms are implemented in the present paper using the package MATHEMATICA. Several rational test matrices and randomly generated constant matrices are tested and the CPU time is compared and discussed.
Expression Templates Revisited: A Performance Analysis of the Current ET Methodology
Venue: arXiv cs.PF 2011
Year: 2011

In the last decade, Expression Templates (ET) have gained a reputation as an efficient performance optimization tool for C++ codes. This reputation builds on several ET-based linear algebra frameworks focused on combining both elegant and high-performance C++ code. However, on closer examination the assumption that ETs are a performance optimization technique cannot be maintained. In this paper we demonstrate and explain the inability of current ET-based frameworks to deliver high performance for dense and sparse linear algebra operations, and introduce a new "smart" ET implementation that truly allows the combination of high performance code with the elegance and maintainability of a domain-specific language.
Wet paper codes and the dual distance in steganography
Venue: arXiv cs.CR 2011
Year: 2011

In 1998 Crandall introduced a method based on coding theory to secretly embed a message in a digital support such as an image. Later Fridrich et al. improved this method to minimize the distortion introduced by the embedding; a process called wet paper. However, as previously emphasized in the literature, this method can fail during the embedding step. Here we find sufficient and necessary conditions to guarantee a successful embedding by studying the dual distance of a linear code. Since these results are essentially of combinatorial nature, they can be generalized to systematic codes, a large family containing all linear codes. We also compute the exact number of solutions and point out the relationship between wet paper codes and orthogonal arrays.
Amortised Resource Analysis with Separation Logic
Venue: arXiv cs.LO 2011
Year: 2011

Type-based amortised resource analysis following Hofmann and Jost---where resources are associated with individual elements of data structures and doled out to the programmer under a linear typing discipline---have been successful in providing concrete resource bounds for functional programs, with good support for inference. In this work we translate the idea of amortised resource analysis to imperative pointer-manipulating languages by embedding a logic of resources, based on the affine intuitionistic Logic of Bunched Implications, within Separation Logic. The Separation Logic component allows us to assert the presence and shape of mutable data structures on the heap, while the resource component allows us to state the consumable resources associated with each member of the structure. We present the logic on a small imperative language, based on Java bytecode, with procedures and mutable heap. We have formalised the logic and its soundness property within the Coq proof assistant and extracted a certified verification condition generator. We also describe an proof search procedure that allows generated verification conditions to be discharged while using linear programming to infer consumable resource annotations. We demonstrate the logic on some examples, including proving the termination of in-place list reversal on lists with cyclic tails.
Statistical Beamforming on the Grassmann Manifold for the Two-User Broadcast Channel
Venue: arXiv cs.IT 2011
Year: 2011

A Rayleigh fading spatially correlated broadcast setting with M = 2 antennas at the transmitter and two-users (each with a single antenna) is considered. It is assumed that the users have perfect channel information about their links whereas the transmitter has only statistical information of each user's link (covariance matrix of the vector channel). A low-complexity linear beamforming strategy that allocates equal power and one spatial eigen-mode to each user is employed at the transmitter. Beamforming vectors on the Grassmann manifold that depend only on statistical information are to be designed at the transmitter to maximize the ergodic sum-rate delivered to the two users. Towards this goal, the beamforming vectors are first fixed and a closed-form expression is obtained for the ergodic sum-rate in terms of the covariance matrices of the links. This expression is non-convex in the beamforming vectors ensuring that the classical Lagrange multiplier technique is not applicable. Despite this difficulty, the optimal solution to this problem is shown to be the solution to the maximization of an appropriately-defined average signal-to-interference and noise ratio (SINR) metric for each user. This solution is the dominant generalized eigenvector of a pair of positive-definite matrices where the first matrix is the covariance matrix of the forward link and the second is an appropriately-designed "effective" interference covariance matrix. In this sense, our work is a generalization of optimal signalling along the dominant eigen-mode of the transmit covariance matrix in the single-user case. Finally, the ergodic sum-rate for the general broadcast setting with M antennas at the transmitter and M-users (each with a single antenna) is obtained in terms of the covariance matrices of the links and the beamforming vectors.
A Case for a Global Information Network
Venue: arXiv cs.NI 2011
Year: 2011

This paper argues for the adoption of a information centric system model instead of the current service-oriented one. We present an architecture for a global information storage and dissemination network which provides for efficient interaction and coordination among autonomous actors through a shared information space. We believe that the resulting, loosely coupled systems, while probabilistic in nature, will lead to robust outcomes at large scales.
From a Modified Ambrosio-Tortorelli to a Randomized Part Hierarchy Tree
Venue: arXiv cs.CV 2011
Year: 2011

We demonstrate the possibility of coding parts, features that are higher level than boundaries, using a modified AT field after augmenting the interaction term of the AT energy with a non-local term and weakening the separation into boundary/not-boundary phases. The iteratively extracted parts using the level curves with double point singularities are organized as a proper binary tree. Inconsistencies due to non-generic configurations for level curves as well as due to visual changes such as occlusion are successfully handled once the tree is endowed with a probabilistic structure. The work is a step in establishing the AT function as a bridge between low and high level visual processing.
Experimental Investigation of Forecasting Methods Based on Universal Measures
Venue: arXiv cs.IT 2011
Year: 2011

We describe and experimentally investigate a method to construct forecasting algorithms for stationary and ergodic processes based on universal measures (or so-called universal data compressors). Using some geophysical and economical time series as examples, we show that the precision of thus obtained predictions is higher than that of known methods.
Reactive Imperative Programming with Dataflow Constraints
Venue: arXiv cs.PL 2011
Year: 2011

Dataflow languages provide natural support for specifying constraints between objects in dynamic applications, where programs need to react efficiently to changes of their environment. Researchers have long investigated how to take advantage of dataflow constraints by embedding them into procedural languages. Previous mixed imperative/dataflow systems, however, require syntactic extensions or libraries of ad hoc data types for binding the imperative program to the dataflow solver. In this paper we propose a novel approach that smoothly combines the two paradigms without placing undue burden on the programmer. In our framework, programmers can define ordinary commands of the host imperative language that enforce constraints between objects stored in "reactive" memory locations. Reactive objects can be of any legal type in the host language, including primitive data types, pointers, arrays, and structures. Constraints are automatically re-executed every time their input memory locations change, letting a program behave like a spreadsheet where the values of some variables depend upon the values of other variables. The constraint solving mechanism is handled transparently by altering the semantics of elementary operations of the host language for reading and modifying objects. We provide a formal semantics and describe a concrete embodiment of our technique into C/C++, showing how to implement it efficiently in conventional platforms using off-the-shelf compilers. We discuss relevant applications to reactive scenarios, including incremental computation, observer design pattern, and data structure repair. The performance of our implementation is compared to ad hoc problem-specific change propagation algorithms and to language-centric approaches such as self-adjusting computation and subject/observer communication mechanisms, showing that the proposed approach is efficient in practice.
Computational Complexity on Signed Numbers
Venue: arXiv cs.CC 2011
Year: 2011

This paper presents a new representation of natural numbers and discusses its consequences for computability and computational complexity. The paper argues that the introduction of the first Peano axiom in the traditional definition of natural numbers is not essential. It claims that natural numbers remain usable in traditional ways without assuming the existence of at least one natural number. However, the uncertainty about the existence of natural numbers translates into every computation and introduces intrinsic uncertainty that cannot be avoided. The uncertainty in the output of a computation can be reduced, though, at the expense of a longer runtime and thus higher complexity. For the new representation of natural numbers, the paper claims that, with the first Peano axiom, P is equal to NP, and that without the first Peano axiom, P becomes a proper subset of NP.
Load-Balancing Spatially Located Computations using Rectangular Partitions
Venue: arXiv cs.DC 2011
Year: 2011

Distributing spatially located heterogeneous workloads is an important problem in parallel scientific computing. We investigate the problem of partitioning such workloads (represented as a matrix of non-negative integers) into rectangles, such that the load of the most loaded rectangle (processor) is minimized. Since finding the optimal arbitrary rectangle-based partition is an NP-hard problem, we investigate particular classes of solutions: rectilinear, jagged and hierarchical. We present a new class of solutions called m-way jagged partitions, propose new optimal algorithms for m-way jagged partitions and hierarchical partitions, propose new heuristic algorithms, and provide worst case performance analyses for some existing and new heuristics. Moreover, the algorithms are tested in simulation on a wide set of instances. Results show that two of the algorithms we introduce lead to a much better load balance than the state-of-the-art algorithms. We also show how to design a two-phase algorithm that reaches different time/quality tradeoff.
Liquidsoap: a High-Level Programming Language for Multimedia Streaming
Venue: arXiv cs.PL 2011
Year: 2011

Generating multimedia streams, such as in a netradio, is a task which is complex and difficult to adapt to every users' needs. We introduce a novel approach in order to achieve it, based on a dedicated high-level functional programming language, called Liquidsoap, for generating, manipulating and broadcasting multimedia streams. Unlike traditional approaches, which are based on configuration files or static graphical interfaces, it also allows the user to build complex and highly customized systems. This language is based on a model for streams and contains operators and constructions, which make it adapted to the generation of streams. The interpreter of the language also ensures many properties concerning the good execution of the stream generation.