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:
We will give a short review of various topics discussed in the first semester and last Monday and then we'll pick the fruits: namely, we will show how to get groups which are no approximated.
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.
Abstract:
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.
Abstract:
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.
Sun, 07/10/2018 (All day) to Thu, 11/10/2018 (All day)
Location:
Israel Institute for Advanced Studies, The Hebrew University of Jerusalem
In this workshop we intend to explore which methods and results can be extended from the realm of groups to stationary random graphs. In doing so we hope to gain better understanding of the factors that determine each random walk behavior, both on stationary random graphs and on Cayley graphs.
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.