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.