OpenRaiser/Intern-Atlas huggingface dataset:
An existing, ecologically-successful genus of collectively intelligent artificial creatures
Venue: arXiv cs.SI 2012
Year: 2012

People sometimes worry about the Singularity [Vinge, 1993; Kurzweil, 2005], or about the world being taken over by artificially intelligent robots. I believe the risks of these are very small. However, few people recognize that we already share our world with artificial creatures that participate as intelligent agents in our society: corporations. Our planet is inhabited by two distinct kinds of intelligent beings --- individual humans and corporate entities --- whose natures and interests are intimately linked. To co-exist well, we need to find ways to define the rights and responsibilities of both individual humans and corporate entities, and to find ways to ensure that corporate entities behave as responsible members of society.
Learning From An Optimization Viewpoint
Venue: arXiv cs.LG 2012
Year: 2012

In this dissertation we study statistical and online learning problems from an optimization viewpoint.The dissertation is divided into two parts : I. We first consider the question of learnability for statistical learning problems in the general learning setting. The question of learnability is well studied and fully characterized for binary classification and for real valued supervised learning problems using the theory of uniform convergence. However we show that for the general learning setting uniform convergence theory fails to characterize learnability. To fill this void we use stability of learning algorithms to fully characterize statistical learnability in the general setting. Next we consider the problem of online learning. Unlike the statistical learning framework there is a dearth of generic tools that can be used to establish learnability and rates for online learning problems in general. We provide online analogs to classical tools from statistical learning theory like Rademacher complexity, covering numbers, etc. We further use these tools to fully characterize learnability for online supervised learning problems. II. In the second part, for general classes of convex learning problems, we provide appropriate mirror descent (MD) updates for online and statistical learning of these problems. Further, we show that the the MD is near optimal for online convex learning and for most cases, is also near optimal for statistical convex learning. We next consider the problem of convex optimization and show that oracle complexity can be lower bounded by the so called fat-shattering dimension of the associated linear class. Thus we establish a strong connection between offline convex optimization problems and statistical learning problems. We also show that for a large class of high dimensional optimization problems, MD is in fact near optimal even for convex optimization.
Fair Allocation Without Trade
Venue: arXiv cs.GT 2012
Year: 2012

We consider the age-old problem of allocating items among different agents in a way that is efficient and fair. Two papers, by Dolev et al. and Ghodsi et al., have recently studied this problem in the context of computer systems. Both papers had similar models for agent preferences, but advocated different notions of fairness. We formalize both fairness notions in economic terms, extending them to apply to a larger family of utilities. Noting that in settings with such utilities efficiency is easily achieved in multiple ways, we study notions of fairness as criteria for choosing between different efficient allocations. Our technical results are algorithms for finding fair allocations corresponding to two fairness notions: Regarding the notion suggested by Ghodsi et al., we present a polynomial-time algorithm that computes an allocation for a general class of fairness notions, in which their notion is included. For the other, suggested by Dolev et al., we show that a competitive market equilibrium achieves the desired notion of fairness, thereby obtaining a polynomial-time algorithm that computes such a fair allocation and solving the main open problem raised by Dolev et al.
Designing generalisation evaluation function through human-machine dialogue
Venue: arXiv cs.HC 2012
Year: 2012

Automated generalisation has known important improvements these last few years. However, an issue that still deserves more study concerns the automatic evaluation of generalised data. Indeed, many automated generalisation systems require the utilisation of an evaluation function to automatically assess generalisation outcomes. In this paper, we propose a new approach dedicated to the design of such a function. This approach allows an imperfectly defined evaluation function to be revised through a man-machine dialogue. The user gives its preferences to the system by comparing generalisation outcomes. Machine Learning techniques are then used to improve the evaluation function. An experiment carried out on buildings shows that our approach significantly improves generalisation evaluation functions defined by users.
Computing Multiplicities of Lie Group Representations
Venue: arXiv cs.CC 2012
Year: 2012

For fixed compact connected Lie groups H \subseteq G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes. The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Non-asymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory.
Coupling Clinical Decision Support System with Computerized Prescriber Order Entry and their Dynamic Plugging in the Medical Workflow System
Venue: arXiv cs.MA 2012
Year: 2012

This work deals with coupling Clinical Decision Support System (CDSS) with Computerized Prescriber Order Entry (CPOE) and their dynamic plugging in the medical Workflow Management System (WfMS). First, in this paper we argue some existing CDSS representative of the state of the art in order to emphasize their inability to deal with coupling with CPOE and medical WfMS. The multi-agent technology is at the basis of our proposition since (i) it provides natural abstractions to deal with distribution, heterogeneity and autonomy which are inherent to the previous systems (CDSS, CPOE and medical WfMS), and (ii) it introduces powerful concepts such as organizations, goals and roles useful to describe in details the coordination of the different components involved in these systems. In this paper, we also propose a Multi-Agent System (MAS) to support the coupling CDSS with CPOE. Finally, we show how we integrate the proposed MAS in the medical workflow management system which is also based on collaborating agents
Complexity of tropical and min-plus linear prevarieties
Venue: arXiv cs.CC 2012
Year: 2012

A tropical (or min-plus) semiring is a set $\mathbb{Z}$ (or $\mathbb{Z \cup \{\infty\}}$) endowed with two operations: $\oplus$, which is just usual minimum, and $\odot$, which is usual addition. In tropical algebra the vector $x$ is a solution to a polynomial $g_1(x) \oplus g_2(x) \oplus...\oplus g_k(x)$, where $g_i(x)$'s are tropical monomials, if the minimum in $\min_i(g_{i}(x))$ is attained at least twice. In min-plus algebra solutions of systems of equations of the form $g_1(x)\oplus...\oplus g_k(x) = h_1(x)\oplus...\oplus h_l(x)$ are studied. In this paper we consider computational problems related to tropical linear system. We show that the solvability problem (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$) and the problem of deciding the equivalence of two linear systems (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$) are equivalent under polynomial-time reduction to mean payoff games and are also equivalent to analogous problems in min-plus algebra. In particular, all these problems belong to $\mathsf{NP} \cap \mathsf{coNP}$. Thus we provide a tight connection of computational aspects of tropical linear algebra with mean payoff games and min-plus linear algebra. On the other hand we show that computing the dimension of the solution space of a tropical linear system and of a min-plus linear system are $\mathsf{NP}$-complete. We also extend some of our results to the systems of min-plus linear inequalities.
Numerical Analysis of Diagonal-Preserving, Ripple-Minimizing and Low-Pass Image Resampling Methods
Venue: arXiv cs.GR 2012
Year: 2012

Image resampling is a necessary component of any operation that changes the size of an image or its geometry. Methods tuned for natural image upsampling (roughly speaking, image enlargement) are analyzed and developed with a focus on their ability to preserve diagonal features and suppress overshoots. Monotone, locally bounded and almost monotone "direct" interpolation and filtering methods, as well as face split and vertex split surface subdivision methods, alone or in combination, are studied. Key properties are established by way of proofs and counterexamples as well as numerical experiments involving 1D curve and 2D diagonal data resampling. In addition, the Remez minimax method for the computation of low-cost polynomial approximations of low-pass filter kernels tuned for natural image downsampling (roughly speaking, image reduction) is refactored for relative error minimization in the presence of roots in the interior of the interval of approximation and so that even and odd functions are approximated with like polynomials. The accuracy and frequency response of the approximations are tabulated and plotted against the original, establishing their rapid convergence.
Tight lower bound of consecutive lengths for QC-LDPC codes with girth twelve
Venue: arXiv cs.IT 2012
Year: 2012

For an arbitrary (3,L) QC-LDPC code with a girth of twelve, a tight lower bound of the consecutive lengths is proposed. For an arbitrary length above the bound the resultant code necessarily has a girth of twelve, and for the length meeting the bound, the corresponding code inevitably has a girth smaller than twelve. The conclusion can play an important role in the proofs of the existence of large-girth QC-LDPC codes, the construction of large-girth QC-LDPC codes based on the Chinese remainder theorem, and the construction of LDPC codes with the guaranteed error correction capability.
MPIFA: A Modified Protocol Independent Fairness Algorithm for Community Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

Community Wireless Mesh Networks (WMN) is a paradigm in wireless communication of 21st centuary as means of providing high speed braodband access. Un-cooperative nodes, both selfish and malicious proves to be a significant threat in Community WMN that require a solution independent of routing protocols being used. We propose to implement Modified PIFA (MPIFA), an Improved version of Protocol Independent Fairness Algorithm (PIFA) proposed by Younghwan Yoo, Sanghyun and P. Agrawal [6] with ability to cater specific requirements in Community WMN. MPIFA has malicious nodes detection rate improvement of 50% when nodes demonstrate low probabilistic malicious behavior of 10% to circumvent the security measures in place. Improvements were also made to reduce false malicious node detections to 4% when node-to-node link failures occur in Community WMN.
Mitigating Systemic Risks in Future Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper elaborates about the potential risk of systemic instabilities in future networks and proposes a methodology to mitigate it. The starting concept is modeling the network as a complex environment (e.g. ecosystem) of resources and associated functional controllers in a continuous and dynamic game of cooperation - competition. Methodology foresees defining and associating utility functions to these controllers and elaborating a global utility function (as a function of the controllers' utility functions) for the overall network. It is conjectured that the optimization of the global utility function ensures network stability and security evaluations. Paper concludes arguing that self-governance (with limited human intervention) is possible provided that proper local, global control rules are coded into these utility functions optimization processes.
The Distributed Ontology Language (DOL): Ontology Integration and Interoperability Applied to Mathematical Formalization
Venue: arXiv cs.LO 2012
Year: 2012

The Distributed Ontology Language (DOL) is currently being standardized within the OntoIOp (Ontology Integration and Interoperability) activity of ISO/TC 37/SC 3. It aims at providing a unified framework for (1) ontologies formalized in heterogeneous logics, (2) modular ontologies, (3) links between ontologies, and (4) annotation of ontologies. This paper focuses on an application of DOL's meta-theoretical features in mathematical formalization: validating relationships between ontological formalizations of mathematical concepts in COLORE (Common Logic Repository), which provide the foundation for formalizing real-world notions such as spatial and temporal relations.
Stochastic Analysis of Mean Interference for RTS/CTS Mechanism
Venue: arXiv cs.NI 2012
Year: 2012

The RTS/CTS handshake mechanism in WLAN is studied using stochastic geometry. The effect of RTS/CTS is treated as a thinning procedure for a spatially distributed point process that models the potential transceivers in a WLAN, and the resulting concurrent transmission processes are described. Exact formulas for the intensity of the concurrent transmission processes and the mean interference experienced by a typical receiver are established. The analysis yields useful results for understanding how the design parameters of RTS/CTS affect the network interference.
Compact DSOP and partial DSOP Forms
Venue: arXiv cs.DM 2012
Year: 2012

Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don't care conditions of $f$) can be covered any number of times. We discuss finding DSOPs and partial DSOP with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a product p as a functions of the number of fragments induced on other cubes by the selection of p, and show how product weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.
The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words
Venue: arXiv cs.FL 2012
Year: 2012

The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give a new proof for Almeida and Azevedo's effective characterization of the join of R-trivial and L-trivial monoids. This characterization is a single identity of omega-terms using three variables.
FastFlow tutorial
Venue: arXiv cs.DC 2012
Year: 2012

FastFlow is a structured parallel programming framework targeting shared memory multicores. Its layered design and the optimized implementation of the communication mechanisms used to implement the FastFlow streaming networks provided to the application programmer as algorithmic skeletons support the development of efficient fine grain parallel applications. FastFlow is available (open source) at SourceForge (http://sourceforge.net/projects/mc-fastflow/). This work introduces FastFlow programming techniques and points out the different ways used to parallelize existing C/C++ code using FastFlow as a software accelerator. In short: this is a kind of tutorial on FastFlow.
A New Approach of Improving CFA Image for Digital Camera's
Venue: arXiv cs.CV 2012
Year: 2012

This paper work directly towards the improving the quality of the image for the digital cameras and other visual capturing products. In this Paper, the authors clearly defines the problems occurs in the CFA image. A different methodology for removing the noise is discuses in the paper for color correction and color balancing of the image. At the same time, the authors also proposed a new methodology of providing denoisiing process before the demosaickingfor the improving the image quality of CFA which is much efficient then the other previous defined. The demosaicking process for producing the colors in the image in a best way is also discuss.
Weakest Preconditions and Cumulative Subgoal Fulfillment: A Comparison
Venue: arXiv cs.SE 2012
Year: 2012

We contrast the use of weakest preconditions for the correct construction of procedures with the cumulative subgoal fulfillment (CSF) approach. An example of Cohen and Monin is used for this purpose. The CSF construction process is demonstrated.
Faster Treasure Hunt and Better Strongly Universal Exploration Sequences
Venue: arXiv cs.DS 2012
Year: 2012

In this paper, we investigate the explicit deterministic treasure hunt problem in a $n$-vertex network. This problem was firstly introduced by Ta-Shma and Zwick in \cite{TZ07} [SODA'07]. Note also it is a variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. In this paper, we propose an $O(n^{c(1+\frac{1}λ)})$-time algorithm for the treasure hunt problem, which significantly improves the currently best known result of running time $O(n^{2c})$ in \cite{TZ07}, where $c$ is a constant induced from the construction of an universal exploration sequence in \cite{R05,TZ07}, and $λ\gg 1$ is an arbitrary large, but fixed, integer constant. The treasure hunt problem also motivates the study of strongly universal exploration sequences. In this paper, we also propose a much better explicit construction for strongly universal exploration sequences compared to the one in \cite{TZ07}.
Kolmogorov Complexity, Causality And Spin
Venue: arXiv cs.CC 2012
Year: 2012

A novel topological and computational method for 'motion' is described. Motion is constrained by inequalities in terms of Kolmogorov Complexity. Causality is obtained as the output of a high-pass filter, passing through only high values of Kolmogorov Complexity. Motion under the electromagnetic field described with immediate relationship with Subscript[G, 2] Holonomy group and its corresponding dense free 2-subgroup. Similar to Causality, Spin emerges as an immediate and inevitable consequence of high values of Kolmogorov Complexity. Consequently, the physical laws are nothing but a low-pass filter for small values of Kolmogorov Complexity.
Relativizing Small Complexity Classes and their Theories
Venue: arXiv cs.CC 2012
Year: 2012

Existing definitions of the relativizations of \NCOne, Ł and \NL\ do not preserve the inclusions $\NCOne \subseteq Ł$, $\NL\subseteq \ACOne$. We start by giving the first definitions that preserve them. Here for Ł and \NL\ we define their relativizations using Wilson's stack oracle model, but limit the height of the stack to a constant (instead of $\log(n)$). We show that the collapse of any two classes in $\{\ACZm, \TCZ, \NCOne, Ł, \NL\}$ implies the collapse of their relativizations. Next we exhibit an oracle $α$ that makes $\ACk(α)$ a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in [Takeuti, 1995]. The idea is that a circuit whose nested depth of oracle gates is bounded by $k$ cannot compute correctly the $(k+1)$ compositions of every oracle function. Finally we develop theories that characterize the relativizations of subclasses of \Ptime\ by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence the oracle separations imply separations for the relativized theories.
Optimal Mechanisms for Selling Information
Venue: arXiv cs.GT 2012
Year: 2012

The buying and selling of information is taking place at a scale unprecedented in the history of commerce, thanks to the formation of online marketplaces for user data. Data providing agencies sell user information to advertisers to allow them to match ads to viewers more effectively. In this paper we study the design of optimal mechanisms for a monopolistic data provider to sell information to a buyer, in a model where both parties have (possibly correlated) private signals about a state of the world, and the buyer uses information learned from the seller, along with his own signal, to choose an action (e.g., displaying an ad) whose payoff depends on the state of the world. We provide sufficient conditions under which there is a simple one-round protocol (i.e. a protocol where the buyer and seller each sends a single message, and there is a single money transfer) achieving optimal revenue. In these cases we present a polynomial-time algorithm that computes the optimal mechanism. Intriguingly, we show that multiple rounds of partial information disclosure (interleaved by payment to the seller) are sometimes necessary to achieve optimal revenue if the buyer is allowed to abort his interaction with the seller prematurely. We also prove some negative results about the inability of simple mechanisms for selling information to approximate more complicated ones in the worst case.
Basic completion strategies as another application of the Maude strategy language
Venue: arXiv cs.LO 2012
Year: 2012

The two levels of data and actions on those data provided by the separation between equations and rules in rewriting logic are completed by a third level of strategies to control the application of those actions. This level is implemented on top of Maude as a strategy language, which has been successfully used in a wide range of applications. First we summarize the Maude strategy language design and review some of its applications; then, we describe a new case study, namely the description of completion procedures as transition rules + control, as proposed by Lescanne.