Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

Hitting and returning to rare events for all alpha-mixing processes

We prove that for any α-mixing stationary process the hitting time of any n-string A_n converges, when suitably normalized, to an exponential law. We identify the normalization constant λ(A_n). A similar statement holds also for the return time.To establish this result we prove two other results of independent interest. First, we show a relation between the rescaled hitting time and the rescaled return time, generalizing a theorem of Haydn, Lacroix and Vaienti. Second, we show that for positive entropy systems, the probability of observing any n-string in n consecutive observations goes to zero as n goes to infinity.     

Hitting time of large subsets of the hypercube

We study the simple random walk on the n‐dimensional hypercube, in particular its hitting times of large (possibly random) sets. We give simple conditions on these sets ensuring that the properly rescaled hitting time is asymptotically exponentially distributed, uniformly in the starting position of the walk. These conditions are then verified for percolation clouds with densities that are much smaller than (n log n)^‐1. A main motivation behind this article is the study of the so‐called aging phenomenon in the Random Energy Model, the simplest model of a mean‐field spin glass. Our results allow us to prove aging in the REM for all temperatures, thereby extending earlier results to their optimal temperature domain. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

String matching in quantum time

We show how to determine whether a given pattern p of length m occurs in a given text t of length n in time (where allows for logarithmic factors in m and n/m) with inverse polynomial failure probability. This algorithm combines quantum searching algorithms with a technique from parallel string matching, called Deterministic Sampling.     

First Hitting Time of Brownian Motion on Simple Graph with Skew Semiaxes

Consider a stochastic process that lives on n-semiaxes emanating from a common origin. On each semiaxis it behaves as a Brownian motion and at the origin it chooses a semiaxis randomly. In this paper we study the first hitting time of the process. We derive the Laplace transform of the first hitting time, and provide the explicit expressions for its density and distribution functions. Numerical examples are presented to illustrate the application of our results.

     

Hitting, returning and the short correlation function

We consider a stochastic process with the weakest mixing condition: the so called α. For any fixed n-string we prove the following results. (1) The hitting time has approximately exponential law. (2) The return time has approximately a convex combination between a Dirac measure at the origin and an exponential law. In both cases the parameter of the exponential law is λ(A)ℙ(A) where ℙ(A) is the measure of the string and λ(A) is a certain autocorrelation function of the string. We show also that the weight of the convex combination is approximately λ(A). We describe the behavior of this autocorrelation function. Our results hold when the rate of mixing decays polinomially fast with power larger than the golden number.     

On RSA Moduli with Prescribed Bit Patterns

We give a polynomial time probabilistic algorithm that constructs an RSA modulus M=pl, where p and l are two n-bit primes, which has about n/2 bits, on certain positions, prescribed in advance. Although the number of prescribed bits is less than in other constructions, this algorithm can be rigorously analyzed while the other approaches remain heuristic. The proof is based on bounds of exponential sums. We also show that this algorithm can be used for finding 2n-bit RSA moduli whose binary expansions are of Hamming weight about 3n/4. Finally, similar arguments are also applied to smooth integers.     

Exponential sums on An. III

We give two applications of our earlier work [4]. We compute the p-adic cohomology of certain exponential sums on A ⁿ involving a polynomial whose homogeneous component of highest degree defines a projective hypersurface with at worst weighted homogeneous isolated singularities. This study was motivated by recent work of García [9]. We also compute the p-adic cohomology of certain exponential sums on A ⁿ whose degree is divisible by the characteristic. Received: 12 October 1999     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

On discrete time ergodic filters with wrong initial data

For a class of non-uniformly ergodic Markov chains (X _n ) satisfying exponential or polynomial beta-mixing, under observations (Y _n ) subject to an IID noise with a positive density, it is shown that wrong initial data is forgotten in the mean total variation topology, with a certain exponential or polynomial rate.     

A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

A note on the strong polynomiality of convex quadratic programming

We prove that a general convex quadratic program (QP) can be reduced to the problem of finding the nearest point on a simplicial cone inO(n ³ +n logL) steps, wheren andL are, respectively, the dimension and the encoding length of QP. The proof is quite simple and uses duality and repeated perturbation. The implication, however, is nontrivial since the problem of finding the nearest point on a simplicial cone has been considered a simpler problem to solve in the practical sense due to its special structure. Also we show that, theoretically, this reduction implies that (i) if an algorithm solves QP in a polynomial number of elementary arithmetic operations that is independent of the encoding length of data in the objective function then it can be used to solve QP in strongly polynomial time, and (ii) ifL is bounded by a first order exponential function ofn then (i) can be stated even in stronger terms: to solve QP in strongly polynomial time, it suffices to find an algorithm running in polynomial time that is independent of the encoding length of the quadratic term matrix or constraint matrix. Finally, based on these results, we propose a conjecture.corresponding author. The research was done when the author was at the Department of IE & OR, University of California at Berkeley, and partially supported by ONR grant N00014-91-j-1241.     

Discrete real time flows with quasi-discrete spectra and algebras generated by expq(t)

These notes (essentially unedited) were sent to W. Parry in 1964. The first two parts are complete and in a letter to Parry at that time Hahn indicated his intention to publish them. Evidently he did not manage to do this. The remainder of these notes represents an attempt to establish a theory of quasidiscrete spectra for discrete one-parameter flows. Hahn indicates the gaps and in a following note Parry clarifies his theory. The first part of these notes presents a characteristic example of a discrete one-parameter flow with quasidiscrete spectrum. Ergodicity, minimality and distality are established. The second part examines the Banach algebra of functions onR generated by {expq(t): q a real polynomial of degree <n+1} and shows that the shift isometries arise from a discrete one-parameter flow on its maximal ideal space Λ _n and that ifn is finite this flow is isomorphic to the example examined in the first part. Deceased     

Automorphism groups of some algebras

The automorphism groups of algebras are found in many papers. Using auto-invariance, we find the automorphism groups of the Laurent extension of the polynomial ring and the quantum n-plane (respectively, twisting polynomial ring) in this work. As an application of the results of this work, we can find the automorphism group of a twisting algebra. We define a generalized Weyl algebra and show that the generalized Weyl algebra is simple. We also find the automorphism group of a generalized Weyl algebra. We show that the generalized Weyl algebra A _m,m+n is the universal enveloping algebra of the generalized Witt algebra W(m,m + n). This work was supported by 2007 Research fund of Hanyang University     

A geometric inequality and the complexity of computing volume

The volume of the convex hull of anym points of ann-dimensional ball with volumeV is at mostV·m/2 ⁿ . This implies that no polynomial time algorithm can compute the volume of a convex set (given by an oracle) with less than exponential relative error. A lower bound on the complexity of computing width can also be deduced.Dedicated to my teacher Kõváry Károly     

Quantum lower bounds by entropy numbers

We use entropy numbers in combination with the polynomial method to derive a new general lower bound for the nth minimal error in the quantum setting of information-based complexity. As an application, we improve some lower bounds on quantum approximation of embeddings between finite dimensional L_p spaces and of Sobolev embeddings.     

Hitting Time Distributions for Denumerable Birth and Death Processes

For an ergodic continuous-time birth and death process on the nonnegative integers, a well-known theorem states that the hitting time T _0,n starting from state 0 to state n has the same distribution as the sum of n independent exponential random variables. Firstly, we generalize this theorem to an absorbing birth and death process (say, with state ?1 absorbing) to derive the distribution of T _0,n . We then give explicit formulas for Laplace transforms of hitting times between any two states for an ergodic or absorbing birth and death process. Secondly, these results are all extended to birth and death processes on the nonnegative integers with ?? an exit, entrance, or regular boundary. Finally, we apply these formulas to fastest strong stationary times for strongly ergodic birth and death processes.     

On polynomial approximation in the uniform norm by the discrete least squares method

The discrete least squares method is convenient for computing polynomial approximations to functions. We investigate the possibility of using this method to obtain polynomial approximants good in the uniform norm, and find that for a given set ofm nodes, the degreen of the approximating polynomial should be selected so that there is a subset ofn+1 nodes which are close ton+1 Fejér points for the curve. Numerical examples are presented.Sponsored by the United States Army under Contract No. DAAG29-80-C-0041.     

Complete matchings in random subgraphs of the cube

In this article it is shown that for almost every random cube process the hitting time of a complete matching equals the hitting time of having minimal degree (at least) one and also the hitting time of connectedness. It follows from this that if t = (n + c + o(1))2^n?2 for some constant c, then the probability that a random subgraph of the n-cube having precisely t edges has a complete matching tends to e.     

Piecewise optimal distributed Controls for 2D Boussinesq equations

In this article, we study the dynamics of a piecewise (in time) distributed optimal control problem for the Boussinesq equations which model velocity tracking over time coupled to thermal dynamics. We also study the dynamics of semidiscrete approximation of this problem. We prove that the rates of velocity tracking coupled to thermal dynamics are exponential and that the difference between the solution of the semi‐discrete piecewise optimal control problem and the desired states in L² and H¹ norms decay to zero exponentially as n→∞. Copyright © 2000 John Wiley & Sons, Ltd.