OpenRaiser/Intern-Atlas huggingface dataset:
Multi-path Probabilistic Available Bandwidth Estimation through Bayesian Active Learning
Venue: arXiv cs.NI 2010
Year: 2010

Knowing the largest rate at which data can be sent on an end-to-end path such that the egress rate is equal to the ingress rate with high probability can be very practical when choosing transmission rates in video streaming or selecting peers in peer-to-peer applications. We introduce probabilistic available bandwidth, which is defined in terms of ingress rates and egress rates of traffic on a path, rather than in terms of capacity and utilization of the constituent links of the path like the standard available bandwidth metric. In this paper, we describe a distributed algorithm, based on a probabilistic graphical model and Bayesian active learning, for simultaneously estimating the probabilistic available bandwidth of multiple paths through a network. Our procedure exploits the fact that each packet train provides information not only about the path it traverses, but also about any path that shares a link with the monitored path. Simulations and PlanetLab experiments indicate that this process can dramatically reduce the number of probes required to generate accurate estimates.
LXG Compiler - Design and Implementation
Venue: arXiv cs.PL 2010
Year: 2010

LXG is a simple Pascal-like language. It is a functional programming language developed for studying compiler design and implementation. The language supports procedure and variable declarations, but no classes. This paper reports the design and implementation of an LXG compiler. Test results are presented as well.
Knowledge-Based Innovation Systems and the Model of a Triple Helix of University-Industry-Government Relations
Venue: arXiv cs.CY 2010
Year: 2010

The (neo-)evolutionary model of a Triple Helix of University-Industry-Government Relations focuses on the overlay of expectations, communications, and interactions that potentially feed back on the institutional arrangements among the carrying agencies. From this perspective, the evolutionary perspective in economics can be complemented with the reflexive turn from sociology. The combination provides a richer understanding of how knowledge-based systems of innovation are shaped and reconstructed. The communicative capacities of the carrying agents become crucial to the system's further development, whereas the institutional arrangements (e.g., national systems) can be expected to remain under reconstruction. The tension of the differentiation no longer needs to be resolved, since the network configurations are reproduced by means of translations among historically changing codes. Some methodological and epistemological implications for studying innovation systems are explicated.
Distance bounds for algebraic geometric codes
Venue: arXiv cs.IT 2010
Year: 2010

Various methods have been used to obtain improvements of the Goppa lower bound for the minimum distance of an algebraic geometric code. The main methods divide into two categories and all but a few of the known bounds are special cases of either the Lundell-McCullough floor bound or the Beelen order bound. The exceptions are recent improvements of the floor bound by Guneri-Stichtenoth-Taskin, and Duursma-Park, and of the order bound by Duursma-Park and Duursma-Kirov. In this paper we provide short proofs for all floor bounds and most order bounds in the setting of the van Lint and Wilson AB method. Moreover, we formulate unifying theorems for order bounds and formulate the DP and DK order bounds as natural but different generalizations of the Feng-Rao bound for one-point codes.
Efficient Upload Bandwidth Estimation and Communication Resource Allocation Techniques
Venue: arXiv cs.NI 2010
Year: 2010

In this paper we address two problems, for which we present novel, efficient, algorithmic solutions. The first problem is motivated by practical situations and is concerned with the efficient estimation of the upload bandwidth of a machine, particularly in the context of a peer-to-peer content sharing and distribution application. The second problem is more of a theoretical nature and considers a constrained communication resource allocation situation.
Ergodic and Outage Performance of Fading Broadcast Channels with 1-Bit Feedback
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, the ergodic sum-rate and outage probability of a downlink single-antenna channel with K users are analyzed in the presence of Rayleigh flat fading, where limited channel state information (CSI) feedback is assumed. Specifically, only 1-bit feedback per fading block per user is available at the base station. We first study the ergodic sum-rate of the 1-bit feedback scheme, and consider the impact of feedback delay on the system. A closed-form expression for the achievable ergodic sum-rate is presented as a function of the fading temporal correlation coefficient. It is proved that the sum-rate scales as loglogK, which is the same scaling law achieved by the optimal non-delayed full CSI feedback scheme. The sum-rate degradation due to outdated CSI is also evaluated in the asymptotic regimes of either large K or low SNR. The outage performance of the 1-bit feedback scheme for both instantaneous and outdated feedback is then investigated. Expressions for the outage probabilities are derived, along with the corresponding diversity-multiplexing tradeoffs (DMT). It is shown that with instantaneous feedback, a power allocation based on the feedback bits enables to double the DMT compared to the case with short-term power constraint in which a dynamic power allocation is not allowed. But, with outdated feedback, the advantage of power allocation is lost, and the DMT reverts to that achievable with no CSI feedback. Nevertheless, for finite SNR, improvement in terms of outage probability can still be obtained.
The Berlekamp-Massey Algorithm via Minimal Polynomials
Venue: arXiv cs.IT 2010
Year: 2010

We present a recursive minimal polynomial theorem for finite sequences over a commutative integral domain $D$. This theorem is relative to any element of $D$. The ingredients are: the arithmetic of Laurent polynomials over $D$, a recursive 'index function' and simple mathematical induction. Taking reciprocals gives a 'Berlekamp-Massey theorem' i.e. a recursive construction of the polynomials arising in the Berlekamp-Massey algorithm, relative to any element of $D$. The recursive theorem readily yields the iterative minimal polynomial algorithm due to the author and a transparent derivation of the iterative Berlekamp-Massey algorithm. We give an upper bound for the sum of the linear complexities of $s$ which is tight if $s$ has a perfect linear complexity profile. This implies that over a field, both iterative algorithms require at most $2\lfloor \frac{n^2}{4}\rfloor$ multiplications.
On the boundedness of an iteration involving points on the hypersphere
Venue: arXiv cs.CG 2010
Year: 2010

For a finite set of points $X$ on the unit hypersphere in $\mathbb{R}^d$ we consider the iteration $u_{i+1}=u_i+χ_i$, where $χ_i$ is the point of $X$ farthest from $u_i$. Restricting to the case where the origin is contained in the convex hull of $X$ we study the maximal length of $u_i$. We give sharp upper bounds for the length of $u_i$ independently of $X$. Precisely, this upper bound is infinity for $d\ge 3$ and $\sqrt2$ for $d=2$.
Algorithmic Differentiation of Linear Algebra Functions with Application in Optimum Experimental Design (Extended Version)
Venue: arXiv cs.DS 2010
Year: 2010

We derive algorithms for higher order derivative computation of the rectangular $QR$ and eigenvalue decomposition of symmetric matrices with distinct eigenvalues in the forward and reverse mode of algorithmic differentiation (AD) using univariate Taylor propagation of matrices (UTPM). Linear algebra functions are regarded as elementary functions and not as algorithms. The presented algorithms are implemented in the BSD licensed AD tool \texttt{ALGOPY}. Numerical tests show that the UTPM algorithms derived in this paper produce results close to machine precision accuracy. The theory developed in this paper is applied to compute the gradient of an objective function motivated from optimum experimental design: $\nabla_x Φ(C(J(F(x,y))))$, where $Φ= \{λ_1 : λ_1 C\}$, $C = (J^T J)^{-1}$, $J = \frac{\dd F}{\dd y}$ and $F = F(x,y)$.
Divide & Concur and Difference-Map BP Decoders for LDPC Codes
Venue: arXiv cs.IT 2010
Year: 2010

The "Divide and Concur'' (DC) algorithm, recently introduced by Gravel and Elser, can be considered a competitor to the belief propagation (BP) algorithm, in that both algorithms can be applied to a wide variety of constraint satisfaction, optimization, and probabilistic inference problems. We show that DC can be interpreted as a message-passing algorithm on a constraint graph, which helps make the comparison with BP more clear. The "difference-map'' dynamics of the DC algorithm enables it to avoid "traps'' which may be related to the "trapping sets'' or "pseudo-codewords'' that plague BP decoders of low-density parity check (LDPC) codes in the error-floor regime. We investigate two decoders for low-density parity-check (LDPC) codes based on these ideas. The first decoder is based directly on DC, while the second decoder borrows the important "difference-map'' concept from the DC algorithm and translates it into a BP-like decoder. We show that this "difference-map belief propagation'' (DMBP) decoder has dramatically improved error-floor performance compared to standard BP decoders, while maintaining a similar computational complexity. We present simulation results for LDPC codes on the additive white Gaussian noise and binary symmetric channels, comparing DC and DMBP decoders with other decoders based on BP, linear programming, and mixed-integer linear programming.
Two Theorems in List Decoding
Venue: arXiv cs.IT 2010
Year: 2010

We prove the following results concerning the list decoding of error-correcting codes: (i) We show that for \textit{any} code with a relative distance of $δ$ (over a large enough alphabet), the following result holds for \textit{random errors}: With high probability, for a $ρ\le δ-\eps$ fraction of random errors (for any $\eps>0$), the received word will have only the transmitted codeword in a Hamming ball of radius $ρ$ around it. Thus, for random errors, one can correct twice the number of errors uniquely correctable from worst-case errors for any code. A variant of our result also gives a simple algorithm to decode Reed-Solomon codes from random errors that, to the best of our knowledge, runs faster than known algorithms for certain ranges of parameters. (ii) We show that concatenated codes can achieve the list decoding capacity for erasures. A similar result for worst-case errors was proven by Guruswami and Rudra (SODA 08), although their result does not directly imply our result. Our results show that a subset of the random ensemble of codes considered by Guruswami and Rudra also achieve the list decoding capacity for erasures. Our proofs employ simple counting and probabilistic arguments.
Performance Analysis for Data Compression Based Signal Classification Methods
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we present an information theoretic analysis of the blind signal classification algorithm. We show that the algorithm is equivalent to a Maximum A Posteriori (MAP) estimator based on estimated parametric probability models. We prove a lower bound on the error exponents of the parametric model estimation. It is shown that the estimated model parameters converge in probability to the true model parameters except some small bias terms.
A complete characterization of group-strategyproof mechanisms of cost-sharing
Venue: arXiv cs.GT 2010
Year: 2010

We study the problem of designing group-strategyproof cost-sharing mechanisms. The players report their bids for getting serviced and the mechanism decides which players are going to be serviced and how much each one of them is going to pay. We determine three conditions: \emph{Fence Monotonicity}, \emph{Stability} of the allocation and \emph{Validity} of the tie-breaking rule that are necessary and sufficient for group-strategyproofness, regardless of the cost function. Fence Monotonicity puts restrictions only on the payments of the mechanism and stability only on the allocation. Consequently Fence Monotonicity characterizes group-strategyproof cost-sharing schemes. Finally, we use our results to prove that there exist families of cost functions, where any group-strategyproof mechanism has unbounded approximation ratio.
Quantitative Games on Probabilistic Timed Automata
Venue: arXiv cs.GT 2010
Year: 2010

Two-player zero-sum games are a well-established model for synthesising controllers that optimise some performance criterion. In such games one player represents the controller, while the other describes the (adversarial) environment, and controller synthesis corresponds to computing the optimal strategies of the controller for a given criterion. Asarin and Maler initiated the study of quantitative games on (non-probabilistic) timed automata by synthesising controllers which optimise the time to reach a final state. The correctness and termination of their approach was dependent on exploiting the properties of a special class of functions, called simple functions, that can be finitely represented. In this paper we consider quantitative games over probabilistic timed automata. Since the concept of simple functions is not sufficient to solve games in this setting, we generalise simple functions to so-called quasi-simple functions. Then, using this class of functions, we demonstrate that the problem of solving games with either expected reachability-time or expected discounted-time criteria on probabilistic timed automata are in NEXPTIME $\cap$ co-NEXPTIME.
A Wide range Survey on Recall Based Graphical User Authentications Algorithms Based on ISO and Attack Patterns
Venue: arXiv cs.CR 2010
Year: 2010

Nowadays, user authentication is one of the important topics in information security. Text based strong password schemes could provide with certain degree of security. However, the fact that strong passwords being difficult to memorize often leads their owners to write them down on papers or even save them in a computer file. Graphical user authentication (GUA) has been proposed as a possible alternative solution to text based authentication, motivated particularly by the fact that humans can remember images better than text. In recent years, many networks, computer systems and Internet based environments try used GUA technique for their users authentication. All of GUA algorithms have two different aspects which are usability and security. Unfortunately, none of graphical algorithms were being able to cover both of these aspects at the same time. This paper presents a wide range survey on the pure and cued recall based algorithms in GUA, based on ISO standards for usability and attack patterns standards for security. After explain usability ISO standards and attack patterns international standards, we try to collect the major attributes of usability and security in GUA. Finally, try to make comparison tables among all recall based algorithms based on usability attributes and attack patterns those we found.
A New Method to Extract Dorsal Hand Vein Pattern using Quadratic Inference Function
Venue: arXiv cs.CV 2010
Year: 2010

Among all biometric, dorsal hand vein pattern is attracting the attention of researchers, of late. Extensive research is being carried out on various techniques in the hope of finding an efficient one which can be applied on dorsal hand vein pattern to improve its accuracy and matching time. One of the crucial step in biometric is the extraction of features. In this paper, we propose a method based on quadratic inference function to the dorsal hand vein features to extract its features. The biometric system developed was tested on a database of 100 images. The false acceptance rate (FAR), false rejection rate (FRR) and the matching time are being computed.
Evaluating Effectiveness of Tamper Proofing on Dynamic Graph Software Watermarks
Venue: arXiv cs.MM 2010
Year: 2010

For enhancing the protection level of dynamic graph software watermarks and for the purpose of conducting the analysis which evaluates the effect of integrating two software protection techniques such as software watermarking and tamper proofing, constant encoding technique along with the enhancement through the idea of constant splitting is proposed. In this paper Thomborson technique has been implemented with the scheme of breaking constants which enables to encode all constants without having any consideration about their values with respect to the value of watermark tree. Experimental analysis which have been conducted and provided in this paper concludes that the constant encoding process significantly increases the code size, heap space usage, and execution time, while making the tamper proofed code resilient to variety of semantic preserving program transformation attacks.
Design and Analysis of a Spurious Switching Suppression Technique Equipped Low Power Multiplier with Hybrid Encoding Scheme
Venue: arXiv cs.OH 2010
Year: 2010

Multiplication is an arithmetic operation that is mostly used in Digital Signal Processing (DSP) and communication applications. Efficient implementation of the multipliers is required in many applications. The design and analysis of Spurious Switching Suppression Technique (SSST) equipped low power multiplier with hybrid encoding is presented in this paper. The proposed encoding technique reduces the number of switching activity and dynamic power consumption by analyzing the bit patterns in the input data. In this proposed encoding scheme, the operation is executed depends upon the number of 1s and its position in the multiplier data. The architecture of the proposed multiplier is designed using a low power full adder which consumes less power than the other adder architectures. The switching activity of the proposed multiplier has been reduced by 86 percent and 46percent compared with conventional and Booth multiplier respectively. It is observed from the device level simulation using TANNER 12.6 EDA that the power consumption of the proposed multiplier has been reduced by 87 percent and 26 percent compared with conventional and Booth multiplier.
ICD 10 Based Medical Expert System Using Fuzzy Temporal Logic
Venue: arXiv cs.AI 2010
Year: 2010

Medical diagnosis process involves many levels and considerable amount of time and money are invariably spent for the first level of diagnosis usually made by the physician for all the patients every time. Hence there is a need for a computer based system which not only asks relevant questions to the patients but also aids the physician by giving a set of possible diseases from the symptoms obtained using logic at inference. In this work, an ICD10 based Medical Expert System that provides advice, information and recommendation to the physician using fuzzy temporal logic. The knowledge base used in this system consists of facts of symptoms and rules on diseases. It also provides fuzzy severity scale and weight factor for symptom and disease and can vary with respect to time. The system generates the possible disease conditions based on modified Euclidean metric using Elders algorithm for effective clustering. The minimum similarity value is used as the decision parameter to identify a disease.
Hierarchical Route Optimization by Using Tree information option in a Mobile Networks
Venue: arXiv cs.NI 2010
Year: 2010

The Networks Mobility (NEMO) Protocol is a way of managing the mobility of an entire network, and mobile internet protocol is the basic solution for Networks Mobility. A hierarchical route optimization system for mobile network is proposed to solve management of hierarchical route optimization problems. In present paper, we study Hierarchical Route Optimization Scheme using Tree Information Option (HROSTIO). The concept of optimization finding the extreme of a function that maps candidate solution to scalar values of quality, is an extremely general and useful idea. For solving this problem, we use a few salient adaptations and we also extend HROSTIO perform routing between the mobile networks.
Fast-Group-Decodable STBCs via Codes over GF(4)
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we construct low decoding complexity STBCs by using the Pauli matrices as linear dispersion matrices. In this case the Hurwitz-Radon orthogonality condition is shown to be easily checked by transferring the problem to $\mathbb{F}_4$ domain. The problem of constructing low decoding complexity STBCs is shown to be equivalent to finding certain codes over $\mathbb{F}_4$. It is shown that almost all known low complexity STBCs can be obtained by this approach. New codes are given that have the least known decoding complexity in particular ranges of rate.
The Isomorphism Problem On Classes of Automatic Structures
Venue: arXiv cs.LO 2010
Year: 2010

Automatic structures are finitely presented structures where the universe and all relations can be recognized by finite automata. It is known that the isomorphism problem for automatic structures is complete for $Σ^1_1$; the first existential level of the analytical hierarchy. Several new results on isomorphism problems for automatic structures are shown in this paper: (i) The isomorphism problem for automatic equivalence relations is complete for $Π^0_1$ (first universal level of the arithmetical hierarchy). (ii) The isomorphism problem for automatic trees of height $n \geq 2$ is $Π^0_{2n-3}$-complete. (iii) The isomorphism problem for automatic linear orders is not arithmetical. This solves some open questions of Khoussainov, Rubin, and Stephan.
Sampled Longest Common Prefix Array
Venue: arXiv cs.DS 2010
Year: 2010

When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compressed representation of the LCP array is also one of the main building blocks in many compressed suffix tree proposals. In this paper, we describe a new compressed LCP representation: the sampled LCP array. We show that when used with a compressed suffix array (CSA), the sampled LCP array often offers better time/space trade-offs than the existing alternatives. We also show how to construct the compressed representations of the LCP array directly from a CSA.
Cooperative Automated Worm Response and Detection Immune Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

The role of T-cells within the immune system is to confirm and assess anomalous situations and then either respond to or tolerate the source of the effect. To illustrate how these mechanisms can be harnessed to solve real-world problems, we present the blueprint of a T-cell inspired algorithm for computer security worm detection. We show how the three central T-cell processes, namely T-cell maturation, differentiation and proliferation, naturally map into this domain and further illustrate how such an algorithm fits into a complete immune inspired computer security system and framework.
Weighted Logics for Nested Words and Algebraic Formal Power Series
Venue: arXiv cs.LO 2010
Year: 2010

Nested words, a model for recursive programs proposed by Alur and Madhusudan, have recently gained much interest. In this paper we introduce quantitative extensions and study nested word series which assign to nested words elements of a semiring. We show that regular nested word series coincide with series definable in weighted logics as introduced by Droste and Gastin. For this we establish a connection between nested words and the free bisemigroup. Applying our result, we obtain characterizations of algebraic formal power series in terms of weighted logics. This generalizes results of Lautemann, Schwentick and Therien on context-free languages.