OpenRaiser/Intern-Atlas huggingface dataset:
A coevolving model based on preferential triadic closure for social media networks
Venue: arXiv cs.SI 2013
Year: 2013

The dynamical origin of complex networks, i.e., the underlying principles governing network evolution, is a crucial issue in network study. In this paper, by carrying out analysis to the temporal data of Flickr and Epinions--two typical social media networks, we found that the dynamical pattern in neighborhood, especially the formation of triadic links, plays a dominant role in the evolution of networks. We thus proposed a coevolving dynamical model for such networks, in which the evolution is only driven by the local dynamics--the preferential triadic closure. Numerical experiments verified that the model can reproduce global properties which are qualitatively consistent with the empirical observations.
Truth Table Minimization of Computational Models
Venue: arXiv cs.CC 2013
Year: 2013

Complexity theory offers a variety of concise computational models for computing boolean functions - branching programs, circuits, decision trees and ordered binary decision diagrams to name a few. A natural question that arises in this context with respect to any such model is this: Given a function f:{0,1}^n \to {0,1}, can we compute the optimal complexity of computing f in the computational model in question? (according to some desirable measure). A critical issue regarding this question is how exactly is f given, since a more elaborate description of f allows the algorithm to use more computational resources. Among the possible representations are black-box access to f (such as in computational learning theory), a representation of f in the desired computational model or a representation of f in some other model. One might conjecture that if f is given as its complete truth table (i.e., a list of f's values on each of its 2^n possible inputs), the most elaborate description conceivable, then any computational model can be efficiently computed, since the algorithm computing it can run poly(2^n) time. Several recent studies show that this is far from the truth - some models have efficient and simple algorithms that yield the desired result, others are believed to be hard, and for some models this problem remains open. In this thesis we will discuss the computational complexity of this question regarding several common types of computational models. We shall present several new hardness results and efficient algorithms, as well as new proofs and extensions for known theorems, for variants of decision trees, formulas and branching programs.
The Rise and Fall of Semantic Rule Updates Based on SE-Models
Venue: arXiv cs.AI 2013
Year: 2013

Logic programs under the stable model semantics, or answer-set programs, provide an expressive rule-based knowledge representation framework, featuring a formal, declarative and well-understood semantics. However, handling the evolution of rule bases is still a largely open problem. The AGM framework for belief change was shown to give inappropriate results when directly applied to logic programs under a non-monotonic semantics such as the stable models. The approaches to address this issue, developed so far, proposed update semantics based on manipulating the syntactic structure of programs and rules. More recently, AGM revision has been successfully applied to a significantly more expressive semantic characterisation of logic programs based on SE-models. This is an important step, as it changes the focus from the evolution of a syntactic representation of a rule base to the evolution of its semantic content. In this paper, we borrow results from the area of belief update to tackle the problem of updating (instead of revising) answer-set programs. We prove a representation theorem which makes it possible to constructively define any operator satisfying a set of postulates derived from Katsuno and Mendelzon's postulates for belief update. We define a specific operator based on this theorem, examine its computational complexity and compare the behaviour of this operator with syntactic rule update semantics from the literature. Perhaps surprisingly, we uncover a serious drawback of all rule update operators based on Katsuno and Mendelzon's approach to update and on SE-models.
Improving the efficiency of the LDPC code-based McEliece cryptosystem through irregular codes
Venue: arXiv cs.IT 2013
Year: 2013

We consider the framework of the McEliece cryptosystem based on LDPC codes, which is a promising post-quantum alternative to classical public key cryptosystems. The use of LDPC codes in this context allows to achieve good security levels with very compact keys, which is an important advantage over the classical McEliece cryptosystem based on Goppa codes. However, only regular LDPC codes have been considered up to now, while some further improvement can be achieved by using irregular LDPC codes, which are known to achieve better error correction performance than regular LDPC codes. This is shown in this paper, for the first time at our knowledge. The possible use of irregular transformation matrices is also investigated, which further increases the efficiency of the system, especially in regard to the public key size.
Stability of Multi-Task Kernel Regression Algorithms
Venue: arXiv cs.LG 2013
Year: 2013

We study the stability properties of nonlinear multi-task regression in reproducing Hilbert spaces with operator-valued kernels. Such kernels, a.k.a. multi-task kernels, are appropriate for learning prob- lems with nonscalar outputs like multi-task learning and structured out- put prediction. We show that multi-task kernel regression algorithms are uniformly stable in the general case of infinite-dimensional output spaces. We then derive under mild assumption on the kernel generaliza- tion bounds of such algorithms, and we show their consistency even with non Hilbert-Schmidt operator-valued kernels . We demonstrate how to apply the results to various multi-task kernel regression methods such as vector-valued SVR and functional ridge regression.
Multi-view in Lensless Compressive Imaging
Venue: arXiv cs.IT 2013
Year: 2013

Multi-view images are acquired by a lensless compressive imaging architecture, which consists of an aperture assembly and multiple sensors. The aperture assembly consists of a two dimensional array of aperture elements whose transmittance can be individually controlled to implement a compressive sensing matrix. For each transmittance pattern of the aperture assembly, each of the sensors takes a measurement. The measurement vectors from the multiple sensors represent multi-view images of the same scene. We present theoretical framework for multi-view reconstruction and experimental results for enhancing quality of image using multi-view.
Lifting $\ell_q$-optimization thresholds
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we look at a connection between the $\ell_q,0\leq q\leq 1$, optimization and under-determined linear systems of equations with sparse solutions. The case $q=1$, or in other words $\ell_1$ optimization and its a connection with linear systems has been thoroughly studied in last several decades; in fact, especially so during the last decade after the seminal works \cite{CRT,DOnoho06CS} appeared. While current understanding of $\ell_1$ optimization-linear systems connection is fairly known, much less so is the case with a general $\ell_q,0<q<1$, optimization. In our recent work \cite{StojnicLqThrBnds10} we provided a study in this direction. As a result we were able to obtain a collection of lower bounds on various $\ell_q,0\leq q\leq 1$, optimization thresholds. In this paper, we provide a substantial conceptual improvement of the methodology presented in \cite{StojnicLqThrBnds10}. Moreover, the practical results in terms of achievable thresholds are also encouraging. As is usually the case with these and similar problems, the methodology we developed emphasizes their a combinatorial nature and attempts to somehow handle it. Although our results' main contributions should be on a conceptual level, they already give a very strong suggestion that $\ell_q$ optimization can in fact provide a better performance than $\ell_1$, a fact long believed to be true due to a tighter optimization relaxation it provides to the original $\ell_0$ sparsity finding oriented original problem formulation. As such, they in a way give a solid boost to further exploration of the design of the algorithms that would be able to handle $\ell_q,0<q<1$, optimization in a reasonable (if not polynomial) time.
Satisfiability Algorithms for Restricted Circuit Classes
Venue: arXiv cs.CC 2013
Year: 2013

In recent years, finding new satisfiability algorithms for various circuit classes has been a very active line of research. Despite considerable progress, we are still far away from a definite answer on which circuit classes allow fast satisfiability algorithms. This survey takes a (far from exhaustive) look at some recent satisfiability algorithms for a range of circuit classes and high- lights common themes. A special focus is given to connections between satisfiability algorithms and circuit lower bounds. A second focus is on reductions from satisfiability algorithms to a range of polynomial time problems, such as matrix multiplication and the Vector Domination Problem.
An Algorithm to Find Optimal Attack Paths in Nondeterministic Scenarios
Venue: arXiv cs.CR 2013
Year: 2013

As penetration testing frameworks have evolved and have become more complex, the problem of controlling automatically the pentesting tool has become an important question. This can be naturally addressed as an attack planning problem. Previous approaches to this problem were based on modeling the actions and assets in the PDDL language, and using off-the-shelf AI tools to generate attack plans. These approaches however are limited. In particular, the planning is classical (the actions are deterministic) and thus not able to handle the uncertainty involved in this form of attack planning. We herein contribute a planning model that does capture the uncertainty about the results of the actions, which is modeled as a probability of success of each action. We present efficient planning algorithms, specifically designed for this problem, that achieve industrial-scale runtime performance (able to solve scenarios with several hundred hosts and exploits). These algorithms take into account the probability of success of the actions and their expected cost (for example in terms of execution time, or network traffic generated). We thus show that probabilistic attack planning can be solved efficiently for the scenarios that arise when assessing the security of large networks. Two "primitives" are presented, which are used as building blocks in a framework separating the overall problem into two levels of abstraction. We also present the experimental results obtained with our implementation, and conclude with some ideas for further work.
Energy efficient routing in mobile ad-hoc networks for Healthcare Environments
Venue: arXiv cs.NI 2013
Year: 2013

The modern and innovative medical applications based on wireless network are being developed in the commercial sectors as well as in research. The emerging wireless networks are rapidly becoming a fundamental part of medical solutions due to increasing accessibility for healthcare professionals/patients reducing healthcare costs. Discovering the routes among hosts that are energy efficient without compromise on smooth communication is desirable. This work investigates energy efficiency of some selected proactive and reactive routing protocols in wireless network for healthcare environments. After simulation and analysis we found that DSR is best energy efficient routing protocol among DSR, DSDV and AODV, because DSR has maximum remaining energy.
Modeling of Multipath Transport
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we propose a model for evaluating the transmission performance of multipath transport. Previous researches focused exclusively on single pair users in simple scenarios. The distinct perspective in this paper is to build models for analyzing the performance when multipath transport is used in the entire network scope. We illustrate the influences on the transmission performance caused by the variation of network topologies, the services' arrival rate, the services' size and other parameters. We demonstrate through simulation that multipath transport could conditionally increase the throughput than single-path transport. And it has the capability to support higher services' arrival rate in various network topologies. And higher multi-parent probability will be beneficial for multipath transport to take its advantages.
Application of particle swarm optimization for enhanced cyclic steam stimulation in a offshore heavy oil reservoir
Venue: arXiv cs.CE 2013
Year: 2013

Three different variations of PSO algorithms, i.e. Canonical, Gaussian Bare-bone and Lévy Bare-bone PSO, are tested to optimize the ultimate oil recovery of a large heavy oil reservoir. The performance of these algorithms was compared in terms of convergence behaviour and the final optimization results. It is found that, in general, all three types of PSO methods are able to improve the objective function. The best objective function is found by using the Canonical PSO, while the other two methods give similar results. The Gaussian Bare-bone PSO may picks positions that are far away from the optimal solution. The Lévy Bare-bone PSO has similar convergence behaviour as the Canonical PSO. For the specific optimization problem investigated in this study, it is found that the temperature of the injection steam, CO2 composition in the injection gas, and the gas injection rates have bigger impact on the objective function, while steam injection rate and the liquid production rate have less impact on the objective function.
Exploring Verbalization and Collaboration during Usability Evaluation with Children in Context
Venue: arXiv cs.HC 2013
Year: 2013

In this paper, we investigate the effect of context on usability evaluation. The focus is on how children behave and perform when they are tested in different settings. Two most commonly applied usability evaluation methods: the think-aloud and constructive interactions are applied to the children in different physical contexts. We present an experimental design involving 54 children participating in two different configurations of constructive interaction and a traditional think-aloud. The behavior and performance of the children in two different physical contexts is measured by evaluating the results of application of think-aloud and constructive interaction. Finally, we outline lessons on the impact of context on involving children in usability testing.
Punjabi Language Interface to Database: a brief review
Venue: arXiv cs.CL 2013
Year: 2013

Unlike most user-computer interfaces, a natural language interface allows users to communicate fluently with a computer system with very little preparation. Databases are often hard to use in cooperating with the users because of their rigid interface. A good NLIDB allows a user to enter commands and ask questions in native language and then after interpreting respond to the user in native language. For a large number of applications requiring interaction between humans and the computer systems, it would be convenient to provide the end-user friendly interface. Punjabi language interface to database would proof fruitful to native people of Punjab, as it provides ease to them to use various e-governance applications like Punjab Sewa, Suwidha, Online Public Utility Forms, Online Grievance Cell, Land Records Management System,legacy matters, e-District, agriculture, etc. Punjabi is the mother tongue of more than 110 million people all around the world. According to available information, Punjabi ranks 10th from top out of a total of 6,900 languages recognized internationally by the United Nations. This paper covers a brief overview of the Natural language interface to database, its different components, its advantages, disadvantages, approaches and techniques used. The paper ends with the work done on Punjabi language interface to database and future enhancements that can be done.
Hierarchical Parallel Matrix Multiplication on Large-Scale Distributed Memory Platforms
Venue: arXiv cs.DC 2013
Year: 2013

Matrix multiplication is a very important computation kernel both in its own right as a building block of many scientific applications and as a popular representative for other scientific applications. Cannon algorithm which dates back to 1969 was the first efficient algorithm for parallel matrix multiplication providing theoretically optimal communication cost. However this algorithm requires a square number of processors. In the mid 1990s, the SUMMA algorithm was introduced. SUMMA overcomes the shortcomings of Cannon algorithm as it can be used on a non-square number of processors as well. Since then the number of processors in HPC platforms has increased by two orders of magnitude making the contribution of communication in the overall execution time more significant. Therefore, the state of the art parallel matrix multiplication algorithms should be revisited to reduce the communication cost further. This paper introduces a new parallel matrix multiplication algorithm, Hierarchical SUMMA (HSUMMA), which is a redesign of SUMMA. Our algorithm reduces the communication cost of SUMMA by introducing a two-level virtual hierarchy into the two-dimensional arrangement of processors. Experiments on an IBM BlueGene-P demonstrate the reduction of communication cost up to 2.08 times on 2048 cores and up to 5.89 times on 16384 cores.
On the Broadcast Latency in Finite Cooperative Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

The aim of this paper is to study the effect of cooperation on system delay, quantified as the number of retransmissions required to deliver a broadcast message to all intended receivers. Unlike existing works on broadcast scenarios, where distance between nodes is not explicitly considered, we examine the joint effect of small scale fading and propagation path loss. Also, we study cooperation in application to finite networks, i.e. when the number of cooperating nodes is small. Stochastic geometry and order statistics are used to develop analytical models that tightly match the simulation results for non-cooperative scenario and provide a lower bound for delay in a cooperative setting. We demonstrate that even for a simple flooding scenario, cooperative broadcast achieves significantly lower system delay.
A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
Venue: arXiv cs.CR 2013
Year: 2013

In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type $n^{O(\log n)}$ where $n$ is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any $L(\varepsilon)$ for $ε>0$. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to $L(1/4+o(1))$.
Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences
Venue: arXiv cs.DM 2013
Year: 2013

The Longest Common Subsequence (LCS) problem is a very important problem in math- ematics, which has a broad application in scheduling problems, physics and bioinformatics. It is known that the given two random sequences of infinite lengths, the expected length of LCS will be a constant. however, the value of this constant is not yet known. Moreover, the variance distribution of LCS length is also not fully understood. The problem becomes more difficult when there are (a) multiple sequences, (b) sequences with non-even distribution of alphabets and (c) large alphabets. This work focus on these more complicated issues. We have systematically analyze the expected length, variance and distribution of LCS based on extensive Monte Carlo simulation. The results on expected length are consistent with currently proved theoretical results, and the analysis on variance and distribution provide further insights into the problem.
Vérification Formelle des Processus Workflow Collaboratifs
Venue: arXiv cs.SE 2013
Year: 2013

In this paper, we present a method of verification of collaborative workflow processes based on model checking techniques. In particular, we propose to verify soundness properties of these processes using SPIN model checker. First we translate the adopted specification of workflows (i.e. the WF-net) to Promela which is the description language of models to be verified by SPIN. Then we express the soundness properties in Linear Temporal Logic (LTL) and use SPIN to test whether each property is satisfied by the Promela model of the WF-net in question. Finally, we express the properties of k-soundness for WF-nets modeling multiple instances and (k,R)-soundness for workflow processes with multiple instances and sharing resources.
Dimming the Internet: Detecting Throttling as a Mechanism of Censorship in Iran
Venue: arXiv cs.NI 2013
Year: 2013

In the days immediately following the contested June 2009 Presidential election, Iranians attempting to reach news content and social media platforms were subject to unprecedented levels of the degradation, blocking and jamming of communications channels. Rather than shut down networks, which would draw attention and controversy, the government was rumored to have slowed connection speeds to rates that would render the Internet nearly unusable, especially for the consumption and distribution of multimedia content. Since, political upheavals elsewhere have been associated with headlines such as "High usage slows down Internet in Bahrain" and "Syrian Internet slows during Friday protests once again," with further rumors linking poor connectivity with political instability in Myanmar and Tibet. For governments threatened by public expression, the throttling of Internet connectivity appears to be an increasingly preferred and less detectable method of stifling the free flow of information. In order to assess this perceived trend and begin to create systems of accountability and transparency on such practices, we attempt to outline an initial strategy for utilizing a ubiquitious set of network measurements as a monitoring service, then apply such methodology to shed light on the recent history of censorship in Iran.
Approximation Algorithm for Sparsest k-Partitioning
Venue: arXiv cs.DS 2013
Year: 2013

Given a graph $G$, the sparsest-cut problem asks to find the set of vertices $S$ which has the least expansion defined as $$ϕ_G(S) := \frac{w(E(S,\bar{S}))}{\min \set{w(S), w(\bar{S})}}, $$ where $w$ is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer $k$, compute a $k$-partition $\set{P_1, \ldots, P_k}$ of the vertex set so as to minimize $$ ϕ_k(\set{P_1, \ldots, P_k}) := \max_i ϕ_G(P_i). $$ Our main result is a polynomial time bi-criteria approximation algorithm which outputs a $(1 - \e)k$-partition of the vertex set such that each piece has expansion at most $O_{\varepsilon}(\sqrt{\log n \log k})$ times $OPT$. We also study balanced versions of this problem.