Construction of superoptimal approximants

LetG be a matrix function of type m×n and suppose thatG is expressible as the sum of anH ^∞ function and a continuous function on the unit circle. Then it is known that there is a unique superoptimal approximant toG inH ^∞: that is, there is a unique analytic matrix functionQ in the open unit disc which minimizess ^∞(G?Q) or, in other words, which minimizes the sequence $$(s_0^\infty (G - Q),s_1^\infty (G - Q),s_2^\infty (G - Q), \ldots )$$ with respect to the lexicographic ordering, wheres _j ^∞ (F)=sup _x∈ s _j (F(z)) ands _j (·) denotes thejth singular value of a matrix. We give a function-theoretic (frequency domain) algorithm for the construction of this approximant. We calculate an example to illustrate the algorithm. The construction works for rationalG, but is also valid for non-rational functions. It is based on the authors' uniqueness proof in [PY1], but contains extra ingredients required to render it practicable, notably one which obviates the need for the preliminary solution of a Nehari problem. We also establish a formula forQ in terms of the maximizing vectors of a sequence of Hankel-type operators.     

Small deviations for two classes of Gaussian stationary processes and <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-functionals, 0 < <Emphasis Type="Italic">p</Emphasis> ≤ ∞

Let w(t) be a standard Wiener process, w(0) = 0, and let η _a (t) = w(t + a) − w(t), t ≥ 0, be increments of the Wiener process, a > 0. Let Z _a (t), t ∈ [0, 2a], be a zeromean Gaussian stationary a.s. continuous process with a covariance function of the form E Z _a (t)Z _a (s) = 1/2[a − |t − s|], t, s ∈ [0, 2a]. For 0 < p < ∞, we prove results on sharp asymptotics as ɛ → 0 of the probabilities

Simultaneous inner and outer approximation of shapes

For compact Euclidean bodiesP, Q, we define (P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy . HeresQ denotes a scaling ofQ by the factors, andQ,Q are some translates ofQ. This function gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.)For integerk 3, define (k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with (P, Q) (k). Among other results, we prove that 2.118 ... <-(3) 2.25 and (k) = 1 + (k ^–2). We give anO(n ² log² n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes (T, P) among triangles. However, in linear time we can find a trianglet with (t, P)<-2.25.Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.Work of all authors was partially supported by the ESPRIT II Basic Research Actions Program of the EC under Contract No. 3075 (project ALCOM). Rudolf Fleischer and Kurt Mehlhorn acknowledge also DFG (Grant SPP Me 620/6). Chee Yap acknowledges also DFG (Grant Be 142/46-1) and NSF (Grants DCR-84-01898 and CCR-87-03458). This research was performed when Günter Rote and Chee Yap were at the Freie Universität Berlin.     

H ∞ Optimal control

Our aim in this paper is to develop a new approach for solving the H ^∞ optimal control problem where the feedback arrangement takes the form of a linear fractional transformation. The paper is in two parts. In Part 1, a basic kind of model-matching problem is considered: given rational matrices M(s) and N(s), the H ^∞-norm of an error function defined as E(s)=M(s) – N(s)Q(s) is minimized (or bounded) subject to E(s) and Q(s) being stable. Closed-form state-space characterizations are obtained for both E(s) and Q(s). The results established here will be used in Part 2 of the paper (Hung 1989) to solve the H ^∞ optimal control problem.     

On a Stroboscopic Approach to Quantum Tomography of Qudits Governed by Gaussian Semigroups

In this paper, we discuss the minimal number of observables Q ₁, ..., Q , where expectation values at some time instants t ₁, ..., t _r determine the trajectory of a d-level quantum system (qudit) governed by the Gaussian semigroup . We assume that the macroscopic information about the system in question is given by the mean values E _j(Q _i) = tr(Q _i(t _j)) of n selfadjoint operators Q ₁, ..., Q _n at some time instants t ₁ < t ₂ < ... < t _r, where n < d ²– 1 and r deg (, ). Here (, ) stands for the minimal polynomial of the generator of the Gaussian flow (t).     

Feedback representations of critical controls for well-posed linear systems

This is the first part in a three part study of the suboptimal full information H^∞ problem for a well-posed linear system with input space U, state space H, and output space Y. We define a cost function Q(x₀,u)=∫〈y(s),Jy(s)〉_Yds, where y∈L²_loc( R ⁺; Y) is the output of the system with initial state x₀∈H and control u∈L²_loc( R ⁺; U), and J is a self-adjoint operator on Y. The cost function Qis quadratic in x₀ and u, and we suppose (in the stable case) that the second derivative of Q(x₀, u) with respect to u is non-singular. This implies that, for each x₀∈H, there is a unique critical control u^crit such that the derivative of Q(x₀, u) with respect to u vanishes at u=u^crit. We show that u^crit can be written in feedback form whenever the input/output map of the system has a coprime factorization with a (J, S)-inner numerator; here S is a particular self-adjoint operator on U. A number of properties of this feedback representation are established, such as the equivalence of the (J, S)-losslessness of the factorization and the positivity of the Riccati operator on the reachable subspace. © 1998 John Wiley & Sons, Ltd.     

Construction and enumeration of Boolean functions with maximum algebraic immunity

Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks, Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions with maximum algebraic immunity are constructed. Enumeration of such functions is also given. For a given function p(x) with deg(p(x)) < , we give a method to construct functions in the form p(x)+q(x) which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q(x) has degree no less than . Supported by the National Natural Science Foundation of China (Grant No. 60673068), and the Natural Science Foundation of Shandong Province (Grant Nos. Y2007G16, Y2008G01)     

Calcolo approssimato per difetto e per eccesso di integrali

Sommario Viene fornito un metodo in cui si fa uso di formule di quadratura generalizate per il calcolo approssimato per difetto e per eccesso dell'integrale ..u(x)dx doveu(x)∈AC ⁿ⁻¹ [0,1];u ⁽ⁿ⁾ (x) è limitata inferiormente;p(x)=1 oppurep(x)∈L [0, 1],p(x)>-0 e . Vengono poi dati alcuni esempi numerici.

---

A method, using generalized quadrature formulae, is given for approximate evaluation from below and above of whereu(x)∈A C ⁿ⁻¹ [0,1],u ⁽ⁿ⁾ (x) lower bounded,p(x)=1 orp(x)∈L [0,1],p(x)≥0, . Some numerical examples are given.

---

---

Lavoro eseguito nell'ambito del gruppo di ricerca G.N.A.F.A. del C.N.R.     

Risoluzione numerica di una disequazione variazionale

Riassunto Sia Ω un insieme aperto, connesso e limitato dello spazio euclideo reale adn dimensioni ℝ ⁿ . Sia ψ una funzione reale definita sulla chinsura di Ω e non positiva in prossimità della frontiera Γ di Ω. Presentiamo un metodo per la risoluzione numerica della disequazione variazionale dove ℝ={u∈H ₀ ¹ (Ω)|u≥ψ su ea(u, v) è una forma bilineare coercitiva sul sottospazioH ₀ ¹ (Ω) dello spazio reale di SobolevH ¹ (Ω).

---

Let Ω be an open, connected and bounded set of then-dimensional real Euclidean space ℝ ⁿ . Let ψ be a real function defined on the closure of Ω and non-positive near the boundary of Ω. We present a method for the numerical solution of the variational inequality where ℝ={u∈H ₀ ¹ (Ω)|u≥ψ on anda(u, v) is a bilinear form coercive on the subspaceH ₀ ¹ (Ω) of the real Sobolev spaceH ¹ (Ω).

     

Bent and hyper-bent functions over a field of 2ℓ elements

We study the parameters of bent and hyper-bent (HB) functions in n variables over a field $ P = \mathbb{F}_q We study the parameters of bent and hyper-bent (HB) functions in n variables over a field with q = 2^ℓ elements, ℓ > 1. Any such function is identified with a function F: Q → P, where . The latter has a reduced trace representation F = tr _P ^Q (Φ), where Φ(x) is a uniquely defined polynomial of a special type. It is shown that the most accurate generalization of results on parameters of bent functions from the case ℓ = 1 to the case ℓ > 1 is obtained if instead of the nonlinearity degree of a function one considers its binary nonlinearity index (in the case ℓ = 1 these parameters coincide). We construct a class of HB functions that generalize binary HB functions found in [1]; we indicate a set of parameters q and n for which there are no other HB functions. We introduce the notion of the period of a function and establish a relation between periods of (hyper-)bent functions and their frequency characteristics. Original Russian Text ? A.S. Kuz’min, V.T. Markov, A.A. Nechaev, V.A. Shishkin, A.B. Shishkov, 2008, published in Problemy Peredachi Informatsii, 2008, Vol. 44, No. 1, pp. 15–37. Supported in part by the Russian Foundation for Basic Research, project nos. 05-01-01018 and 05-01-01048, and the President of the Russian Federation Council for State Support of Leading Scientific Schools, project nos. NSh-8564.2006.10 and NSh-5666.2006.1. A part of the results were obtained in the course of research in the Cryptography Academy of the Russian Federation.     

Optimal Path Embedding in the Exchanged Crossed Cube

The (s + t + 1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s ≥ 3, t ≥ 3, for any two different vertices, all paths whose lengths are between \( \max \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2 ^s+t+1 ? 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +2 \). The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQ _n .     

The design of robust multi-loop-cascaded hydro governors

In the present paper, a new multi-loop-cascaded governor is proposed for hydro turbine controls. A turbine model is obtained that covers the effects of the water hammer, travelling waves, inelastic water penstocks and head loss due to the friction. Plant parameter uncertainties are taken into account to investigate stability robustness. The polynomial H robust control design method is used to design the multi-loop-cascaded governor. Water and load disturbance, and permanent oscillations in the power systems such as inter-area modes are included in the robust design procedure. Robust performance is achieved by using parameterised dynamic weighting functions of the design theory. The designed governor ensures that the overall system remains asymptotically stable for all norm-bounded uncertainties. Simulation results show that the system performance specifications and stability margins are improved significantly even in the presence of parameter uncertainties.Nomenclature - Polynomial notation is employed and the polynomials are assumed to be functions of the complex s variable. X^* denotes complex conjugate of the X. - a. S: complex frequency and is the frequency. - b. R₊: Set of all positive real numbers - c. R: Set of all real numbers - d. R(.): Set of all real rational functions - e. R[.]: Set of finite polynomials with real coefficients - f. R^mxm(.): Set of all real (mxm) matrices - g. R^mxm[.]: Set of polynomial (mxm) matrices.     

A parameter extraction technique for solving complex resonance problems using the transmission line matrix algorithm

An efficient and accurate parameter extraction technique is proposed for characterizing complex microwave resonance problems. The transmission line matrix algorithm is used to simulate resonator structures of different geometries in the frequency domain. A sequence of sinusoidally modulated impulses with exponentially damped amplitude is introduced to account for the influence of power dissipation due to ohmic and dielectric losses or loading effects, thereby extracting the Q-factor and resonant frequency without a Fourier transform. Theoretical results are compared with other solutions and experiments. © 1996 John Wiley & Sons, Inc.     

A measure of non-Gaussianity for quantum states

We propose a measure of non-Gaussianity for quantum states of a system of n oscillator modes. Our measure is based on the quasi-probability \({Q(\alpha),\alpha\in\mathcal{C}^n}\) . Since any measure of non-Gaussianity is necessarily an attempt at making a quantitative statement on the departure of the shape of the Q function from Gaussian, any good measure of non-Gaussianity should be invariant under transformations which do not alter the shape of the Q functions, namely displacements, passage through passive linear systems, and uniform scaling of all the phase space variables: Q(α) → λ²ⁿ Q(λα). Our measure which meets this ‘shape criterion’ is computed for a few families of states, and the results are contrasted with existing measures of non-Gaussianity. The shape criterion implies, in particular, that the non-Gaussianity of the photon-added thermal states should be independent of temperature.     

Communication Complexity Under Product and Nonproduct Distributions

We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R_∈(f) and $D^\mu_\in (f)$D^\mu_\in (f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu \{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence of a function f : {0, 1}ⁿ ×{0, 1}ⁿ ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which max_{μ product} {D^m _? (f)} = Q(1)  but R _? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously posed by the author (2007).     

High quality factor silicon cantilever driven by piezoelectric thin film actuator for resonant based mass detection

A high quality factor (Q-factor) piezoelectric lead zirconate titanate (PZT) thin film actuated single crystal silicon cantilever was proposed in this paper for resonant based ultra sensitive mass detection. Intrinsic energy dissipation and other negative effects from PZT-electrode stack were successfully compressed by separating the PZT actuator from the resonant structure. Excellent Q-factor, which is comparable to silicon cantilever (without actuator) and several times larger than that of latest reported other integrated cantilevers, was successfully obtained under both atmospheric pressure and reduced pressures. For a 30 μm-wide 100 μm-long cantilever, the Q-factor was measured as 1,113 and 7,279 under the pressure of 101.2 KPa and 35 Pa, respectively. Besides, it was found that greater Q-factor can be achieved at high vibration mode by the proposed structure. However, support loss became significant because of the increased actuator’s vibration amplitude which in turn leads to unexpected energy dissipation. Therefore, an optimized structure using node-point actuation was suggested and discussed in last section of this paper.     

Faster Approximate String Matching for Short Patterns

We study the classical approximate string matching problem, that is, given strings P and Q and an error threshold k, find all ending positions of substrings of Q whose edit distance to P is at most k. Let P and Q have lengths m and n, respectively. On a standard unit-cost word RAM with word size w≥log n we present an algorithm using time

Interpretations of open default theories in non-monotonic logics

It is shown that the translation of an open default into a modal formula x(L(x)LM ₁ (x)...LM _m (x)w(x)) gives rise to an embedding of open default systems into non-monotonic logics.     

Factorisation of finite state machines under strong and observational equivalences

The factorisation problem is to construct the specification of a submoduleX when the specifications of the system and all submodules butX are given. It is usually described by the equation where P and X are submodules of system Q, ¦ is a composition operator, and is the equivalence criterion. In this paper we use a finite state machine (FSM) model consistent with CCS and study two factorisation problems:P |||P Q andP |||P Q, where ||| is a derived CCS composition operator, and represent strong and observational equivalences. Algorithms are presented and proved correct to find the most general specification of submoduleX forP |||P Q withQ -deterministic and forP |||P Q withQ deterministic. Conditions on the submachines of the most general solutions that remain solutions toP |||P Q(P |||P Q) are given. This paper extends and is based on the work of M. W. Shields.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that