OpenRaiser/Intern-Atlas huggingface dataset:
Complex Contagions in Kleinberg's Small World Model
Venue: arXiv cs.DS 2014
Year: 2014

Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires the influence by two or more neighbors. In a $k$-complex contagion, a cluster of nodes are initially infected, and additional nodes become infected in the next round if they have at least $k$ already infected neighbors. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. This has motivated rigorous understanding of spreading of complex contagions in social networks. Despite simple contagions ($k=1$) that spread fast in all small world graphs, how complex contagions spread is much less understood. Previous work~\cite{Ghasemiesfeh:2013:CCW} analyzes complex contagions in Kleinberg's small world model~\cite{kleinberg00small} where edges are randomly added according to a spatial distribution (with exponent $γ$) on top of a two dimensional grid structure. It has been shown in~\cite{Ghasemiesfeh:2013:CCW} that the speed of complex contagions differs exponentially when $γ=0$ compared to when $γ=2$. In this paper, we fully characterize the entire parameter space of $γ$ except at one point, and provide upper and lower bounds for the speed of $k$-complex contagions. We study two subtly different variants of Kleinberg's small world model and show that, with respect to complex contagions, they behave differently. For each model and each $k \geq 2$, we show that there is an intermediate range of values, such that when $γ$ takes any of these values, a $k$-complex contagion spreads quickly on the corresponding graph, in a polylogarithmic number of rounds. However, if $γ$ is outside this range, then a $k$-complex contagion requires a polynomial number of rounds to spread to the entire network.
Graphs with large chromatic number induce $3k$-cycles
Venue: arXiv cs.DM 2014
Year: 2014

Answering a question of Kalai and Meshulam, we prove that graphs without induced cycles of length $3k$ have bounded chromatic number. This implies the very first case of a much broader question asserting that every graph with large chromatic number induces a graph $H$ such that the sum of the Betti numbers of the independence complex of $H$ is also large.
A new operational matrix based on Bernoulli polynomials
Venue: arXiv cs.NA 2014
Year: 2014

In this research, the Bernoulli polynomials are introduced. The properties of these polynomials are employed to construct the operational matrices of integration together with the derivative and product. These properties are then utilized to transform the differential equation to a matrix equation which corresponds to a system of algebraic equations with unknown Bernoulli coefficients. This method can be used for many problems such as differential equations, integral equations and so on. Numerical examples show the method is computationally simple and also illustrate the efficiency and accuracy of the method.
Dictionary Matching with One Gap
Venue: arXiv cs.DS 2014
Year: 2014

The dictionary matching with gaps problem is to preprocess a dictionary $D$ of $d$ gapped patterns $P_1,\ldots,P_d$ over alphabet $Σ$, where each gapped pattern $P_i$ is a sequence of subpatterns separated by bounded sequences of don't cares. Then, given a query text $T$ of length $n$ over alphabet $Σ$, the goal is to output all locations in $T$ in which a pattern $P_i\in D$, $1\leq i\leq d$, ends. There is a renewed current interest in the gapped matching problem stemming from cyber security. In this paper we solve the problem where all patterns in the dictionary have one gap with at least $α$ and at most $β$ don't cares, where $α$ and $β$ are given parameters. Specifically, we show that the dictionary matching with a single gap problem can be solved in either $O(d\log d + |D|)$ time and $O(d\log^{\varepsilon} d + |D|)$ space, and query time $O(n(β-α)\log\log d \log ^2 \min \{ d, \log |D| \} + occ)$, where $occ$ is the number of patterns found, or preprocessing time and space: $O(d^2 + |D|)$, and query time $O(n(β-α) + occ)$, where $occ$ is the number of patterns found. As far as we know, this is the best solution for this setting of the problem, where many overlaps may exist in the dictionary.
On the Complexity of Bandit Linear Optimization
Venue: arXiv cs.LG 2014
Year: 2014

We study the attainable regret for online linear optimization problems with bandit feedback, where unlike the full-information setting, the player can only observe its own loss rather than the full loss vector. We show that the price of bandit information in this setting can be as large as $d$, disproving the well-known conjecture that the regret for bandit linear optimization is at most $\sqrt{d}$ times the full-information regret. Surprisingly, this is shown using "trivial" modifications of standard domains, which have no effect in the full-information setting. This and other results we present highlight some interesting differences between full-information and bandit learning, which were not considered in previous literature.
Video Face Editing Using Temporal-Spatial-Smooth Warping
Venue: arXiv cs.CV 2014
Year: 2014

Editing faces in videos is a popular yet challenging aspect of computer vision and graphics, which encompasses several applications including facial attractiveness enhancement, makeup transfer, face replacement, and expression manipulation. Simply applying image-based warping algorithms to video-based face editing produces temporal incoherence in the synthesized videos because it is impossible to consistently localize facial features in two frames representing two different faces in two different videos (or even two consecutive frames representing the same face in one video). Therefore, high performance face editing usually requires significant manual manipulation. In this paper we propose a novel temporal-spatial-smooth warping (TSSW) algorithm to effectively exploit the temporal information in two consecutive frames, as well as the spatial smoothness within each frame. TSSW precisely estimates two control lattices in the horizontal and vertical directions respectively from the corresponding control lattices in the previous frame, by minimizing a novel energy function that unifies a data-driven term, a smoothness term, and feature point constraints. Corresponding warping surfaces then precisely map source frames to the target frames. Experimental testing on facial attractiveness enhancement, makeup transfer, face replacement, and expression manipulation demonstrates that the proposed approaches can effectively preserve spatial smoothness and temporal coherence in editing facial geometry, skin detail, identity, and expression, which outperform the existing face editing methods. In particular, TSSW is robust to subtly inaccurate localization of feature points and is a vast improvement over image-based warping methods.
Compatible Connectivity-Augmentation of Planar Disconnected Graphs
Venue: arXiv cs.CG 2014
Year: 2014

Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled $n$-vertex planar graph, $\mathcal{G}$, that has $r\ge 2$ connected components, and $k\ge 2$ isomorphic planar straight-line drawings, $G_1,\ldots,G_k$, of $\mathcal{G}$. We wish to augment $\mathcal G$ by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to $G_1,\ldots,G_k$ as points and straight-line segments, respectively, to obtain $k$ planar straight-line drawings isomorphic to the augmentation of $\mathcal G$. We show that adding $Θ(nr^{1-1/k})$ edges and vertices to $\mathcal{G}$ is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all $r\in\{2,\ldots,n\}$ and $k\ge 2$ and is achievable by an algorithm whose running time is $O(nr^{1-1/k})$ for $k=O(1)$ and whose running time is $O(kn^2)$ for general values of $k$. The lower bound holds for all $r\in\{2,\ldots,n/4\}$ and $k\ge 2$.
Controlled Natural Language Processing as Answer Set Programming: an Experiment
Venue: arXiv cs.CL 2014
Year: 2014

Most controlled natural languages (CNLs) are processed with the help of a pipeline architecture that relies on different software components. We investigate in this paper in an experimental way how well answer set programming (ASP) is suited as a unifying framework for parsing a CNL, deriving a formal representation for the resulting syntax trees, and for reasoning with that representation. We start from a list of input tokens in ASP notation and show how this input can be transformed into a syntax tree using an ASP grammar and then into reified ASP rules in form of a set of facts. These facts are then processed by an ASP meta-interpreter that allows us to infer new knowledge.
Computational Evidence that Self-regulation of Creativity is Good for Society
Venue: arXiv cs.CY 2014
Year: 2014

Excess individual creativity can be detrimental to society because creators invest in unproven ideas at the expense of propagating proven ones. Moreover, a proportion of individuals can benefit from creativity without being creative themselves by copying creators. We hypothesized that (1) societies increase their rate of cultural evolution by tempering the novelty-generating effects of creativity with the novelty-preserving effects of imitation, and (2) this is carried out by selectively rewarding and punishing creativity according to the value of the individuals' creative outputs. We tested this using an agent-based model of cultural evolution in which each agent self-regulated its invention-to-imitation ratio as a function of the fitness of its cultural outputs. In self-regulating societies, agents segregated into creators and imitators. The mean fitness of cultural outputs was higher than in non-self-regulating societies, and changes in diversity were rapider and more pronounced. We discuss limitations and possible social implications of our findings.
A Proposed Framework for Development of a Visualizer Based on Memory Transfer Language (MTL)
Venue: arXiv cs.PL 2014
Year: 2014

Computer programming is among the fundamental aspects of computer science curriculum. Many students first introduced to introductory computer programming courses experience difficulties in learning and comprehending. Vast amount of researches have revealed that, generally programming courses are regarded as difficult and challenging and thus often have the highest dropout rates. Moreover, numerous researches have devoted in delivering new approaches and tools in enhancing the process of teaching and learning computer programming to novice programmers. One among the tools that have emerged to offer positive results is Program Visualization tool (Visualizer). Visualizers have shown remarkable contributions in facilitating novices to learn and comprehend computer programming. In addition to that, an approach to visualize codes execution, Memory Transfer Language (MTL), allows a novice to animate the code through paper and pencil mechanism without actively involving the machine. MTL depends on the concepts of RAM (Random Access Memory) to interpret the code line by line. Programming requires effort and special approach in the way it is learned and taught, thus this paper aimed at presenting a proposed framework for developing a visualizer that employs the use of MTL to enhance teaching and learning programming.
TCP-Forward: Fast and Reliable TCP Variant for Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

The congestion control algorithms in TCP may incur inferior performance in a lossy network context like wireless networks. Previous works have shown that random linear network coding can improve the throughput of TCP in such networks, although it introduces extra decoding delay at the destination. In this paper we try to alleviate the decoding delay by replacing random linear network coding with LT Codes. Due to the inherent difference between linear network coding and Fountain Codes, such replacement is not as simple as it sounds. We conquer some practical problems and come up with TCP-Forward, a new TCP variant which offers many properties that TCP as a streaming transport protocol should offer. Our performance evaluation shows TCP-Forward provides better performance than previous works.
First Experiences With Validating and Using the Cray Power Management Database Tool
Venue: arXiv cs.DC 2014
Year: 2014

In October 2013 CSCS installed the first hybrid Cray XC-30 system, dubbed Piz Daint. This system features the power management database (PMDB), that was recently introduced by Cray to collect detailed power consumption information in a non-intrusive manner. Power measurements are taken on each node, with additional measurements for the Aries network and blowers, and recorded in a database. This enables fine-grained reporting of power consumption that is not possible with external power meters, and is useful to both application developers and facility operators. This paper will show how benchmarks of representative applications at CSCS were used to validate the PMDB on Piz Daint. Furthermore we will elaborate, with the well-known HPL benchmark serving as prototypical application, on how the PMDB streamlines the tuning for optimal power efficiency in production, which lead to Piz Daint being recognised as the most energy efficient petascale supercomputer presently in operation.
Fast Convex Decomposition for Truthful Social Welfare Approximation
Venue: arXiv cs.GT 2014
Year: 2014

Approximating the optimal social welfare while preserving truthfulness is a well studied problem in algorithmic mechanism design. Assuming that the social welfare of a given mechanism design problem can be optimized by an integer program whose integrality gap is at most $α$, Lavi and Swamy~\cite{Lavi11} propose a general approach to designing a randomized $α$-approximation mechanism which is truthful in expectation. Their method is based on decomposing an optimal solution for the relaxed linear program into a convex combination of integer solutions. Unfortunately, Lavi and Swamy's decomposition technique relies heavily on the ellipsoid method, which is notorious for its poor practical performance. To overcome this problem, we present an alternative decomposition technique which yields an $α(1 + ε)$ approximation and only requires a quadratic number of calls to an integrality gap verifier.
Certifying solutions to overdetermined and singular polynomial systems over Q
Venue: arXiv cs.SC 2014
Year: 2014

This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute the exact "rational univariate representation" (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using alpha-theory. To certify isolated singular roots, we use a determinantal form of the "isosingular deflation", which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
The Influence of Architectural Styles on Security, Using the Example of a Certification Authority
Venue: arXiv cs.CR 2014
Year: 2014

Often, security is considered in an advanced stage of the implementation of a system, rather than integrating it into the system design. This leads to less secure systems, as the security mechanisms are only applied as an afterthought and therefore do not integrate well with the rest of the design. Also, several statistics about discovered vulnerabilities in existing systems suggest, that most of the vulnerabilities of a system are not caused by errors in the cryptographic primitives, but in other parts of the implementation. So integrating security concerns early in the design process seems a promising approach for increasing the security of the resulting system. This work evaluates how the choice of the architectural style affects the security of the resulting system. The evaluation is done on the example of an existing certification authority (CA). The requirements for the system are gathered and multiple designs according to different architectural styles are drafted and evaluated using a risk evaluation method. Then the evaluated designs are compared to find out whether there are significant differences.
Learning a hyperplane classifier by minimizing an exact bound on the VC dimension
Venue: arXiv cs.LG 2014
Year: 2014

The VC dimension measures the capacity of a learning machine, and a low VC dimension leads to good generalization. While SVMs produce state-of-the-art learning performance, it is well known that the VC dimension of a SVM can be unbounded; despite good results in practice, there is no guarantee of good generalization. In this paper, we show how to learn a hyperplane classifier by minimizing an exact, or \boldmath{$Θ$} bound on its VC dimension. The proposed approach, termed as the Minimal Complexity Machine (MCM), involves solving a simple linear programming problem. Experimental results show, that on a number of benchmark datasets, the proposed approach learns classifiers with error rates much less than conventional SVMs, while often using fewer support vectors. On many benchmark datasets, the number of support vectors is less than one-tenth the number used by SVMs, indicating that the MCM does indeed learn simpler representations.
A CryptoCubic Protocol for Hacker-Proof Off-Chain Bitcoin Transactions
Venue: arXiv cs.CR 2014
Year: 2014

Off-Chain transactions allow for the immediate transfer of Cryptocurrency between two parties, without delays or unavoidable transaction fees. Such capabilities are critical for mainstream Cryptocurrency adaption. They allow for the "Coffee-Coin Criteria"; under which a customer orders a coffee and pays for that coffee in bitcoins. This is not possible with On-Chain transactions today. Unfortunately, all existing Off-Chain transaction protocols are notoriously unreliable The current generation of third-party facilitators are vulnerable to hacker-based attacks. As Mt. Gox tragically demonstrated, centralized-transaction institutions are easy targets for Cryptocurrency thieves. The slightest security flaw in a third-party system will pounced on by hackers, who will proceed to devour it like ants devouring a crab. Under such circumstances, it no wonder that the Public treats most Cryptocurrency services with a constant shadow of suspicion. For Bitcoin to flourish, its anti-hierarchy principles must be applied to safe Off-Chain transactions. First and foremost, we need a new hacker-proof protocol that can easily be executed by any experienced developer. Preferably, the protocol will be open-sourced for full reliability and transparency. This paper presents one such procedure, which allows for he safe transmission of Bitcoin private key control by way of Cryptocubic transactions.
Learning Multi-Scale Representations for Material Classification
Venue: arXiv cs.CV 2014
Year: 2014

The recent progress in sparse coding and deep learning has made unsupervised feature learning methods a strong competitor to hand-crafted descriptors. In computer vision, success stories of learned features have been predominantly reported for object recognition tasks. In this paper, we investigate if and how feature learning can be used for material recognition. We propose two strategies to incorporate scale information into the learning procedure resulting in a novel multi-scale coding procedure. Our results show that our learned features for material recognition outperform hand-crafted descriptors on the FMD and the KTH-TIPS2 material classification benchmarks.
Real-Time Impulse Noise Suppression from Images Using an Efficient Weighted-Average Filtering
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we propose a method for real-time high density impulse noise suppression from images. In our method, we first apply an impulse detector to identify the corrupted pixels and then employ an innovative weighted-average filter to restore them. The filter takes the nearest neighboring interpolated image as the initial image and computes the weights according to the relative positions of the corrupted and uncorrupted pixels. Experimental results show that the proposed method outperforms the best existing methods in both PSNR measure and visual quality and is quite suitable for real-time applications.
Coalitional Graph Games for Popular Content Distribution in Cognitive Radio VANETs
Venue: arXiv cs.GT 2014
Year: 2014

Popular content distribution is one of the key services provided by vehicular ad hoc networks (VANETs), in which a popular file is broadcasted by roadside units (RSUs) to the on-board units (OBUs) driving through a particular area. Due to fast speed and deep fading, some file packets might be lost during the vehicle-to-roadside broadcasting stage. In this paper, we propose a peer-to-peer (P2P) approach to allow the OBUs to exchange data and complement the missing packets. Specifically, we introduce a coalitional graph game to model the cooperation among OBUs and propose a coalition formation algorithm to implement the P2P approach. Moreover, cognitive radio is utilized for vehicle-to-vehicle transmissions so that the P2P approach does not require additional bandwidth. Simulation results show that the proposed approach performs better in various conditions, relative to the non-cooperative approach, in which the OBUs share no information and simply response to any data request from other OBUs.
Joint User Association and Reuse Pattern Selection in Heterogeneous Networks
Venue: arXiv cs.IT 2014
Year: 2014

The successful deployment of LTE heterogeneous networks (HetNets) depends crucially on the inter-cell interference (ICI) management. Among ICI coordination schemes, fractional frequency reuse (FFR) is considered as an efficient technique well-suited to OFDMA-based HetNets. Two coupled questions in this context are: 1) how to associate users to appropriate base-stations considering the long list of available candidate cells, and 2) how to allocate frequency resources among multiple cells. In this paper, we treat the multi-cell frequency allocation as frequency partitioning among multiple reuse patterns, and develop a novel algorithm to solve these two coupled questions in a joint manner. We also provide practical criterion to select the set of essential candidate patterns from all possible patterns. Results show that the proposed joint strategy improves both the cell-edge user and overall network throughput.