Tuesday at 16:10 on 2004 November 2

Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m non-zero elements. We present a new algorithm that multiplies A and B using O(m^0.7n^1.2+n^2+o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. The naive matrix multiplication algorithm, on the other hand, may need to perform W(mn) operations to accomplish the same task. For m £ n^1.14, the new algorithm performs an almost optimal number of only n^2+o(1) operations! For m £ n^1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n^2.38) algebraic operations. Obtaining a fast sparse matrix multiplication algorithm that beats the naive method even for very sparse matrices was a long standing open problem. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices.

Joint work with Uri Zwick

Remmert's Proper Mapping Theorem says that the image of a complex analytic set under a proper holomorphic map is an analytic subset of the target manifold. The theorem fails without the properness assumptions for several reasons the most obvious being that the image set might not be even topologically closed .

I will discuss this and other classical theorems from complex analytic geometry under the further assumption that the sets in question are locally "defined in an o-minimal structure". This assumption (satisfied for example by all real subanalytic sets) which originates in Model Theory turns out to be very powerful, with many consequences in different fields of mathematics such as group theory, topology, real analysis, differential equations, optimization theory and more.

In the context of complex analytic geometry we prove for example the following version of the above theorem of Remmert: Let f : M->N be a holomorphic map between complex manifolds and A a complex analytic subset of M. If f(A) is topologically closed and "locally defined in an o-minimal structure" then it is necessarily an analytic subset of N.

I intend to explain the basic complex analytic notions as well as the notion of an o-minimal structure and its implications.

Joint work with S. Starchenko .

I will give an introduction to work done over the last 5 years combining combinatorics of hyperplane arrangements, representation theory and p-adic algebraic geometry.

How many pieces can you get by making n cuts in a block of cheese? The right generalization of this question to complex affine space lead to interesting work of Arnold, Brieskorn, and Orlik and Solomon.

Over the p-adic numbers (whose definition I will recall) this is even more interesting, and new phenomena occur because of the possibility to impose on the space a variety of integral structures. Harmonic analysis on buildings (higher dimensional analogues of trees) appears as a powerful tool. Applications to the cohomology of p-adically uniformized varieties will be mentioned at the end, but most of the talk will require no background at all.

The braid group is one of the simplest noncommutative group and can be described in several equivalent ways (fundamental group of the configuration space of C, mapping class group of the complement of n points in the unit disk, etc). We will present this group and some recent rigidity results.

A mapping f from a domain W in C into C is called (planar) harmonic if f=u+iv where u and v are both real harmonic. This is a natural generalization of analytic functions. These mappings are in one to one correspondence with minimal surfaces and that is where their importance stems from. Under mild conditions these are quasiregular maps and under even milder conditions they are pseodoanalytic. Most of all complex analytic methods proved to be useful in there study . In this talk we shall refer to some of the results in the field related to mappings onto convex domains and discuss some open problems.

The matrix representation of the set D(d³), d³ = (d₁,d₂,d₃), of the integers which are unrepresentable by d₁,d₂,d₃ is found. The diagrammatic procedure of calculation of the generating function F(d³;z) for the set D(d³) is developed. The Frobenius number F(d³), genus G(d³) and Hilbert series H(d³;z) of a graded subring for non-symmetric and symmetric semigroups S(d³) are found.

The tropical algebraic geometry, i.e., an algebraic geometry over the reals equipped with the operations of maximum and addition, appears as a limit (dequantization) of the classical algebraic geometry. We discuss an application of this relation to enumeration of real and complex algebraic curves (due to Mikhalkin, Itenberg, Kharlamov, Seibert and the author), resulting in answers, expressed via combinatorics of convex lattice polytopes and their lattice subdivisions.

We prove an old conjecture of Erdos, saying that Menger's theorem is valid also for infinite graphs, in the following strong form: given sets A and B of vertices in a directed graph, there exists a family P of disjoint A-B paths, and an A-B separating set S, such that S consists of a choice of precisely one vertex from each path in P. The talk will describe the history of the problem and the main ideas of  our proof.

This is joint work with Ron Aharoni.

We investigate finitely generated groups by studying their actions on sets. Our focus is on groups that have some geometric flavor to them such as: linear groups, hyperbolic groups, mapping class groups, and more.
A group action on a set is called primitive if there is no non-trivial invariant equivalence relation on the set. One can think of primitive actions as ``irreducible'' permutation representations. We call a group primitive if it admits a faithful primitive action on a set. In all of the geometric settings cited above we obtain a complete classification of finitely generated primitive groups. Here is an example of a theorem that is simple to state: "A finitely generated linear group with a simple Zarisky closure is primitive."
A slightly more technical statement gives a complete characterization of finitely generated primitive linear groups.
As a corollary we prove a conjecture of Neumann and Higman on the Frattini subgroup of an amalgamated free product. The talk will be non-technical and suitable for a wide mathematical audience.
 

This is a joint work with Tsachik Gelander.

E. Plotkin: On solvability of finite groups. A way to the solvable radical

The theorem by R. Baer (1957) shows how to characterize the nilpotent radical of a finite group. This theorem is a natural generalization of the classical theorems by Engel and Zorn which describe the nilpotency property in terms of two variable laws.

The aim of the talk is to outline the ways for a describing in similar manner the solvable radical of a finite group and to discuss the solvable counterparts of Baer's and Zorn's theorem for finite dimensional Lie algebras.

Wafiq Hibi: The Beckman-Quarles theorem for rational spaces

Let R^d and Q^d denote the real and the rational d-dimensional spaces, respectively. For a real number b, a mapping f:X --> X, where X is either R^d or Q^d, is called b-distance preserving if dist(x,y)=b implies dist(f(x),f(y))=b for all x,y in X.

The Beckman-Quarles theorem states that every unit distance preserving mapping f:R^d --> R^d is an isometry, provided d is at least 2. A few papers have been written about rational analogues of this theorem, showing that for some values of d the property: "every unit distance preserving mapping f:Q^d --> Q^d, is an isometry" holds as well.
I will discuss the following recent result: For every d satisfying d => 5, every unit-distance preserving mapping of Q^d to Q^d is an isometry.

Amnon Besser: A new proof of de Shalit's p-adic period relation

Let S be a Riemann surface of positive genus g. Then S can be written as the quotient of a complex domain D by a discrete automorphism group G. It has a fundamental domain whose boundary is a polygon with 4g sides: a₁,b₁,a₁^-1,b₁^-1,¼a_g^-1,b_g^-1 and the group action identifies a side with its opposite side. A fundamental theorem states that for two holomorphic differential forms on S, which are the same thing as holomorphic G-invariant forms w and h on D, one has the period relation

We comment that this relation can be generalized to mermorphic vector valued forms.
The situation over the p-adic numbers is more interesting. There is an analogue notion of a p-adic domain and quotients of such are called Mumford curves. In the mid 80's de Shalit found an analogous relation in the p-adic case. The main point is to discover what replaces the integrals, which are not available p-adically. de Shait defines two kinds of periods, one involving residues and the other involving a p-adic integration theory known as Coleman integration.
Recently we gave a new proof of de Shalit's result, which is very much shorter than the original proof. It is based on an elementary generalization of the notion of a residue.
In my talk I will review both the classical and the p-adic theories, explain the generalized residue and give a five line proof of the p-adic analogue of the period relation.

The RSK algorithm, named after G. de B. Robinson, C. Schensted, and D. Knuth, is perhaps the most interesting algorithm in all of mathematics. In its most basic form, it transforms a permutation of 1,2,...,n into a pair of standard Young tableaux of the same shape with n squares. The beauty and importance of this algorithm stems from (1) its remarkable symmetry and other properties, (2) the deep connections with representation theory, probability theory, and other areas, and (3) its many variations and extensions.

The main motivation for Bregman-function-based proximal methods is that,
for certain classes of (ill-posed, in general) variational inequalities, an appropriate
choice of a Bregman function permits one to preserve good regularizing properties
of the original version of the proximal point method and to provide that regularized
problems can be treated as unconstrained ones.
However, convergence results for such interior proximal methods suppose
that a maximal monotone operator in a variational inequality possesses also the
paramonotonicity property. This additional requirement is rather restrictive: in
particular, an operator associated with a Lagrangian of a convex programming
problem is typically not paramonotone.
In this talk, we present the convergence analysis of Bregman-function based
proximal methods for finding saddle points of convex programming problems in
Hilbert spaces, as well as for finite-dimensional complementarity problems with
multi-valued monotone operators (without the paramonotonicity assumption). The
convergence results admit a successive approximation of the variational inequality
and an inexact treatment of proximal iterations.

We construct a model in which spin 1 and spin 1/2 particles coexist. The
model is the spin factor, one type of Bounded Symmetric Domains. We develop
the geometry of that domain, using the spin triple product which is an
analog of the Canonical Anticommutation Relations and Clifford algebra
product. We present a geometric spectral theorem for this domain. We obtain
both spin 1 and spin 1/2 representations of the Lorentz group on this
domain.

Prof. Friedman will give another talk on Monday, April 4 at 14-16 in the seminar on Operator Theory and Mathematical Physics (room 570, Education/Science Building)

We prove extensions of Menchoff's inequality and the Menchoff-Rademacher theorem for sequences {f_n} Ì L_p, based on the size of the norms of sums of sub-blocks of the first n functions.

The results are applied to the study of a.e. convergence of series å_n [(a_n Tⁿg)/(n^a )] when T is an L₂-contraction, g Î L₂, and {a_n} is an appropriate sequence.

Given a sequence {f_n} Ì L_p(W,m) of independent symmetric random variables, we study conditions for the existence of a set of x of m-probability 1, such that for every contraction T on L₂(Y,p) and g Î L₂(p), the random power series å_n f_n(x)Tⁿ g converges p-a.e.

This is a joint work with M. Lin.

It is known that a tube over a K\"ahler submanifold in a complex space form is a Hopf hypersurface. In some sense the reverse statement is true: a connected compact generic immersed $C^{2n-1}$ regular Hopf hypersurface in the complex projective space is a tube over an irreducible algebraic variety. In the complex hyperbolic space a connected compact generic immersed $C^{2n-1}$ regular Hopf hypersurface is a geodesic hypersphere.

The following theorem gives a complete description of the global structure of Hopf hypersurfaces in complex space forms. Let M be an immersed regular hypersurface in a regular manifold N. Suppose that for a point P in N of self-intersection the linear span of
the tangent hyperplanes to the branches of M coincides with thetangent space T_PN of the ambient manifold. This point is called a generic point of self-intersection. If every point of self-intersection of the hypersurface M is a generic point of self-intersection then the hypersurface M is called a generic immersed hypersurface.

Theorem 1. Let M be a $C^{2n-1}$-regular compact generic immersed orientable Hopf hypersurface in the complex projective space $CP^n\ (n>2)$. Then M is a tube over an irreducible algebraic variety.

Theorem 2. Let M be a $C^{2n}$-regular connected compact generic immersed orientable Hopf hypersurface in the complex projective space $CP^n\ (n>2)$ contained in a geodesic ball of radius $R<\pi/2$. Then M is a geodesic hypersphere.

Let $CH^n$ be the complex hyperbolic space of constant holomorphic curvature $-4$.

Theorem 3.  Let M be a connected compact generic immersed orientable $C^{2n-1}$ regular Hopf hypersurface in the complex hyperbolic space $CH^n\ (n>2)$. Then the Hopf hypersurface M is a geodesic hypersphere.

PROFESSOR BORISENKO IS A VISITOR OF THE CENTER OF COMPUTATIONAL MATHEMATICS AND SCIENTIFIC COMPUTATION OF THE UNIVERSITY OF HAIFA

In the lecture I define the two important notions of
differentiability of Lipschitz functions between Banach spaces: Gateaux
differentiability and Frechet differentiability. I will discuss the
surprisingly difficult (and to a large extent, still open) question of
existence of Frechet derivatives. There is a strong connection between
this question and the structure of porous sets. Various notions of porous
sets will be defined and investigated.

SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET/WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the streams. We need to assign wavelengths so as to minimize the total number of used ADMs. Following previous work, we consider several models of the ADM minimization problem. The input is given as pairs of ring vertices, and the paths may be either pre-assigned (arc version) or to be assigned by the algorithm (chord/routing version). Furthermore, we also consider the model where traffic streams can be divided into several parts, and assigned to different wavelengths. We present approximation algorithms for the different cases, each of which has a better performance guarantee than the best algorithm previously known for the problem.

Based on joint work with Asaf Levin.