Search

This paper presents a novel physically-based model for virtual Chinese brush. Compared with previous works, the main advantage of our method lies in the use of physically based modeling methods that describe the behavior of the real brush's deformation in terms of the interaction of the external and internal forces with the virtual writing paper. Instead of simulating the brush using bristles, we use points to simulate the whole brush bundle, which can drastically decrease the complexity inherent in the conventional bristle-level approach. A spring network is derived to calculate the physical deflection of brush according to the force exerted on it. With this model, we can get a more effective simulation of real brush painting. [ABSTRACT FROM AUTHOR]

Several features of today's grid are based on centralized or hierarchical services. However, as the grid size increasing, some of their functions especially resource discovery should be decentralized to avoid performance bottlenecks and guarantee scalability. A novel grid resource discovery method based on adaptive k-Nearest Neighbors clustering is presented in this paper. A class is formed by a collection of nodes with some similarities in their characteristics, each class is managed by a leader and consists of members that serve as workers. Resource requests are ideally forwarded to an appropriate class leader that would then direct it to one of its workers. This method can handle resource requests by searching a small subset out of a large number of nodes by resource clustering which can improve the resource query efficiency; on the other hand, it also achieves well scalability by managing grid resources with adaptive mechanism. It is shown from a series of experiments that the method presented in this paper achieves more scalability and efficient lookup performance than other existing methods. [ABSTRACT FROM AUTHOR]

The split-radix FFT computes a size-n complex DFT, when n is a large power of 2, using just $4n\lg n-6n+8$ arithmetic operations on real numbers. This operation count was first announced in 1968, stood unchallenged for more than thirty years, and was widely believed to be best possible. Recently James Van Buskirk posted software demonstrating that the split-radix FFT is not optimal. Van Buskirk's software computes a size-n complex DFT using only $(34/9+o(1))n\lg n$ arithmetic operations on real numbers. There are now three papers attempting to explain the improvement from 4 to 34/9: Johnson and Frigo, IEEE Transactions on Signal Processing, 2007; Lundy and Van Buskirk, Computing, 2007; and this paper. This paper presents the "tangent FFT," a straightforward in-place cache-friendly DFT algorithm having exactly the same operation counts as Van Buskirk's algorithm. This paper expresses the tangent FFT as a sequence of standard polynomial operations, and pinpoints how the tangent FFT saves time compared to the split-radix FFT. This description is helpful not only for understanding and analyzing Van Buskirk's improvement but also for minimizing the memory-access costs of the FFT. [ABSTRACT FROM AUTHOR]

Nowadays, it is still the primary problem to find the inhibitors of retrovirus, protease and integrase in anti-AIDS drug design. However, the research and experimental results about anti-AIDS inhibitors mainly exist in large numbers of scientific literature, not in readable format for computer. In this paper, we introduce an Ontology-based Information Extraction (OIE) approach to extract anti-AIDS inhibitors from literature. Key to the approach is the construction of anti-AIDS inhibitors ontology, which provides a semantic framework for information extraction, and annotation of corpus. Consequently, this paper primarily focuses on the architecture of OIE, on which we construct the anti-AIDS ontology using Protégé tool and annotate corpus. Finally, we employ a demonstrated application scenario to show how to annotate the PubMed articles based on the ontology we have constructed. [ABSTRACT FROM AUTHOR]

This paper proposes a semiring formulation for reasoning about an agent's changing beliefs: a dynamic epistemic semiring(DES). A DES is a modal semiring extended with epistemic-action operators. The paper concentrates on the revision operator by proposing an axiomatisation, developing a basic calculus and deriving the classical AGM revision axioms in the algebra. [ABSTRACT FROM AUTHOR]

Logiweb is a system for electronic publication and archival of machine checked mathematics of high typographic quality. It can verify the formal correctness of pages, i.e. mathematical papers expressed suitably. The present paper is an example of such a Logiweb page and the present paper is formally correct in the sense that it has been verified by Logiweb. The paper may of course contain informal errors like any other paper. Logiweb is neutral with respect to choice of logic and choice of notation and can support any kind of formal reasoning. Logiweb uses the World Wide Web to publish Logiweb pages and Logiweb pages can be viewed by ordinary Web browsers. Logiweb pages can reference definitions, lemmas, and proofs on previously referenced Logiweb pages across the Internet. When Logiweb verifies a Logiweb page, it takes all transitively referenced pages into account. [ABSTRACT FROM AUTHOR]

In this paper a new problem-solving environment (PSE) for geometric processing of surfaces is introduced. The PSE has been designed to be responsive to the needs of our collaboration with an industrial partner, the Spanish company CANDEMAT S.A., devoted to build moulds and dies for the automotive industry. The PSE has been implemented in Matlab and is aimed to support the full range of activities carried out by our partner in the field of geometric processing of surfaces for the automotive industry. Firstly, the paper describes the architecture of the system and some implementation details. Then, some examples of its application to critical problems in the automotive industry - such as the computation of the intersection curves of surfaces, the generation of tool-path trajectories for NC machining and the visualization of geometric entities stored in industrial files of several formats - are briefly described. The PSE has shown to provide our partner with accurate, reliable solutions to these and other problems and to serve as a communication channel for exchange of geometrical data as well as a platform for trial and research support. [ABSTRACT FROM AUTHOR]

We introduce and analyse a simple probabilistic model of genome evolution. It is based on three fundamental evolutionary events: gene duplication, loss and innovation, and it is called DLI model. The focus of the paper is around the size distribution of gene families. The formulas for equilibrium gene family sizes are derived showing that they follow a logarithmic distribution. We consider also a disjoint union of DLI models and we present the result of this study. Some empirical results for microbial genomes are presented. [ABSTRACT FROM AUTHOR]

This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with $O(\sqrt{N}/{\varepsilon})$ queries to ε-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\varepsilon}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of ε. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new framework to provide continuous services to users by a collection of mobile servers distributed over an interconnection network. We model those mobile servers as a subset of host computers, and assume that a user host can receive the service if at least one adjacent host computer (including itself) plays the role of a server; i.e., we assume that the service could not be routed via the interconnection network. The main results obtained in this paper are summarized as follows: For the class of trees with n hosts, ⌈(n+1)/2⌉ mobile servers are necessary and sufficient to realize continuous services by the mobile servers, and for the class of Hamiltonian graphs with n hosts, ⌈(n+1)/3⌉ mobile servers are necessary and sufficient. [ABSTRACT FROM AUTHOR]

We initiate a study on automata recognizing labelled posets constructed from scattered and countable linear orderings. More precisely, the class of labelled posets considered in this paper is the smallest containing letters, closed under finite parallel operation and sequential product indexed by all countable and scattered linear orderings. The first result of this paper establishes that those labelled posets are precisely the N-free ones. The second result is a Kleene-like theorem, which establishes that the class of languages of labelled posets accepted by branching automata is exactly the class of rational languages. This generalizes both the finite [9] and ω-labelled posets [2,6] cases, and the Kleene-like theorem on words on linear orderings [3]. [ABSTRACT FROM AUTHOR]

The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p ≤ 1/clogn. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1/n1/2, and does not when p ∈ 1/O(n1/2). Furthermore, a network built of tori is designed, with the same fault-tolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ∈ 1/O(n1/d). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. [ABSTRACT FROM AUTHOR]

Compression is most important when space is in short supply, so compression algorithms are often implemented in limited memory. Most analyses ignore memory constraints as an implementation detail, however, creating a gap between theory and practice. In this paper we consider the effect of memory limitations on compression algorithms. In the first part of the paper we assume the memory available is fixed and prove nearly tight upper and lower bound on how much is needed to compress a string close to its k-th order entropy. In the second part we assume the memory available grows (slowly) as more and more characters are read. In this setting we show that the rate of growth of the available memory determines the speed at which the compression ratio approaches the entropy. In particular, we establish a relationship between the rate of growth of the sliding window in the LZ77 algorithm and its convergence rate. [ABSTRACT FROM AUTHOR]

In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of sorting by reversals(SBR): given two strings, A and B, find the minimum number of reversals that transform the string A into the string B (a reversalρ(i,j), i

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on random error-correcting codes. In this paper we investigate the security and the efficiency of their proposal. We show that a passive attacker who may intercept just a few signatures can recover the private key. We give precisely the number of signatures required to achieve this goal. This enables us to prove that all the schemes given in the original paper can be broken with at most 20 signatures. We improve the efficiency of these schemes by firstly providing parameters that enable to sign about 40 messages, and secondly, by describing a way to extend these few-times signatures into classical multi-time signatures. We finally study their key sizes and a mean to reduce them by means of more compact matrices. [ABSTRACT FROM AUTHOR]

Edwards curves have attracted great interest for several reasons. When curve parameters are chosen properly, the addition formulas use only 10M + 1S. The formulas are strongly unified, i.e., work without change for doublings; even better, they are complete, i.e., work without change for all inputs. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. This paper introduces inverted Edwards coordinates. Inverted Edwards coordinates (X1:Y1:Z1) represent the affine point (Z1/X1,Z1/Y1) on an Edwards curve; for comparison, standard Edwards coordinates (X1:Y1:Z1) represent the affine point (X1/Z1,Y1/Z1). This paper presents addition formulas for inverted Edwards coordinates using only 9M + 1S. The formulas are not complete but still are strongly unified. Dedicated doubling formulas use only 3M + 4S, and dedicated tripling formulas use only 9M + 4S. Inverted Edwards coordinates thus save 1M for each addition, without slowing down doubling or tripling. [ABSTRACT FROM AUTHOR]

This paper studies the problem of computing an upward topological book embedding of an upward planar digraph G, i.e. a topological book embedding of G where all edges are monotonically increasing in the upward direction. Besides having its own inherent interest in the theory of upward book embeddability, the question has applications to well studied research topics of computational geometry and of graph drawing. The main results of the paper are as follows. Every upward planar digraph G with n vertices admits an upward topological book embedding such that every edge of G crosses the spine of the book at most once.Every upward planar digraph G with n vertices admits a point-set embedding on any set of n distinct points in the plane such that the drawing is upward and every edge of G has at most two bends.Every pair of upward planar digraphs sharing the same set of n vertices admits an upward simultaneous embedding with at most two bends per edge. [ABSTRACT FROM AUTHOR]

Tree-based algorithms, such as Patricia, LC-trie, LPFST, etc, are widely used to do longest prefix matching (LPM). These algorithms use all the bits of the prefix to build the tree and the bits are used from the most significant bit to the least significant bit sequentially. Thus the tree is not balanced and the tree depth is high. In this paper, we propose bit selection tree (BS-tree) to do LPM. The bits of the prefix are selected to build BS-tree based on their costs defined in this paper. BS-tree has lower tree depth and is more balanced compared to other tree-based schemes. BS-tree has good scalability to the length of the IP address and is suitable for both IPv4 and IPv6. We evaluate the performances of BS-tree using both IPv4 and IPv6, and specially refine it for IPv6 based on the observations on IPv6 address and real IPv6 routing tables. [ABSTRACT FROM AUTHOR]

In wireless sensor networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem and perform some other tasks such as area monitoring. Previous work in this area has mainly focused on how to set up a small virtual backbone for high efficiency, which is modelled as the minimum Connected Dominating Set (CDS) problem. In this paper we consider how to establish a small virtual backbone to balance efficiency and fault tolerance. This problem can be formalized as the minimum m-connected k-dominating set problem, which is a general version of minimum CDS problem with m = 1 and k = 1. In this paper we will propose some approximation algorithms for this problem that beat the current best performance ratios. [ABSTRACT FROM AUTHOR]

This paper studies a spanning tree problem with interval data that finds diverse applications in network design. Given an underlying network G = (V,E), each link e ∈ E can be established by paying a cost $c_e\in[\underline{c}_e,\overline{c}_e]$, and accordingly takes a risk $\frac{\overline{c}_e-c_e}{\overline{c}_e-\underline{c}_e}$ of link failure. The minimum risk spanning tree (MRST) problem is to establish a spanning tree in G of total cost no more than a given constant so that the risk sum over the links on the spanning tree is minimized. In this paper, we propose an exact algorithm for the MRST problem that has time-complexity of O(m2logm logn(m + n logn)), where m = E and n = V. [ABSTRACT FROM AUTHOR]

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs (pLPs) and solved explicitly offline. Several algorithms have recently been proposed in the literature that solve these pLPs in a fairly efficient manner, all of which have as a base operation the computation and removal of redundant constraints. For many problems, it is this redundancy elimination that requires the vast majority of the computation time. This paper introduces a new solution technique for multiparametric linear programs based on the primal-dual paradigm. The proposed approach reposes the problem as the vertex enumeration of a linearly transformed polytope and then simultaneously computes both its vertex and halfspace representations. Exploitation of the halfspace representation allows, for smaller problems, a very significant reduction in the number of redundancy elimination operations required, resulting in many cases in a much faster algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E →R+ and two subsets R and R′ satisfying $R'\subset R\subseteq V$, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem. [ABSTRACT FROM AUTHOR]

The enumerate-and-expand paradigm for solving NP-hard problems has been introduced and applied to some Vertex Cover variants in a recently published preliminary paper. In this paper we improve on the runtime for Connected Vertex Cover, obtaining a bound of O*(2.7606k),The O*-notation is equivalent to the well-known Landau notation, except that polynomial factors may be suppressed. For instance, 2kk2n3=O*(2k). and use the technique in order to gain the fastest known method for counting the number of vertex covers in a graph, which takes O*(1.3803k) time. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding the 1-median on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an O(mn2log n)-time algorithm for the problem on a general graph, and had an O(nlog2n)-time algorithm on a tree. In this paper, we improve these two bounds to O(mn2 + n3log n) and O(nlog n), respectively. Keywords: Location theory, minmax regret optimization, medians. [ABSTRACT FROM AUTHOR]

The problem addressed in this paper is searching for a dependence between the correlation dimension of a time series and the mean square error (MSE) obtained when predicting the future time series values using a multilayer perceptron. The relation between the correlantion dimension and the ability of a neural network to adapt to sample data represented by in-sample mean square error is also studied. The dependence between correlation dimension and in-sample and out-of-sample MSE is found in many real-life as well as artificial time series. The results presented in the paper were obtained using various neural network sizes and various activation functions of the output layer neurons. [ABSTRACT FROM AUTHOR]

According to the interactive view of computation, communication happens during the computation, not before or after it. This approach, distinct from concurrency theory and the theory of computation, represents a paradigm shift that changes our understanding of what is computation and how it is modeled. Interaction machines extend Turing machines with interaction to capture the behavior of concurrent systems, promising to bridge these two fields. This promise is hindered by the widespread belief, incorrectly known as the Church-Turing thesis, that no model of computation more expressive than Turing machines can exist. Yet Turing's original thesis only refers to the computation of functions and explicitly excludes other computational paradigms such as interaction. In this paper, we identify and analyze the historical reasons for this widespread belief. Only by accepting that it is false can we begin to properly investigate formal models of interaction machines. We conclude the paper by presenting one such model, Persistent Turing Machines (PTMs). PTMs capture sequential interaction, which is a limited form of concurrency; they allow us to formulate the Sequential Interaction Thesis, going beyond the expressiveness of Turing machines and of the Church-Turing thesis. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in (Parida et al., CPM'01), (Pisanti et al.,MFCS'03) and (Pelfrene et al., CPM'03), its output-polynomial time computability is still open. The main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n with O(n3) time per motif with O(n2) space and O(n3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique called prefix-preserving closure extension. We also show an exponential lowerbound and a succinctness result on the number of maximal motifs, which indicate the limit of a straightforward approach. [ABSTRACT FROM AUTHOR]

The paper describes a new method for extracting objects from high resolution color remote sensing images. This method is based on the fuzzy segmentation algorithm which has been developed in our previous works. The proposed object extraction method is following three steps. (1) Segmenting color images, (2) Detecting objects from segmented images, and (3) Postprocessing of extracted object. The paper also gives experimental results from using the proposed method to extract centerlines of road networks and roofs of building from QuickBird and Ikonos Images. [ABSTRACT FROM AUTHOR]

A gene team is a set of genes that appear in two or more species, possibly in a different order yet with the distance between adjacent genes in the team for each chromosome always no more than a certain threshold. The focus of this paper is the problem of finding gene teams of two chromosomes. Béal et al. [1] had an O(nlog2n)-time algorithm for this problem. In this paper, two O(nlogd)-time algorithms are proposed, where d ≤ n is the number of gene teams. The proposed algorithms are obtained by modifying Béal et al.΄s algorithm, using two different approaches. Béal et al.΄s algorithm can be extended to find the gene teams of k chromosomes in O(knlog2n) time. Our improved algorithms can be extended to find the gene teams of k chromosomes in O(knlogd) time. [ABSTRACT FROM AUTHOR]

One of the most important problems for Wireless Sensor Networks (WSNs) is energy consumption since it ultimately determines the lifetime of the system. Medium Access Control (MAC) protocols based on schedules (e.g., TDMA) play an important role, since collisions and idle listening can be avoided, effectively reducing energy consumption. The problem of determining good transmission schedules for WSNs can be mapped to the distance-2 edge coloring problem in graphs, where edge colors represent slots in a TDMA-based MAC protocol, for example. In this paper, we propose and evaluate two new probabilistic and distributed distance-2 edge coloring algorithms that require no global node identifiers. We obtain analytical results for the worst-case convergence time. Moreover, we use simulations to evaluate the performance of the algorithms with respect to several metrics. Our findings indicate a tradeoff between convergence time and message overhead versus number of colors used. [ABSTRACT FROM AUTHOR]

Web prefetching is a primary means to reduce user access latency. The PPM was used to predict user request patterns in traditional literature. However the existing PPM models are usually constructed in offline case, they could not be updated incrementally for user coming new request, such models are only suitable for the relatively stable user access patterns. In this paper, we present an online PPM granular prediction model to capture the changing patterns and the limitation of memory, its implementation is based on a noncompact suffix tree and a sliding window W, the results show that our granular prediction model gives the best result comparing with existing PPM prediction models. [ABSTRACT FROM AUTHOR]

This paper presents a novel stochastic model that explains the relation between power laws of In-Degree and PageRank. PageRank is a popularity measure designed by Google to rank Web pages. We model the relation between PageRank and In-Degree through a stochastic equation, which is inspired by the original definition of PageRank. Using the theory of regular variation and Tauberian theorems, we prove that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with Web data. Categories and Subject Descriptors H.3.3:[Information Storage and Retrieval]: Information Search and Retrieval– Retrieval models; G.3:[Mathematics of Computing]: Probability and statistics – Stochastic processes, Distribution functions [ABSTRACT FROM AUTHOR]

In this paper we introduce a new technique to synthesize functions matching a given set of input-output pairs. Using techniques similar to defunctionalisation the abstract syntax tree of the candidate functions is specified at a high level of abstraction. We use a recursive data type to represent the syntax tree of the candidate functions. The test system G∀ST is used for the systematic synthesis of candidate functions and the selection of functions matching the given condition. The representation of candidate functions as data structures gives us full control over them and the transformation of the syntax tree to the actual function is straight forward. Instances of the syntax tree are generated by a generic algorithm that can be tailored easily to specific needs. This yields a very flexible system to synthesize clear (recursive) function definitions efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we develop a theory that studies words with nested data values with the help of shuffle expressions. We study two cases, which we call "ordered" and "unordered". In the unordered case, we show that emptiness (of the two related problems) is decidable. In the ordered case, we prove undecidability. As a proof vehicle for the latter, we introduce the notion of higher-order multicounter automata. [ABSTRACT FROM AUTHOR]

In this paper, we study the pattern matching problem in given intervals. Depending on whether the intervals are given a priori for pre-processing, or during the query along with the pattern or, even in both cases, we develop solutions for different variants of this problem. In particular, we present efficient indexing schemes for each of the above variants of the problem. [ABSTRACT FROM AUTHOR]

We say that, for k ≥ 2 and ℓ> k, a tree T is a (k,ℓ)-leaf root of a graph G = (VG,EG) if VG is the set of leaves of T, for all edges xy ∈ EG, the distance dT(x,y) in T is at most k and, for all non-edges $xy \not\in E_G$, dT(x,y) is at least ℓ. A graph G is a (k,ℓ)-leaf power if it has a (k,ℓ)-leaf root. This new notion modifies the concept of k-leaf power which was introduced and studied by Nishimura, Ragde and Thilikos motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. For k = 3 and k = 4, structural characterisations and linear time recognition algorithms of k-leaf powers are known, and, recently, a polynomial time recognition of 5-leaf powers was given. For larger k, the recognition problem is open. We give structural characterisations of (k,ℓ)-leaf powers, for some k and ℓ, which also imply an efficient recognition of these classes, and in this way we also improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs and leaf powers. [ABSTRACT FROM AUTHOR]

Finding the sub-vector with the largest sum in a sequence of n numbers is known as the maximum sum problem. Finding the k sub-vectors with the largest sums is a natural extension of this, and is known as the k maximal sums problem. In this paper we design an optimal O(n + k) time algorithm for the k maximal sums problem. We use this algorithm to obtain algorithms solving the two-dimensional k maximal sums problem in O(m2·n + k) time, where the input is an m ×n matrix with m ≤ n. We generalize this algorithm to solve the d-dimensional problem in O(n2d − 1 + k) time. The space usage of all the algorithms can be reduced to O(nd − 1 + k). This leads to the first algorithm for the k maximal sums problem in one dimension using O(n + k) time and O(k) space. [ABSTRACT FROM AUTHOR]

Consider a rooted directed acyclic graph G = (V, E) with root r, representing a collection V of web pages connected via a set E of hyperlinks. Each node v is associated with the probability that a user wants to access the node v. The access cost is defined as the expected number of steps required to reach a node from the root r. A bookmark is an additional shortcut from r to a node of G, which may reduce the access cost. The bookmark assignment problem is to find a set of bookmarks that achieves the greatest improvement in the access cost. For the problem, the paper presents a polynomial time approximation algorithm with factor (1 − 1/e), and shows that there exists no polynomial time approximation algorithm with a better constant factor than (1 − 1/e) unless ${\cal NP}\subseteq {\cal DTIME}(N^{O(\log\log N)})$, where N is the size of the inputs. [ABSTRACT FROM AUTHOR]

Consider the Dynamic Program h(n) = min 1 ≤j ≤na(n,j) for n = 1, 2..., N. For arbitrary values of a(n,j), calculating all the h(n) requires Θ(N2) time. It is well known that, if the a(n,j) satisfy the Monge property, then there are techniques to reduce the time down to O(N). This speedup is inherently static, i.e., it requires N to be known in advance. In this paper we show that if the a(n,j) satisfy a stronger condition, then it is possible, without knowing N in advance, to compute the values of h(n) in the order of n = 1, 2..., N, in O(1) amortized time per h(n). This maintains the DP speedup online, in the sense that the time to compute all h(n) is O(N). A slight modification of our algorithm restricts the worst case time to be O(logN) per h(n), while maintaining the amortized time bound. For a(n,j) that satisfy our stronger condition, our algorithm is also simpler to implement than the standard Monge speedup. We illustrate the use of our algorithm on two examples from the literature. The first shows how to make the speedup of the D-median on a line problem in an online settings. The second shows how to improve the running time for a DP used to reduce the amount of bandwidth needed when paging mobile wireless users. [ABSTRACT FROM AUTHOR]

In this paper, we present for the first time efficient explicit formulas for arithmetic in the degree 0 divisor class group of a real hyperelliptic curve. Hereby, we consider real hyperelliptic curves of genus 2 given in affine coordinates for which the underlying finite field has characteristic > 3. These formulas are much faster than the optimized generic algorithms for real hyperelliptic curves and the cryptographic protocols in the real setting perform almost as well as those in the imaginary case. We provide the idea for the improvements and the correctness together with a comprehensive analysis of the number of field operations. Finally, we perform a direct comparison of cryptographic protocols using explicit formulas for real hyperelliptic curves with the corresponding protocols presented in the imaginary model. [ABSTRACT FROM AUTHOR]

In this paper we propose a new structure for multiplication using optimal normal bases of type 2. The multiplier uses an efficient linear transformation to convert the normal basis representations of elements of $\mathbb{F}_{q^{n}}$ to suitable polynomials of degree at most n over $\mathbb{F}_{q}$. These polynomials are multiplied using any method which is suitable for the implementation platform, then the product is converted back to the normal basis using the inverse of the above transformation. The efficiency of the transformation arises from a special factorization of its matrix into sparse matrices. This factorization — which resembles the FFT factorization of the DFT matrix — allows to compute the transformation and its inverse using O(n logn) operations in $\mathbb{F}_{q}$, rather than O(n2) operations needed for a general change of basis. Using this technique we can reduce the asymptotic cost of multiplication in optimal normal bases of type 2 from reported by Gao et al. (2000) to ${\sf M}(n)+O(n \log n)$ operations in $\mathbb{F}_{q}$, where ${\sf M}(n)$ is the number of $\mathbb{F}_{q}$-operations to multiply two polynomials of degree n − 1 over $\mathbb{F}_{q}$. We show that this cost is also smaller than other proposed multipliers for n > 160, values which are used in elliptic curve cryptography. [ABSTRACT FROM AUTHOR]

Embedded systems require efficient yet flexible implementations of cryptographic primitives with a minimal impact on the overall cost of a device. In this paper we present the design of a functional unit (FU) for accelerating the execution of cryptographic software on 32-bit processors. The FU is basically a multiply-accumulate (MAC) unit able to perform multiplications and MAC operations on integers and binary polynomials. Polynomial arithmetic is a performance-critical building block of numerous cryptosystems using binary extension fields, including public-key primitives based on elliptic curves (e.g. ECDSA), symmetric ciphers (e.g. AES or Twofish), and hash functions (e.g. Whirlpool). We integrated the FU into the Leon2 SPARC V8 core and prototyped the extended processor in an FPGA. All operations provided by the FU are accessible to the programmer through custom instructions. Our results show that the FU allows to accelerate the execution of 128-bit AES by up to 78% compared to a conventional software implementation using only native SPARC V8 instructions. Moreover, the custom instructions reduce the code size by up to 87.4%. The FU increases the silicon area of the Leon2 core by just 8,352 gates and has almost no impact on its cycle time. [ABSTRACT FROM AUTHOR]

We deal with the asymptotic enumeration of combinatorial structures on planar maps. Prominent instances of such problems are the enumeration of spanning trees, bipartite perfect matchings, and ice models. The notion of an α-orientation unifies many different combinatorial structures, including the afore mentioned. We ask for the number of α-orientations and also for special instances thereof, such as Schnyder woods and bipolar orientations. The main focus of this paper are bounds for the maximum number of such structures that a planar map with n vertices can have. We give examples of triangulations with 2.37n Schnyder woods, 3-connected planar maps with 3.209n Schnyder woods and inner triangulations with 2.91n bipolar orientations. These lower bounds are accompanied by upper bounds of 3.56n, 8n, and 3.97n, respectively. We also show that for any planar map M and any α the number of α-orientations is bounded from above by 3.73n and we present a family of maps which have at least 2.598nα-orientations for n big enough. [ABSTRACT FROM AUTHOR]

The uniform distribution of the trace map lends itself very well to the construction of binary and non-binary codes from Galois fields and Galois rings. In this paper we study the distribution of the trace map with the argument ax2 over the Galois field GF(p,2). We then use this distribution to construct two-weight, self-orthogonal, trace codes. [ABSTRACT FROM AUTHOR]

In this paper we consider some properties of quasi-cyclic codes over the integer residue rings. A quasi-cyclic code over ℤk, the ring of integers modulo k, reduces to a direct product of quasi-cyclic codes over ${\mathbb{Z}}_{p_i^{e_i}}$, $k = \prod_{i=1}^s p_i^{e_i}$, pi a prime. Let T be the standard shift operator. A linear code $\mathcal{C}$ over a ring R is called an l-quasi-cyclic code if $T^l(c) \in \mathcal{C}$, whenever $ c\in \mathcal{C}$. It is shown that if (m, q) = 1, q = pr, p a prime, then an l-quasi-cyclic code of length lm over ℤq is a direct product of quasi-cylcic codes over some Galois extension rings of ℤq. We have discussed about the structure of the generator of a 1-generator l-quasi-cyclic code of length lm over ℤq. A method to obtain quasi-cyclic codes over ℤq, which are free modules over ℤq, has been discussed. [ABSTRACT FROM AUTHOR]

This paper proposes a joint coding with three functions: source coding, channel coding, and public-key encryption. A codeword is simply generated as a product of an encoding matrix and a sparse information word. This encoding method has much lower encoding complexity than the conventional coding techniques in which source coding, encryption, and channel coding are successively applied to an information word. The encoding matrix is generated by using two linear error control codes and randomly generated nonsingular matrices. Encryption is based on the intractableness of factorizing a matrix into randomly constructed factor matrices, and of decoding an error control code defined by a random parity-check matrix. Evaluation shows that the proposed joint coding gives a lower bit error rate and a superior compression ratio than the conventional codings. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method for fault tolerant computation over GF(2k) for use in public key cryptosystems. In particular, we are concerned with the active side channel attacks, i.e., fault attacks. We define a larger ring in which new computation is performed with encoded elements while arithmetic structure is preserved. Computation is decomposed into parallel, mutually independent, identical channels, so that fault effects do not spread to the other channels. By assuming certain fault models, our proposed model provides protection against their error propagation. Also, we provide an analysis of the error detection and correction capabilities of our proposed model. [ABSTRACT FROM AUTHOR]

The code length of Tardos's collusion-secure fingerprinting code (STOC'03) is of theoretically minimal order with respect to the number of malicious users (pirates); however, the constant factor should be further reduced for practical implementation. In this paper we give a collusion-secure fingerprinting code by mixing recent two improvements of Tardos code and modifying their pirates tracing algorithms. Our code length is significantly shorter than Tardos code, especially in the case of fewer pirates. For example, the ratio of our length relative to Tardos code in some practical situation with 4 pirates is 4.33%; while the lowest among the preceding codes in this case (S̆korić et al., 2007) is 9.87%. [ABSTRACT FROM AUTHOR]

Finding the similarity between two sequences is a major problem in computer science. It is motivated by many issues from computational biology as well as from information retrieval and image processing. These fields take into account possible corruptions of the data caused by genome rearrangements, typing mistakes, and more. Therefore, many applications do not require merely complete resemblance of the sequences, but rather an approximated matching. We consider mismatches and swaps as natural mistakes which are allowed in a meagre number. The edit distance problem with swap and mismatch operations was discussed by Amir et. al. [3]. They solved the problem in $O(n\sqrt{m}\log m)$ time. From then on the problem of string matching with at most k swaps and mismatches errors was open. In this paper we present an algorithm that finds all locations where the pattern has at most k mismatch and swap errors in time $O(n\sqrt{k\log m})$. [ABSTRACT FROM AUTHOR]

Gossiping is an important problem in Radio Networks that has been well studied, leading to many important results. Due to strong resouce limitations of sensor nodes, previous solutions are frequently not feasible in Sensor Networks. In this paper, we study the gossiping problem in the restrictive context of Sensor Networks. By exploiting the geometry of sensor node distributions, we present reduced, optimal running time of O(D + Δ) for an algorithm that completes gossiping with high probability in a Sensor Network of unknown topology and adversarial wake-up, where D is the diameter and Δ the maximum degree of the network. Given that an algorithm for gossiping also solves the broadcast problem, our result proves that the classic lower bound of [16] can be broken if nodes are allowed to do preprocessing. [ABSTRACT FROM AUTHOR]