A k-dimensional permutation is a (k+1)-dimensional array of zeros
and ones, with exactly a single one in every axis parallel line. We consider the
“number on the forehead" communication complexity of a k-dimensional permutation
and ask how small and how large it can be. We give some initial answers to these questions.
We prove a very weak lower bound that holds for every permutation, and mention a surprising
upper bound. We motivate these questions by describing several closely related problems:
A random linear (binary) code is a dimension lamba*n (0
Much of the interesting information about a code C is captured by its weight vector. Namely, this is the vector (w_0,w_1,...,w_n) where w_i counts the elements of C with Hamming weight i. In this work we study the weight vector of a random linear code. Our main result is computing the moments of the random variable w_(gamma*n), where 0 < gamma < 1 is a fixed constant and n goes to infinity.
This is a joint work with Nati Linial.
The study of elastic membranes carrying topological defects has a longstanding history, going back at least to the 1950s. When allowed to buckle in three-dimensional space, membranes with defects can totally relieve their in-plane strain, remaining with a bending energy, whose rigidity modulus is small compared to the stretching modulus.
I will discuss a family of random processes in discrete time related to products of random matrices (product matrix processes). Such processes are formed by singular values of random matrix products, and the number of factors in a random matrix product plays a role of a discrete time. I will explain that in certain cases product matrix processes are discrete-time determinantal point processes, whose correlation kernels can be expressed in terms of double contour integrals. This enables to investigate determinantal processes for products of ra ndom matrices in
Title: S-machines and their applications
Abstract: I will discuss applications of S-machines which were first introduced in 1996. The applications include
* Description of possible Dehn functions of groups
* Various Higman-like embedding theorems
* Finitely presented non-amenable torsion-by-cyclic groups
* Aspherical manifolds containing expanders
* Groups with quadratic Dehn functions and undecidable conjugacy problem
Title: Random walks on planar graphs
Abstract: We will discuss several results relating the behavior of a random walk on a planar graph and the geometric properties of a nice embedding of the graph in the plane (e.g. a circle packing of the graph). An example of such a result is that for a bounded degree graph, the simple random walk is recurrent if and only if the boundary of the nice embedding is a polar set (that is, Brownian motion misses it almost surely).
No prior knowledge about random walks, circle packings or Brownian motion is required.
The Hodge decomposition theorem is the climax of a beautiful theory involving geometry, analysis and topology, which has far-reaching implications in various fields. I will present the Hodge decomposition in compact Riemannian manifolds, with or without boundary. The non-empty-boundary case is more interesting, as it requires the formulation of an appropriate boundary condition. As it turns out, the Hodge-Laplacian has two different elliptic boundary conditions generalizing the classical Dirichlet and Neumann conditions, respectively.
An ergodic system (X;B; μ; T) is said to have the weak Pinsker
property if for any ε > 0 one can express the system as the direct
product of two systems with the first having entropy less than ε and
the second one being isomorphic to a Bernoulli system. The problem
as to whether or not this property holds for all systems was open for
more than forty years and has been recently settled in the affirmative
in a remarkable work by Tim Austin.
I will begin by describing why Jean-Paul formulated this prob-
Using formal power series one can define, over any field, a class of functions including algebraic and classical modular functions over C. Under simple conditions the power series will have coefficients in a subring of the field - say Z - and this plays a role in Apery's proof of the irrationality of \zeta(3). Remarkably over a finite field all such functions/power series are algebraic.
I will call attention to a natural - but open - problem in this area.
An old result of Hedlund tells us that there are no closed orbits for the horocycle flow on a compact Riemann surface M. The situation is different if M is non-compact in which case there is a one-parameter family of periodic orbits for every cusp of M. I want to talk about a result by Sarnak concerning the distribution of the such orbits in each of these families when their length goes to infinity. It turns out that these orbits become equidistributed in M and the rate of convergence can in fact be quantified in terms of spectral properties of the Eisenstein series on M.
An old problem (Going back to Turing, Ulam and others) asks about the "stability" of solutions in some algebraic contexts. We will discuss this general problem in the context group theory: Given an "almost homomorphism" between two groups, is it close to a homomorphism?