Search

Dirty paper coding are relevant for wireless networks, multiuser channels, and digital watermarking. We show that the problem of dirty paper is essentially equivalent to some classes of constrained memories, and we explore the binary so-called nested codes, which are used for efficient coding and error-correction on such channels and memories. Keywords: dirty paper, constrained memory, nested codes, covering codes. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

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]

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

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]

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]

Decision tree construction is a well-studied problem in data mining. Recently, there has been much interest in mining data streams. Domingos and Hulten have presented a one-pass algorithm for decision tree constructions. Their system using Hoeffding inequality to achieve a probabilistic bound on the accuracy of the tree constructed. Gama et al. have extended VFDT in two directions. Their system VFDTc can deal with continuous data and use more powerful classification techniques at tree leaves. Peng et al. present soft discretization method to solve continuous attributes in data mining. In this paper, we revisit these problems and implemented a system sVFDT for data stream mining. We make the following contributions: 1) we present a binary search trees (BST) approach for efficiently handling continuous attributes. Its processing time for values inserting is O(nlogn), while VFDT‘s processing time is O(n2). 2) We improve the method of getting the best split-test point of a given continuous attribute. Comparing to the method used in VFDTc, it decreases fromO(nlogn) to O (n) in processing time. 3) Comparing to VFDTc, sVFDT‘zs candidate split-test number decrease fromO(n) to O(logn).4)Improve the soft discretization method to increase classification accuracy in data stream mining. [ABSTRACT FROM AUTHOR]

Job shop scheduling problem has earned a reputation for being difficult to solve. Varieties of algorithms are employed to obtain optimal or near optimal schedules. Optimization algorithms provide optimal results if the problems to be solved are not large. But most scheduling problems are NP-hard, hence optimization algorithms are ruled out in practice. The quality of solutions using branch and bound algorithms depends upon the good bound that requires a substantial amount of computation. Local search-based heuristics are known to produce decent results in short running times, but they are susceptible to being stuck in local minima. Therefore, in this paper, we presented a brand-new heuristic approach for job shop scheduling. The performance of the proposed method was validated based on some benchmark problems of job shop scheduling, with regard to both solution quality and computational time. [ABSTRACT FROM AUTHOR]

With the development of network and distributed systems, more and more security protocols rely heavily on time stamps, which are taken into account by a few formal methods. Generally, these methods use constraints to describe the characteristic of time variables. However, few of them give a feasible solution to the corresponding constraints solving problem. An effective framework to model and verify time sensitive security protocols is introduced in [1], which doesn't give an automatic algorithm for constraints solution. In this paper, an effective method is presented to determine whether the constraints system has a solution, and then implemented in our verifying tool SPVT. Finally, Denning-Sacco protocol is taken as an example to show that security protocols with time constraints can be modeled naturally and verified automatically and efficiently in our models. [ABSTRACT FROM AUTHOR]

In this paper, we resolve two open questions on the computation and approximation of an Arrow-Debreu equilibrium in a Leontief exchange economy: We prove that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, unless PPAD ⊆ P.We show that the smoothed complexity of any algorithm for computing a market equilibrium in a Leontief economy, is not polynomial, unless PPAD ⊆ RP. [ABSTRACT FROM AUTHOR]

This paper proposes a generalized on-line risk-reward model, by introducing the notion of the probabilistic forecast. Using this model, we investigate the on-line rental problem. We design the risk rental algorithms under the basic probability forecast and the geometric distribution probability forecast, respectively. In contrast to the existing competitive analyses of the on-line rental problem, our results are more flexible and can help the investor choosing the optimal algorithm according to his/her own risk tolerance level and probabilistic forecast. Moreover, we also show that this model has a good linkage to the stochastic competitive ratio analysis. [ABSTRACT FROM AUTHOR]

This paper describes the experiments and results obtained from distributing an improved insertion heuristic for the scheduling of passengers' trip requests over a fleet of vehicles. The distribution has been obtained by means of an agent architecture implemented over Jade. Agents make use of the contract-net protocol as base coordination mechanism for the planning and scheduling of passenger trips. In particular, this paper focuses on the insertion heuristic implementation details within the agent-based architecture and its performance in diverse distributed scenarios when varying the number of hosts. [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]

The line-of-sight networks is a network model introduced recently by Frieze et al. It considers wireless networks in which the underlying environment has a large number of obstacles and the communication can only take place between objects that are close in space and are in the line of sight to one another. To capture the main properties of this model, Frieze et al. proposed a new random networks model in which nodes are randomly placed on an n ×n grid and a node can communicate with all the nodes that are in at most a certain fixed distance r and which are in the same row or column. Frieze et al. concentrated their study on basic structural properties of the random line-of-sight networks and in this paper we focus on their communication aspects in the scenario of ad-hoc radio communication networks. We present efficient algorithms for two fundamental communication problems of broadcasting and gossiping in the classical ad-hoc radio communication model adjusted to random line-of-sight networks. [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]

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 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]

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 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]

Let G = (V,E) denote an undirected weighted graph of n nodes and m edges, and let U ⊆ V. The relative eccentricity of a node v ∈ U is the maximum distance in G between v and any other node of U, while the radius of U in G is the minimum relative eccentricity of all the nodes in U. Several facility location problems ask for partitioning the nodes of G so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of G into exactly p ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the total radius of the partition. This problem can be easily seen to be NP-hard when p is part of the input, but when p is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient O(n3) time algorithm for the notable case p = 2, which improves the O(mn2 + n3 logn) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when p is part of the input, we show that (i) when G is a tree, then the problem can be solved in O(n3p3) time, and (ii) when G has bounded treewidth h, then the problem can be solved in O(n4h + 4p3) time. [ABSTRACT FROM AUTHOR]