Nearly Linear Time Algorithms for Permutation Groups: An Interplay Between Theory and Practice

We survey polynomial time algorithms (both deterministic and random) for computations with permutation groups. Particular emphasis is given to algorithms with running time of the form O(n log ^c |G|), where G is a permutation group of degree n. In the case of small-base groups, i.e., when log |G| is polylogarithmic as a function of n, such algorithms run in nearly linear, O(n log^c' n) time. Important classes of groups, including all permutation representations of simple groups except the alternating ones, as well as most primitive groups, belong to this category. For large n, the majority of practical computations is carried out on small-base groups.In the last section, we present some new nearly linear time algorithms, culminating in the computation of the upper central series in nilpotent groups.     

Nearly optimal distributed edge coloring in O(log log n) rounds

An extremely simple distributed randomized algorithm is presented which with high probability properly edge colors a given graph using (1 + ϵ)Δ colors, where Δ is the maximum degree of the graph and ϵ is any given positive constant. The algorithm is very fast. In particular, for graphs with sufficiently large vertex degrees (larger than polylog n, but smaller than any positive power of n), the algorithm requires only O(log log n) communication rounds. The algorithm is inherently distributed, but can be implemented on the PRAM, where it requires O(mΔ) processors and O(log Δ log log n) time, or in a sequential setting, where it requires O(mΔ) time. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 385–405 (1997)     

Computing Mixed Discriminants, Mixed Volumes, and Permanents

We construct a probabilistic polynomial time algorithm that computes the mixed discriminant of given n positive definite matrices within a 2 ^O(n) factor. As a corollary, we show that the permanent of an nonnegative matrix and the mixed volume of n ellipsoids in R ⁿ can be computed within a 2 ^O(n) factor by probabilistic polynomial time algorithms. Since every convex body can be approximated by an ellipsoid, the last algorithm can be used for approximating in polynomial time the mixed volume of n convex bodies in R ⁿ within a factor n ^O(n) . Received July 10, 1995, and in revised form May 20, 1996.     

一个求解半正定规划问题的新原始一对偶内点算法

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O（√n log n log n/c）和O（√n log n/ε）,这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。     

Proportional concentration phenomena on the sphere

In this paper we establish concentration phenomena for subspaces with arbitrary dimension. Namely, we display conditions under which the Haar measure on the sphere concentrates on a neighborhood of the intersection of the sphere with a subspace ofR ⁿ of a given dimension. We display applications to a problem of projections of points on the sphere, and to the duality of entropy numbers conjecture. Research was partially supported by the Israel Science Foundation.     

Method of analytic continuation for the inverse spherical mean transform in constant curvature spaces

The following problem arises in thermoacoustic tomography and has intimate connection with PDEs and integral geometry. Reconstruct a function f supported in an n-dimensional ball B given the spherical means of f over all geodesic spheres centered on the boundary of B. We propose a new approach to this problem, which yields explicit reconstruction formulas in arbitrary constant curvature space, including euclidean space ? ⁿ , the n-dimensional sphere, and hyperbolic space. The main idea is analytic continuation of the corresponding operator families. The results are applied to inverse problems for a large class of Euler-Poisson-Darboux equations in constant curvature spaces of arbitrary dimension.     

使用自正则度量的凸二次规划的原始对偶内点法的多项式复杂性

最近Peng等人使用新的搜索方向和自正则度量为求解线性规划问题提出了一个原始对偶内点法.本文将这个长步法延伸到凸二次规划.在线性规划情形时,原始空间和对偶空间中的尺度Newton方向是正交的,而在二次规划情形时这是不成立的.本文将处理这个问题并且证明多项式复杂性,并且得到复杂性的上界为O(n√log n log (n/ε)).     

Dimensionality Reductions in ℓ<Subscript>2</Subscript> that Preserve Volumes and Distance to Affine Spaces

Let X be a subset of n points of the Euclidean space, and let 0 < ε < 1. A classical result of Johnson and Lindenstrauss [JL] states that there is a projection of X onto a subspace of dimension O(ε^-2 log n) with distortion ≤ 1+ ε. We show a natural extension of the above result to a stronger preservation of the geometry of finite spaces. By a k-fold increase of the number of dimensions used compared with [JL], a good preservation of volumes and of distances between points and affine spaces is achieved. Specifically, we show how to embed a subset of size n of the Euclidean space into a O(ε^-2 log n)-dimensional Euclidean space, so that no set of size s ≤ k changes its volume by more than (1 + ε^s-1. Moreover, distances of points from affine hulls of sets of at most k - 1 points in the space do not change by more than a factor of 1 + ε. A consequence of the above with k = 3 is that angles can be preserved using asymptotically the same number of dimensions as the one used in [JL]. Our method can be applied to many problems with high-dimensional nature such as Projective Clustering and Approximated Nearest Affine Neighbour Search. In particular, it shows a first polylogarithmic query time approximation algorithm to the latter. We also show a structural application that for volume respecting embedding in the sense introduced by Feige [F], the host space need not generally be of dimensionality greater than polylogarithmic in the size of the graph.     

Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems

Due to their fundamental nature and numerous applications, sphere constrained polynomial optimization problems have received a lot of attention lately. In this paper, we consider three such problems: (i) maximizing a homogeneous polynomial over the sphere; (ii) maximizing a multilinear form over a Cartesian product of spheres; and (iii) maximizing a multiquadratic form over a Cartesian product of spheres. Since these problems are generally intractable, our focus is on designing polynomial-time approximation algorithms for them. By reducing the above problems to that of determining the L ₂-diameters of certain convex bodies, we show that they can all be approximated to within a factor of Ω((log n/n) ^d/2–1) deterministically, where n is the number of variables and d is the degree of the polynomial. This improves upon the currently best known approximation bound of Ω((1/n) ^d/2–1) in the literature. We believe that our approach will find further applications in the design of approximation algorithms for polynomial optimization problems with provable guarantees.     

The Discrepancy of Boxes in Higher Dimension

We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo> ^d can be as high as n ^Ω(1) in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2 ^Ω(d) . Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo> ^d . We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) . Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001.     

An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set

We describe a deterministic algorithm for computing the diameter of a finite set of points in R ³ , that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog ² n) . The diameter algorithm appears to be the last one in Clarkson and Shor's paper that up to now had no deterministic counterpart with a matching running time. Received May 10, 2000, and in revised form November 3, 2000. Online publication June 22, 2001.     

Polynomials with palindromic and unimodal coefficients

Let f(q) = ar qr+ ··· + as qs, with ar = 0 and as = 0, be a real polynomial. It is a palindromic polynomial of darga n if r + s = n and ar+i = as-i for all i. Polynomials of darga n form a linear subspace Pn(q) of R(q)n+1 of dimension n2 + 1. We give transition matrices between two bases qj(1 + q + ··· + qn-2j), qj(1 + q)n-2j and the standard basis qj(1 + qn-2j)of Pn(q).We present some characterizations and sufficient conditions for palindromic polynomials that can be expressed in terms of these two bases with nonnegative coefficients. We also point out the link between such polynomials and rank-generating functions of posets.     

Factorization of solvable polynomials over finite fields and the generalized Riemann hypothesis

This article presents an algorithm that, assuming the generalized Riemann hypothesis, factors a polynomial f mod p, where f Z[X] is solvable overQ, into irreducible (over the fieldF _pm) factors in time polynomial in m, log p, and the length of notation of f. The following problems are also solved in time polynomial in m, n, and log p: 1) construction of the fieldF _pm, 2) construction of all isomorphisms between two realizations ofF _p ^m, and 3) computation of the roots of degree n inF _{p m}.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Mathematicheskogo Instituta im. V. A. Steklova Akademii Nauk SSSR, Vol. 176, pp. 104–117, 1989.     

Evaluating polynomials over the unit disk and the unit ball

We investigate the use of orthonormal polynomials over the unit disk ??² in ?² and the unit ball ??³ in ?³. An efficient evaluation of an orthonormal polynomial basis is given, and it is used in evaluating general polynomials over ??² and ??³. The least squares approximation of a function f on the unit disk by polynomials of a given degree is investigated, including how to write a polynomial using the orthonormal basis. Matlab codes are given.     

A new trust region technique for the maximum weight clique problem

A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n³), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS.Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances.     

A quasi-wavelet algorithm for second kind boundary integral equations

In solving integral equations with a logarithmic kernel, we combine the Galerkin approximation with periodic quasi-wavelet (PQW) [4]. We develop an algorithm for solving the integral equations with only O(N log N) arithmetic operations, where N is the number of knots. We also prove that the Galerkin approximation has a polynomial rate of convergence.     

一类离散型奇异积分算子

设｛αｋ｝∞ｋ＝－∞为正数缺项序列，满足ｉｎｆｋαｋ＋１／ｄｋ＝α＞１，Ω（ｙ′）为Ｂｅｓｏｖ空间Ｂ０，１１（Ｓｎ－１）上的函数，其中Ｓｎ－１为Ｒｎ（ｎ２）上的单位球面．本文证明：若∫Ｓｎ－１Ω（ｙ′）ｄσ（ｙ′）＝０，则离散型奇异积分ＴΩ（ｆ）（ｘ）＝∑∞ｋ＝－∞∫Ｓｎ－１ｆ（ｘ－αｋｙ′）Ω（ｙ′）ｄσ（ｙ′）和相关的极大算子ＴΩ（ｆ）（ｘ）＝ｓｕｐＮ∑∞ｋ＝Ｎ∫Ｓｎ－１ｆ（ｘ－αｋｙ′）Ω（ｙ′）ｄσ（ｙ′）均在Ｌ２（Ｒｎ）上有界．上述结果推广了Ｄｕｏａｎｄｉｋｏｅｔｘｅａ和ＲｕｂｉｏｄｅＦｒａｎｃｉａ［１］在Ｌ２情形下的一个结果     

Exact packing dimension in random recursive constructions

We explore the exact packing dimension of certain random recursive constructions. In case of polynomial decay at 0 of the distribution function of random variable X, associated with the construction, we prove that it does not exist, and in case of exponential decay it is t|log|logt||, where is the fractal dimension of the limit set and 1/ is the rate of exponential decay.Research supported by the Department of Mathematics and Statistics (Mathematics) at University of Jyväskylä.Mathematics Subject Classification (2000):Primary 28A78, 28A80; Secondary 60D05, 60J80     

A sequential subspace projection method for extreme Z‐eigenvalues of supersymmetric tensors

Z‐eigenvalues of tensors, especially extreme ones, are quite useful and are related to many problems, such as automatic control, quantum physics, and independent component analysis. For supersymmetric tensors, calculating the smallest/largest Z‐eigenvalue is equivalent to solving a global minimization/maximization problem of a homogenous polynomial over the unit sphere. In this paper, we utilize the sequential subspace projection method (SSPM) to find extreme Z‐eigenvalues and the corresponding Z‐eigenvectors. The main idea of SSPM is to form a 2‐dimensional subspace at the current point and then solve the original optimization problem in the subspace. SSPM benefits from the fact that the 2‐dimensional subproblem can be solved by a direct method. Global convergence and linear convergence are established for supersymmetric tensors under certain assumptions. Preliminary numerical results over several testing problems show that SSPM is very promising. Besides, the globalization strategy of random phase can be easily incorporated into SSPM, which promotes the ability to find extreme Z‐eigenvalues. Copyright © 2014 John Wiley & Sons, Ltd.