On the complexity of suboptimal decoding for list and decision feedback schemes

We consider bounded distance list decoding, such that the decoder calculates the list of all codewords within a sphere around the received vector. We analyze the performance and the complexity of this suboptimum list decoding scheme for the binary symmetric channel. The reliability function of the list decoding scheme is equivalent to the sphere-packing bound, where the decoding complexity is asymptotically bounded by 2^nR(1-R). Furthermore, we investigate a decision feedback strategy that is based on bounded distance list decoding. Here, any output with zero or many codewords will call for a repeated transmission. In this case the decoding complexity will be of the order 2^nR(1-C), where C denotes the channel capacity. The reliability function is close to Forney's feedback exponent.     

The vulnerability of geometric sequences based on fields of odd characteristic

A new method of cryptologic attack on binary sequences is given, using their linear complexities relative to odd prime numbers. We show that, relative to a particular prime number p, the linear complexity of a binary geometric sequence is low. It is also shown that the prime p can be determined with high probability by a randomized algorithm if a number of bits much smaller than the linear complexity is known. This determination is made by exploiting the imbalance in the number of zeros and ones in the sequences in question, and uses a new statistical measure, the partial imbalance.This project was sponsored by the National Security Agency under Grant No. MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.     

Features of the Motion of a Gas-Liquid Medium in a Compound Shell (Sphere and Truncated Cone) Subject to Vibration

The results from an experimental study into the dynamic behavior of a gas-liquid medium and solid particles in a compound shell (sphere-truncated cone) are reported on. The following processes are studied: formation of gas bubbles and their clusters, strong macroflows, and intensive chaotic motion of the medium in the truncated cone as a nonlinear vibrating liquid-gas system__________Translated from Prikladnaya Mekhanika, Vol. 41, No. 1, pp. 112–118, January 2005.     

Pure adaptive search in global optimization

Pure adaptive seach iteratively constructs a sequence of interior points uniformly distributed within the corresponding sequence of nested improving regions of the feasible space. That is, at any iteration, the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly superior in value to the previous points in the sequence. The complexity of this algorithm is measured by the expected number of iterations required to achieve a given accuracy of solution. We show that for global mathematical programs satisfying the Lipschitz condition, its complexity increases at mostlinearly in the dimension of the problem.This work was supported in part by NATO grant 0119/89.     

Rational Points on the Sphere

Using only basic tools from the theory of modular forms, the rational points of bounded height on the sphere are counted and shown to be uniformly distributed. The more difficult case of points with a given height is also treated.     

A note on the complexity and tractability of the heat equation

We wish to solve the heat equation u_t=Δu-qu in I^d×(0,T), where I is the unit interval and T is a maximum time value, subject to homogeneous Dirichlet boundary conditions and to initial conditions u(·,0)=f over I^d. We show that this problem is intractable if f belongs to standard Sobolev spaces, even if we have complete information about q. However, if f and q belong to a reproducing kernel Hilbert space with finite-order weights, we can show that the problem is tractable, and can actually be strongly tractable.     

非球面最适球面的确定方法——三点法

根据非球面生产的实际情况．指出非球面最适球面的确定方法．详细分析最适球面的计算方法．并对一抛物面进行了实例计算，通过与最小二乘法的计算结果比较．指出该方法具有计算简单、与加工工艺过程相符合等特点。     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

A study on the applications of the acoustic design sensitivity analysis of vibrating bodies

The determination of the sensitivity of the acoustical characteristics of vibrating systems with respect to the variation of the design parameters predicting these characteristics is a necessary and important step of the acoustic design and optimization process. Acoustic design sensitivity analysis includes the computation and evaluation of the sensitivity information required for this procedure. In this study, a boundary element code performing the sensitivity analysis of the acoustic pressure by using the matrix sensitivities with respect to different design variables has been developed. The effect of the precision of boundary element discretization on the acoustic pressure sensitivity is examined via this code. The formulation is applied to a multi-source system and the dimension sensitivity analysis of near field pressures of two-dilating-spherical source is performed. The last application is devoted to a real sound source: a washing machine sitting on the floor. Sensitivity of the field pressures to the machine’s dimensions (size), surface velocity and frequency is examined on the bases of the boundary element model of the machine and half-space condition. The impacts of these variables are compared; and a limiting speed for the machine responding both the acoustical and operational requirements is determined.