On representations and <Emphasis Type="Italic">K</Emphasis>-theory of the braid groups

 Let Γ be the fundamental group of the complement of a K(Γ, 1) hyperplane arrangement (such as Artin's pure braid group) or more generally a homologically toroidal group as defined below. The triviality of bundles arising from orthogonal representations of Γ is characterized completely as follows. An orthogonal representation gives rise to a trivial bundle if and only if the representation factors through the spinor groups. Furthermore, the subgroup of elements in the complex K-theory of BΓ which arises from complex unitary representations of Γ is shown to be trivial. In the case of real K-theory, the subgroup of elements which arises from real orthogonal representations of Γ is an elementary abelian 2-group, which is characterized completely in terms of the first two Stiefel-Whitney classes of the representation. In addition, quadratic relations in the cohomology algebra of the pure braid groups which correspond precisely to the Jacobi identity for certain choices of Poisson algebras are shown to give the existence of certain homomorphisms from the pure braid group to generalized Heisenberg groups. These cohomology relations correspond to non-trivial Spin representations of the pure braid groups which give rise to trivial bundles. Received: 6 February 2002 / Revised version: 19 September 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" Partially supported by the NSF RID="⋆⋆" ID="⋆⋆" Partially supported by grant LEQSF(1999-02)-RD-A-01 from the Louisiana Board of Regents, and by grant MDA904-00-1-0038 from the National Security Agency RID="⋆" ID="⋆" Partially supported by the NSF Mathematics Subject Classification (2000): 20F36, 32S22, 55N15, 55R50     

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.     

Extension of primal-dual interior point algorithms to symmetric cones

 In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions. Received: April 2000 / Accepted: May 2002 Published online: March 28, 2003 RID="⋆" ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational Optimization at Columbia University. RID="⋆⋆" ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research contract number N00014-96-1-0704.     

A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

A Bernstein type theorem on a Randers space

We consider Finsler spaces with a Randers metric F=+, on the three-dimensional real vector space, where is the Euclidean metric and is a 1-form with norm b,0 b1. By using the notion of mean curvature for immersions in Finsler spaces, introduced by Z. Shen, we obtain the partial differential equation that characterizes the minimal surfaces which are graphs of functions. For each b, 0 b1/, we prove that it is an elliptic equation of mean curvature type. Then the Bernstein type theorem and other properties, such as the nonexistence of isolated singularities, of the solutions of this equation follow from the theory developped by L. Simon. For b 1/, the differential equation is not elliptic. Moreover, for every b, 1/b1 we provide solutions, which describe minimal cones, with an isolated singularity at the origin.Partially supported by CAPES/PROCAD.Partially supported by NSF grant DMS-0072242.Partially supported by CNPq and CAPES/PROCAD.     

Seshadri-exceptional foliations

 The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L ⁿ , n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ³ and ample line bundles on smooth threefolds of Picard number 1. Received: 29 June 2001 / Published online: 16 October 2002 RID="⋆" ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF. RID="⋆⋆" ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF.     

A direct impedance tomography algorithm for locating small inhomogeneities

Summary.  Impedance tomography seeks to recover the electrical conductivity distribution inside a body from measurements of current flows and voltages on its surface. In its most general form impedance tomography is quite ill-posed, but when additional a-priori information is admitted the situation changes dramatically. In this paper we consider the case where the goal is to find a number of small objects (inhomogeneities) inside an otherwise known conductor. Taking advantage of the smallness of the inhomogeneities, we can use asymptotic analysis to design a direct (i.e., non-iterative) reconstruction algorithm for the determination of their locations. The viability of this direct approach is documented by numerical examples. Received May 28, 2001 / Revised version received March 15, 2002 / Published online July 18, 2002 RID="⋆" ID="⋆" Supported by the Deutsche Forschungsgemeinschaft (DFG) under grant HA 2121/2-3 RID="⋆⋆" ID="⋆⋆" Supported by the National Science Foundation under grant DMS-0072556 Mathematics Subject Classification (2000): 65N21, 35R30, 35C20     

Degree complexity for a modified pigeonhole principle

 We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole (according to some rules). Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω(log n). We also prove a simple Lemma giving a simulation of Resolution by Polynomial Calculus. Using this lemma, and a Resolution upper bound by Goerdt [7], we obtain that the degree lower bound is tight. Our lower bound establishes the optimality of the tree-like Resolution simulation by the Polynomial Calculus given in [6]. Received: 29 March 2001 / Published online: 2 September 2002 RID="⋆" ID="⋆" A prelimianry version appeared as part of the paper A Study of Proof Search Algorithms for Resolution and Polynomial Calculus published in the Proceedings of the 40-th IEEE Conference on Foundations of Computer Science, 1999 RID="†" ID="†" Partly supported by Project CICYT, TIC 98-0410-C02-01 and Promoción General del Conocimiento PB98-0937-C04-03. RID="††" ID="††" Part of this work was done while the author was a member of the School of Mathematics at Institute for Advanced Study supported by a NSF grant n. 9987845     

Unique continuation for the linearized Benjamin-Bona-Mahony equation with space-dependent potential

 In this paper, we analyze a unique continuation problem for the linearized Benjamin-Bona-Mahony equation with space-dependent potential in a bounded interval with Dirichlet boundary conditions. The underlying Cauchy problem is a characteristic one. We prove two unique continuation results by means of spectral analysis and the (generalized) eigenvector expansion of the solution, instead of the usual Holmgren-type method or Carleman-type estimates. It is found that the unique continuation property depends very strongly on the nature of the potential and, in particular, on its zero set, and not only on its boundedness or integrability properties. Received: 6 December 2001 / Revised version: 13 June 2002 / Published online: 10 February 2003 RID="⋆" ID="⋆" Supported by a Postdoctoral Fellowship of the Spanish Education and Culture Ministry, the Foundation for the Author of National Excellent Doctoral Dissertation of P.R. China (Project No: 200119), and the NSF of China under Grant 19901024 RID="⋆⋆" ID="⋆⋆" Supported by grant PB96-0663 of the DGES (Spain) and the EU TMR Project "Homogenization and Multiple Scales". Mathematics Subject Classification (2000): 35B60, 47A70, 47B07     

Commutators of integral operators with variable kernels on Hardy spaces

LetT _Ω,α (0 ≤ α< n) be the singular and fractional integrals with variable kernel Ω(x, z), and [b, T_Ω,α] be the commutator generated by T_Ω,α and a Lipschitz functionb. In this paper, the authors study the boundedness of [b, T_Ω,α] on the Hardy spaces, under some assumptions such as theL ^r -Dini condition. Similar results and the weak type estimates at the end-point cases are also given for the homogeneous convolution operators . The smoothness conditions imposed on are weaker than the corresponding known results.     

Propagation of polarization in elastodynamics with residual stress and travel times

 We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map. Received: 6 December 2001 / Revised version: 29 October 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit in fall 2000. RID="⋆⋆" ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for partial support and for providing a very stimulating environment during the inverse problems program in fall 2001.     

Asymptotic separation for independent trajectories of Markov processes

We say that n independent trajectories ξ₁(t),…,ξ _n (t) of a stochastic process ξ(t)on a metric space are asymptotically separated if, for some ɛ > 0, the distance between ξ _i (t _i ) and ξ _j (t _j ) is at least ɛ, for some indices i, j and for all large enough t ₁,…,t _n , with probability 1. We prove sufficient conitions for asymptotic separationin terms of the Green function and the transition function, for a wide class of Markov processes. In particular,if ξ is the diffusion on a Riemannian manifold generated by the Laplace operator Δ, and the heat kernel p(t, x, y) satisfies the inequality p(t, x, x) ≤ Ct ^−ν/2 then n trajectories of ξ are asymptotically separated provided . Moreover, if for some α∈(0, 2)then n trajectories of ξ^(α) are asymptotically separated, where ξ^(α) is the α-process generated by −(−Δ)^α/2. Received: 10 June 1999 / Revised version: 20 April 2000 / Published online: 14 December 2000 RID="*" ID="*" Supported by the EPSRC Research Fellowship B/94/AF/1782 RID="**" ID="**" Partially supported by the EPSRC Visiting Fellowship GR/M61573     

Boundedness of commutators related to Marcinkiewicz integrals on hardy type spaces

In this paper, the authors study the boundedness of the operator [μΩ, b], the commutator generated by a function b ∈ Lipβ(Rn)(0 ＜β≤ 1) and the Marcinkiewicz integrals μΩ, on the classical Hardy spaces and the Herz-type Hardy spaces in the case Ω∈ Lipα(Sn-1)(0 ＜α≤ 1).     

On the Expected Condition Number of Linear Programming Problems

Summary.   Let A be an n×m real matrix and consider the linear conic system

Optimization for products of concave functions

Ifh denotes the product of finitely many concave non-negative functions on a compact interval [a, b], then it is shown that there exist pointsα andβ witha≤α≤β≤b such thath is strictly increasing on [α, α), constant on (α, β), and strictly decreasing on (β, b]. This structure theorem leads to an extension of several classical optimization results for concave functions on convex sets to the case of products of concave functions.     

Vertex Covers by Edge Disjoint Cliques

Dedicated to the memory of Paul Erdős Let H be a simple graph having no isolated vertices. An (H,k)-vertex-cover of a simple graph G = (V,E) is a collection of subgraphs of G satisfying 1.  , for all i = 1, ..., r, 2.  , 3.  , for all , and 4.  each is in at most k of the . We consider the existence of such vertex covers when H is a complete graph, , in the context of extremal and random graphs. Received October 31, 1999 RID="*" ID="*" Supported in part by NSF grant DMS-9627408. RID="†" ID="†" Supported in part by NSF grant CCR-9530974. RID="‡" ID="‡" Supported in part by OTKA Grants T 030059 and T 29074, FKFP 0607/1999 and by the Bolyai Foundation. RID="§" ID="§" Supported in part by NSF grant DMS-9970622.     

On （α,β）-Metrics of Scalar Flag Curvature with Constant S-curvature

In this paper, we study （α,β）-metrics of scalar flag curvature on a manifold M of dimension n （n 〉 3）. Suppose that an （α,β）-metric F is not a Finsler metric of Randers type, that is, F ≠k1 V√α^2 ＋ k2β^2 ＋ k3β, where k1 〉 0, k2 and k3 are scalar functions on M. We prove that F is of scalar flag curvature and of vanishing S-curvature if metric. In this case, F is a locally Minkowski and only if the flag curvature K = 0 and F is a Berwald metric.     

Some remarks on the universal cover of an open K3 surface

 We shall give, in an optimal form, a sufficient numerical condition for the finiteness of the fundamental group of the smooth locus of a normal K3 surface. We shall moreover prove that, if the normal K3 surface is elliptic and the above fundamental group is not finite, then there is a finite covering which is a complex torus. Received: 13 April 2001 / Published online: 16 October 2002 RID="⋆" ID="⋆" Supported by Korea Research Foundation Grant(KRF-2001-041-D00025) Mathematics Subject Classification (2000): 14J28     

Homogenization of two-phase metrics and applications

We consider two-phase metrics of the form ϕ(x, ξ) ≔ , where α,β are fixed positive constants and B _α, B _β are disjoint Borel sets whose union is ℝ^N, and prove that they are dense in the class of symmetric Finsler metrics ϕ satisfying