|May 20, 2010|
Alex Lubotzky (HUJI)
On Rank gradient, Heegard splitting and Cost
|We will present a paper of M. Abert and N. Nikolov. In that prepring they consider two conjectures- one in 3-dim. geometry (saying that the number of generators of the fundamental group of an hyperbolic 3-manifold is equal to its Heegard genus) and one in measurable group theory ( "Fixed cost conjecture"). There main result is that (at least) one of these (seemingly unrealetd!) conjectures is false! They prove it by relating the cost of the action of a group on its profinite completion to its rank gradient. All the relevant notions will be explained.|
|May 6, 2010|
Boaz Tsaban (BIU)
The Algebraic Eraser and short expressions of permutations as products
March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced the
Algebraic Eraser scheme for key agreement over an insecure channel,
using a novel hybrid of infinite and finite noncommutative groups. They
also introduced the Colored Burau Key Agreement Protocol (CBKAP), a
concrete realization of this scheme.|
We present general, efficient heuristic algorithms, which extract the shared key out of the public information provided by CBKAP. These algorithms are, according to heuristic reasoning and according to massive experiments, successful for all sizes of the security parameters, assuming that the keys are chosen with standard distributions.
Our methods come from probabilistic group theory, and have not been used before in cryptanalysis. In particular, we provide a(n embarrassingly) simple and efficient heuristic algorithm for finding short expressions of permutations in S_n, as products of given random permutations.
Our algorithm gives (heuristically and experimentally) expressions of length O(n^2\log n), in time O(n^4\log n) and space O(n^2\log n), and is the first practical one for n>128.
The talk is self-contained and was already delivered successfully to students. So, students are welcome.
Joint work with Arkadius Kalka and Mina Teicher (BIU).
Disclaimer: Our work does not make any claim concerning the security of the actual distributions used in the Algebraic Eraser (TM). These distributions are are proprietary and are not available to the authors
April 29, 2010
Amnon Yekutieli (BGU)
Central Extensions of Gerbes
The talk will begin with an explanation of the concept of extension of groupoids.
Next I will explain what is a gerbe. This is a very complicated concept. My point of view is that a gerbe G, on a topological space X, is the geometric version of a nonempty connected groupoid -- much in the same way that a sheaf of groups on X is the geometric version of a group. I will try to avoid the horrid technicalities of 2-categories and stacks.
The structure of nonabelian gerbes is known to be very complicated. Mainly one wants to know if a given gerbe G is trivial. The theory of nonabelian cohomology (Giraud, 1960's) was invented for this purpose. However this theory is too abstract to be useful.
An extension of gerbes is gotten by geometrizing the concept of extension of groupoids.
I will state a couple of results about obstruction theory for central
extensions of gerbes. This theory gives concrete criteria to determine
if a given gerbe is trivial.
If time permits I will explain how the last result is used in my work on twisted deformation quantization of algebraic varieties.
The paper (same title as lecture) is available online as arXiv:0801.0083; to appear in Advances Math.
|April 22, 2010|
Amitai Regev (Weizmann)
A characterization of standard polynomials by codimension growth
|Given a p.i. algebra A, it has a sequence of codimentions c_n(A). A deep theorem of Giambruno and Zaicev says that as n goes to infinity, the limit of the n-th root of c_n(A) always exist (and is an integer). That integer, denoted exp(A), is called the exponent of the algebra A. Given a polynomial f, one considers U(f), the relatively free p.i. algebra satisfying f=0, then denotes exp(f):= exp(U(f)). Given n\ge 6, we show that if f=St_n is the standard polynomial of degree n, and g is any polynomial of degree n which is not a multiple of St_n, then exp(g) < exp(St_n).|
|March 25 - April 9: Pesach vacation|
|March 18, 2010|
David El-Chai Ben-Ezra (HUJI)
O’Nan Scott Theorem
|The above is a classification theorem of the primitive finite
groups. Primitive groups in certain meanings are the “atoms” of
permutation groups, and, therefore, have great importance in the study
of their structure. Moreover, the point stabilizers of a primitive
group form a conjugacy class of maximal subgroups, so classification of
primitive groups is closely related to the study of maximal subgroups.
It turns out that the key to analyzing finite primitive groups is to
study the socle, which is the subgroup generated by the minimal normal
In the lecture we will study the structure of the socle of primitive finite groups, and will give a brief description of the types of the primitive finite groups.
The lecture will be given in Hebrew, and only basic knowledge of group theory is needed.
|March 11, 2010|
Uri Shapira (HUJI)
Applying dynamics to Number Theory
|I will describe a recent joint work with Manfred Einsiedler and Lior
Fishman in which we use rigidity results in dynamics to solve several
problems regarding continued fraction expansions. In particular, we
settle the following conjecture of M. Boshernitzan: For a real number
x, let a_n(x) be the n'th coefficient in the continued fraction
expansion of x and let c(x) = limsup a_n(x) (the number c(x) has a
clear geometric meaning that I will explain in the talk). |
Theorem (EFS): For any irrational x, the sequence c(nx) is unbounded.
The talk is intended for general audience and will not assume prior knowledge in the subject.
|March 4, 2010|
Chen Meiri (HUJI)
The congruence subgroup property for Aut(F_2)
|Asada proved that Aut(F_2) has the congruence subgroup property. |
His proof was based on techniques involving Galois extensions of rational function fields of algebraic curves.
In this talk we will present a group-theoretic proof of Bux, Ershov and Rapinchuk for this theorem.
|February 25, 2010|
Doron Shafrir (HUJI)
Duality of orbits and invariant polynomials in algebraic actions
|Given a group G acting on a finite dimensional vector space V, it is
natural to try to parametrize the orbits of the action. This is the
goal of invariant theory. For example, if the group is finite the
orbits are parametrized by point of an affine variety. When the group
and action are algebraic it is possible to give a variety that
corresponds to "most" (Zariski open subset) orbits. To find the
quotient variety it is important to understand the ring of invariants
k[V]^G. In this talk I will discuss properties of this ring in
connection with the orbits.|
For example, we will see that when the ring is polynomial, and if G has no characters, then every orbit of maximal dimension is a component of a set of invariant equations.
The talk is part of the Action Now day, and therefore will be held in Canada Elion and will start at 12:10.
|February 25, 2010|
Doron Shafrir (HUJI)
Nov 26, 2009
Seymour Bachmuth (UCSB)
Solution of Burnside’s Problem
Nov 19, 2009
Construction of nill- but not nilpotent semigroup
Nov 12, 2009
Konstantin Golubev (HUJI)
Cayley graphs and dessins
Nov 05, 2009
Andy Magid (Oklahoma)
The Complete Differential Galois Closure of a Differential Field
Oct 29, 2009
Avinoam Mann (HUJI)
The growth of free products