OpenRaiser/Intern-Atlas huggingface dataset:
Unbiased Statistics of a CSP - A Controlled-Bias Generator
Venue: arXiv cs.AI 2011
Year: 2011

We show that estimating the complexity (mean and distribution) of the instances of a fixed size Constraint Satisfaction Problem (CSP) can be very hard. We deal with the main two aspects of the problem: defining a measure of complexity and generating random unbiased instances. For the first problem, we rely on a general framework and a measure of complexity we presented at CISSE08. For the generation problem, we restrict our analysis to the Sudoku example and we provide a solution that also explains why it is so difficult.
Different types of attacks in Mobile ADHOC Network
Venue: arXiv cs.NI 2011
Year: 2011

Security in mobile AD HOC network is a big challenge as it has no centralized authority which can supervise the individual nodes operating in the network. The attacks can come from both inside the network and from the outside. We are trying to classify the existing attacks into two broad categories: DATA traffic attacks and CONTROL traffic attacks. We will also be discussing the presently proposed methods of mitigating those attacks.
A probabilistic-numerical approximation for an obstacle problem arising in game theory
Venue: arXiv cs.GT 2011
Year: 2011

We investigate a two-player zero-sum stochastic differential game in which one of the players has more information on the game than his opponent. We show how to construct numerical schemes for the value function of this game, which is given by the solution of a quasilinear partial differential equation with obstacle.
The Feedback Arc Set Problem with Triangle Inequality is a Vertex Cover Problem
Venue: arXiv cs.DS 2011
Year: 2011

We consider the (precedence constrained) Minimum Feedback Arc Set problem with triangle inequalities on the weights, which finds important applications in problems of ranking with inconsistent information. We present a surprising structural insight showing that the problem is a special case of the minimum vertex cover in hypergraphs with edges of size at most 3. This result leads to combinatorial approximation algorithms for the problem and opens the road to studying the problem as a vertex cover problem.
Question Answering in a Natural Language Understanding System Based on Object-Oriented Semantics
Venue: arXiv cs.CL 2011
Year: 2011

Algorithms of question answering in a computer system oriented on input and logical processing of text information are presented. A knowledge domain under consideration is social behavior of a person. A database of the system includes an internal representation of natural language sentences and supplemental information. The answer {\it Yes} or {\it No} is formed for a general question. A special question containing an interrogative word or group of interrogative words permits to find a subject, object, place, time, cause, purpose and way of action or event. Answer generation is based on identification algorithms of persons, organizations, machines, things, places, and times. Proposed algorithms of question answering can be realized in information systems closely connected with text processing (criminology, operation of business, medicine, document systems).
Quantum Fourier sampling, Code Equivalence, and the quantum security of the McEliece and Sidelnikov cryptosystems
Venue: arXiv cs.CC 2011
Year: 2011

The Code Equivalence problem is that of determining whether two given linear codes are equivalent to each other up to a permutation of the coordinates. This problem has a direct reduction to a nonabelian hidden subgroup problem (HSP), suggesting a possible quantum algorithm analogous to Shor's algorithms for factoring or discrete log. However, we recently showed that in many cases of interest---including Goppa codes---solving this case of the HSP requires rich, entangled measurements. Thus, solving these cases of Code Equivalence via Fourier sampling appears to be out of reach of current families of quantum algorithms. Code equivalence is directly related to the security of McEliece-type cryptosystems in the case where the private code is known to the adversary. However, for many codes the support splitting algorithm of Sendrier provides a classical attack in this case. We revisit the claims of our previous article in the light of these classical attacks, and discuss the particular case of the Sidelnikov cryptosystem, which is based on Reed-Muller codes.
The Anatomy of the Facebook Social Graph
Venue: arXiv cs.SI 2011
Year: 2011

We study the structure of the social graph of active Facebook users, the largest social network ever analyzed. We compute numerous features of the graph including the number of users and friendships, the degree distribution, path lengths, clustering, and mixing patterns. Our results center around three main observations. First, we characterize the global structure of the graph, determining that the social network is nearly fully connected, with 99.91% of individuals belonging to a single large connected component, and we confirm the "six degrees of separation" phenomenon on a global scale. Second, by studying the average local clustering coefficient and degeneracy of graph neighborhoods, we show that while the Facebook graph as a whole is clearly sparse, the graph neighborhoods of users contain surprisingly dense structure. Third, we characterize the assortativity patterns present in the graph by studying the basic demographic and network properties of users. We observe clear degree assortativity and characterize the extent to which "your friends have more friends than you". Furthermore, we observe a strong effect of age on friendship preferences as well as a globally modular community structure driven by nationality, but we do not find any strong gender homophily. We compare our results with those from smaller social networks and find mostly, but not entirely, agreement on common structural network characteristics.
Redundant Wavelets on Graphs and High Dimensional Data Clouds
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we propose a new redundant wavelet transform applicable to scalar functions defined on high dimensional coordinates, weighted graphs and networks. The proposed transform utilizes the distances between the given data points. We modify the filter-bank decomposition scheme of the redundant wavelet transform by adding in each decomposition level linear operators that reorder the approximation coefficients. These reordering operators are derived by organizing the tree-node features so as to shorten the path that passes through these points. We explore the use of the proposed transform to image denoising, and show that it achieves denoising results that are close to those obtained with the BM3D algorithm.
Linear Relation on General Ergodic T-Function
Venue: arXiv cs.CR 2011
Year: 2011

We find linear (as well as quadratic) relations in a very large class of T-functions. The relations may be used in analysis of T-function-based stream ciphers.
Cancer gene prioritization by integrative analysis of mRNA expression and DNA copy number data: a comparative review
Venue: arXiv cs.CE 2011
Year: 2011

A variety of genome-wide profiling techniques are available to probe complementary aspects of genome structure and function. Integrative analysis of heterogeneous data sources can reveal higher-level interactions that cannot be detected based on individual observations. A standard integration task in cancer studies is to identify altered genomic regions that induce changes in the expression of the associated genes based on joint analysis of genome-wide gene expression and copy number profiling measurements. In this review, we provide a comparison among various modeling procedures for integrating genome-wide profiling data of gene copy number and transcriptional alterations and highlight common approaches to genomic data integration. A transparent benchmarking procedure is introduced to quantitatively compare the cancer gene prioritization performance of the alternative methods. The benchmarking algorithms and data sets are available at http://intcomp.r-forge.r-project.org
Solving the TTC 2011 Reengineering Case with Edapt
Venue: arXiv cs.SE 2011
Year: 2011

This paper gives an overview of the Edapt solution to the reengineering case of the Transformation Tool Contest 2011.
Saying Hello World with Epsilon - A Solution to the 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

Epsilon is an extensible platform of integrated and task-specific languages for model management. With solutions to the 2011 TTC Hello World case, this paper demonstrates some of the key features of the Epsilon Object Language (an extension and reworking of OCL), which is at the core of Epsilon. In addition, the paper introduces several of the task-specific languages provided by Epsilon including the Epsilon Generation Language (for model-to-text transformation), the Epsilon Validation Language (for model validation) and Epsilon Flock (for model migration).
Adleman-Manders-Miller Root Extraction Method Revisited
Venue: arXiv cs.SC 2011
Year: 2011

In 1977, Adleman, Manders and Miller had briefly described how to extend their square root extraction method to the general $r$th root extraction over finite fields, but not shown enough details. Actually, there is a dramatic difference between the square root extraction and the general $r$th root extraction because one has to solve discrete logarithms for $r$th root extraction. In this paper, we clarify their method and analyze its complexity. Our heuristic presentation is helpful to grasp the method entirely and deeply.
Drivers of the Cost of Spreadsheet Audit
Venue: arXiv cs.SE 2011
Year: 2011

A review of 75 formal audit assignments shows that the effort taken to identify defects in financial models taken from the domain of limited recourse (project) finance is uncorrelated with common measures of the physical characteristics of the spreadsheets concerned.
Computation of generalized inverses using Php/MySql environment
Venue: arXiv cs.DB 2011
Year: 2011

The main aim of this paper is to develop a client/server-based model for computing the weighted Moore-Penrose inverse using the partitioning method as well as for storage of generated results. The web application is developed in the PHP/MySQL environment. The source code is open and free for testing by using a web browser. Influence of different matrix representations and storage systems on the computational time is investigated. The CPU time for searching the previously stored pseudo-inverses is compared with the CPU time spent for new computation of the same inverses.
Distributed Representation of Geometrically Correlated Images with Compressed Linear Measurements
Venue: arXiv cs.CV 2011
Year: 2011

This paper addresses the problem of distributed coding of images whose correlation is driven by the motion of objects or positioning of the vision sensors. It concentrates on the problem where images are encoded with compressed linear measurements. We propose a geometry-based correlation model in order to describe the common information in pairs of images. We assume that the constitutive components of natural images can be captured by visual features that undergo local transformations (e.g., translation) in different images. We first identify prominent visual features by computing a sparse approximation of a reference image with a dictionary of geometric basis functions. We then pose a regularized optimization problem to estimate the corresponding features in correlated images given by quantized linear measurements. The estimated features have to comply with the compressed information and to represent consistent transformation between images. The correlation model is given by the relative geometric transformations between corresponding features. We then propose an efficient joint decoding algorithm that estimates the compressed images such that they stay consistent with both the quantized measurements and the correlation model. Experimental results show that the proposed algorithm effectively estimates the correlation between images in multi-view datasets. In addition, the proposed algorithm provides effective decoding performance that compares advantageously to independent coding solutions as well as state-of-the-art distributed coding schemes based on disparity learning.
Connecting Spatially Coupled LDPC Code Chains
Venue: arXiv cs.IT 2011
Year: 2011

Codes constructed from connected spatially coupled low-density parity-check code (SC-LDPCC) chains are proposed and analyzed. It is demonstrated that connecting coupled chains results in improved iterative decoding performance. The constructed protograph ensembles have better iterative decoding thresholds compared to an individual SC-LDPCC chain and require less computational complexity per bit when operating in the near-threshold region. In addition, it is shown that the proposed constructions are asymptotically good in terms of minimum distance.
Agile and Pro-Active Public Administration as a Collaborative Networked Organization
Venue: arXiv cs.CY 2011
Year: 2011

In highly competitive, globalized economies and societies of always-on-line people intensively using the Internet and mobile phones, public administrations have to adapt to new challenges. Enterprises and citizens expect public administrations to be agile and pro-active to foster development. A way to achieve agility and pro-activity is application of a model of Collaborative Network Organizations in its two forms: Virtual Organizations (VO) and Virtual Organization Breeding Environments (VOBE). In the paper, advantages are shown of public administration playing a role of a Virtual Organization customer on the one hand, and a Virtual Organization member on the other hand. It is also shown how public administration playing a role of a Virtual Organization Breeding Environment may improve its agility and promote advanced technologies and management methods among local organizations. It is argued in the paper that public administration should provide a Virtual Organization Breeding Environment as a part of public services.
Reference Model for Performance Management in Service-Oriented Virtual Organization Breeding Environments
Venue: arXiv cs.OH 2011
Year: 2011

Performance management (PM) is a key function of virtual organization (VO) management. A large set of PM indicators has been proposed and evaluated within the context of virtual breeding environments (VBEs). However, it is currently difficult to describe and select suitable PM indicators because of the lack of a common vocabulary and taxonomies of PM indicators. Therefore, there is a need for a framework unifying concepts in the domain of VO PM. In this paper, a reference model for VO PM is presented in the context of service-oriented VBEs. In the proposed reference model, both a set of terms that could be used to describe key performance indicators, and a set of taxonomies reflecting various aspects of PM are proposed. The proposed reference model is a first attempt and a work in progress that should not be supposed exhaustive.
Social Requirements for Virtual Organization Breeding Environments
Venue: arXiv cs.SI 2011
Year: 2011

The creation of Virtual Breeding Environments (VBE) is a topic which has received too little attention: in most former works, the existence of the VBE is either assumed, or is considered as the result of the voluntary, participatory gathering of a set of candidate companies. In this paper, the creation of a VBE by a third authority is considered: chambers of commerce, as organizations whose goal is to promote and facilitate business interests and activity in the community, could be good candidates for exogenous VBE creators. During VBE planning, there is a need to specify social requirements for the VBE. In this paper, SNA metrics are proposed as a way for a VBE planner to express social requirements for a VBE to be created. Additionally, a set of social requirements for VO planners, VO brokers, and VBE members are proposed.
Enhancing LTE-Advanced Relay Deployments via Relay Cell Extension
Venue: arXiv cs.NI 2011
Year: 2011

Relaying is a promising enhancement to current radio access networks. Relay enhanced LTE-Advanced networks are expected to fulfill the demanding coverage and capacity requirements in a cost-efficient way. However, due to low transmit power, the coverage areas of the relay nodes will be small. Therefore, the performance of relay deployments may be limited by load imbalances. In this study, we present a practical solution for this problem by introducing a bias to cell selection and handover decisions along with a reduction in eNB transmit power. This method results in an extension of the relay cells and an appropriate load balance can then be achieved. Moreover, it is shown that a proper power control setting is necessary in the uplink and that power control optimization can further enhance the system performance. Comprehensive system level simulations confirm that the proposed solution yields significant user throughput gains both in the uplink and the downlink.
Robustness Analysis for Battery Supported Cyber-Physical Systems
Venue: arXiv cs.ET 2011
Year: 2011

This paper establishes a novel analytical approach to quantify robustness of scheduling and battery management for battery supported cyber-physical systems. A dynamic schedulability test is introduced to determine whether tasks are schedulable within a finite time window. The test is used to measure robustness of a real-time scheduling algorithm by evaluating the strength of computing time perturbations that break schedulability at runtime. Robustness of battery management is quantified analytically by an adaptive threshold on the state of charge. The adaptive threshold significantly reduces the false alarm rate for battery management algorithms to decide when a battery needs to be replaced.
Erdős-Szekeres and Testing Weak epsilon-Nets are NP-hard in 3 dimensions - and what now?
Venue: arXiv cs.CG 2011
Year: 2011

We consider the computational versions of the Erd\H os-Szekeres theorem and related problems in 3 dimensions. We show that, in constrast to the planar case, no polynomial time algorithm exists for determining the largest (empty) convex subset (unless P=NP) among a set of points, by proving that the corresponding decision problem is NP-hard. This answers a question by Dobkin, Edelsbrunner and Overmars from 1990. As a corollary, we derive a similar result for the closely related problem of testing weak epsilon-nets in R^3. Answering a question by Chazelle et al. from 1995, our reduction shows that the problem is co-NP-hard. This is work in progress - we are still trying to find a smart approximation algorithm for the problems.
The Clique Problem in Ray Intersection Graphs
Venue: arXiv cs.CG 2011
Year: 2011

Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvíl and Nešetřil.
Optimal Organizational Hierarchies: Source Coding: Disaster Relief
Venue: arXiv cs.NI 2011
Year: 2011

ulticasting is an important communication paradigm for enabling the dissemination of information selectively. This paper considers the problem of optimal secure multicasting in a communication network captured through a graph (optimal is in an interesting sense) and provides a doubly optimal solution using results from source coding. It is realized that the solution leads to optimal design (in a well defined optimality sense) of organizational hierarchies captured through a graph. In this effort two novel concepts : prefix free path, graph entropy are introduced. Some results of graph entropy are provided. Also some results on Kraft inequality are discussed. As an application Hierarchical Hybrid Communication Network is utilized as a model of structured Mobile Adhoc network for utility in Disaster Management. Several new research problems that naturally emanate from this research are summarized.
On the error performance of the $A_n$ lattices
Venue: arXiv cs.IT 2011
Year: 2011

We consider the root lattice $A_n$ and derive explicit formulae for the moments of its Voronoi cell. We then show that these formulae enable accurate prediction of the error probability of lattice codes constructed from $A_n$.
A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. For an $n\times n$ 0-1 matrix $C,$ let $K_{C}$ be the complete weighted graph on the rows of $C$ where the weight of an edge between two rows is equal to their Hamming distance. Let $MWT(C)$ be the weight of a minimum weight spanning tree of $K_{C}.$ We show that the all-pairs shortest path problem for a directed graph $G$ on $n$ vertices with nonnegative real weights and adjacency matrix $A_G$ can be solved by a combinatorial randomized algorithm in time $$\widetilde{O}(n^{2}\sqrt {n + \min\{MWT(A_G), MWT(A_G^t)\}})$$ As a corollary, we conclude that the transitive closure of a directed graph $G$ can be computed by a combinatorial randomized algorithm in the aforementioned time. $\widetilde{O}(n^{2}\sqrt {n + \min\{MWT(A_G), MWT(A_G^t)\}})$ We also conclude that the all-pairs shortest path problem for uniform disk graphs, with nonnegative real vertex weights, induced by point sets of bounded density within a unit square can be solved in time $\widetilde{O}(n^{2.75})$.
Secure Geographic Routing Protocols: Issues and Approaches
Venue: arXiv cs.NI 2011
Year: 2011

In the years, routing protocols in wireless sensor networks (WSN) have been substantially investigated by researches. Most state-of-the-art surveys have focused on reviewing of wireless sensor network .In this paper we review the existing secure geographic routing protocols for wireless sensor network (WSN) and also provide a qualitative comparison of them.
Publishing Location Dataset Differential Privately with Isotonic Regression
Venue: arXiv cs.CR 2011
Year: 2011

We consider the problem of publishing location datasets, in particular 2D spatial pointsets, in a differentially private manner. Many existing mechanisms focus on frequency counts of the points in some a priori partition of the domain that is difficult to determine. We propose an approach that adds noise directly to the point, or to a group of neighboring points. Our approach is based on the observation that, the sensitivity of sorting, as a function on sets of real numbers, can be bounded. Together with isotonic regression, the dataset can be accurately reconstructed. To extend the mechanism to higher dimension, we employ locality preserving function to map the dataset to a bounded interval. Although there are fundamental limits on the performance of locality preserving functions, fortunately, our problem only requires distance preservation in the "easier" direction, and the well-known Hilbert space-filling curve suffices to provide high accuracy. The publishing process is simple from the publisher's point of view: the publisher just needs to map the data, sort them, group them, add Laplace noise and publish the dataset. The only parameter to determine is the group size which can be chosen based on predicted generalization errors. Empirical study shows that the published dataset can also exploited to answer other queries, for example, range query and median query, accurately.