OpenRaiser/Intern-Atlas huggingface dataset:
Local versus Global Search in Channel Graphs
Venue: arXiv cs.CC 2010
Year: 2010

Previous studies of search in channel graphs has assumed that the search is global; that is, that the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well known channel graphs may require exponentially more probes, on the average, when search must be local than when it may be global.
Lossy Source Compression of Non-Uniform Binary Sources Using GQ-LDGM Codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we study the use of GF(q)-quantized LDGM codes for binary source coding. By employing quantization, it is possible to obtain binary codewords with a non-uniform distribution. The obtained statistics is hence suitable for optimal, direct quantization of non-uniform Bernoulli sources. We employ a message-passing algorithm combined with a decimation procedure in order to perform compression. The experimental results based on GF(q)-LDGM codes with regular degree distributions yield performances quite close to the theoretical rate-distortion bounds.
A Note on Fault Diagnosis Algorithms
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we review algorithms for checking diagnosability of discrete-event systems and timed automata. We point out that the diagnosability problems in both cases reduce to the emptiness problem for (timed) Büchi automata. Moreover, it is known that, checking whether a discrete-event system is diagnosable, can also be reduced to checking bounded diagnosability. We establish a similar result for timed automata. We also provide a synthesis of the complexity results for the different fault diagnosis problems.
SMT-based Verification of LTL Specifications with Integer Constraints and its Application to Runtime Checking of Service Substitutability
Venue: arXiv cs.LO 2010
Year: 2010

An important problem that arises during the execution of service-based applications concerns the ability to determine whether a running service can be substituted with one with a different interface, for example if the former is no longer available. Standard Bounded Model Checking techniques can be used to perform this check, but they must be able to provide answers very quickly, lest the check hampers the operativeness of the application, instead of aiding it. The problem becomes even more complex when conversational services are considered, i.e., services that expose operations that have Input/Output data dependencies among them. In this paper we introduce a formal verification technique for an extension of Linear Temporal Logic that allows users to include in formulae constraints on integer variables. This technique applied to the substitutability problem for conversational services is shown to be considerably faster and with smaller memory footprint than existing ones.
The communication complexity of XOR games via summing operators
Venue: arXiv cs.CC 2010
Year: 2010

The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to give good bounds, because the increment of the value of the game is linear (rather than exponential) in the number of communicated bits. We show in this paper the existence of XOR games where the discrepancy method yields bounds as poor as one desires. Indeed, we show the existence of such games with any previously prescribed value. To prove this result we apply the theory of p-summing operators, a central topic in Banach space theory. We show in the paper other applications of this theory to the study of the communication complexity of XOR games.
Hybrid CDN structure with a P2P based streaming protocol
Venue: arXiv cs.NI 2010
Year: 2010

Over the last decade, internet has seen an exponential increase in its growth.With more and more people using it, efficient data delivery over the internet has become a key issue. Peer-to-peer (P2P)/seed sharing based networks have several desirable features for content distribution, such as low costs, scalability, and fault tolerance. While the invention of each of such specialized systems has improved the user experience, some fundamental shortcomings of these systems have often been neglected. These shortcomings of content distribution systems have become severe bottlenecks in scalability of the internet.In order to combine the desired features of classical Content Distribution Networks (CDNs) and P2P/seed sharing based networks, we propose a hybrid CDN structure with a P2P/seed sharing based streaming protocol in the access network . In this work, we focus on the problem of data redundancy (at each node) and show how severely it impacts the network economics and the experience of end-user and hence leads to low traffic load and redundancy
Persistent Asymmetric Password-Based Key Exchange
Venue: arXiv cs.CR 2010
Year: 2010

Asymmetric password based key exchange is a key exchange protocol where a client and a server share a low entropic password while the server additionally owns a high entropic secret for a public key. There are simple solutions for this (e.g. Halevi and Krawczyk (ACM TISSEC 1999) and its improvement by Boyarsky (CCS 1999)). In this paper, we consider a new threat to this type of protocol: if a server's high entropic secret gets compromised (e.g., due to cryptanalysis, virus attack or a poor management), the adversary might {\em quickly} break lots of passwords and cause uncountable damage. In this case, one should not expect the protocol to be secure against an off-line dictionary attack since, otherwise, the protocol is in fact a secure password-only key exchange where the server also only has a password (by making the server high entropic secret public). Of course a password-only key exchange does not suffer from this threat as the server does not have a high entropic secret at all. However, known password-only key exchange are not very efficient (note: we only consider protocols without random oracles). This motivates us to study efficient and secure asymmetric password key exchange that avoids the new threat. In this paper, we first provide a formal model for the new threat, where essentially we require that the active adversary can break $\ell$ passwords in $α\ell |{\cal D}|$ steps (for $α<1/2$) only with a probability negligibly close to $\exp(-β\ell)$ for some $β>0$. Then, we construct a framework of asymmetric password based key exchange. We prove that our protocol is secure in the usual sense. We also show that it prevents the new threat. To do this, we introduce a new technique by abstracting a probabilistic experiment from the main proof and providing a neat analysis of it.
Prizing on Paths: A PTAS for the Highway Problem
Venue: arXiv cs.DS 2010
Year: 2010

In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the tolls), the highway owner collects from each driver the weight of the associated path, when it does not exceed the budget of the driver, and zero otherwise. The goal is choosing weights so as to maximize the profit. A lot of research has been devoted to this apparently simple problem. The highway problem was shown to be strongly NP-hard only recently [Elbassioni,Raman,Ray-'09]. The best-known approximation is O(\log n/\log\log n) [Gamzu,Segev-'10], which improves on the previous-best O(\log n) approximation [Balcan,Blum-'06]. In this paper we present a PTAS for the highway problem, hence closing the complexity status of the problem. Our result is based on a novel randomized dissection approach, which has some points in common with Arora's quadtree dissection for Euclidean network design [Arora-'98]. The basic idea is enclosing the highway in a bounding path, such that both the size of the bounding path and the position of the highway in it are random variables. Then we consider a recursive O(1)-ary dissection of the bounding path, in subpaths of uniform optimal weight. Since the optimal weights are unknown, we construct the dissection in a bottom-up fashion via dynamic programming, while computing the approximate solution at the same time. Our algorithm can be easily derandomized. We demonstrate the versatility of our technique by presenting PTASs for two variants of the highway problem: the tollbooth problem with a constant number of leaves and the maximum-feasibility subsystem problem on interval matrices. In both cases the previous best approximation factors are polylogarithmic [Gamzu,Segev-'10,Elbassioni,Raman,Ray,Sitters-'09].
Universal Coding of Ergodic Sources for Multiple Decoders with Side Information
Venue: arXiv cs.IT 2010
Year: 2010

A multiterminal lossy coding problem, which includes various problems such as the Wyner-Ziv problem and the complementary delivery problem as special cases, is considered. It is shown that any point in the achievable rate-distortion region can be attained even if the source statistics are not known.
Some long-period random number generators using shifts and xors
Venue: arXiv cs.DS 2010
Year: 2010

Marsaglia recently introduced a class of xorshift random number generators (RNGs) with periods 2n-1 for n = 32, 64, etc. Here we give a generalisation of Marsaglia's xorshift generators in order to obtain fast and high-quality RNGs with extremely long periods. RNGs based on primitive trinomials may be unsatisfactory because a trinomial has very small weight. In contrast, our generators can be chosen so that their minimal polynomials have large weight (number of nonzero terms). A computer search using Magma has found good generators for n a power of two up to 4096. These have been implemented in a free software package xorgens.
MP users guide
Venue: arXiv cs.MS 2010
Year: 2010

MP is a package of ANSI Standard Fortran (ANS X3.9-1966) subroutines for performing multiple-precision floating-point arithmetic and evaluating elementary and special functions. The subroutines are machine independent and the precision is arbitrary, subject to storage limitations. The User's Guide describes the routines and their calling sequences, example and test programs, use of the Augment precompiler, and gives installation instructions for the package.
GAC: Energy-Efficient Hybrid GPS-Accelerometer-Compass GSM Localization
Venue: arXiv cs.NI 2010
Year: 2010

Adding location to the available information enables a new category of applications. With the constrained battery on cell phones, energy-efficient localization becomes an important challenge. In this paper we introduce a low-energy calibration-free localization scheme based on the available internal sensors in many of today's phones. We start by energy profiling the different sensors that can be used for localization. Based on that, we propose GAC: a hybrid GPS/accelerometer/compass scheme that depends mainly on using the low-energy accelerometer and compass sensors and uses the GPS infrequently for synchronization. We implemented our system on Android-enabled cell phones and evaluated it in both highways and intra-city driving environments. Our results show that the proposed hybrid scheme has an exponential saving in energy, with a linear loss in accuracy compared to the GPS accuracy. We also evaluate the effect of the different parameters on the energy-accuracy tradeoff.
Introducing Dendritic Cells as a Novel Immune-Inspired Algorithm for Anomoly Detection
Venue: arXiv cs.AI 2010
Year: 2010

Dendritic cells are antigen presenting cells that provide a vital link between the innate and adaptive immune system. Research into this family of cells has revealed that they perform the role of coordinating T-cell based immune responses, both reactive and for generating tolerance. We have derived an algorithm based on the functionality of these cells, and have used the signals and differentiation pathways to build a control mechanism for an artificial immune system. We present our algorithmic details in addition to some preliminary results, where the algorithm was applied for the purpose of anomaly detection. We hope that this algorithm will eventually become the key component within a large, distributed immune system, based on sound immunological concepts.
Decision Support Systems (DSS) in Construction Tendering Processes
Venue: arXiv cs.AI 2010
Year: 2010

The successful execution of a construction project is heavily impacted by making the right decision during tendering processes. Managing tender procedures is very complex and uncertain involving coordination of many tasks and individuals with different priorities and objectives. Bias and inconsistent decision are inevitable if the decision-making process is totally depends on intuition, subjective judgement or emotion. In making transparent decision and healthy competition tendering, there exists a need for flexible guidance tool for decision support. Aim of this paper is to give a review on current practices of Decision Support Systems (DSS) technology in construction tendering processes. Current practices of general tendering processes as applied to the most countries in different regions such as United States, Europe, Middle East and Asia are comprehensively discussed. Applications of Web-based tendering processes is also summarised in terms of its properties. Besides that, a summary of Decision Support System (DSS) components is included in the next section. Furthermore, prior researches on implementation of DSS approaches in tendering processes are discussed in details. Current issues arise from both of paper-based and Web-based tendering processes are outlined. Finally, conclusion is included at the end of this paper.
Optimized Fuzzy Logic Based Framework for Effort Estimation in Software Development
Venue: arXiv cs.SE 2010
Year: 2010

Software effort estimation at early stages of project development holds great significance for the industry to meet the competitive demands of today's world. Accuracy, reliability and precision in the estimates of effort are quite desirable. The inherent imprecision present in the inputs of the algorithmic models like Constructive Cost Model (COCOMO) yields imprecision in the output, resulting in erroneous effort estimation. Fuzzy logic based cost estimation models are inherently suitable to address the vagueness and imprecision in the inputs, to make reliable and accurate estimates of effort. In this paper, we present an optimized fuzzy logic based framework for software development effort prediction. The said framework tolerates imprecision, incorporates experts knowledge, explains prediction rationale through rules, offers transparency in the prediction system, and could adapt to changing environments with the availability of new data. The traditional cost estimation model COCOMO is extended in the proposed study by incorporating the concept of fuzziness into the measurements of size, mode of development for projects and the cost drivers contributing to the overall development effort.
A New Approach to Keyphrase Extraction Using Neural Networks
Venue: arXiv cs.IR 2010
Year: 2010

Keyphrases provide a simple way of describing a document, giving the reader some clues about its contents. Keyphrases can be useful in a various applications such as retrieval engines, browsing interfaces, thesaurus construction, text mining etc.. There are also other tasks for which keyphrases are useful, as we discuss in this paper. This paper describes a neural network based approach to keyphrase extraction from scientific articles. Our results show that the proposed method performs better than some state-of-the art keyphrase extraction approaches.
Communication and Round Efficient Information Checking Protocol
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we present a very important primitive called Information Checking Protocol (ICP) which plays an important role in constructing statistical Verifiable Secret Sharing (VSS) and Weak Secret Sharing (WSS) protocols. Informally, ICP is a tool for authenticating messages in the presence of computationally unbounded corrupted parties. Here we extend the basic bare-bone definition of ICP, introduced by Rabin et al. and then present an ICP that attains the best communication complexity and round complexity among all the existing ICPs in the literature. We also show that our ICP satisfies several interesting properties such as linearity property which is an important requirement in many applications of ICP. Though not presented in this paper, we can design communication and round efficient statistical (i.e involves negligible error probability in computation) VSS and Multiparty Computation (MPC) protocol using our new ICP.
Propose a Fuzzy Queuing Maximal Benefit Location Problem
Venue: arXiv cs.OH 2010
Year: 2010

This paper presents a fuzzy queuing location model for congested system. In a queuing system there are different criteria that are not constant such as service rate, service rate demand, queue length, the occupancy probability of a service center and Probability of joining the queue line. In this paper with fuzzifying all of these variables, will try to reach an accurate real problem. Finally we change the problem to a single objective function and as far as this model is in NP-Hard classification we will use genetic algorithm for solving it and ant colony for comparison is used for their results and run time.
Policies and Economics of Digital Multimedia Transmission
Venue: arXiv cs.MM 2010
Year: 2010

There are different Standards of digital multimedia transmission, for example DVB in Europe and ISDB in Japan and DMB in Korea, with different delivery system (example MPEG-2, MPEG-4).This paper describe an overview of Digital Multimedia Transmission (DMT) technologies. The economic aspects of digital content & software solution industry as a strategic key in the future will be discussed. The study then focuses on some important policy and technology issues, such S-DMB, T-DMB, Digital Video Broadcasting Handheld (DVB-H) and concludes DMT policies for convergence of telecommunications and broadcasting.
Computer Aided Design Modeling for Heterogeneous Objects
Venue: arXiv cs.CE 2010
Year: 2010

Heterogeneous object design is an active research area in recent years. The conventional CAD modeling approaches only provide geometry and topology of the object, but do not contain any information with regard to the materials of the object and so can not be used for the fabrication of heterogeneous objects (HO) through rapid prototyping. Current research focuses on computer-aided design issues in heterogeneous object design. A new CAD modeling approach is proposed to integrate the material information into geometric regions thus model the material distributions in the heterogeneous object. The gradient references are used to represent the complex geometry heterogeneous objects which have simultaneous geometry intricacies and accurate material distributions. The gradient references helps in flexible manipulability and control to heterogeneous objects, which guarantees the local control over gradient regions of developed heterogeneous objects. A systematic approach on data flow, processing, computer visualization, and slicing of heterogeneous objects for rapid prototyping is also presented.
Information Theory and Quadrature Rules
Venue: arXiv cs.IT 2010
Year: 2010

Quadrature rules estimate the value of an integral when the function is given by a table of values. Every binary string defines a quadrature rule by choosing which endpoint of each interval represents the interval. The standard rules, such as Simpson's Rule, correspond to strings of low Kolmogorov complexity, making it possible to define new quadrature rules with no smoothness assumptions, as well as in higher dimensions. Error results depend on concepts from compressed sensing. Good quadrature rules exist for "sparse" functions, which also satisfy an error--information duality principle.
Modelling Immunological Memory
Venue: arXiv cs.AI 2010
Year: 2010

Accurate immunological models offer the possibility of performing highthroughput experiments in silico that can predict, or at least suggest, in vivo phenomena. In this chapter, we compare various models of immunological memory. We first validate an experimental immunological simulator, developed by the authors, by simulating several theories of immunological memory with known results. We then use the same system to evaluate the predicted effects of a theory of immunological memory. The resulting model has not been explored before in artificial immune systems research, and we compare the simulated in silico output with in vivo measurements. Although the theory appears valid, we suggest that there are a common set of reasons why immunological memory models are a useful support tool; not conclusive in themselves.
Hashing Image Patches for Zooming
Venue: arXiv cs.CV 2010
Year: 2010

In this paper we present a Bayesian image zooming/super-resolution algorithm based on a patch based representation. We work on a patch based model with overlap and employ a Locally Linear Embedding (LLE) based approach as our data fidelity term in the Bayesian inference. The image prior imposes continuity constraints across the overlapping patches. We apply an error back-projection technique, with an approximate cross bilateral filter. The problem of nearest neighbor search is handled by a variant of the locality sensitive hashing (LSH) scheme. The novelty of our work lies in the speed up achieved by the hashing scheme and the robustness and inherent modularity and parallel structure achieved by the LLE setup. The ill-posedness of the image reconstruction problem is handled by the introduction of regularization priors which encode the knowledge present in vast collections of natural images. We present comparative results for both run-time as well as visual image quality based measurements.
n-Level Graph Partitioning
Venue: arXiv cs.DS 2010
Year: 2010

We present a multi-level graph partitioning algorithm based on the extreme idea to contract only a single edge on each level of the hierarchy. This obviates the need for a matching algorithm and promises very good partitioning quality since there are very few changes between two levels. Using an efficient data structure and new flexible ways to break local search improvements early, we obtain an algorithm that scales to large inputs and produces the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 155 improvements dominating the entries for large graphs.
Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model
Venue: arXiv cs.IT 2010
Year: 2010

In compressive sensing, sparse signals are recovered from underdetermined noisy linear observations. One of the interesting problems which attracted a lot of attention in recent times is the support recovery or sparsity pattern recovery problem. The aim is to identify the non-zero elements in the original sparse signal. In this article we consider the sparsity pattern recovery problem under a probabilistic signal model where the sparse support follows a Bernoulli distribution and the signal restricted to this support follows a Gaussian distribution. We show that the energy in the original signal restricted to the missed support of the MAP estimate is bounded above and this bound is of the order of energy in the projection of the noise signal to the subspace spanned by the active coefficients. We also derive sufficient conditions for no misdetection and no false alarm in support recovery.