OpenRaiser/Intern-Atlas huggingface dataset:
System Dynamics Modelling of the Processes Involving the Maintenance of the Naive T Cell Repertoire
Venue: arXiv cs.AI 2010
Year: 2010

The study of immune system aging, i.e. immunosenescence, is a relatively new research topic. It deals with understanding the processes of immunodegradation that indicate signs of functionality loss possibly leading to death. Even though it is not possible to prevent immunosenescence, there is great benefit in comprehending its causes, which may help to reverse some of the damage done and thus improve life expectancy. One of the main factors influencing the process of immunosenescence is the number and phenotypical variety of naive T cells in an individual. This work presents a review of immunosenescence, proposes system dynamics modelling of the processes involving the maintenance of the naive T cell repertoire and presents some preliminary results.
Nearly Optimal Algorithms for the Decomposition of Multivariate Rational Functions and the Extended Lüroth's Theorem
Venue: arXiv cs.SC 2010
Year: 2010

The extended Lüroth's Theorem says that if the transcendence degree of $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)/\KK$ is 1 then there exists $f \in \KK(\underline{X})$ such that $\KK(\mathsf{f}_1,\dots,\mathsf{f}_m)$ is equal to $\KK(f)$. In this paper we show how to compute $f$ with a probabilistic algorithm. We also describe a probabilistic and a deterministic algorithm for the decomposition of multivariate rational functions. The probabilistic algorithms proposed in this paper are softly optimal when $n$ is fixed and $d$ tends to infinity. We also give an indecomposability test based on gcd computations and Newton's polytope. In the last section, we show that we get a polynomial time algorithm, with a minor modification in the exponential time decomposition algorithm proposed by Gutierez-Rubio-Sevilla in 2001.
Interface Building for Software by Modular Three-Valued Abstraction Refinement
Venue: arXiv cs.LO 2010
Year: 2010

Verification of software systems is a very hard problem due to the large size of program state-space. The traditional techniques (like model checking) do not scale; since they include the whole state-space by inlining the library function codes. Current research avoids these problem by creating a lightweight representation of the library in form of an "interface graph" (call sequence graph). In this paper we introduce a new algorithm to compute a safe, permissive interface graph for C-type functions. In this modular analysis, each function transition is summarized following three-valued abstraction semantics. There are two kinds of abstraction used here. The global abstraction contains predicates over global variables only; however the local abstraction inside each function may also contain the local variables. The abstract summary needs refinement to guarantee safety and permissiveness. We have implemented the algorithms in TICC tool and compared this algorithm with some related interface generation algorithms. We also discuss the application of interface as an offline test-suite. We create an interface from the model program (specification) and the interface will act as a test-suite for the new implementation-under-test (IUT).
Security Estimates for Quadratic Field Based Cryptosystems
Venue: arXiv cs.CR 2010
Year: 2010

We describe implementations for solving the discrete logarithm problem in the class group of an imaginary quadratic field and in the infrastructure of a real quadratic field. The algorithms used incorporate improvements over previously-used algorithms, and extensive numerical results are presented demonstrating their efficiency. This data is used as the basis for extrapolations, used to provide recommendations for parameter sizes providing approximately the same level of security as block ciphers with $80,$ $112,$ $128,$ $192,$ and $256$-bit symmetric keys.
Symbolic Domain Decomposition
Venue: arXiv cs.SC 2010
Year: 2010

Decomposing the domain of a function into parts has many uses in mathematics. A domain may naturally be a union of pieces, a function may be defined by cases, or different boundary conditions may hold on different regions. For any particular problem the domain can be given explicitly, but when dealing with a family of problems given in terms of symbolic parameters, matters become more difficult. This article shows how hybrid sets, that is multisets allowing negative multiplicity, may be used to express symbolic domain decompositions in an efficient, elegant and uniform way, simplifying both computation and reasoning. We apply this theory to the arithmetic of piecewise functions and symbolic matrices and show how certain operations may be reduced from exponential to linear complexity.
On Achieving Local View Capacity Via Maximal Independent Graph Scheduling
Venue: arXiv cs.IT 2010
Year: 2010

"If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sumrates. In this paper, we formalize this increase of sum-rate with increased knowledge of the network state. The knowledge of network state is measured in terms of the number of hops, h, of information available to each transmitter and is labeled as h-local view. To understand how much capacity is lost due to limited information, we propose to use the metric of normalized sum-capacity, which is the h-local view sum-capacity divided by global-view sum capacity. For the cases of one and two-local view, we characterize the normalized sum-capacity for many classes of deterministic and Gaussian interference networks. In many cases, a scheduling scheme called maximal independent graph scheduling is shown to achieve normalized sum-capacity. We also show that its generalization for 1-local view, labeled coded set scheduling, achieves normalized sum-capacity in some cases where its uncoded counterpart fails to do so.
Global Linear Complexity Analysis of Filter Keystream Generators
Venue: arXiv cs.CR 2010
Year: 2010

An efficient algorithm for computing lower bounds on the global linear complexity of nonlinearly filtered PN-sequences is presented. The technique here developed is based exclusively on the realization of bit wise logic operations, which makes it appropriate for both software simulation and hardware implementation. The present algorithm can be applied to any arbitrary nonlinear function with a unique term of maximum order. Thus, the extent of its application for different types of filter generators is quite broad. Furthermore, emphasis is on the large lower bounds obtained that confirm the exponential growth of the global linear complexity for the class of nonlinearly filtered sequences.
The Exact Closest String Problem as a Constraint Satisfaction Problem
Venue: arXiv cs.AI 2010
Year: 2010

We report (to our knowledge) the first evaluation of Constraint Satisfaction as a computational framework for solving closest string problems. We show that careful consideration of symbol occurrences can provide search heuristics that provide several orders of magnitude speedup at and above the optimal distance. We also report (to our knowledge) the first analysis and evaluation -- using any technique -- of the computational difficulties involved in the identification of all closest strings for a given input set. We describe algorithms for web-scale distributed solution of closest string problems, both purely based on AI backtrack search and also hybrid numeric-AI methods.
Influence of distortions of key frames on video transfer in wireless networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper it is shown that for substantial increase of video quality in wireless network it is necessary to execute two obligatory points on modernization of the communication scheme. The player on the received part should throw back automatically duplicated RTP packets, server of streaming video should duplicate the packets containing the information of key frames. Coefficients of the mathematical model describing video quality in wireless network have been found for WiFi and 3G standards and codecs MPEG-2 and MPEG-4 (DivX). The special experimental technique which has allowed collecting and processing the data has been developed for calculation of values of factors.
A Simple Attack on Some Clock-Controlled Generators
Venue: arXiv cs.CR 2010
Year: 2010

We present a new approach to edit distance attacks on certain clock-controlled generators, which applies basic concepts of Graph Theory to simplify the search trees of the original attacks in such a way that only the most promising branches are analyzed. In particular, the proposed improvement is based on cut sets defined on some graphs so that certain shortest paths provide the edit distances. The strongest aspects of the proposal are that the obtained results from the attack are absolutely deterministic, and that many inconsistent initial states of the target registers are recognized beforehand and avoided during search.
Security Scheme for Distributed DoS in Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

In Mobile Ad Hoc Networks (MANET), various types of Denial of Service Attacks (DoS) are possible because of the inherent limitations of its routing protocols. Considering the Ad Hoc On Demand Vector (AODV) routing protocol as the base protocol it is possible to find a suitable solution to over-come the attack of initiating / forwarding fake Route Requests (RREQs) that lead to hogging of network resources and hence denial of service to genuine nodes. In this paper, a proactive scheme is proposed that could prevent a specific kind of DoS attack and identify the misbehaving node. Since the proposed scheme is distributed in nature it has the capability to prevent Distributed DoS (DDoS) as well. The performance of the proposed algorithm in a series of simulations reveal that the proposed scheme provides a better solution than existing approaches with no extra overhead.
Software Design Document, Testing, Deployment and Configuration Management, and User Manual of the UUIS -- a Team 4 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

This document provides a description of the technical design for Unified University Inventory System - Web Portal. This document's primary purpose is to describe the technical vision for how business requirements will be realized. This document provides an architectural overview of the system to depict different aspects of the system. This document also functions as a foundational reference point for developers.
Node-Context Network Clustering using PARAFAC Tensor Decomposition
Venue: arXiv cs.IR 2010
Year: 2010

We describe a clustering method for labeled link network (semantic graph) that can be used to group important nodes (highly connected nodes) with their relevant link's labels by using PARAFAC tensor decomposition. In this kind of network, the adjacency matrix can not be used to fully describe all information about the network structure. We have to expand the matrix into 3-way adjacency tensor, so that not only the information about to which nodes a node connects to but by which link's labels is also included. And by applying PARAFAC decomposition on this tensor, we get two lists, nodes and link's labels with scores attached to each node and labels, for each decomposition group. So clustering process to get the important nodes along with their relevant labels can be done simply by sorting the lists in decreasing order. To test the method, we construct labeled link network by using blog's dataset, where the blogs are the nodes and labeled links are the shared words among them. The similarity measures between the results and standard measures look promising, especially for two most important tasks, finding the most relevant words to blogs query and finding the most similar blogs to blogs query, about 0.87.
Security in Distributed Storage Systems by Communicating a Logarithmic Number of Bits
Venue: arXiv cs.CR 2010
Year: 2010

We investigate the problem of maintaining an encoded distributed storage system when some nodes contain adversarial errors. Using the error-correction capabilities that are built into the existing redundancy of the system, we propose a simple linear hashing scheme to detect errors in the storage nodes. Our main result is that for storing a data object of total size $\size$ using an $(n,k)$ MDS code over a finite field $\F_q$, up to $t_1=\lfloor(n-k)/2\rfloor$ errors can be detected, with probability of failure smaller than $1/ \size$, by communicating only $O(n(n-k)\log \size)$ bits to a trusted verifier. Our result constructs small projections of the data that preserve the errors with high probability and builds on a pseudorandom generator that fools linear functions. The transmission rate achieved by our scheme is asymptotically equal to the min-cut capacity between the source and any receiver.
Classes of lower bounds on outage error probability and MSE in Bayesian parameter estimation
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, new classes of lower bounds on the outage error probability and on the mean-square-error (MSE) in Bayesian parameter estimation are proposed. The minima of the h-outage error probability and the MSE are obtained by the generalized maximum a-posteriori probability and the minimum MSE (MMSE) estimators, respectively. However, computation of these estimators and their corresponding performance is usually not tractable and thus, lower bounds on these terms can be very useful for performance analysis. The proposed class of lower bounds on the outage error probability is derived using Holder's inequality. This class is utilized to derive a new class of Bayesian MSE bounds. It is shown that for unimodal symmetric conditional probability density functions (pdf) the tightest probability of outage error lower bound in the proposed class attains the minimum probability of outage error and the tightest MSE bound coincides with the MMSE performance. In addition, it is shown that the proposed MSE bounds are always tighter than the Ziv-Zakai lower bound (ZZLB). The proposed bounds are compared with other existing performance lower bounds via some examples.
When can we decide that a P-finite sequence is positive?
Venue: arXiv cs.SC 2010
Year: 2010

We consider two algorithms which can be used for proving positivity of sequences that are defined by a linear recurrence equation with polynomial coefficients (P-finite sequences). Both algorithms have in common that while they do succeed on a great many examples, there is no guarantee for them to terminate, and they do in fact not terminate for every input. For some restricted classes of P-finite recurrence equations of order up to three we provide a priori criteria that assert the termination of the algorithms.
An approach to visualize the course of solving of a research task in humans
Venue: arXiv cs.AI 2010
Year: 2010

A technique to study the dynamics of solving of a research task is suggested. The research task was based on specially developed software Right- Wrong Responder (RWR), with the participants having to reveal the response logic of the program. The participants interacted with the program in the form of a semi-binary dialogue, which implies the feedback responses of only two kinds - "right" or "wrong". The technique has been applied to a small pilot group of volunteer participants. Some of them have successfully solved the task (solvers) and some have not (non-solvers). In the beginning of the work, the solvers did more wrong moves than non-solvers, and they did less wrong moves closer to the finish of the work. A phase portrait of the work both in solvers and non-solvers showed definite cycles that may correspond to sequences of partially true hypotheses that may be formulated by the participants during the solving of the task.
Software Requirements Specification of the IUfA's UUIS -- a Team 3 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

The purpose of this document is to specify the requirements of the University Unified Inventory System, of the UIfA. The Team of Analysts used a Feedback Waterfall approach to collect the requirements. UML diagrams, such as Use case diagrams, Block Diagrams, Domain Models, and interface prototypes are some of the tools employed to develop the present document.
The Enigma of CDMA Revisited
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we explore the mystery of synchronous CDMA as applied to wireless and optical communication systems under very general settings for the user symbols and the signature matrix entries. The channel is modeled with real/complex additive noise of arbitrary distribution. Two problems are addressed. The first problem concerns whether overloaded error free codes exist in the absence of additive noise under these general settings, and if so whether there are any practical optimum decoding algorithms. The second one is about the bounds for the sum channel capacity when user data and signature codes employ any real or complex alphabets (finite or infinite). In response to the first problem, we have developed practical Maximum Likelihood (ML) decoding algorithms for overloaded CDMA systems for a large class of alphabets. In response to the second problem, a general theorem has been developed in which the sum capacity lower bounds with respect to the number of users and spreading gain and Signal-to-Noise Ratio (SNR) can be derived as special cases for a given CDMA system. To show the power and utility of the main theorem, a number of sum capacity bounds for special cases are simulated. An important conclusion of this paper is that the lower and upper bounds of the sum capacity for small/medium size CDMA systems depend on both the input and the signature symbols; this is contrary to the asymptotic results for large scale systems reported in the literature (also confirmed in this paper) where the signature symbols and statistics disappear in the asymptotic sum capacity. Moreover, these questions are investigated for the case when not all users are active. Furthermore, upper and asymptotic bounds are derived and numerically evaluated and compared to other derivations.
Towards Hardware implementation of video applications in new telecommunications devices
Venue: arXiv cs.MM 2010
Year: 2010

Among the areas, most demanding in terms of calculation is the telecommunication and video applications are now included in several telecommunication devices such as set-top boxes, mobile phones. Embedded videos applications in new generations of telecommunication devices need a processing capacity that can not be achieved by the conventional processor, to work around this problem the use of programmable technology has a lot of interest. First, Field Programmable Gate Arrays (FPGAs) present many performance benefits for real-time image processing applications. The FPGA structure is able to exploit spatial and temporal parallelism. In this paper, we present a new method for implementation of the Color Structure Descriptor (CSD) using the FPGA circuit. In fact the (CSD) provides satisfactory image indexing and retrieval results among all colorbased descriptors in MPEG-7. But the real time implementation of this descriptor is still having problems. In this paper we propose a method for adapting this descriptor for possible implementation under the constraints of the video processing in real time. We have verified the real-time implementation of the (CSD) with an image size of 120*80 pixels.
Software Requirements Specification of the IUfA's UUIS -- a Team 2 COMP5541-W10 Project Approach
Venue: arXiv cs.SE 2010
Year: 2010

In the 52-page document, we describe our approach to the Software Requirements Specification of the IUfA's UUIS prototype. This includes the overall system description, functional requirements, non-functional requirements, use cases, the corresponding data dictionary for all entities involved, mock user interface (UI) design, and the overall projected cost estimate. The design specification of UUIS can be found in arXiv:1005.0665.
A Kinetic Triangulation Scheme for Moving Points in The Plane
Venue: arXiv cs.CG 2010
Year: 2010

We present a simple randomized scheme for triangulating a set $P$ of $n$ points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of $P$ move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of $O(n^2β_{s+2}(n)\log^2n)$ discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here $s$ is the maximum number of times where any specific triple of points of $P$ can become collinear, $β_{s+2}(q)=λ_{s+2}(q)/q$, and $λ_{s+2}(q)$ is the maximum length of Davenport-Schinzel sequences of order $s+2$ on $n$ symbols. Thus, compared to the previous solution of Agarwal et al.~\cite{AWY}, we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is simpler to implement and analyze.
Implementation of the Six Channel Redundancy to achieve fault tolerance in testing of satellites
Venue: arXiv cs.OH 2010
Year: 2010

This paper aims to implement the six channel redundancy to achieve fault tolerance in testing of satellites with acoustic spectrum. We mainly focus here on achieving fault tolerance. An immediate application is the microphone data acquisition and to do analysis at the Acoustic Test Facility (ATF) centre, National Aerospace Laboratories. It has an 1100 cubic meter reverberation chamber in which a maximum sound pressure level of 157 dB is generated. The six channel Redundancy software with fault tolerant operation is devised and developed. The data are applied to program written in C language. The program is run using the Code Composer Studio by accepting the inputs. This is tested with the TMS 320C 6727 DSP, Pro Audio Development Kit (PADK).
Polynomial integration on regions defined by a triangle and a conic
Venue: arXiv cs.SC 2010
Year: 2010

We present an efficient solution to the following problem, of relevance in a numerical optimization scheme: calculation of integrals of the type \[\iint_{T \cap \{f\ge0\}} ϕ_1ϕ_2 \, dx\,dy\] for quadratic polynomials $f,ϕ_1,ϕ_2$ on a plane triangle $T$. The naive approach would involve consideration of the many possible shapes of $T\cap\{f\geq0\}$ (possibly after a convenient transformation) and parameterizing its border, in order to integrate the variables separately. Our solution involves partitioning the triangle into smaller triangles on which integration is much simpler.
Efficiency Loss in Revenue Optimal Auctions
Venue: arXiv cs.GT 2010
Year: 2010

We study efficiency loss in Bayesian revenue optimal auctions. We quantify this as the worst case ratio of loss in the realized social welfare to the social welfare that can be realized by an efficient auction. Our focus is on auctions with single-parameter buyers and where buyers' valuation sets are finite. For binary valued single-parameter buyers with independent (not necessarily identically distributed) private valuations, we show that the worst case efficiency loss ratio (ELR) is no worse than it is with only one buyer; moreover, it is at most 1/2. Moving beyond the case of binary valuations but restricting to single item auctions, where buyers' private valuations are independent and identically distributed, we obtain bounds on the worst case ELR as a function of number of buyers, cardinality of buyers' valuation set, and ratio of maximum to minimum possible values that buyers can have for the item.
A Simple Approach to Error Reconciliation in Quantum Key Distribution
Venue: arXiv cs.DS 2010
Year: 2010

We discuss the error reconciliation phase in quantum key distribution (QKD) and analyse a simple scheme in which blocks with bad parity (that is, blocks containing an odd number of errors) are discarded. We predict the performance of this scheme and show, using a simulation, that the prediction is accurate.