OpenRaiser/Intern-Atlas huggingface dataset:
Strong Equivalence of Qualitative Optimization Problems
Venue: arXiv cs.LO 2011
Year: 2011

We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.
Performance Study on Image Encryption Schemes
Venue: arXiv cs.CR 2011
Year: 2011

Image applications have been increasing in recent years.Encryption is used to provide the security needed for image applications. In this paper, we classify various image encryption schemes and analyze them with respect to various parameters like tunability, visual degradation, compression friendliness,format compliance, encryption ratio, speed, and cryptographic security.
Interleaved Product LDPC Codes
Venue: arXiv cs.IT 2011
Year: 2011

Product LDPC codes take advantage of LDPC decoding algorithms and the high minimum distance of product codes. We propose to add suitable interleavers to improve the waterfall performance of LDPC decoding. Interleaving also reduces the number of low weight codewords, that gives a further advantage in the error floor region.
Class of Trustworthy Pseudo-Random Number Generators
Venue: arXiv cs.CR 2011
Year: 2011

With the widespread use of communication technologies, cryptosystems are therefore critical to guarantee security over open networks as the Internet. Pseudo-random number generators (PRNGs) are fundamental in cryptosystems and information hiding schemes. One of the existing chaos-based PRNGs is using chaotic iterations schemes. In prior literature, the iterate function is just the vectorial boolean negation. In this paper, we propose a method using Graph with strongly connected components as a selection criterion for chaotic iterate function. In order to face the challenge of using the proposed chaotic iterate functions in PRNG, these PRNGs are subjected to a statistical battery of tests, which is the well-known NIST in the area of cryptography.
Secretary Problems with Convex Costs
Venue: arXiv cs.DS 2011
Year: 2011

We consider online resource allocation problems where given a set of requests our goal is to select a subset that maximizes a value minus cost type of objective function. Requests are presented online in random order, and each request possesses an adversarial value and an adversarial size. The online algorithm must make an irrevocable accept/reject decision as soon as it sees each request. The "profit" of a set of accepted requests is its total value minus a convex cost function of its total size. This problem falls within the framework of secretary problems. Unlike previous work in that area, one of the main challenges we face is that the objective function can be positive or negative and we must guard against accepting requests that look good early on but cause the solution to have an arbitrarily large cost as more requests are accepted. This requires designing new techniques. We study this problem under various feasibility constraints and present online algorithms with competitive ratios only a constant factor worse than those known in the absence of costs for the same feasibility constraints. We also consider a multi-dimensional version of the problem that generalizes multi-dimensional knapsack within a secretary framework. In the absence of any feasibility constraints, we present an O(l) competitive algorithm where l is the number of dimensions; this matches within constant factors the best known ratio for multi-dimensional knapsack secretary.
Performance Analysis of a Keyed Hash Function based on Discrete and Chaotic Proven Iterations
Venue: arXiv cs.CR 2011
Year: 2011

Security of information transmitted through the Internet is an international concern. This security is guaranteed by tools like hash functions. However, as security flaws have been recently identified in the current standard in this domain, new ways to hash digital media must be investigated. In this document an original keyed hash function is evaluated. It is based on chaotic iterations and thus possesses various topological properties as uniform repartition and sensibility to its initial condition. These properties make our hash function satisfy the requirements in this field. This claim is verified qualitatively and experimentally in this research work, among other things by realizing simulations of diffusion and confusion.
Additive schemes (splitting schemes) for some systems of evolutionary equations
Venue: arXiv cs.NA 2011
Year: 2011

On the basis of additive schemes (splitting schemes) we construct efficient numerical algorithms to solve approximately the initial-boundary value problems for systems of time-dependent partial differential equations (PDEs). In many applied problems the individual components of the vector of unknowns are coupled together and then splitting schemes are applied in order to get a simple problem for evaluating components at a new time level. Typically, the additive operator-difference schemes for systems of evolutionary equations are constructed for operators coupled in space. In this paper we investigate more general problems where coupling of derivatives in time for components of the solution vector takes place. Splitting schemes are developed using an additive representation for both the primary operator of the problem and the operator at the time derivative. Splitting schemes are based on a triangular two-component representation of the operators.
Multi-granular Perspectives on Covering
Venue: arXiv cs.AI 2011
Year: 2011

Covering model provides a general framework for granular computing in that overlapping among granules are almost indispensable. For any given covering, both intersection and union of covering blocks containing an element are exploited as granules to form granular worlds at different abstraction levels, respectively, and transformations among these different granular worlds are also discussed. As an application of the presented multi-granular perspective on covering, relational interpretation and axiomization of four types of covering based rough upper approximation operators are investigated, which can be dually applied to lower ones.
Low-delay, High-rate Non-square Complex Orthogonal Designs
Venue: arXiv cs.IT 2011
Year: 2011

The maximal rate of a non-square complex orthogonal design for $n$ transmit antennas is $1/2+\frac{1}{n}$ if $n$ is even and $1/2+\frac{1}{n+1}$ if $n$ is odd and the codes have been constructed for all $n$ by Liang (IEEE Trans. Inform. Theory, 2003) and Lu et al. (IEEE Trans. Inform. Theory, 2005) to achieve this rate. A lower bound on the decoding delay of maximal-rate complex orthogonal designs has been obtained by Adams et al. (IEEE Trans. Inform. Theory, 2007) and it is observed that Liang's construction achieves the bound on delay for $n$ equal to 1 and 3 modulo 4 while Lu et al.'s construction achieves the bound for $n=0,1,3$ mod 4. For $n=2$ mod 4, Adams et al. (IEEE Trans. Inform. Theory, 2010) have shown that the minimal decoding delay is twice the lower bound, in which case, both Liang's and Lu at al.'s construction achieve the minimum decoding delay. % when $n=2$ mod 4. For large value of $n$, it is observed that the rate is close to half and the decoding delay is very large. A class of rate-1/2 codes with low decoding delay for all $n$ has been constructed by Tarokh et al. (IEEE Trans. Inform. Theory, 1999). % have constructed a class of rate-1/2 codes with low decoding delay for all $n$. In this paper, another class of rate-1/2 codes is constructed for all $n$ in which case the decoding delay is half the decoding delay of the rate-1/2 codes given by Tarokh et al. This is achieved by giving first a general construction of square real orthogonal designs which includes as special cases the well-known constructions of Adams, Lax and Phillips and the construction of Geramita and Pullman, and then making use of it to obtain the desired rate-1/2 codes. For the case of 9 transmit antennas, the proposed rate-1/2 code is shown to be of minimal-delay.
A literature review: What exactly should we preserve? How scholars address this question and where is the gap
Venue: arXiv cs.DL 2011
Year: 2011

This review addresses the question of what exactly should we preserve, and how the digital preservation community and scholars address this question. The paper first introduces the much-abused-term "significant properties," before revealing how some scholars are of the opinion that characteristics of digital objects to be preserved (i.e., significant properties) can be identified and should be expressed formally, while others are not of that opinion. The digital preservation community's attempt to expound on the general characteristics of digital objects and significant properties will then be discussed. Finally, the review shows that while there may be ways to identify the technical makeup or general characteristics of a digital object, there is currently no formal and objective methodology to help stakeholders identify and decide what the significant properties of the objects are. This review thus helps open questions and generates a formative recommendation based on expert opinion that expressing an object's functions in an explicit and formal way (using didactic guides from the archives community) could be the solution to help stakeholders decide what characteristics/ elements exactly we should preserve.
Bipartite ranking algorithm for classification and survival analysis
Venue: arXiv cs.LG 2011
Year: 2011

Unsupervised aggregation of independently built univariate predictors is explored as an alternative regularization approach for noisy, sparse datasets. Bipartite ranking algorithm Smooth Rank implementing this approach is introduced. The advantages of this algorithm are demonstrated on two types of problems. First, Smooth Rank is applied to two-class problems from bio-medical field, where ranking is often preferable to classification. In comparison against SVMs with radial and linear kernels, Smooth Rank had the best performance on 8 out of 12 benchmark benchmarks. The second area of application is survival analysis, which is reduced here to bipartite ranking in a way which allows one to use commonly accepted measures of methods performance. In comparison of Smooth Rank with Cox PH regression and CoxPath methods, Smooth Rank proved to be the best on 9 out of 10 benchmark datasets.
Lie algebra conjugacy
Venue: arXiv cs.CC 2011
Year: 2011

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set L of matrices such that $A, B\in L$ implies $AB - BA \in L$. Two matrix Lie algebras are conjugate if there is an invertible matrix $M$ such that $L_1 = M L_2 M^{-1}$. We show that certain cases of Lie algebra conjugacy are equivalent to graph isomorphism. On the other hand, we give polynomial-time algorithms for other cases of Lie algebra conjugacy, which allow us to essentially derandomize a recent result of Kayal on affine equivalence of polynomials. Affine equivalence is related to many complexity problems such as factoring integers, graph isomorphism, matrix multiplication, and permanent versus determinant. Specifically, we show: Abelian Lie algebra conjugacy is equivalent to the code equivalence problem, and hence is as hard as graph isomorphism. Abelian Lie algebra conjugacy of $n \times n$ matrices can be solved in poly(n) time when the Lie algebras have dimension O(1). Semisimple Lie algebra conjugacy is equivalent to graph isomorphism. A Lie algebra is semisimple if it is a direct sum of simple Lie algebras. Semisimple Lie algebra conjugacy of $n \times n$ matrices can be solved in polynomial time when the Lie algebras consist of only $O(\log n)$ simple direct summands. Conjugacy of completely reducible Lie algebras---that is, a direct sum of an abelian and a semisimple Lie algebra---can be solved in polynomial time when the abelian part has dimension O(1) and the semisimple part has $O(\log n)$ simple direct summands.
ECAKP: Encrypt Collect Authenticate Kill Play
Venue: arXiv cs.CR 2011
Year: 2011

We are taught from a young age that plagiarism (copying other's work) is wrong. However, the problem of Illegal copies of multimedia data is exacerbated by the widespread availability of circumvention devices, which enable people to make infringing copies of multimedia data. Recently, Joint Video Compression and Encryption (JVCE) has gained increased attention to reduce the computational complexity of video compression, as well as provide encryption of multimedia data. In this paper, a novel protection method for multimedia data (ECAKP) is proposed. It combines encryption process and compression with authenticating process. The method had been implemented and the results are discussed in detail.
Modelling Gesture Based Ubiquitous Applications
Venue: arXiv cs.MM 2011
Year: 2011

A cost effective, gesture based modelling technique called Virtual Interactive Prototyping (VIP) is described in this paper. Prototyping is implemented by projecting a virtual model of the equipment to be prototyped. Users can interact with the virtual model like the original working equipment. For capturing and tracking the user interactions with the model image and sound processing techniques are used. VIP is a flexible and interactive prototyping method that has much application in ubiquitous computing environments. Different commercial as well as socio-economic applications and extension to interactive advertising of VIP are also discussed.
An Information Theoretic Analysis of Decision in Computer Chess
Venue: arXiv cs.AI 2011
Year: 2011

The basis of the method proposed in this article is the idea that information is one of the most important factors in strategic decisions, including decisions in computer chess and other strategy games. The model proposed in this article and the algorithm described are based on the idea of a information theoretic basis of decision in strategy games . The model generalizes and provides a mathematical justification for one of the most popular search algorithms used in leading computer chess programs, the fractional ply scheme. However, despite its success in leading computer chess applications, until now few has been published about this method. The article creates a fundamental basis for this method in the axioms of information theory, then derives the principles used in programming the search and describes mathematically the form of the coefficients. One of the most important parameters of the fractional ply search is derived from fundamental principles. Until now this coefficient has been usually handcrafted or determined from intuitive elements or data mining. There is a deep, information theoretical justification for such a parameter. In one way the method proposed is a generalization of previous methods. More important, it shows why the fractional depth ply scheme is so powerful. It is because the algorithm navigates along the lines where the highest information gain is possible. A working and original implementation has been written and tested for this algorithm and is provided in the appendix. The article is essentially self-contained and gives proper background knowledge and references. The assumptions are intuitive and in the direction expected and described intuitively by great champions of chess.
Information and Search in Computer Chess
Venue: arXiv cs.AI 2011
Year: 2011

The article describes a model of chess based on information theory. A mathematical model of the partial depth scheme is outlined and a formula for the partial depth added for each ply is calculated from the principles of the model. An implementation of alpha-beta with partial depth is given. The method is tested using an experimental strategy having as objective to show the effect of allocation of a higher amount of search resources on areas of the search tree with higher information. The search proceeds in the direction of lines with higher information gain. The effects on search performance of allocating higher search resources on lines with higher information gain are tested experimentaly and conclusive results are obtained. In order to isolate the effects of the partial depth scheme no other heuristic is used.
The Expert System Designed to Improve Customer Satisfaction
Venue: arXiv cs.NE 2011
Year: 2011

Customer Relationship Management becomes a leading business strategy in highly competitive business environment. It aims to enhance the performance of the businesses by improving the customer satisfaction and loyalty. The objective of this paper is to improve customer satisfaction on product's colors and design with the help of the expert system developed by using Artificial Neural Networks. The expert system's role is to capture the knowledge of the experts and the data from the customer requirements, and then, process the collected data and form the appropriate rules for choosing product's colors and design. In order to identify the hidden pattern of the customer's needs, the Artificial Neural Networks technique has been applied to classify the colors and design based upon a list of selected information. Moreover, the expert system has the capability to make decisions in ranking the scores of the colors and design presented in the selection. In addition, the expert system has been validated with a different customer types.
Chinese Restaurant Game - Part II: Applications to Wireless Networking, Cloud Computing, and Online Social Networking
Venue: arXiv cs.SI 2011
Year: 2011

In Part I of this two-part paper [1], we proposed a new game, called Chinese restaurant game, to analyze the social learning problem with negative network externality. The best responses of agents in the Chinese restaurant game with imperfect signals are constructed through a recursive method, and the influence of both learning and network externality on the utilities of agents is studied. In Part II of this two-part paper, we illustrate three applications of Chinese restaurant game in wireless networking, cloud computing, and online social networking. For each application, we formulate the corresponding problem as a Chinese restaurant game and analyze how agents learn and make strategic decisions in the problem. The proposed method is compared with four common-sense methods in terms of agents' utilities and the overall system performance through simulations. We find that the proposed Chinese restaurant game theoretic approach indeed helps agents make better decisions and improves the overall system performance. Furthermore, agents with different decision orders have different advantages in terms of their utilities, which also verifies the conclusions drawn in Part I of this two-part paper.
A Survey on Cooperative Diversity and Its Applications in Various Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Cooperative diversity is a technique in which various radio terminals relay signals for each other. Cooperative diversity results when cooperative communications is used primarily to leverage the spatial diversity available among distributed radios. In this paper different cooperative diversity schemes and their applications in various wireless networks are discussed. In this paper the impact of cooperative diversity on the energy consumption and lifetime of sensor network and the impact of cooperation in cognitive radio are discussed. Here, user scheduling and radio resource allocation techniques are also discussed which are developed in order to efficiently integrate various cooperative diversity schemes for the emerging IEEE 802.16j based systems.
A duality between exceptions and states
Venue: arXiv cs.LO 2011
Year: 2011

In this short note we study the semantics of two basic computational effects, exceptions and states, from a new point of view. In the handling of exceptions we dissociate the control from the elementary operation which recovers from the exception. In this way it becomes apparent that there is a duality, in the categorical sense, between exceptions and states.
Medium Access Control Protocols for Wireless Sensor Networks with Energy Harvesting
Venue: arXiv cs.IT 2011
Year: 2011

The design of Medium Access Control (MAC) protocols for wireless sensor networks (WSNs) has been conventionally tackled by assuming battery-powered devices and by adopting the network lifetime as the main performance criterion. While WSNs operated by energy-harvesting (EH) devices are not limited by network lifetime, they pose new design challenges due to the uncertain amount of harvestable energy. Novel design criteria are thus required to capture the trade-offs between the potentially infinite network lifetime and the uncertain energy availability. This paper addresses the analysis and design of WSNs with EH devices by focusing on conventional MAC protocols, namely TDMA, Framed-ALOHA (FA) and Dynamic-FA (DFA), and by accounting for the performance trade-offs and design issues arising due to EH. A novel metric, referred to as delivery probability, is introduced to measure the capability of a MAC protocol to deliver the measure of any sensor in the network to the intended destination (or fusion center, FC). The interplay between delivery efficiency and time efficiency (i.e., the data collection rate at the FC), is investigated analytically using Markov models. Numerical results validate the analysis and emphasize the critical importance of accounting for both delivery probability and time efficiency in the design of EH-WSNs.
A Mediated Definite Delegation Model allowing for Certified Grid Job Submission
Venue: arXiv cs.DC 2011
Year: 2011

Grid computing infrastructures need to provide traceability and accounting of their users" activity and protection against misuse and privilege escalation. A central aspect of multi-user Grid job environments is the necessary delegation of privileges in the course of a job submission. With respect to these generic requirements this document describes an improved handling of multi-user Grid jobs in the ALICE ("A Large Ion Collider Experiment") Grid Services. A security analysis of the ALICE Grid job model is presented with derived security objectives, followed by a discussion of existing approaches of unrestricted delegation based on X.509 proxy certificates and the Grid middleware gLExec. Unrestricted delegation has severe security consequences and limitations, most importantly allowing for identity theft and forgery of delegated assignments. These limitations are discussed and formulated, both in general and with respect to an adoption in line with multi-user Grid jobs. Based on the architecture of the ALICE Grid Services, a new general model of mediated definite delegation is developed and formulated, allowing a broker to assign context-sensitive user privileges to agents. The model provides strong accountability and long- term traceability. A prototype implementation allowing for certified Grid jobs is presented including a potential interaction with gLExec. The achieved improvements regarding system security, malicious job exploitation, identity protection, and accountability are emphasized, followed by a discussion of non- repudiation in the face of malicious Grid jobs.