OpenRaiser/Intern-Atlas huggingface dataset:
Studying Diffusion of Viral Content at Dyadic Level
Venue: arXiv cs.SI 2014
Year: 2014

Diffusion of information and viral content, social contagion and influence are still topics of broad evaluation. As theory explaining the role of influentials moves slightly to reduce their importance in the propagation of viral content, authors of the following paper have studied the information epidemic in a social networking platform in order to confirm recent theoretical findings in this area. While most of related experiments focus on the level of individuals, the elementary entities of the following analysis are dyads. The authors study behavioral motifs that are possible to observe at the dyadic level. The study shows significant differences between dyads that are more vs less engaged in the diffusion process. Dyads that fuel the diffusion proccess are characterized by stronger relationships (higher activity, more common friends), more active and networked receiving party (higher centrality measures), and higher authority centrality of person sending a viral message.
Simulation of Collision Resistant Secure Sum Protocol
Venue: arXiv cs.CR 2014
Year: 2014

secure multi-party computation is widely studied area in computer science. It is touching all most every aspect of human life. This paper demonstrates theoretical and experimental results of one of the secure multi-party computation protocols proposed by Shukla et al. implemented using visual C++. Data outflow probability is computed by changing parameters. At the end, time and space complexity is calculated using theoretical and experimental results.
Cross-Modal Learning via Pairwise Constraints
Venue: arXiv cs.CV 2014
Year: 2014

In multimedia applications, the text and image components in a web document form a pairwise constraint that potentially indicates the same semantic concept. This paper studies cross-modal learning via the pairwise constraint, and aims to find the common structure hidden in different modalities. We first propose a compound regularization framework to deal with the pairwise constraint, which can be used as a general platform for developing cross-modal algorithms. For unsupervised learning, we propose a cross-modal subspace clustering method to learn a common structure for different modalities. For supervised learning, to reduce the semantic gap and the outliers in pairwise constraints, we propose a cross-modal matching method based on compound ?21 regularization along with an iteratively reweighted algorithm to find the global optimum. Extensive experiments demonstrate the benefits of joint text and image modeling with semantically induced pairwise constraints, and show that the proposed cross-modal methods can further reduce the semantic gap between different modalities and improve the clustering/retrieval accuracy.
DL-PA and DCL-PC: model checking and satisfiability problem are indeed in PSPACE
Venue: arXiv cs.LO 2014
Year: 2014

We prove that the model checking and the satisfiability problem of both Dynamic Logic of Propositional Assignments DL-PA and Coalition Logic of Propositional Control and Delegation DCL-PC are in PSPACE. We explain why the proof of EXPTIME-hardness of the model checking problem of DL-PA presented in (Balbiani, Herzig, Troquard, 2013) is false. We also explain why the proof of membership in PSPACE of the model checking problem of DCL-PC given in (van der Hoek, Walther, Wooldridge, 2010) is wrong.
The Importance of Being Earnest in Crowdsourcing Systems
Venue: arXiv cs.HC 2014
Year: 2014

This paper presents the first systematic investigation of the potential performance gains for crowdsourcing systems, deriving from available information at the requester about individual worker earnestness (reputation). In particular, we first formalize the optimal task assignment problem when workers' reputation estimates are available, as the maximization of a monotone (submodular) function subject to Matroid constraints. Then, being the optimal problem NP-hard, we propose a simple but efficient greedy heuristic task allocation algorithm. We also propose a simple ``maximum a-posteriori`` decision rule. Finally, we test and compare different solutions, showing that system performance can greatly benefit from information about workers' reputation. Our main findings are that: i) even largely inaccurate estimates of workers' reputation can be effectively exploited in the task assignment to greatly improve system performance; ii) the performance of the maximum a-posteriori decision rule quickly degrades as worker reputation estimates become inaccurate; iii) when workers' reputation estimates are significantly inaccurate, the best performance can be obtained by combining our proposed task assignment algorithm with the LRA decision rule introduced in the literature.
Verifiably Truthful Mechanisms
Venue: arXiv cs.GT 2014
Year: 2014

It is typically expected that if a mechanism is truthful, then the agents would, indeed, truthfully report their private information. But why would an agent believe that the mechanism is truthful? We wish to design truthful mechanisms, whose truthfulness can be verified efficiently (in the computational sense). Our approach involves three steps: (i) specifying the structure of mechanisms, (ii) constructing a verification algorithm, and (iii) measuring the quality of verifiably truthful mechanisms. We demonstrate this approach using a case study: approximate mechanism design without money for facility location.
Low-Order Mathematical Modelling of Electric Double Layer Supercapacitors Using Spectral Methods
Venue: arXiv cs.SY 2014
Year: 2014

This work investigates two physics-based models that simulate the non-linear partial differential algebraic equations describing an electric double layer supercapacitor. In one model the linear dependence between electrolyte concentration and conductivity is accounted for, while in the other model it is not. A spectral element method is used to discretise the model equations and it is found that the error convergence rate with respect to the number of elements is faster compared to a finite difference method. The increased accuracy of the spectral element approach means that, for a similar level of solution accuracy, the model simulation computing time is approximately 50% of that of the finite difference method. This suggests that the spectral element model could be used for control and state estimation purposes. For a typical supercapacitor charging profile, the numerical solutions from both models closely match experimental voltage and current data. However, when the electrolyte is dilute or where there is a long charging time, a noticeable difference between the numerical solutions of the two models is observed. Electrical impedance spectroscopy simulations show that the capacitance of the two models rapidly decreases when the frequency of the perturbation current exceeds an upper threshold.
Simple pairs of points in digital spaces. Topology-preserving transformations of digital spaces by contracting simple pairs of points
Venue: arXiv cs.DM 2014
Year: 2014

Transformations of digital spaces preserving local and global topology play an important role in thinning, skeletonization and simplification of digital images. In the present paper, we introduce and study contractions of simple pair of points based on the notions of a digital contractible space and contractible transformations of digital spaces. We show that the contraction of a simple pair of points preserves local and global topology of a digital space. Relying on the obtained results, we study properties if digital manifolds. In particular, we show that a digital n-manifold can be transformed to its compressed form with the minimal number of points by sequential contractions of simple pairs. Key Words: Graph, digital space, contraction, splitting, simple pair, homotopy, thinning
Parameter Space Design of Repetitive Controllers for Satisfying a Robust Performance Requirement
Venue: arXiv cs.SY 2014
Year: 2014

A parameter space procedure for designing chosen parameters of a repetitive controller to satisfy a robust performance criterion is presented. Using this method, low order robust repetitive controllers can be designed and implemented for plants that possibly include time delay, poles on the imaginary axis and discontinuous weights. A design and simulation study based on a high speed atomic force microscope position control example is utilized to illustrate the method presented in this paper.
Mapping of Secondary Virtual Networks onto Wireless Substrate based on Cognitive Radio: multi-objective formulation and analysis
Venue: arXiv cs.NI 2014
Year: 2014

There is a growing demand for wireless services with different requirements in a dense and heterogeneous wireless environment. Handling this complex ecosystem is becoming a challenging issue, and wireless virtualization emerges as an efficient solution. Although the inclusion of virtualization in wireless networks ensures a better use of resources, current approaches adopted for wireless virtualization can cause an underutilization of resources, since the resource allocated to a virtual wireless network is not shared with other one. This problem can be overcome by combining wireless virtualization with the cognitive radio (CR) technology and dynamic access spectrum (DSA) techniques. Thus, virtual wireless networks with different access priorities to resources (e.g., primary and secondary) can be deployed in an overlay form and share the same substrate wireless network, where the secondary networks use the resources opportunistically. However, challenges emerge in this new scenario, ranging from the mapping to the operation of these networks. This paper is the first to propose the cognitive radio virtual network environment and to formulate the problem of mapping the secondary virtual networks (SVNs) onto the wireless substrate network based on CR. To this end, a multi-objective formulation is designed. Moreover, an analysis of the metrics defined in the problem is performed in order to give the reader useful assistance in designing schemes to solve the problem of mapping SVNs onto substrate networks.
Braid is undecidable
Venue: arXiv cs.CC 2014
Year: 2014

Braid is a 2008 puzzle game centered around the ability to reverse time. We show that Braid can simulate an arbitrary computation. Our construction makes no use of Braid's unique time mechanics, and therefore may apply to many other video games. We also show that a plausible "bounded" variant of Braid lies within 2-EXPSPACE. Our proof relies on a technical lemma about Turing machines which may be of independent interest. Namely, define a braidlike Turing machine to be a Turing machine that, when it writes to the tape, deletes all data on the tape to the right of the head. We prove that deciding the behavior of such a machine lies in EXPSPACE.
Fast and Optimal Power Control Games in Multiuser MIMO Networks
Venue: arXiv cs.GT 2014
Year: 2014

In this paper, we analyze the problem of power control in a multiuser MIMO network, where the optimal linear precoder is employed in each user to achieve maximum point- to-point information rate. We design a distributed power control algorithm based on the concept of game theory and contractive functions that has a couple of advantages over the previous designs (e.g. more uniqueness probability of Nash equilibria and asynchronous implementation). Despite these improvements, the sum-rate of the users does not increase because the proposed algorithm can not lead the power control game to an efficient equilibrium point. We solve this issue by modifying our algorithm such that the game is led to the equilibrium that satisfies a particular criterion. This criterion can be chosen by the designer to achieve a certain optimality among the equilibria. Furthermore, we propose the inexact method that helps us to boost the convergence speed of our modified algorithms. Lastly, we show that pricing algorithms can also be a special case of our modified algorithms. Simulations show a noticeable improvement in the sum-rate when we modify our proposed algorithm.
Semantic HMC for Big Data Analysis
Venue: arXiv cs.AI 2014
Year: 2014

Analyzing Big Data can help corporations to im-prove their efficiency. In this work we present a new vision to derive Value from Big Data using a Semantic Hierarchical Multi-label Classification called Semantic HMC based in a non-supervised Ontology learning process. We also proposea Semantic HMC process, using scalable Machine-Learning techniques and Rule-based reasoning.
On the Induced Matching Problem in Hamiltonian Bipartite Graphs
Venue: arXiv cs.CC 2014
Year: 2014

In this paper, we study the parameterized complexity and inapproximability of the {\sc Induced Matching} problem in hamiltonian bipartite graphs. We show that, given a hamiltonian cycle in a hamiltonian bipartite graph, the problem is W[1]-hard and cannot be solved in time $n^{o(k^{\frac{1}{2}})}$ unless W[1]=FPT, where $n$ is the number of vertices in the graph. In addition, we show that unless NP=P, the maximum induced matching in a hamiltonian graph cannot be approximated within a ratio of $n^{1-ε}$, where $n$ is the number of vertices in the graph. For a bipartite hamiltonian graph in $n$ vertices, it is NP-hard to approximate its maximum induced matching based on a hamiltonian cycle of the graph within a ratio of $n^{\frac{1}{4}-ε}$, where $n$ is the number of vertices in the graph and $ε$ is any positive constant.
Tree-like resolution complexity of two planar problems
Venue: arXiv cs.CC 2014
Year: 2014

We consider two CSP problems: the first CSP encodes 2D Sperner's lemma for the standard triangulation of the right triangle on $n^2$ small triangles; the second CSP encodes the fact that it is impossible to match cells of $n \times n$ square to arrows (two horizontal, two vertical and four diagonal) such that arrows in two cells with a common edge differ by at most $45^\circ$, and all arrows on the boundary of the square do not look outside (this fact is a corollary of the Brower's fixed point theorem). We prove that the tree-like resolution complexities of these CSPs are $2^{Θ(n)}$. For Sperner's lemma our result implies $Ω(n)$ lower bound on the number of request to colors of vertices that is enough to make in order to find a trichromatic triangle; this lower bound was originally proved by Crescenzi and Silvestri. CSP based on Sperner's lemma is related with the $\rm PPAD$-complete problem. We show that CSP corresponding to arrows is also related with a $\rm PPAD$-complete problem.
Verification of Programs by Combining Iterated Specialization with Interpolation
Venue: arXiv cs.LO 2014
Year: 2014

We present a verification technique for program safety that combines Iterated Specialization and Interpolating Horn Clause Solving. Our new method composes together these two techniques in a modular way by exploiting the common Horn Clause representation of the verification problem. The Iterated Specialization verifier transforms an initial set of verification conditions by using unfold/fold equivalence preserving transformation rules. During transformation, program invariants are discovered by applying widening operators. Then the output set of specialized verification conditions is analyzed by an Interpolating Horn Clause solver, hence adding the effect of interpolation to the effect of widening. The specialization and interpolation phases can be iterated, and also combined with other transformations that change the direction of propagation of the constraints (forward from the program preconditions or backward from the error conditions). We have implemented our verification technique by integrating the VeriMAP verifier with the FTCLP Horn Clause solver, based on Iterated Specialization and Interpolation, respectively. Our experimental results show that the integrated verifier improves the precision of each of the individual components run separately.
Simple Two-Dimensional Object Tracking based on a Graph Algorithm
Venue: arXiv cs.CV 2014
Year: 2014

The visual observation and tracking of cells and other micrometer-sized objects has many different biomedical applications. The automation of those tasks based on computer methods helps in the evaluation of such measurements. In this work, we present a general purpose algorithm that excels at evaluating deterministic behavior of micrometer-sized objects. Our concrete application is the tracking of fast moving objects over large distances along deterministic trajectories in a microscopic video. Thereby, we are able to determine characteristic properties of the objects. For this purpose, we use a set of basic algorithms, including blob recognition, feature-based shape recognition and a graph algorithm, and combined them in a novel way. An evaluation of the algorithms performance shows a high accuracy in the recognition of objects as well as of complete trajectories. Moreover, a direct comparison to a similar algorithm shows superior recognition rates.
Ceramics Fragments Digitization by Photogrammetry, Reconstructions and Applications
Venue: arXiv cs.GR 2014
Year: 2014

This paper presents an application of photogrammetry on ceramic fragments from two excavation sites located north-west of France. The restitution by photogrammetry of these different fragments allowed reconstructions of the potteries in their original state or at least to get to as close as possible. We used the 3D reconstructions to compute some metrics and to generate a presentation support by using a 3D printer. This work is based on affordable tools and illustrates how 3D technologies can be quite easily integrated in archaeology process with limited financial resources. 1. INTRODUCTION Today, photogrammetry and 3D modelling are an integral part of the methods used in archeology and heritage management. They provide answers to scientific needs in the fields of conservation, preservation, restoration and mediation of architectural, archaeological and cultural heritage [2] [6] [7] [9]. Photogrammetry on ceramic fragments was one of the first applications contemporary of the development of this technique applied in the archaeological community [3]. More recently and due to its democratization, it was applied more generally to artifacts [5]. Finally joined today by the rise of 3D printing [8] [10], it can restore fragmented artifacts [1] [12]. These examples target one or several particular objects and use different types of equipment that can be expensive. These aspects can put off uninitiated archaeologists. So it would be appropriate to see if these techniques could be generalized to a whole class of geometrically simple and common artifacts, such as ceramics. From these observations, associated to ceramics specialists with fragments of broken ceramics, we aimed at arranging different tools and methods, including photogrammetry, to explore opportunities for a cheap and attainable reconstruction methodology and its possible applications. Our first objective was to establish a protocol for scanning fragments with photogrammetry, and for reconstruction of original ceramics. We used the digital reconstitutions of the ceramics we got following our process to calculate some metrics and to design and 3D print a display for the remaining fragments of one pottery.
A perspective on the advancement of natural language processing tasks via topological analysis of complex networks
Venue: arXiv cs.CL 2014
Year: 2014

Comment on "Approaching human language with complex networks" by Cong and Liu (Physics of Life Reviews, Volume 11, Issue 4, December 2014, Pages 598-618).
CloudQTL: Evolving a Bioinformatics Application to the Cloud
Venue: arXiv cs.DC 2014
Year: 2014

A timeline is presented which shows the stages involved in converting a bioinformatics software application from a set of standalone algorithms through to a simple web based tool then to a web based portal harnessing Grid technologies and on to its latest inception as a Cloud based bioinformatics web tool. The nature of the software is discussed together with a description of its development at various stages including a detailed account of the Cloud service. An outline of user results is also included.
Efficient algorithms to decide tightness
Venue: arXiv cs.CG 2014
Year: 2014

Tightness is a generalisation of the notion of convexity: a space is tight if and only if it is "as convex as possible", given its topological constraints. For a simplicial complex, deciding tightness has a straightforward exponential time algorithm, but efficient methods to decide tightness are only known in the trivial setting of triangulated surfaces. In this article, we present a new polynomial time procedure to decide tightness for triangulations of $3$-manifolds -- a problem which previously was thought to be hard. Furthermore, we describe an algorithm to decide general tightness in the case of $4$-dimensional combinatorial manifolds which is fixed parameter tractable in the treewidth of the $1$-skeletons of their vertex links, and we present an algorithm to decide $\mathbb{F}_2$-tightness for weak pseudomanifolds $M$ of arbitrary but fixed dimension which is fixed parameter tractable in the treewidth of the dual graph of $M$.
Searching and Indexing Genomic Databases via Kernelization
Venue: arXiv cs.DS 2014
Year: 2014

The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one reference genome and the parts of the other genomes where they differ. In this paper we survey the twenty-year history of this idea and discuss its relation to kernelization in parameterized complexity.
Chases and Bag-Set Certain Answers
Venue: arXiv cs.DB 2014
Year: 2014

In this paper we show that the chase technique is powerful enough to capture the bag-set semantics of conjunctive queries over IDBs and IDs and TGDs. In addition, we argue that in such cases it provides efficient (LogSpace) query evaluation algorithms and that, moreover, it can serve as a basis for evaluating some restricted classes of aggregate queries under incomplete information.
Tracking the Frequency Moments at All Times
Venue: arXiv cs.DS 2014
Year: 2014

The traditional requirement for a randomized streaming algorithm is just {\em one-shot}, i.e., algorithm should be correct (within the stated $\eps$-error bound) at the end of the stream. In this paper, we study the {\em tracking} problem, where the output should be correct at all times. The standard approach for solving the tracking problem is to run $O(\log m)$ independent instances of the one-shot algorithm and apply the union bound to all $m$ time instances. In this paper, we study if this standard approach can be improved, for the classical frequency moment problem. We show that for the $F_p$ problem for any $1 < p \le 2$, we actually only need $O(\log \log m + \log n)$ copies to achieve the tracking guarantee in the cash register model, where $n$ is the universe size. Meanwhile, we present a lower bound of $Ω(\log m \log\log m)$ bits for all linear sketches achieving this guarantee. This shows that our upper bound is tight when $n=(\log m)^{O(1)}$. We also present an $Ω(\log^2 m)$ lower bound in the turnstile model, showing that the standard approach by using the union bound is essentially optimal.