OpenRaiser/Intern-Atlas huggingface dataset:
The nature of individual choice: a formalism for utility function based on set theory
Venue: arXiv cs.GT 2010
Year: 2010

In the theory of social choice the research is focused around the projection of individual preference orders to the social preference order. Also, the justification of the preference order formalism begins with the concept of utility i.e. an alternative is preferred to another one if the utility over the first is higher then the utility over the second. In this paper is proposed an ideal model of measuring utilities by considering individuals and alternatives no more as atomic concepts but as being composed by other entities. Furthermore is proposed a formal definition of evaluation processes based on utilities.
Multiparty Equality Function Computation in Networks with Point-to-Point Links
Venue: arXiv cs.IT 2010
Year: 2010

In this report, we study the multiparty communication complexity problem of the multiparty equality function (MEQ): EQ(x_1,...,x_n) = 1 if x_1=...=x_n, and 0 otherwise. The input vector (x_1,...,x_n) is distributed among n>=2 nodes, with x_i known to node i, where x_i is chosen from the set {1,...,M}, for some integer M>0. Instead of the "number on the forehand" model, we consider a point-to-point communication model (similar to the message passing model), which we believe is more realistic in networking settings. We assume a synchronous fully connected network of n nodes, the node IDs (identifiers) are common knowledge. We assume that all point-to-point communication channels/links are private such that when a node transmits, only the designated recipient can receive the message. The identity of the sender is known to the recipient. We demonstrate that traditional techniques generalized from two-party communication complexity problem are not sufficient to obtain tight bounds under the point-to-point communication model. We then introduce techniques which significantly reduce the space of protocols to study. These techniques are used to study some instances of the MEQ problem.
Multiple Parameter Estimation With Quantized Channel Output
Venue: arXiv cs.IT 2010
Year: 2010

We present a general problem formulation for optimal parameter estimation based on quantized observations, with application to antenna array communication and processing (channel estimation, time-of-arrival (TOA) and direction-of-arrival (DOA) estimation). The work is of interest in the case when low resolution A/D-converters (ADCs) have to be used to enable higher sampling rate and to simplify the hardware. An Expectation-Maximization (EM) based algorithm is proposed for solving this problem in a general setting. Besides, we derive the Cramer-Rao Bound (CRB) and discuss the effects of quantization and the optimal choice of the ADC characteristic. Numerical and analytical analysis reveals that reliable estimation may still be possible even when the quantization is very coarse.
A Graphical Approach to Progress for Structured Communication in Web Services
Venue: arXiv cs.PL 2010
Year: 2010

We investigate a graphical representation of session invocation interdependency in order to prove progress for the pi-calculus with sessions under the usual session typing discipline. We show that those processes whose associated dependency graph is acyclic can be brought to reduce. We call such processes transparent processes. Additionally, we prove that for well-typed processes where services contain no free names, such acyclicity is preserved by the reduction semantics. Our results encompass programs (processes containing neither free nor restricted session channels) and higher-order sessions (delegation). Furthermore, we give examples suggesting that transparent processes constitute a large enough class of processes with progress to have applications in modern session-based programming languages for web services.
Safer in the Clouds (Extended Abstract)
Venue: arXiv cs.CR 2010
Year: 2010

We outline the design of a framework for modelling cloud computing systems.The approach is based on a declarative programming model which takes the form of a lambda-calculus enriched with suitable mechanisms to express and enforce application-level security policies governing usages of resources available in the clouds. We will focus on the server side of cloud systems, by adopting a pro-active approach, where explicit security policies regulate server's behaviour.
A linear programming approach to general dataflow process network verification and dimensioning
Venue: arXiv cs.DC 2010
Year: 2010

In this paper, we present linear programming-based sufficient conditions, some of them polynomial-time, to establish the liveness and memory boundedness of general dataflow process networks. Furthermore, this approach can be used to obtain safe upper bounds on the size of the channel buffers of such a network.
The Role of Monotonicity in the Epistemic Analysis of Strategic Games
Venue: arXiv cs.GT 2010
Year: 2010

It is well-known that in finite strategic games true common belief (or common knowledge) of rationality implies that the players will choose only strategies that survive the iterated elimination of strictly dominated strategies. We establish a general theorem that deals with monotonic rationality notions and arbitrary strategic games and allows to strengthen the above result to arbitrary games, other rationality notions, and transfinite iterations of the elimination process. We also clarify what conclusions one can draw for the customary dominance notions that are not monotonic. The main tool is Tarski's Fixpoint Theorem.
Information-theoretic inference of common ancestors
Venue: arXiv cs.IT 2010
Year: 2010

A directed acyclic graph (DAG) partially represents the conditional independence structure among observations of a system if the local Markov condition holds, that is, if every variable is independent of its non-descendants given its parents. In general, there is a whole class of DAGs that represents a given set of conditional independence relations. We are interested in properties of this class that can be derived from observations of a subsystem only. To this end, we prove an information theoretic inequality that allows for the inference of common ancestors of observed parts in any DAG representing some unknown larger system. More explicitly, we show that a large amount of dependence in terms of mutual information among the observations implies the existence of a common ancestor that distributes this information. Within the causal interpretation of DAGs our result can be seen as a quantitative extension of Reichenbach's Principle of Common Cause to more than two variables. Our conclusions are valid also for non-probabilistic observations such as binary strings, since we state the proof for an axiomatized notion of mutual information that includes the stochastic as well as the algorithmic version.
An Alternative Approach to Data Acquisition Using Keyboard Emulation Technique
Venue: arXiv cs.HC 2010
Year: 2010

A number of data acquisition systems depend on human interface to access computer for measuring, processing and analyzing data and to prepare it for presentation and storage. Data acquisition software is installed on the computer and all intended operations are performed manually. The data acquisition software requires user intervention for operations like selection of measurement setup, acquisition and storage of data to computer. The duty of users becomes laborious if the data acquisition process lasts for a long duration and requires continuous repetition of steps. An appropriate solution to overcome such problem is to replace the physical operator with a virtual user. This software generated simulated user sits at the data acquisition process through out and automate all the intended steps of data acquisition. This paper presents a new approach for data acquisition by using keyboard emulation technique. A keyboard emulation software is developed which runs beside the main data acquisition software and acts as a virtual user. All the operations which require user interface are performed through fully automated computer program. The developed software/system is executed in a real time environment and the functionality of the software is verified. In the end, potential application areas of the designed keyboard emulation software are explored.
Ergodic Secret Alignment
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we introduce two new achievable schemes for the fading multiple access wiretap channel (MAC-WT). In the model that we consider, we assume that perfect knowledge of the state of all channels is available at all the nodes in a causal fashion. Our schemes use this knowledge together with the time varying nature of the channel model to align the interference from different users at the eavesdropper perfectly in a one-dimensional space while creating a higher dimensionality space for the interfering signals at the legitimate receiver hence allowing for better chance of recovery. While we achieve this alignment through signal scaling at the transmitters in our first scheme (scaling based alignment (SBA)), we let nature provide this alignment through the ergodicity of the channel coefficients in the second scheme (ergodic secret alignment (ESA)). For each scheme, we obtain the resulting achievable secrecy rate region. We show that the secrecy rates achieved by both schemes scale with SNR as 1/2log(SNR). Hence, we show the sub-optimality of the i.i.d. Gaussian signaling based schemes with and without cooperative jamming by showing that the secrecy rates achieved using i.i.d. Gaussian signaling with cooperative jamming do not scale with SNR. In addition, we introduce an improved version of our ESA scheme where we incorporate cooperative jamming to achieve higher secrecy rates. Moreover, we derive the necessary optimality conditions for the power control policy that maximizes the secrecy sum rate achievable by our ESA scheme when used solely and with cooperative jamming.
Qualitative Reasoning about Relative Direction on Adjustable Levels of Granularity
Venue: arXiv cs.AI 2010
Year: 2010

An important issue in Qualitative Spatial Reasoning is the representation of relative direction. In this paper we present simple geometric rules that enable reasoning about relative direction between oriented points. This framework, the Oriented Point Algebra OPRA_m, has a scalable granularity m. We develop a simple algorithm for computing the OPRA_m composition tables and prove its correctness. Using a composition table, algebraic closure for a set of OPRA statements is sufficient to solve spatial navigation tasks. And it turns out that scalable granularity is useful in these navigation tasks.
Implicit Real Vector Automata
Venue: arXiv cs.FL 2010
Year: 2010

This paper addresses the symbolic representation of non-convex real polyhedra, i.e., sets of real vectors satisfying arbitrary Boolean combinations of linear constraints. We develop an original data structure for representing such sets, based on an implicit and concise encoding of a known structure, the Real Vector Automaton. The resulting formalism provides a canonical representation of polyhedra, is closed under Boolean operators, and admits an efficient decision procedure for testing the membership of a vector.
Fast Histograms using Adaptive CUDA Streams
Venue: arXiv cs.DC 2010
Year: 2010

Histograms are widely used in medical imaging, network intrusion detection, packet analysis and other stream-based high throughput applications. However, while porting such software stacks to the GPU, the computation of the histogram is a typical bottleneck primarily due to the large impact on kernel speed by atomic operations. In this work, we propose a stream-based model implemented in CUDA, using a new adaptive kernel that can be optimized based on latency hidden CPU compute. We also explore the tradeoffs of using the new kernel vis-à-vis the stock NVIDIA SDK kernel, and discuss an intelligent kernel switching method for the stream based on a degeneracy criterion that is adaptively computed from the input stream.
Intuitionistic Fuzzy Ideal Extensions of Γ-Semigroups
Venue: arXiv cs.IT 2010
Year: 2010

In this paper the concept of the extensions of intuitionistic fuzzy ideals in a semigroup has been extended to a Γ-Semigroups. Among other results characterization of prime ideals in a Γ-Semigroups in terms of intuitionistic fuzzy ideal extension has been obtained.
Construction of New Delay-Tolerant Space-Time Codes
Venue: arXiv cs.IT 2010
Year: 2010

Perfect Space-Time Codes (STC) are optimal codes in their original construction for Multiple Input Multiple Output (MIMO) systems. Based on Cyclic Division Algebras (CDA), they are full-rate, full-diversity codes, have Non-Vanishing Determinants (NVD) and hence achieve Diversity-Multiplexing Tradeoff (DMT). In addition, these codes have led to optimal distributed space-time codes when applied in cooperative networks under the assumption of perfect synchronization between relays. However, they loose their diversity when delays are introduced and thus are not delay-tolerant. In this paper, using the cyclic division algebras of perfect codes, we construct new codes that maintain the same properties as perfect codes in the synchronous case. Moreover, these codes preserve their full-diversity in asynchronous transmission.
Computational Modeling for the Activation Cycle of G-proteins by G-protein-coupled Receptors
Venue: arXiv cs.CE 2010
Year: 2010

In this paper, we survey five different computational modeling methods. For comparison, we use the activation cycle of G-proteins that regulate cellular signaling events downstream of G-protein-coupled receptors (GPCRs) as a driving example. Starting from an existing Ordinary Differential Equations (ODEs) model, we implement the G-protein cycle in the stochastic Pi-calculus using SPiM, as Petri-nets using Cell Illustrator, in the Kappa Language using Cellucidate, and in Bio-PEPA using the Bio-PEPA eclipse plug in. We also provide a high-level notation to abstract away from communication primitives that may be unfamiliar to the average biologist, and we show how to translate high-level programs into stochastic Pi-calculus processes and chemical reactions.
Modeling biological systems with delays in Bio-PEPA
Venue: arXiv cs.CE 2010
Year: 2010

Delays in biological systems may be used to model events for which the underlying dynamics cannot be precisely observed, or to provide abstraction of some behavior of the system resulting more compact models. In this paper we enrich the stochastic process algebra Bio-PEPA, with the possibility of assigning delays to actions, yielding a new non-Markovian process algebra: Bio-PEPAd. This is a conservative extension meaning that the original syntax of Bio-PEPA is retained and the delay specification which can now be associated with actions may be added to existing Bio-PEPA models. The semantics of the firing of the actions with delays is the delay-as-duration approach, earlier presented in papers on the stochastic simulation of biological systems with delays. These semantics of the algebra are given in the Starting-Terminating style, meaning that the state and the completion of an action are observed as two separate events, as required by delays. Furthermore we outline how to perform stochastic simulation of Bio-PEPAd systems and how to automatically translate a Bio-PEPAd system into a set of Delay Differential Equations, the deterministic framework for modeling of biological systems with delays. We end the paper with two example models of biological systems with delays to illustrate the approach.
Edge- and Node-Disjoint Paths in P Systems
Venue: arXiv cs.DC 2010
Year: 2010

In this paper, we continue our development of algorithms used for topological network discovery. We present native P system versions of two fundamental problems in graph theory: finding the maximum number of edge- and node-disjoint paths between a source node and target node. We start from the standard depth-first-search maximum flow algorithms, but our approach is totally distributed, when initially no structural information is available and each P system cell has to even learn its immediate neighbors. For the node-disjoint version, our P system rules are designed to enforce node weight capacities (of one), in addition to edge capacities (of one), which are not readily available in the standard network flow algorithms.
A better tester for bipartiteness?
Venue: arXiv cs.DS 2010
Year: 2010

Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of O(1/ε) vertices is bipartite with high probability. We conjecture that the induced subgraph is Ω~(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1/ε^c), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε^2) queries (Bogdanov and Trevisan, CCC 2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness.
Improving the Technical Aspects of Software Testing in Enterprises
Venue: arXiv cs.SE 2010
Year: 2010

Many software developments projects fail due to quality problems. Software testing enables the creation of high quality software products. Since it is a cumbersome and expensive task, and often hard to manage, both its technical background and its organizational implementation have to be well founded. We worked with regional companies that develop software in order to learn about their distinct weaknesses and strengths with regard to testing. Analyzing and comparing the strengths, we derived best practices. In this paper we explain the project's background and sketch the design science research methodology used. We then introduce a graphical categorization framework that helps companies in judging the applicability of recommendations. Eventually, we present details on five recommendations for tech-nical aspects of testing. For each recommendation we give im-plementation advice based on the categorization framework.
Significance of Classification Techniques in Prediction of Learning Disabilities
Venue: arXiv cs.AI 2010
Year: 2010

The aim of this study is to show the importance of two classification techniques, viz. decision tree and clustering, in prediction of learning disabilities (LD) of school-age children. LDs affect about 10 percent of all children enrolled in schools. The problems of children with specific learning disabilities have been a cause of concern to parents and teachers for some time. Decision trees and clustering are powerful and popular tools used for classification and prediction in Data mining. Different rules extracted from the decision tree are used for prediction of learning disabilities. Clustering is the assignment of a set of observations into subsets, called clusters, which are useful in finding the different signs and symptoms (attributes) present in the LD affected child. In this paper, J48 algorithm is used for constructing the decision tree and K-means algorithm is used for creating the clusters. By applying these classification techniques, LD in any child can be identified.
Detecting Ontological Conflicts in Protocols between Semantic Web Services
Venue: arXiv cs.AI 2010
Year: 2010

The task of verifying the compatibility between interacting web services has traditionally been limited to checking the compatibility of the interaction protocol in terms of message sequences and the type of data being exchanged. Since web services are developed largely in an uncoordinated way, different services often use independently developed ontologies for the same domain instead of adhering to a single ontology as standard. In this work we investigate the approaches that can be taken by the server to verify the possibility to reach a state with semantically inconsistent results during the execution of a protocol with a client, if the client ontology is published. Often database is used to store the actual data along with the ontologies instead of storing the actual data as a part of the ontology description. It is important to observe that at the current state of the database the semantic conflict state may not be reached even if the verification done by the server indicates the possibility of reaching a conflict state. A relational algebra based decision procedure is also developed to incorporate the current state of the client and the server databases in the overall verification procedure.
A recombination algorithm for the decomposition of multivariate rational functions
Venue: arXiv cs.SC 2010
Year: 2010

In this paper we show how we can compute in a deterministic way the decomposition of a multivariate rational function with a recombination strategy. The key point of our recombination strategy is the used of Darboux polynomials. We study the complexity of this strategy and we show that this method improves the previous ones. In appendix, we explain how the strategy proposed recently by J. Berthomieu and G. Lecerf for the sparse factorization can be used in the decomposition setting. Then we deduce a decomposition algorithm in the sparse bivariate case and we give its complexity
Featureless 2D-3D Pose Estimation by Minimising an Illumination-Invariant Loss
Venue: arXiv cs.CV 2010
Year: 2010

The problem of identifying the 3D pose of a known object from a given 2D image has important applications in Computer Vision ranging from robotic vision to image analysis. Our proposed method of registering a 3D model of a known object on a given 2D photo of the object has numerous advantages over existing methods: It does neither require prior training nor learning, nor knowledge of the camera parameters, nor explicit point correspondences or matching features between image and model. Unlike techniques that estimate a partial 3D pose (as in an overhead view of traffic or machine parts on a conveyor belt), our method estimates the complete 3D pose of the object, and works on a single static image from a given view, and under varying and unknown lighting conditions. For this purpose we derive a novel illumination-invariant distance measure between 2D photo and projected 3D model, which is then minimised to find the best pose parameters. Results for vehicle pose detection are presented.
Data Group Anonymity: General Approach
Venue: arXiv cs.CR 2010
Year: 2010

In the recent time, the problem of protecting privacy in statistical data before they are published has become a pressing one. Many reliable studies have been accomplished, and loads of solutions have been proposed. Though, all these researches take into consideration only the problem of protecting individual privacy, i.e., privacy of a single person, household, etc. In our previous articles, we addressed a completely new type of anonymity problems. We introduced a novel kind of anonymity to achieve in statistical data and called it group anonymity. In this paper, we aim at summarizing and generalizing our previous results, propose a complete mathematical description of how to provide group anonymity, and illustrate it with a couple of real-life examples.