Counting the number of points of Jacobian varieties of hyperelliptic curves over finite fields is necessary for construction of hyperelliptic curve cryptosystems. Recently Gaudry and Harley proposed a practical scheme for point counting of hyperelliptic curves. Their scheme consists of two parts: firstly to compute the residue modulo a positive integer m of the order of a given Jacobian variety, and then search for the order by a square-root algorithm. In particular, the parallelized Pollard's lambda-method was used as the square-root algorithm, which took 50CPU days to compute an order of 127 bits. This paper shows a new variation of the baby step giant step algorithm to improve the square-root algorithm part in the Gaudry-Harley scheme. With knowledge of the residue modulo m of the characteristic polynomial of the Frobenius endomorphism of a Jacobian variety, the proposed algorithm provides a speed up by a factor m, instead of in square-root algorithms. Moreover, implementation results of the proposed algorithm is presented including a 135-bit prime order computed about 15 hours on Alpha 21264/667 MHz and a 160-bit order.

We discuss applications of quantum computation to geometric data processing. Especially, we give efficient algorithms for intersection problems and proximity problems. Our algorithms are based on Brassard et al. 's amplitude amplification method, and analogous to Buhrman et al. 's algorithm for element distinctness. Revealing these applications is useful for classifying geometric problems, and also emphasizing potential usefulness of quantum computation in geometric data processing. Thus, the results will promote research and development of quantum computers and algorithms.

This paper presents an innovative 155Mb/s burst-mode laser transmitter chip, which was designed and successfully demonstrated, and contains several new subsystems: a digitally programmed current source, programmable up to 120mA with a resolution of 0.1mA, a fast but accurate intermittent optical level monitoring circuit, and a digital Automatic Power Control (APC) algorithm. This generic and intelligent chip was developed in a standard digital 0.35µm CMOS process. Extensive testing showed a high yield and algorithm stability, as well as excellent performance. During initialization, when the transmitter is connected to the Passive Optical Network (PON) for the first time, maximum three Laser Control Fields (LCF) are needed, with a length of 17bytes (0.88microsecond at 155Mb/s), to stabilize the laser output power. In this short time, the chip can regulate the launched optical output power of any FSAN (Full Service Access Network) compliant laser diode to the required level, even in the extreme circumstances caused by outdoor operation or by battery backup operation during power outages. Other tests show that the chip can further stabilize and track this launched optical power with a tolerance lower than 1dB over a wide temperature range, during the burst mode data transmission. The APC algorithm intermittently adjusts the optical power to be transmitted in a digital way, starting from loosely specified but safe preset values, to the required stable logic "1" and "0" level. No laborious calibration of the laser characteristic curve and storage of the calibration values in lookup tables are needed, nor any off-chip adjustable component. The power consumption is significantly reduced by disabling inactive circuitry and by gating the digital high-speed clock. Although this laser transmitter was developed for FSAN PON applications, which are standardized at a speed of 155Mb/s upstream, the design concept is quite generic and can be applied for developing a wide range of burst mode laser transmitters, such as required for Gigabit PON systems or other TDMA networks.

Polarimetric SAR interferometry has been successful and attractive for forest parameters (tree height and canopy extinction) estimation. In this paper, we propose to use the ESPRIT algorithm to extract the interferometric phase of local scatterers with polarimetric and interferometric SAR data. Two or three local scattering waves can be extracted at each image patch when a fully polarimetric data set (HH, HV, VV) is available. Furthermore, the ESPRIT can estimate two dominant local scattering centers when only a dual polarimetric data set (e.g., VV and VH) is provided. In order to demonstrate effectiveness the proposed technqiue, we examined the relation between local scattering centers extracted by this method and complex coherence of the coherent scattering model for vegetation cover. The results show that the three-wave estimation can be more accurate than the two-wave case. The extracted interferometric phases with full and dual polarization data sets correspond to effective ground and canopy scattering centers. In this investigation, SIR-C/X-SAR data of the Tien Shan flight-pass are used.

This paper presents a new reconfigurable hardware paradigm, called evolvable hardware (EHW), and its application to the biomedical engineering problem of an artificial hand controller. Evolvable hardware is based on the idea of combining a reconfigurable hardware device with an artificial intelligence robust search technique called genetic algorithms (GAs) to execute reconfiguration autonomously. The first version of the EHW chip was designed in 1998, and this paper describes the latest improvements to the EHW chip, as well as outlining its architecture and the hardware implementation of the GA operations. Execution speed for genetic operations is shown to be about 38.7 times faster with the hardware implementation than with software program running on an AMD Athlon processor (1.2GHz). As an application of the EHW chip, this paper introduces a controller for a multi-functional prosthetic-hand, and presents experimental data in which a practical myoelectric pattern classification rate of 97.8% was achieved through the application of the EHW chip.

Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using (Δ1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using (n 1-3/(k+1)) colors. This improved Wigderson's algorithm, which uses O(n1-1/(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses (Δ 1-x/k) colors for 2

A dual greedy polyhedron is defined by a system of linear inequalities, where the right-hand sides are given by a submodular function and the coefficients matrix is given by the incidence vectors of antichains of a rooted forest. Faigle and Kern introduced this concept and showed that a dual greedy algorithm works for the linear program over dual greedy polyhedra. In this paper, we show that a dual greedy polyhedron is the isomorphic image of an ordinary submodular polyhedron under the Mobius function of the underlying rooted forest. This observation enables us to reduce linear optimization problems over dual greedy polyhedra to those over ordinary submodular polyhedra. We show a new max-min theorem for intersection of two dual greedy polyhedra as well.

The problem of constructing the suffix tree of a tree is a generalization of the problem of constructing the suffix tree of a string. It has many applications, such as in minimizing the size of sequential transducers and in tree pattern matching. The best-known algorithm for this problem is Breslauer's O(nlog |Σ|) time algorithm where n is the size of the CS-tree and |Σ| is the alphabet size, which requires O(nlog n) time if |Σ| is large. We improve this bound by giving an optimal linear time algorithm for integer alphabets. We also describe a new data structure, the Bsuffix tree, which enables efficient query for patterns of completely balanced k-ary trees from a k-ary tree or forest. We also propose an optimal O(n) algorithm for constructing the Bsuffix tree for integer alphabets.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n3) time algorithm for solving the minimum vertex ranking spanning tree problem on an interval graph.

A Radio Network (RN, for short) is a distributed system with no central arbiter, consisting of p radio stations each of which is endowed with a radio transceiver. In this work we consider single-hop, single channel RNs, where each station S(i), (1ip), initially stores si items which are tagged with the unique destination they must be routed. Since each item must be transmitted at least once, every routing protocol must take at least n = s1 + s2 + + sp time slots to route each item to its final destination. Similarly, each station S(i), (1ip), must be awake for at least si + di time slots to broadcast si items and to receive di items, where di denotes the number of items destined for S(i). The main contribution of this work is to present a randomized time- and energy-optimal routing protocol on the RN. Let qi, (1ip), be the number of stations that have items destined for S(i), q=q1 +q2 ++ qp, and ri be the number of stations for which S(i) has items. When qi is known to station S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in n + O(q + log f) time slots with each station S(i) being awake for at most si + di + O(qi + ri + log f) time slots. Since qidi, risi, and qn always hold, our randomized routing protocol is optimal. We also show that, when the value of di is known to S(i), our routing protocol runs, with probability exceeding 1 - , (f > 1), in O(n + log f) time slots with no station being awake for more than O(si + di + log f) time slots.

Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). In this paper, we prove that any series-parallel simple graph G has an L-edge-coloring if |L(e)| max{3,d(v),d(w)} for each edge e = vw, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. Our proof yields a linear algorithm for finding an L-edge-coloring of series-parallel graphs.

We have developed a low-power, high-performance MPEG-4 codec LSI for mobile video applications. This codec LSI is capable of up to CIF 30-fps encoding, making it suitable for various visual applications. The measured power consumption of the codec core was 9 mW for QCIF 15-fps codec operation and 38 mW for CIF 30-fps encoding. To provide an error-robust MPEG-4 codec, we implemented an error-resilience function in the LSI. We describe the techniques that have enabled low power consumption and high performance and discuss our test results.

This paper describes an ultra low power, motion estimation (ME) processor for MPEG2 HDTV resolution video. It adopts a Gradient Descent Search (GDS) algorithm that drastically reduces required computational power to 6 GOPS. A SIMD datapath architecture optimized for the GDS algorithm decreases the clock frequency and operating voltage. A low power 3-port SRAM with a write-disturb-free cell array arrangement is newly designed for image data caches of the processor. The proposed ME processor contains 7-M transistors, integrated in 4.50 mm 3.35 mm area using 0.13 µm CMOS technology. Estimated power consumption is less than 100 mW at 81 MHz@1.0 V. The processor is applicable to a portable HDTV system.

Caching web files reduces user response time as well as network traffic. When implementing caches, the file caching problem must be addressed; the problem is how to determine which files should be evicted from a cache when there is insufficient space for storing a new file so that the sum of the mis-hit (fault) file costs is minimized. Greedy-Dual-Size (GDS) is the best online algorithm in terms of competitiveness, i. e. , (k)/(k-h+1)-competitive, where k and h are the storage space of, respectively, GDS and an optimal offline algorithm. GDS performs very well even in trace-driven simulations. The worst-case time taken to service a request is another important measure for online file caching algorithms since slow response times render caching meaningless from the client's view point. This paper proposes a fast randomized (k)/(k-h+1)-competitive algorithm that performs in O(2log ^* k) time per file eviction or insertion, whereas GDS takes O(log k) time, where 2log ^* k is a much slower increasing function than log k. To confirm its practicality, we conduct trace driven simulations. Experimental results show that our algorithm attains only slightly worse byte hit rates and sufficiently large reduced latency in comparison with GDS, and our algorithm is a good candidate for caches requiring high-speed processing such as second-level caches in the large networks.

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices and with maximum degree at most D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulation but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulations with exactly n vertices and maximum degree at most D in O(1) time per triangulation, and all biconnected (non-based) plane triangulations with exactly n vertices and maximum degree at most D in O(n3) time per triangulation without duplications.

This paper presents a maximum likelihood (ML) identification and restoration method for noisy blurred images. The unitary discrete sine transform (DST) is employed to decouple the large order spatial state-space representation of the noisy blurred image into a bank of one-dimensional real state-space scalar subsystems. By assuming that the noises are Gaussian distributed processes, the maximum likelihood estimation technique using the expectation-maximization (EM) algorithm is developed to jointly identify the blurring functions, the image model parameters and the noise variances. In order to improve the computational efficiency, the conventional Kalman smoother is incorporated to give the estimates. The identification process also yields the estimates of transformed image data, from which the original image is restored by the inverse DST. The experimental results show the effectiveness of the proposed method and its superiority over the recently proposed spatial domain DFT-based methods.

A heterogeneous parallel computing environment consisting of different types of workstations and communication links plays an important role in parallel computing. In many applications on the system, collective communication operations are commonly used as communication primitives. Thus, design of the efficient collective communication operations is the key to achieve high-performance parallel computing. But the heterogeneity of the system complicates the design. In this paper, we consider design of an efficient gather operation, one of the most important collective operations. We show that an optimal gather schedule is found in O(n2k-1) time for the heterogeneous parallel computing environment with n processors of k distinct types, and that a nearly-optimal schedule is found in O(n) time if k=2.

GPS receivers are susceptible to jamming by interference. This paper proposes a recurrent neural network (RNN) predictor for new application in GPS anti-jamming systems. Five types of narrowband jammers, i. e. AR process, continuous wave interference (CWI), multi-tone CWI, swept CWI, and pulsed CWI, are considered in order to emulate realistic conditions. As the observation noise of received signals is highly non-Gaussian, an RNN estimator with a nonlinear structure is employed to accurately predict the narrowband signals based on a real-time learning method. The node decoupled extended Kalman filter (NDEKF) algorithm is adopted to achieve better performance in terms of convergence rate and quality of solution while requiring less computation time and memory. We analyze the computational complexity and memory requirements of the NDEKF approach and compare them to the global extended Kalman filter (GEKF) training paradigm. Simulation results show that our proposed scheme achieves a superior performance to conventional linear/nonlinear predictors in terms of SNR improvement and mean squared prediction error (MSPE) while providing inherent protection against a broad class of interference environments.

The 2-vertex-connectivity augmentation problem for specified vertices (2VCA-SV) is defined as follows: Given an undirected graph G=(V,E), a subgraph G0=(V,E') of G, a specified set of vertices S V and a weight function w:E R^+ (nonnegative real numbers), find a set E" E-E' with the minimum total weight, such that G0+E"=(V,E' E") has at least two internally disjoint paths between any pair of vertices in S. In this paper, we propose an O(|V||E|+ |V|2 log |V|) time algorithm 2-ABIS, whose performance ratio is 2 (3, respectively), for 2VCA-SV if G0 has a connected component containing S (otherwise).