“Spatial Coupling as a Proof Technique”
Speaker: Rudiger Urbanke, EPFL, Switzerland
Location: Sala de Video, 3.S1.08
Time and Date: December 11, 10:00-11:30
Abstract:
Spatial coupling is a good way of constructing graphical models from given components in a way that the resulting graphical model is suitable for iterative processing. This principle has successfully been applied in order to construct good error correcting codes and good compressive sensing schemes and it is applicable whenever we have control over the graphical model that is used.
But spatial coupling can also be useful as a proof technique. Consider the following scenario. Assume that we spatially couple a graphical model and that we can determine its behavior (threshold) under a specific algorithm (typcially a simple message-passing algorithm). Assume further that we can show that any achievable threshold of the spatially coupled model is also a lower bound on the threshold of the uncoupled model under optimal processing. This second step is typically accomplished by the so-called “interpolation method.” Then, in this way, we have a method for determining bounds on the fundamental threshold of the uncoupled system.
This technique was originally used to determine the MAP threshold of codes on graphs. I will discuss as application new lower bounds on the MAX-SAT threshold of random K-SAT.
This is joint work with Dimitris Achlioptas, Hamed Hassani and Nicolas Macris.
“Waiting Times, Dependence Balances, Search Codes, and False Acceptance”
Speaker: Frans M. J. Willems, Eindhoven University of Technology, The Netherlands
Location: Sala de Video, 3.S1.08
Time and Date: December 11, 12:00-13:30
Abstract:
The lecture consists of four parts.
(A) In the first part we focus on universal compression based on waiting times. We discuss the optimality of such methods in terms of parameter redundancy.
(B) Then we switch to the dependence balance bound and we focus both on a local version of it, but also the well-known global dependence balance bound.
(C) Part three of the lecture is about codes that can be applied to search biometric databases. A trade-off between search complexity and memory complexity is derived.
(D) Finally, we concentrate on biometric template protection and focus on the relation between false-accept rate and secret-key capacity.