Polynomial Decompositions in Polynomial Time

Fix a prime p. Given a positive integer k, a vector of positive integers Delta = (Delta(1), Delta(2), ... , Delta(k)) and a function Gamma : F-p(k) -> F-p, we say that a function P : F-p(n) -> F-p is (k, Delta, Gamma)-structured if there exist polynomials P-1, P-2, ..., P-k : F-p(n) -> F-p with each deg(P-i) <= Delta(i) such that for all x is an element of F-p(n), P(x) = Gamma(P-1(x), P-2(x), ..., P-k(x)). For instance, an n-variate polynomial over the field Fp of total degree d factors nontrivially exactly when it is (2, (d - 1, d - 1), prod)- structured where prod(a, b) = a . b. We show that if p > d, then for any fixed k, Delta, Gamma, we can decide whether a given polynomial P(x(1), x(2), ..., x(n)) of degree d is (k, Delta, Gamma)-structured and if so, find a witnessing decomposition. The algorithm takes poly(n) time. Our approach is based on higher-order Fourier analysis.

Small signal Nonquasi-Static Model for Common Double-Gate MOSFETs Adapted to Gate Oxide Thickness Asymmetry

We present a physics-based closed form small signal Nonquasi-static (NQS) model for a long channel Common Double Gate MOSFET (CDG) by taking into account the asymmetry that may prevail between the gate oxide thickness. We use the unique quasi-linear relationship between the surface potentials along the channel to solve the governing continuity equation (CE) in order to develop the analytical expressions for the Y parameters. The Bessel function based solution of the CE is simplified in form of polynomials so that it could be easily implemented in any circuit simulator. The model shows good agreement with the TCAD simulation at-least till 4 times of the cut-off frequency for different device geometries and bias conditions.

B-Spline potential function for maximum a-posteriori image reconstruction in fluorescence microscopy

An iterative image reconstruction technique employing B-Spline potential function in a Bayesian framework is proposed for fluorescence microscopy images. B-splines are piecewise polynomials with smooth transition, compact support and are the shortest polynomial splines. Incorporation of the B-spline potential function in the maximum-a-posteriori reconstruction technique resulted in improved contrast, enhanced resolution and substantial background reduction. The proposed technique is validated on simulated data as well as on the images acquired from fluorescence microscopes (widefield, confocal laser scanning fluorescence and super-resolution 4Pi microscopy). A comparative study of the proposed technique with the state-of-art maximum likelihood (ML) and maximum-a-posteriori (MAP) with quadratic potential function shows its superiority over the others. B-Spline MAP technique can find applications in several imaging modalities of fluorescence microscopy like selective plane illumination microscopy, localization microscopy and STED. (C) 2015 Author(s).

Mixed norm estimates for the Riesz transforms on the Heisenberg group

In this paper we prove weighted mixed norm estimates for Riesz transforms on the Heisenberg group and Riesz transforms associated to the special Hermite operator. From these results vector-valued inequalities for sequences of Riesz transforms associated to generalised Grushin operators and Laguerre operators are deduced.

Similarity of Matrices Over Local Rings of Length Two

Let R be a (commutative) local principal ideal ring of length two, for example, the ring R = Z/p(2)Z with p prime. In this paper, we develop a theory of normal forms for similarity classes in the matrix rings M-n (R) by interpreting them in terms of extensions of R t]-modules. Using this theory, we describe the similarity classes in M-n (R) for n <= 4, along with their centralizers. Among these, we characterize those classes which are similar to their transposes. Non-self-transpose classes are shown to exist for all n > 3. When R has finite residue field of order q, we enumerate the similarity classes and the cardinalities of their centralizers as polynomials in q. Surprisingly, the polynomials representing the number of similarity classes in M-n (R) turn out to have non-negative integer coefficients.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.

Spectral solutions to the Korteweg-de-Vries and nonlinear Schrodinger equations

In this paper, we present the solutions of 1-D and 2-D non-linear partial differential equations with initial conditions. We approach the solutions in time domain using two methods. We first solve the equations using Fourier spectral approximation in the spatial domain and secondly we compare the results with the approximation in the spatial domain using orthogonal functions such as Legendre or Chebyshev polynomials as their basis functions. The advantages and the applicability of the two different methods for different types of problems are brought out by considering 1-D and 2-D nonlinear partial differential equations namely the Korteweg-de-Vries and nonlinear Schrodinger equation with different potential function. (C) 2015 Elsevier Ltd. All rights reserved.

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

We show here a 2(Omega(root d.log N)) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d(3) in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Sigma(i) Pi(j) Q(ij), where the Q(ij)'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that Sigma(i,j) (Number of monomials of Q(ij)) >= 2(Omega(root d.log N)). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on the recent lower bound results 1], 2], 3], 4], 5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of 6] and the N-Omega(log log (N)) lower bound in the independent work of 7].

Counting zero kernel pairs over a finite field

Helmke et al. have recently given a formula for the number of reachable pairs of matrices over a finite field. We give a new and elementary proof of the same formula by solving the equivalent problem of determining the number of so called zero kernel pairs over a finite field. We show that the problem is, equivalent to certain other enumeration problems and outline a connection with some recent results of Guo and Yang on the natural density of rectangular unimodular matrices over F-qx]. We also propose a new conjecture on the density of unimodular matrix polynomials. (C) 2016 Elsevier Inc. All rights reserved.

FAST AND ACCURATE BILATERAL FILTERING USING GAUSS-POLYNOMIAL DECOMPOSITION

The bilateral filter is a versatile non-linear filter that has found diverse applications in image processing, computer vision, computer graphics, and computational photography. A common form of the filter is the Gaussian bilateral filter in which both the spatial and range kernels are Gaussian. A direct implementation of this filter requires O(sigma(2)) operations per pixel, where sigma is the standard deviation of the spatial Gaussian. In this paper, we propose an accurate approximation algorithm that can cut down the computational complexity to O(1) per pixel for any arbitrary sigma (constant-time implementation). This is based on the observation that the range kernel operates via the translations of a fixed Gaussian over the range space, and that these translated Gaussians can be accurately approximated using the so-called Gauss-polynomials. The overall algorithm emerging from this approximation involves a series of spatial Gaussian filtering, which can be efficiently implemented (in parallel) using separability and recursion. We present some preliminary results to demonstrate that the proposed algorithm compares favorably with some of the existing fast algorithms in terms of speed and accuracy.

Interactions of Penny-Shaped Cracks in Three-Dimensional Solids

The interaction of arbitrarily distributed penny-shaped cracks in three-dimensional solids is analyzed in this paper. Using oblate spheroidal coordinates and displacement functions, an analytic method is developed in which the opening and the sliding displacements on each crack surface are taken as the basic unknown functions. The basic unknown functions can be expanded in series of Legendre polynomials with unknown coefficients. Based on superposition technique, a set of governing equations for the unknown coefficients are formulated from the traction free conditions on each crack surface. The boundary collocation procedure and the average method for crack-surface tractions are used for solving the governing equations. The solution can be obtained for quite closely located cracks. Numerical examples are given for several crack problems. By comparing the present results with other existing results, one can conclude that the present method provides a direct and efficient approach to deal with three-dimensional solids containing multiple cracks.

Static Study of Cantilever Beam stiction under Electrostatic Force Influence

The model and analysis of the cantilever beam adhesion problem under the action of electrostatic force are given. Owing to the nonlinearity of electrostatic force, the analytical solution for this kind of problem is not available. In this paper, a systematic method of generating polynomials which are the exact beamsolutions of the loads with different distributions is provided. The polynomials are used to approximate the beam displacement due to electrostatic force. The equilibrium equation offers an answer to how the beam deforms but no information about the unstuck length. The derivative of the functional with respect to the unstuck length offers such information. But to compute the functional it is necessary to know the beam deformation. So the problem is iteratively solved until the results are converged. Galerkin and Newton-Raphson methods are used to solve this nonlinear problem. The effects of dielectric layer thickness and electrostatic voltage on the cantilever beamstiction are studied.The method provided in this paper exhibits good convergence. For the adhesion problem of cantilever beam without electrostatic voltage, the analytical solution is available and is also exactly matched by the computational results given by the method presented in this paper.

迟滞系统随机响应问题基于函数级数的解法

本文提出了一个三次多项式的迟滞模型,并用Wiener-Hermite函数级数展开的方法求解,得到了不同阻尼及不同的非线性强度时系统响应的均方值σ(t)。不仅从理论上而且通过实验证实了用这种方法求解迟滞系统的响应是行之有效的、简便的。

Bending solution of high-order refined shear deformation-theory for rectangular composite plates

A new high-order refined shear deformation theory based on Reissner's mixed variational principle in conjunction with the state- space concept is used to determine the deflections and stresses for rectangular cross-ply composite plates. A zig-zag shaped function and Legendre polynomials are introduced to approximate the in-plane displacement distributions across the plate thickness. Numerical results are presented with different edge conditions, aspect ratios, lamination schemes and loadings. A comparison with the exact solutions obtained by Pagano and the results by Khdeir indicates that the present theory accurately estimates the in-plane responses.

Randomness-efficient curve sampling

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the sampled curve is still low-degree. This property is often used in combination with the sampling property and has found many applications, including PCP constructions, local decoding of codes, and algebraic PRG constructions.

The randomness complexity of curve samplers is a crucial parameter for its applications. It is known that (non-explicit) curve samplers using O(log N + log(1/δ)) random bits exist, where N is the domain size and δ is the confidence error. The question of explicitly constructing randomness-efficient curve samplers was first raised in [TU06] where they obtained curve samplers with near-optimal randomness complexity.

In this thesis, we present an explicit construction of low-degree curve samplers with optimal randomness complexity (up to a constant factor) that sample curves of degree (m log_q(1/δ))^O(1) in F_q^m. Our construction is a delicate combination of several components, including extractor machinery, limited independence, iterated sampling, and list-recoverable codes.