Universal deformation rings need not be complete intersections

We answer a question of M. Flach by showing that there is a linear representation of a profinite group whose (unrestricted) universal deformation ring is not a complete intersection. We show that such examples arise in arithmetic in the following way. There are infinitely many real quadratic fields F for which there is a mod 2 representation of the Galois group of the maximal unramified extension of F whose universal deformation ring is not a complete intersection. Finally, we discuss bounds on the singularities of universal deformation rings of representations of finite groups in terms of the nilpotency of the associated defect groups. The first author was supported in part by NSF Grant DMS01-39737 and NSA Grant H98230-06-1-0021. The second author was supported in part by NSF Grants DMS00-70433 and DMS05-00106.     

Holey self-orthogonal Latin squares with symmetric orthogonal mates

We improve the existence results for holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) and show that the necessary conditions for the existence of a HSOLSSOM of typeh ⁿ are also sufficient with at most 28 pairs (h, n) of possible exceptions. Research supported in part by NSERC Grant A-5320 for the first author, NSF Grants CCR-9504205 and CCR-9357851 for the second author, and NSFC Grant 19231060-2 for the third author.     

Consistent parameter estimation for partially observed diffusions with small noise

In this paper we provide a consistency result for the MLE for partially observed diffusion processes with small noise intensities. We prove that if the underlying deterministic system enjoys an identifiability property, then any MLE is close to the true parameter if the noise intensities are small enough. The proof uses large deviations limits obtained by PDE vanishing viscosity methods. A deterministic method of parameter estimation is formulated. We also specialize our results to a binary detection problem, and compare deterministic and stochastic notions of identifiability.This research was supported: by Systems Research Center, University of Maryland through NSF Grant CDR-85-00108 and AFOSR-URI Grant 87-0073; by Lefschetz Center for Dynamical Systems, Division of Applied Mathematics, Brown University, under ARO/MIT Grant DAAL-03-86-K-0171; by INRIA Sophia Antipolis, under ERO/INRIA Grant DAJA45-90-C-0008, and by the CNRS-GRAutomatique.     

Consistency of infinitesimal perturbation analysis estimators with rates

We study a class of infinitesimal perturbation analysis (IPA) algorithms for queueing systems with load-dependent service and/or arrival rates. Such IPA algorithms were originally motivated by applications to large queueing systems in conjunction with aggregation algorithms. We prove strong consistency of these estimators through a type of birth and death queue. This work was supported in part by the NSF under Grants Nos. ECS85-15449 and CDR-8803012, by ONR under Contracts Nos. N00014-89-J-0075 and N00014-90-K-1093, and by the US Army under Contract No. DAAL-03-83-K-0171. This paper was written while the author was with the Division of Applied Sciences at Harvard University.     

An L-like model containing very large cardinals

We force and construct a model in which level by level equivalence between strong compactness and supercompactness holds, along with a strong form of diamond and a version of square consistent with supercompactness. This generalises a result due to the first author. There are no restrictions in our model on the structure of the class of supercompact cardinals. A. W. Apter’s research was partially supported by PSC-CUNY Grants and CUNY Collaborative Incentive Grants. J. Cummings’s research was partially supported by NSF Grant DMS-0400982.     

State constraints in the linear regulator problem: Case study

In this paper, we consider the problem of minimum-norm control of the double integrator with bilateral inequality constraints for the output. We approximate the constraints by piecewise linear functions and prove that the Langrange multipliers associated with the state constraints of the approximating problem are discrete measures, concentrated in at most two points in every interval of discretization. This allows us to reduce the problem to a convex finite-dimensional optimization problem. An algorithm based on this reduction is proposed and its convergence is examined. Numerical examples illustrate our approach. We also discuss regularity properties of the optimal control for a higher-dimensional state-constrained linear regulator problem.The first author was supported by the National Science Foundation, Grant No. DMS-9404431. The second author was supported by a François-Xavier Bagnoud Doctoral Fellowship and by NSF Grants DMS-9404431 and MSS-9114630.     

Effective bandwidths for Markov regenerative sources

In this paper we consider the multiplexing of independent stochastic fluid sources onto a single buffer. The rate at which a source generates fluid is assumed to be modulated by a Markov regenerative process. We develop the exponential decay rates for the tails of the steady-state distribution of the buffer content. We also develop expressions for the effective bandwidths for such sources. All the results are in terms of the Perron-Frobenius eigenvalue of a matrix defined for the Markov regenerative source. As a special case we derive similar results for regenerative sources. We apply the results to video sources.This research was partially supported by NSF Grant No. NCR-9406823.     

Measurement scheduling for recursive team estimation

We consider a decentralized LQG measurement scheduling problem in which every measurement is costly, no communication between observers is permitted, and the observers' estimation errors are coupled quadratically. This setup, motivated by considerations from organization theory, models measurement scheduling problems in which cost, bandwidth, or security constraints necessitate that estimates be decentralized, although their errors are coupled. We show that, unlike the centralized case, in the decentralized case the problem of optimizing the time integral of the measurement cost and the quadratic estimation error is fundamentally stochastic, and we characterize the -optimal open-loop schedules as chattering solutions of a deterministic Lagrange optimal control problem. Using a numerical example, we describe also how this deterministic optimal control problem can be solved by nonlinear programming.This research was supported in part by ARPA Grant N00174-91-C-0116 and NSF Grant NCR-92-04419.     

Regularity of minimizers of the calculus of variations in Carnot groups via hypoellipticity of systems of Hörmander type

We prove the hypoellipticity for systems of H?rmander type with constant coefficients in Carnot groups of step 2. This result is used to implement blow-up methods and prove partial regularity for local minimizers of non-convex functionals, and for solutions of non-linear systems which appear in the study of non-isotropic metric structures with scalings. We also establish estimates of the Hausdorff dimension of the singular set. Received October 23, 2000 / final version received February 5, 2002?Published online May 15, 2002 The work of the first author was partially supported by NSF Grant No. DMS-9800794 The work of the second author was partially supported by NSF Grants No. DMS-9706892 and DMS-0070492     

The FENE dumbbell model near equilibrium

We study the global existence of smooth solutions near the equilibrium to a coupled microscopic-macroscopic FENE dumbbell model which arises from the kinetic theory of diluted solutions of polymeric liquids with noninteracting polymer chains.     

Lossless Condensers,Unbalanced Expanders,And Extractors

Trevisan showed that many pseudorandom generator constructions give rise to constructions of explicit extractors. We show how to use such constructions to obtain explicit lossless condensers. A lossless condenser is a probabilistic map using only O(logn) additional random bits that maps n bits strings to poly(logK) bit strings, such that any source with support size K is mapped almost injectively to the smaller domain. Our construction remains the best lossless condenser to date. By composing our condenser with previous extractors, we obtain new, improved extractors. For small enough min-entropies our extractors can output all of the randomness with only O(logn) bits. We also obtain a new disperser that works for every entropy loss, uses an O(logn) bit seed, and has only O(logn) entropy loss. This is the best disperser construction to date, and yields other applications. Finally, our lossless condenser can be viewed as an unbalanced bipartite graph with strong expansion properties. * Much of this work was done while the author was in the Computer Science Division, University of California, Berkeley, and supported in part by a David and Lucile Packard Fellowship for Science and Engineering and NSF NYI Grant No. CCR-9457799. The work was also supported in part by an Alon fellowship and by the Israel Science Foundation. † Much of this work was done while the author was a graduate student in the Computer Science Division, University of California, Berkeley. Supported in part by NSF Grants CCR-9820897, CCF-0346991, and an Alfred P. Sloan Research Fellowship. ‡ Much of this work was done while the author was on leave at the Computer Science Division, University of California, Berkeley. Supported in part by a David and Lucile Packard Fellowship for Science and Engineering, NSF Grants CCR-9912428 and CCR-0310960, NSF NYI Grant CCR-9457799, and an Alfred P. Sloan Research Fellowship.     

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.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

An augmented Lagrangian technique for variational inequalities

A general framework for the treatment of a class of elliptic variational inequalities by an augmented Lagrangian method, when inequalities with infinite-dimensional image space are augmented, is developed. Applications to the obstacle problem, the elastoplastic torsion problem, and the Signorini problem are given.The research of the first author was supported in part by the Air Force Office of Scientific Research under Grants AFOSR-84-0398 and AFOSR-85-0303, by the National Aeronautics and Space Administration under Grant NAG-1-1517, and by NSF under Grant No. UINT-8521208. The second author's research was supported in part by the Fonds zur Förderung der wissenschaftlichen Forschung under S3206 and P6005.     

Embeddings in Artinian rings and Sylvester rank functions

Using Sylvester rank functions it is shown that a right Noetherian algebra, modulo the torsion ideal determined by elements regular modulo its nil radical, is embeddable in a simple Artinian ring. This is used to show that a right Noetherian algebra which is right Krull homogeneous embeds in a simple Artinian ring, and that a right Noetherian affine algebra satisfying a polynomial identity embeds in a simple Artinian ring. The research of the second author was supported in part by NSF Grant DMS-8317737.     

Using Selective Orthonormalization to Update the Analytic Center after Addition of Multiple Cuts

We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope. This is an important issue that arises at every stage of cutting-plane algorithms. If q n cuts are to be added, we show that we can use a selective orthonormalization procedure to modify the cuts before adding them; it is then easy to identify a direction for an affine step into the interior of the new polytope and the next analytic center is then found in O(qlog q) Newton steps. Further, we show that multiple cut variants with selective orthonormalization of standard interior-point cutting-plane algorithms have the same complexity as the original algorithms.This research was partially supported by ONR Grant N00014-94-1-0391, by NSF Grants CCR-9901822 and DMS-0317323, and by a grant from the Dutch NWO and Delft University of Technology for the 1997–98 academic year, while the senior author was visiting ITS/TWI/SSOR. The authors thanks two anonymous referees for careful reading of the paper and useful suggestions.     

Alternating direction splitting for block Angular parallel optimization

We develop and compare three decomposition algorithms derived from the method of alternating directions. They may be viewed as block Gauss-Seidel variants of augmented Lagrangian approaches that take advantage of block angular structure. From a parallel computation viewpoint, they are ideally suited to a data parallel environment. Numerical results for large-scale multicommodity flow problems are presented to demonstrate the effectiveness of these decomposition algorithmims on the Thinking Machines CM-5 parallel supercomputer relative to the widely-used serial optimization package MINOS 5.4.This material is based on research supported by the Air Force Office of Scientific Research, Grants AFORS-89-0410 and F49620-1-0036, and by NSF Grants CCR-89-07671, CDA-90-24618, and CCR-93-06807. The work of the second author was supported partially by Grant 95.00732.CT01 from the Italian National Research Council (CNR).     

On the relation between several notions of unconditional structure

The unconditional structure of a space constructed by Kalton and Peck is investigated. Among other things it is proved that even though this space has an unconditional decomposition into subspaces of dimension two, it does not have G.L. l.u.st. Supported in part by NSF Grants MCS 76-06565 and MCS 79-03042. Supported in part by NSF Grant MCS 78-02194.     

Separating Cycles in Doubly Toroidal Embeddings

 We show that every 4-representative graph embedding in the double torus contains a noncontractible cycle that separates the surface into two pieces. As a special case, every triangulation of the double torus in which every noncontractible cycle has length at least 4 has a noncontractible cycle that separates the surface into two pieces. Received: May 22, 2001 Final version received: August 22, 2002 RID="*" ID="*" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070613 RID="†" ID="†" Supported by NSF Grants Numbers DMS-9622780 and DMS-0070430     

Quasi-planar graphs have a linear number of edges

A graph is calledquasi-planar if it can be drawn in the plane so that no three of its edges are pairwise crossing. It is shown that the maximum number of edges of a quasi-planar graph withn vertices isO(n).Work on this paper by Pankaj K. Agarwal, Boris Aronov and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work on this paper by Pankaj K. Agarwal has also been supported by NSF Grant CCR-93-01259, by an Army Research Office MURI grant DAAH04-96-1-0013, by an NYI award, and by matching funds from Xerox Corporation. Work on this paper by Boris Aronov has also been supported by NSF Grant CCR-92-11541 and by a Sloan Research Fellowship. Work on this paper by János Pach, Richard Pollack, and Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-94-24398. Work by János Pach was also supported by Grant OTKA-4269 and by a CUNY Research Award. Work by Richard Pollack was also supported by NSF Grants CCR-94-02640 and DMS-94-00293. Work by Micha Sharir was also supported by NSF Grant CCR-93-11127, by a Max-Planck Research Award, and by grants from the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Part of the work on this paper was done during the participation of the first four authors in the Special Semester on Computational and Combinatorial Geometry organized by the Mathematical Research Institute of Tel Aviv University, Spring 1995.