OpenRaiser/Intern-Atlas huggingface dataset:
Social network markets: the influence of network structure when consumers face decisions over many similar choices
Venue: arXiv cs.SI 2012
Year: 2012

In social network markets, the act of consumer choice in these industries is governed not just by the set of incentives described by conventional consumer demand theory, but by the choices of others in which an individual's payoff is an explicit function of the actions of others. We observe two key empirical features of outcomes in social networked markets. First, a highly right-skewed, non-Gaussian distribution of the number of times competing alternatives are selected at a point in time. Second, there is turnover in the rankings of popularity over time. We show here that such outcomes can arise either when there is no alternative which exhibits inherent superiority in its attributes, or when agents find it very difficult to discern any differences in quality amongst the alternatives which are available so that it is as if no superiority exists. These features appear to obtain, as a reasonable approximation, in many social network markets. We examine the impact of network structure on both the rank-size distribution of choices at a point in time, and on the life spans of the most popular choices. We show that a key influence on outcomes is the extent to which the network follows a hierarchical structure. It is the social network properties of the markets, the meso-level structure, which determine outcomes rather than the objective attributes of the products.
Conflict-driven ASP Solving with External Sources
Venue: arXiv cs.AI 2012
Year: 2012

Answer Set Programming (ASP) is a well-known problem solving approach based on nonmonotonic logic programs and efficient solvers. To enable access to external information, HEX-programs extend programs with external atoms, which allow for a bidirectional communication between the logic program and external sources of computation (e.g., description logic reasoners and Web resources). Current solvers evaluate HEX-programs by a translation to ASP itself, in which values of external atoms are guessed and verified after the ordinary answer set computation. This elegant approach does not scale with the number of external accesses in general, in particular in presence of nondeterminism (which is instrumental for ASP). In this paper, we present a novel, native algorithm for evaluating HEX-programs which uses learning techniques. In particular, we extend conflict-driven ASP solving techniques, which prevent the solver from running into the same conflict again, from ordinary to HEX-programs. We show how to gain additional knowledge from external source evaluations and how to use it in a conflict-driven algorithm. We first target the uninformed case, i.e., when we have no extra information on external sources, and then extend our approach to the case where additional meta-information is available. Experiments show that learning from external sources can significantly decrease both the runtime and the number of considered candidate compatible sets.
Advanced Computer Algebra Algorithms for the Expansion of Feynman Integrals
Venue: arXiv cs.SC 2012
Year: 2012

Two-point Feynman parameter integrals, with at most one mass and containing local operator insertions in $4+\ep$-dimensional Minkowski space, can be transformed to multi-integrals or multi-sums over hyperexponential and/or hypergeometric functions depending on a discrete parameter $n$. Given such a specific representation, we utilize an enhanced version of the multivariate Almkvist--Zeilberger algorithm (for multi-integrals) and a common summation framework of the holonomic and difference field approach (for multi-sums) to calculate recurrence relations in $n$. Finally, solving the recurrence we can decide efficiently if the first coefficients of the Laurent series expansion of a given Feynman integral can be expressed in terms of indefinite nested sums and products; if yes, the all $n$ solution is returned in compact representations, i.e., no algebraic relations exist among the occurring sums and products.
Analysis and Enhancements of Leader Elections algorithms in Mobile Ad Hoc Networks
Venue: arXiv cs.DC 2012
Year: 2012

Mobile Ad Hoc networks (MANET), distinct from traditional distributed systems, are dynamic and self-organizing networks. MANET requires a leader to coordinate and organize tasks. The challenge is to have the right election algorithm that chooses the right leader based on various factors in MANET. In this paper, we analyze four leader election algorithms used in mobile Ad Hoc Networks. Factors considered in our analysis are time complexity, message complexity, assumptions considered, fault tolerance and timing model. Our proposed enhancements include recovered nodes inquiring about the current leader and the use of candidates during election to reduce the overhead of starting a new election session. In addition, better election criteria specific to MANET, such as battery life and signal strength, are proposed. Our evaluation and discussion shows that the proposed enhancements are effective. The analysis can be used as a reference for system designers in choosing the right election algorithm for MANET.
Constellation Design for Transmission over Nonlinear Satellite Channels
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we use a variation of simulated annealing algorithm for optimizing two-dimensional constellations with 32 signals. The main objective is to maximize the symmetric pragmatic capacity under the peak-power constraint. The method allows the joint optimization of constellation and binary labeling. We also investigate the performance of the optimized constellation over nonlinear satellite channel under additive white Gaussian noise. We consider the performance over systems with and without pre-distorters. In both cases the optimized constellations perform considerably better than the conventional Amplitude Phase Shift Keying (APSK) modulations, used in the current digital video broadcasting standard (DVB-S2) on satellite channels. Based on our optimized constellations, we also propose a new labeling for the 4+12+16-APSK constellation of the DVB-S2 standard which is Gray over all rings.
D-FLAT: Declarative Problem Solving Using Tree Decompositions and Answer-Set Programming
Venue: arXiv cs.AI 2012
Year: 2012

In this work, we propose Answer-Set Programming (ASP) as a tool for rapid prototyping of dynamic programming algorithms based on tree decompositions. In fact, many such algorithms have been designed, but only a few of them found their way into implementation. The main obstacle is the lack of easy-to-use systems which (i) take care of building a tree decomposition and (ii) provide an interface for declarative specifications of dynamic programming algorithms. In this paper, we present D-FLAT, a novel tool that relieves the user of having to handle all the technical details concerned with parsing, tree decomposition, the handling of data structures, etc. Instead, it is only the dynamic programming algorithm itself which has to be specified in the ASP language. D-FLAT employs an ASP solver in order to compute the local solutions in the dynamic programming algorithm. In the paper, we give a few examples illustrating the use of D-FLAT and describe the main features of the system. Moreover, we report experiments which show that ASP-based D-FLAT encodings for some problems outperform monolithic ASP encodings on instances of small treewidth.
The Theory of Crowd Capital
Venue: arXiv cs.CY 2012
Year: 2012

We are seeing more and more organizations undertaking activities to engage dispersed populations through IS. Using the knowledge-based view of the organization, this work conceptualizes a theory of Crowd Capital to explain this phenomenon. Crowd Capital is a heterogeneous knowledge resource generated by an organization, through its use of Crowd Capability, which is defined by the structure, content, and process by which an organization engages with the dispersed knowledge of individuals (the Crowd). Our work draws upon a diverse literature and builds upon numerous examples of practitioner implementations to support our theorizing. We present a model of Crowd Capital generation in organizations and discuss the implications of Crowd Capital on organizational boundary and on IS research.
Customised high-value document generation
Venue: arXiv cs.OH 2012
Year: 2012

Contributions of different experts to innovation projects improve enterprise value, captured in documents. A subset of them is the centre of expert constraint convergence. Their production needs to be tailored case by case. Documents are often considered as knowledge transcription. As the base of a structured knowledge-based information environment, this paper presents a global approach that helps knowledge-integration tool deployment. An example, based on process plan in aircraft manufacturing, indicates how fundamental understanding of domain infrastructure contributes to a more coherent architecture of knowledge-based information environments. A comparison with an experiment in insurance services generalised the application of presented principles.
Session Communication and Integration
Venue: arXiv cs.PL 2012
Year: 2012

The scenario-based specification of a large distributed system is usually naturally decomposed into various modules. The integration of specification modules contrasts to the parallel composition of program components, and includes various ways such as scenario concatenation, choice, and nesting. The recent development of multiparty session types for process calculi provides useful techniques to accommodate the protocol modularisation, by encoding fragments of communication protocols in the usage of private channels for a class of agents. In this paper, we extend forgoing session type theories by enhancing the session integration mechanism. More specifically, we propose a novel synchronous multiparty session type theory, in which sessions are separated into the communicating and integrating levels. Communicating sessions record the message-based communications between multiple agents, whilst integrating sessions describe the integration of communicating ones. A two-level session type system is developed for pi-calculus with syntactic primitives for session establishment, and several key properties of the type system are studied. Applying the theory to system description, we show that a channel safety property and a session conformance property can be analysed. Also, to improve the utility of the theory, a process slicing method is used to help identify the violated sessions in the type checking.
Bisimilarity of Probabilistic Pushdown Automata
Venue: arXiv cs.FL 2012
Year: 2012

We study the bisimilarity problem for probabilistic pushdown automata (pPDA) and subclasses thereof. Our definition of pPDA allows both probabilistic and non-deterministic branching, generalising the classical notion of pushdown automata (without epsilon-transitions). Our first contribution is a general construction that reduces checking bisimilarity of probabilistic transition systems to checking bisimilarity of non-deterministic transition systems. This construction directly yields decidability of bisimilarity for pPDA, as well as an elementary upper bound for the bisimilarity problem on the subclass of probabilistic basic process algebras, i.e., single-state pPDA. We further show that, with careful analysis, the general reduction can be used to prove an EXPTIME upper bound for bisimilarity of probabilistic visibly pushdown automata. Here we also provide a matching lower bound, establishing EXPTIME-completeness. Finally we prove that deciding bisimilarity of probabilistic one-counter automata, another subclass of pPDA, is PSPACE-complete. Here we use a more specialised argument to obtain optimal complexity bounds.
ASP modulo CSP: The clingcon system
Venue: arXiv cs.LO 2012
Year: 2012

We present the hybrid ASP solver clingcon, combining the simple modeling language and the high performance Boolean solving capacities of Answer Set Programming (ASP) with techniques for using non-Boolean constraints from the area of Constraint Programming (CP). The new clingcon system features an extended syntax supporting global constraints and optimize statements for constraint variables. The major technical innovation improves the interaction between ASP and CP solver through elaborated learning techniques based on irreducible inconsistent sets. A broad empirical evaluation shows that these techniques yield a performance improvement of an order of magnitude. To appear in Theory and Practice of Logic Programming
The Power of Linear Reconstruction Attacks
Venue: arXiv cs.DS 2012
Year: 2012

We consider the power of linear reconstruction attacks in statistical data privacy, showing that they can be applied to a much wider range of settings than previously understood. Linear attacks have been studied before (Dinur and Nissim PODS'03, Dwork, McSherry and Talwar STOC'07, Kasiviswanathan, Rudelson, Smith and Ullman STOC'10, De TCC'12, Muthukrishnan and Nikolov STOC'12) but have so far been applied only in settings with releases that are obviously linear. Consider a database curator who manages a database of sensitive information but wants to release statistics about how a sensitive attribute (say, disease) in the database relates to some nonsensitive attributes (e.g., postal code, age, gender, etc). We show one can mount linear reconstruction attacks based on any release that gives: a) the fraction of records that satisfy a given non-degenerate boolean function. Such releases include contingency tables (previously studied by Kasiviswanathan et al., STOC'10) as well as more complex outputs like the error rate of classifiers such as decision trees; b) any one of a large class of M-estimators (that is, the output of empirical risk minimization algorithms), including the standard estimators for linear and logistic regression. We make two contributions: first, we show how these types of releases can be transformed into a linear format, making them amenable to existing polynomial-time reconstruction algorithms. This is already perhaps surprising, since many of the above releases (like M-estimators) are obtained by solving highly nonlinear formulations. Second, we show how to analyze the resulting attacks under various distributional assumptions on the data. Specifically, we consider a setting in which the same statistic (either a) or b) above) is released about how the sensitive attribute relates to all subsets of size k (out of a total of d) nonsensitive boolean attributes.
Video De-fencing
Venue: arXiv cs.CV 2012
Year: 2012

This paper describes and provides an initial solution to a novel video editing task, i.e., video de-fencing. It targets automatic restoration of the video clips that are corrupted by fence-like occlusions during capture. Our key observation lies in the visual parallax between fences and background scenes, which is caused by the fact that the former are typically closer to the camera. Unlike in traditional image inpainting, fence-occluded pixels in the videos tend to appear later in the temporal dimension and are therefore recoverable via optimized pixel selection from relevant frames. To eventually produce fence-free videos, major challenges include cross-frame sub-pixel image alignment under diverse scene depth, and "correct" pixel selection that is robust to dominating fence pixels. Several novel tools are developed in this paper, including soft fence detection, weighted truncated optical flow method and robust temporal median filter. The proposed algorithm is validated on several real-world video clips with fences.
Model-Checking Process Equivalences
Venue: arXiv cs.LO 2012
Year: 2012

Process equivalences are formal methods that relate programs and system which, informally, behave in the same way. Since there is no unique notion of what it means for two dynamic systems to display the same behaviour there are a multitude of formal process equivalences, ranging from bisimulation to trace equivalence, categorised in the linear-time branching-time spectrum. We present a logical framework based on an expressive modal fixpoint logic which is capable of defining many process equivalence relations: for each such equivalence there is a fixed formula which is satisfied by a pair of processes if and only if they are equivalent with respect to this relation. We explain how to do model checking, even symbolically, for a significant fragment of this logic that captures many process equivalences. This allows model checking technology to be used for process equivalence checking. We show how partial evaluation can be used to obtain decision procedures for process equivalences from the generic model checking scheme.
The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
Venue: arXiv cs.CC 2012
Year: 2012

For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time. However, it has recently been proved by Oliver Friedmann that the strategy improvement algorithm requires super-polynomially many iteration steps, for all popular local improvements rules, including switch-all (also with Fearnley's snare memorisation), switch-best, random-facet, random-edge, switch-half, least-recently-considered, and Zadeh's Pivoting rule. We analyse the examples provided by Friedmann in terms of complexity measures for directed graphs such as treewidth, DAG-width, Kelly-width, entanglement, directed pathwidth, and cliquewidth. It is known that for every class of parity games on which one of these parameters is bounded, the winning regions can be efficiently computed. It turns out that with respect to almost all of these measures, the complexity of Friedmann's counterexamples is bounded, and indeed in most cases by very small numbers. This analysis strengthens in some sense Friedmann's results and shows that the discrete strategy improvement algorithm is even more limited than one might have thought. Not only does it require super-polynomial running time in the general case, where the problem of polynomial-time solvability is open, it even has super-polynomial lower time bounds on natural classes of parity games on which efficient algorithms are known.
Higher-Order Pushdown Systems with Data
Venue: arXiv cs.FL 2012
Year: 2012

We propose a new extension of higher-order pushdown automata, which allows to use an infinite alphabet. The new automata recognize languages of data words (instead of normal words), which beside each its letter from a finite alphabet have a data value from an infinite alphabet. Those data values can be loaded to the stack of the automaton, and later compared with some farther data values on the input. Our main purpose for introducing these automata is that they may help in analyzing normal automata (without data). As an example, we give a proof that deterministic automata with collapse can recognize more languages than deterministic automata without collapse. This proof is simpler than in the no-data case. We also state a hypothesis how the new automaton model can be related to the original model of higher-order pushdown automata.
Level Set Estimation from Compressive Measurements using Box Constrained Total Variation Regularization
Venue: arXiv cs.CV 2012
Year: 2012

Estimating the level set of a signal from measurements is a task that arises in a variety of fields, including medical imaging, astronomy, and digital elevation mapping. Motivated by scenarios where accurate and complete measurements of the signal may not available, we examine here a simple procedure for estimating the level set of a signal from highly incomplete measurements, which may additionally be corrupted by additive noise. The proposed procedure is based on box-constrained Total Variation (TV) regularization. We demonstrate the performance of our approach, relative to existing state-of-the-art techniques for level set estimation from compressive measurements, via several simulation examples.
Protein Inference and Protein Quantification: Two Sides of the Same Coin
Venue: arXiv cs.CE 2012
Year: 2012

Motivation: In mass spectrometry-based shotgun proteomics, protein quantification and protein identification are two major computational problems. To quantify the protein abundance, a list of proteins must be firstly inferred from the sample. Then the relative or absolute protein abundance is estimated with quantification methods, such as spectral counting. Until now, researchers have been dealing with these two processes separately. In fact, they are two sides of same coin in the sense that truly present proteins are those proteins with non-zero abundances. Then, one interesting question is if we regard the protein inference problem as a special protein quantification problem, is it possible to achieve better protein inference performance? Contribution: In this paper, we investigate the feasibility of using protein quantification methods to solve the protein inference problem. Protein inference is to determine whether each candidate protein is present in the sample or not. Protein quantification is to calculate the abundance of each protein. Naturally, the absent proteins should have zero abundances. Thus, we argue that the protein inference problem can be viewed as a special case of protein quantification problem: present proteins are those proteins with non-zero abundances. Based on this idea, our paper tries to use three very simple protein quantification methods to solve the protein inference problem effectively. Results: The experimental results on six datasets show that these three methods are competitive with previous protein inference algorithms. This demonstrates that it is plausible to take the protein inference problem as a special case of protein quantification, which opens the door of devising more effective protein inference algorithms from a quantification perspective.
Sequence Annotation with HMMs: New Problems and Their Complexity
Venue: arXiv cs.DS 2012
Year: 2012

Hidden Markov models (HMMs) and their variants were successfully used for several sequence annotation tasks. Traditionally, inference with HMMs is done using the Viterbi and posterior decoding algorithms. However, recently a variety of different optimization criteria and associated computational problems were proposed. In this paper, we consider three HMM decoding criteria and prove their NP hardness. These criteria consider the set of states used to generate a certain sequence, but abstract from the exact locations of regions emitted by individual states. We also illustrate experimentally that these criteria are useful for HIV recombination detection.
An anisotropy preserving metric for DTI processing
Venue: arXiv cs.CV 2012
Year: 2012

Statistical analysis of Diffusion Tensor Imaging (DTI) data requires a computational framework that is both numerically tractable (to account for the high dimensional nature of the data) and geometric (to account for the nonlinear nature of diffusion tensors). Building upon earlier studies that have shown that a Riemannian framework is appropriate to address these challenges, the present paper proposes a novel metric and an accompanying computational framework for DTI data processing. The proposed metric retains the geometry and the computational tractability of earlier methods grounded in the affine invariant metric. In addition, and in contrast to earlier methods, it provides an interpolation method which preserves anisotropy, a central information carried by diffusion tensor data.