פעילויות השבוע

The Vertex Cover Problem is the optimization problem of finding a vertex cover V_c of minimal cardinality in a given graph. It is a classic NP-hard problem, and various algorithms have been suggested for it. In this talk, we will start with a basic algorithm for solving the problem. Using a probabilistic idea, we use it to develop an improved algorithm. The algorithm is greedy; at each step it adds to the cover a vertex such that the expected cover size, if we continue randomly after this step, is minimal. We will study the new algorithm theoretically and empirically, and present simulations that compare its performance to that of some algorithms of a similar nature.

Earlier this year, we discovered a new class of zero-dimensional dynamical systems, which we call ”fiberwise essentially minimal“, that are of importance to operator algebras because of the nice properties, in particular K-theoretic classification, of the crossed product. Today, we discuss the Bratteli diagrams associated to these systems, and extend the K-theoretic classification to include a dynamical condition called ”strong orbit equivalence“, extending the existing result in the minimal case due to Giordano-Putnam-Skau.

Continuous wavelet transforms are mappings that isometrically embed a signal space to a coefficient space over a locally compact group, based on so-called square integrable representations. For example, the 1D wavelet transform maps time signals to functions over the time-scale plane based on the affine group. When using wavelet transforms for signal processing, it is often useful to work interchangeably with the signal and the coefficient spaces. For example, we would like to know what operation in the signal domain is equivalent to multiplication in the coefficient space. While such a point of view is natural in classical Fourier analysis (i.e., “time convolution is equivalent to frequency multiplication”), it is not compatible with wavelet analysis, since wavelet transforms are not surjective. In this talk, I will present the wavelet-Plancherel theory – an extension of classical wavelet theory in which the wavelet transform is canonically extended to an isometric isomorphism. The new theory allows formulating a variety of coefficient domain operations as signal domain operations, with closed form formulas. Using these so-called pull-back formulas, we are able to reduce the computational complexity of some wavelet-based signal processing methods. The theory is also useful for proving theorems in wavelet analysis. I will present an extension of the Heisenberg uncertainty principle to wavelet transforms and prove the existence of uncertainty minimizers using the wavelet-Plancherel theory.