Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

Space-charge effects in liquid metal ion sources of different geometries

The current work considers the effect of geometry, other than the ideal Taylor cone, on space charge and axial fields of liquid metal ion sources. Solutions of the spacecharge equation for the concentric sphere and hyperboloidal-planar models of a liquid emitter demonstrate a rather dramatic dependence of the space charge and axial fields on the geometry of the emitting surface.This research was supported in part by the NATO Research Grants Division, Grant No. 1902, Scientific Affairs Division, Brussels, BelgiumAltoona Campus     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Berezin Forms on Line Bundles over Complex Hyperbolic Spaces

We consider complex hyperbolic spaces where and , line bundles , over them and representations of in smooth sections of (the representation is induced by a character of ). We define a Berezin form $, associated with , and give an explicit decomposition of this form into invariant Hermitian (sesqui-linear) forms for irreducible representations of the group for all and . It is the main result of the paper. Besides it, we give the Plancherel formula for . As it turns out, this formula is, en essence, one of the particular cases of the Plancherel formula for the quasiregular representation for rank one semisimple symmetric spaces, see [20], it can be obtained from the quasiregular Plancherel formula for hyperbolic spaces (complex, quaternion, octonion) by analytic continuation in the dimension of the root subspaces. The decomposition of the Berezin form allows us to define and study the Berezin transform, - in particular, to find out an explicit expression of this transform in terms of the Laplacian. Using that, we establish the correspondence principle (an asymptotic expansion as ). At last, considering , we observe an interpolation in the spirit of Neretin between Plancherel formulae for and for the similar representation for a compact form of the space . Submitted: July 12, 2001?Revised: February 12, 2002     

The commutator method for form-relatively compact perturbations

We present a variant of the conjugate operator method which can be used when the group generated by the conjugate operator leaves invariant only the form domain of the Hamiltonian. As an example, we get detailed spectral properties and a large class of locally smooth operators for two-body Schrödinger Hamiltonians with form-relatively compact potentials.     

Recursive construction for 3-regular expanders

We present an algorithm which inn ³ (logn)³ time constructs a 3-regular expander graph onn vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of lengths=clogn decreases (for some fixed absolute constantc). When we reach a local minimum in the number of cycles of lengths the graph is an expander.