Campus Event Calendar
Event Entry
What and Who
Double Header: Balancing location of points on boundary and Deterministic Rateless Codes for Binary Symmetric Channels
Guy Even and Takeshi Tokuyama
Technion and Kyoto University
Lecture
Guy Even, Technion Haifa
Takeshi Tokuyama, Kyoto University
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 February 2014
13:00
75 Minutes
E1 4
024
Saarbrücken
Abstract
Balancing location of points on boundary.
Abstract:
We consider the problem of finding a location (called {\em balancing location}) for a set of points on the boundary of
a region so that their
``center of mass'' coincides with a given point $p$ in the region.
If we locate a pair of points such that their midpoint becomes $p$, then they form an
antipodal pair with respect to $p$.
We give several variations of the problem to give criteria to ensure the existence of a balancing set.
For example, we show that we can always find three points on the boundary of a three-dimensional
polyhedral region so that they form a equilateral triangle with the center at $p$.
This is a joint work obtained with many coauthors.
Deterministic Rateless Codes for Binary Symmetric Channels
abstract:
A rateless code encodes a finite length information word into an infinitely long
codeword. The length of the prefix of the noisy codeword required by the decoder
depends on signal-to-noise ratio of the communication channel. A rateless code
achieves capacity for a family of channels if, for every channel in the family,
reliable communication is obtained with a rate that is arbitrarily close to the
channel's capacity. The encoder is universal because the same encoding is used for
all channels in the family.
In this paper, we construct the first \emph{deterministic} rateless code for the
binary symmetric channel. Our code can be encoded and decoded in $O(\log k)$ time
per bit and in poly-logarithmic parallel time. Furthermore, the error probability
of our code is almost exponentially small $\exp(-\Omega(k/\polyloglog(k)))$.
Previous rateless codes are probabilistic (i.e., based on code ensembles), require
polynomial time per bit for decoding, and have inferior error probabilities.
Joint work with Benny Applebaum and Liron David
Abstract:
We consider the problem of finding a location (called {\em balancing location}) for a set of points on the boundary of
a region so that their
``center of mass'' coincides with a given point $p$ in the region.
If we locate a pair of points such that their midpoint becomes $p$, then they form an
antipodal pair with respect to $p$.
We give several variations of the problem to give criteria to ensure the existence of a balancing set.
For example, we show that we can always find three points on the boundary of a three-dimensional
polyhedral region so that they form a equilateral triangle with the center at $p$.
This is a joint work obtained with many coauthors.
Deterministic Rateless Codes for Binary Symmetric Channels
abstract:
A rateless code encodes a finite length information word into an infinitely long
codeword. The length of the prefix of the noisy codeword required by the decoder
depends on signal-to-noise ratio of the communication channel. A rateless code
achieves capacity for a family of channels if, for every channel in the family,
reliable communication is obtained with a rate that is arbitrarily close to the
channel's capacity. The encoder is universal because the same encoding is used for
all channels in the family.
In this paper, we construct the first \emph{deterministic} rateless code for the
binary symmetric channel. Our code can be encoded and decoded in $O(\log k)$ time
per bit and in poly-logarithmic parallel time. Furthermore, the error probability
of our code is almost exponentially small $\exp(-\Omega(k/\polyloglog(k)))$.
Previous rateless codes are probabilistic (i.e., based on code ensembles), require
polynomial time per bit for decoding, and have inferior error probabilities.
Joint work with Benny Applebaum and Liron David
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only
Kurt Mehlhorn, 01/21/2014 08:55
Kurt Mehlhorn, 01/05/2014 10:51
Kurt Mehlhorn, 10/29/2013 08:36 -- Created document.
Kurt Mehlhorn, 01/05/2014 10:51
Kurt Mehlhorn, 10/29/2013 08:36 -- Created document.