defs.tex
\DeclareMathAlphabet{\mathbcal}{OMS}{cmsy}{b}{n}

\DeclareMathOperator{\de2}{d^2_{\mathcal{E}}}
\DeclareMathOperator{\depth}{depth}
\DeclareMathOperator{\wt}{wt}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\neras}{\mathcal{N}}
\DeclareMathOperator{\erfc}{erfc}
\DeclareMathOperator{\sort}{sort}

\newcommand{\eras}{\ensuremath{\varepsilon}}

\newcommand{\eproj}[2]{\ensuremath{P_{\neras({#1})}\left[{#2}\right]}}

\newcommand{\set}[1]{\ensuremath{#1}}
\newcommand{\abs}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\vect}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\mat}[1]{\ensuremath{\boldsymbol{#1}}}
\newcommand{\submatr}[3]{\ensuremath{left.\boldsymbol{#1}\right|_{#2}^{#3}}}
%\newcommand{\srt}[1]{\ensuremath{{#1}\!\raisebox{1pt}{$\downharpoonright$}}}
\newcommand{\srt}[1]{\ensuremath{\check{#1}}}

\newcommand{\Cu}[1]{\ensuremath{\sigma^{\langle{#1}\rangle}}}
\newcommand{\Ct}{\ensuremath{\Sigma}}

\newcommand{\card}[1]{\ensuremath{\left|{#1}\right|}}
\newcommand{\code}{\ensuremath{\mathcal{C}}}
\newcommand{\codeo}{\ensuremath{\mathcal{A}}}
\newcommand{\codei}{\ensuremath{\mathcal{B}}}
\newcommand{\rscode}{\ensuremath{\mathcal{C}_{\text{RS}}}}
\newcommand{\BCH}{\ensuremath{\text{BCH}}}
\newcommand{\RS}[1]{\ensuremath{\mathcal{RS}\left({#1}\right)}}
\newcommand{\Golay}[1]{\ensuremath{\mathcal{G}\left({#1}\right)}}
\newcommand{\IRS}[1]{\ensuremath{\mathcal{IRS}\left({#1}\right)}}
\newcommand{\F}[1]{\ensuremath{\mathbb{F}}_{#1}}
\newcommand{\E}{\ensuremath{\mathbb{E}}}
\newcommand{\CE}{\ensuremath{\mathcal{E}}}
\newcommand{\FF}[2]{\ensuremath{\mathbb{F}}_{#1}^{#2}}
\newcommand{\GF}[1]{\ensuremath{\text{GF}}\left({#1}\right)}

\newcommand{\Seq}{\ensuremath{\mathcal{S}}}
\newcommand{\XSeq}{\ensuremath{\mathcal{X}}}

\newcommand{\nset}{\ensuremath{\mathcal{N}}}
\newcommand{\mset}{\ensuremath{\mathcal{M}}}

\newcommand{\FT}[1]{\ensuremath{\mathfrak{F}\left({#1}\right)}}
\newcommand{\IFT}[1]{\ensuremath{\mathfrak{F}^{-1}\left({#1}\right)}}

\newcommand{\alg}[1]{\textsf{{#1}}}

\newcommand{\svform}[1]%
{\begin{sideways}\footnotesize\ensuremath{{#1}\;}\end{sideways}}

% trellis stuff
\newcommand{\edg}{\ensuremath{\varepsilon}}
\newcommand{\nod}{\ensuremath{\nu}}
\newcommand{\lbl}{\ensuremath{\lambda}}
\newcommand{\ilbl}{\ensuremath{\lambda^i}}
\newcommand{\edgset}{\ensuremath{\mathcal E}}
\newcommand{\nodset}{\ensuremath{\mathcal V}}
\newcommand{\lblset}{\ensuremath{\mathcal L}}
\newcommand{\edgcard}{\ensuremath{|\mathcal E|}}
\newcommand{\nodcard}{\ensuremath{|\mathcal V|}}
\newcommand{\snode}[1]{\ensuremath{\alpha\left({#1}\right)}}
\newcommand{\enode}[1]{\ensuremath{\omega\left({#1}\right)}}
\newcommand{\epath}{\ensuremath{\boldsymbol{\pmb\varepsilon}}}
\newcommand{\tepath}{\ensuremath{\boldsymbol{\widetilde{\pmb\varepsilon}}}}
\newcommand{\pathset}[1]{\ensuremath{{\mathbcal E}\left({#1}\right)}}
\newcommand{\eseg}[2]{\ensuremath{\left.{\epath}\right|_{#1}^{#2}}}
\newcommand{\esegi}[3]{\ensuremath{\left.{\epath}_{#1}\right|_{#2}^{#3}}}
\newcommand{\ccseg}{\ensuremath{\parallel}}
\newcommand{\segset}{\ensuremath{\mathcal D}}
\newcommand{\tset}{\ensuremath{\mathcal S}}
\newcommand{\tail}[1]{\ensuremath{{\mathcal T}\left({#1}\right)}}
\newcommand{\head}[1]{\ensuremath{{\mathcal H}\left({#1}\right)}}
\newcommand{\tailp}[1]{\ensuremath{{\mathcal T}^\prime\left({#1}\right)}}
\newcommand{\inset}[1]{\ensuremath{{\mathcal I}\left({#1}\right)}}
\newcommand{\insubset}[1]{\ensuremath{{\mathcal J}\left({#1}\right)}}
\newcommand{\insubsetp}[1]{\ensuremath{{\mathcal J}^\prime\left({#1}\right)}}
\newcommand{\outset}[1]{\ensuremath{{\mathcal O}\left({#1}\right)}}
\newcommand{\nodmetset}[1]{\ensuremath{{\mathcal M}\left({#1}\right)}}

\newcommand{\algcomment}[1]{\textsf{\footnotesize/$\ast$\ {#1}$\ \ast$/}}

\makeatletter
\newcommand{\ncirc}[1]{%
        \leavevmode\hbox{\setbox0=\hbox{\ensuremath{#1}}\relax
        \dimen0=\the\wd0\dimen1=\the\ht0
        \ifdim\dimen0>\dimen1\dimen2=\dimen0\else\dimen2=\dimen1\fi
        \divide\dimen0 by 2\divide\dimen1 by 2\advance\dimen2 by 5pt
        \put(\strip@pt\dimen0, \strip@pt\dimen1){\circle{\strip@pt\dimen2}}
        \box0}%
}
\newcommand{\mcirc}[1]{%
        \leavevmode\hbox{\setbox0=\hbox{\scriptsize\ensuremath{#1}}\relax
        \dimen0=\the\wd0\dimen1=\the\ht0
        \ifdim\dimen0>\dimen1\dimen2=\dimen0\else\dimen2=\dimen1\fi
        \divide\dimen0 by 2\advance\dimen0 by -0.4pt
        \divide\dimen1 by 2\advance\dimen1 by -1pt\advance\dimen2 by 1.80pt
        \put(\strip@pt\dimen0, \strip@pt\dimen1){\circle{\strip@pt\dimen2}}
        \box0}%
}
\newcommand{\nbox}[1]{\setlength{\fboxsep}{1.0pt}\fbox{\ensuremath{{#1}}}}
\makeatother

\newcommand{\tmgbox}[1]{\psboxit{box .9 setgray fill}
                     {\setlength{\fboxsep}{1pt}%
                      \spbox{\scriptsize \ensuremath{#1}}}}

schmidt_sidorenko_arxiv.bbl
\begin{thebibliography}{10}

\bibitem{feng_tzeng:1985}
G.-L. Feng and K.~K. Tzeng, ``An iterative algorithm of shift-register
  synthesis for multiple sequences,'' {\em Scientia Sinica (Science in China),
  Series A}, vol.~XXVIII, pp.~1222--1232, November 1985.

\bibitem{feng_tzeng:1991}
G.-L. Feng and K.~K. Tzeng, ``A generalization of the {Berlekamp-Massey}
  algorithm for multisequence shift-register synthesis with applications to
  decoding cyclic codes,'' {\em IEEE Trans. Inform. Theory}, vol.~37,
  pp.~1274--1287, September 1991.

\bibitem{wang_zhu_pei:2004}
L.-P. Wang, Y.-F. Zhu, and D.-Y. Pei, ``On the lattice basis reduction
  multisequence synthesis algorithm,'' {\em IEEE Trans. Inform. Theory},
  vol.~50, no.~11, pp.~2905--2910, 2004.

\bibitem{berlekamp:1968}
E.~R. Berlekamp, {\em Algebraic Coding Theory}.
\newblock New York: McGraw--Hill, 1968.

\bibitem{massey:1969}
J.~L. Massey, ``Shift-register synthesis and {BCH} decoding,'' {\em IEEE Trans.
  Inform. Theory}, vol.~15, pp.~122--127, January 1969.

\bibitem{krachkovsky:2003}
V.~Y. Krachkovsky, ``{Reed--Solomon} codes for correcting phased error busts,''
  {\em IEEE Trans. Inform. Theory}, vol.~IT-49, pp.~2975--2984, November 2003.

\bibitem{bleichenbacher_kiayias_young:2003}
D.~Bleichenbacher, A.~Kiayias, and M.~Young, ``Decoding of interleaved {Reed
  Solomon} codes over noisy data,'' in {\em Springer Lecture Notes in Computer
  Science}, vol.~2719, pp.~97--108, January 2003.

\bibitem{justesen_thommesen_hoeholdt:2004}
J.~Justesen, C.~Thommesen, and T.~H{\o}holdt, ``Decoding of concatenated codes
  with interleaved outer codes,'' in {\em Proc. IEEE Intern. Symposium on Inf.
  Theory}, (Chicago, USA), p.~329, 2004.

\bibitem{schmidt_sidorenko_bossert:2005}
G.~Schmidt, V.~R. Sidorenko, and M.~Bossert, ``Error and erasure correction of
  interleaved {Reed--Solomon} codes,'' in {\em Proc. Int. Workshop on Coding
  and Cryptography}, (Bergen, Norway), pp.~20--29, 2005.

\bibitem{brown_minder_shokrollahi:2004}
A.~Brown, L.~Minder, and A.~Shokrollahi, ``Probabilistic decoding of
  interleaved {RS}-codes on the $q$-ary symmetric channel,'' in {\em Proc. IEEE
  Intern. Symposium on Inf. Theory}, (Chicago, USA), p.~327, 2004.

\bibitem{krachkovsky_lee_garg:1998}
V.~Y. Krachkovsky, Y.~X. Lee, and H.~K. Garg, ``Decoding of parallel {RS} codes
  with applications to product and concatenated codes,'' in {\em Proc. IEEE
  Intern. Symposium on Inf. Theory}, (Boston, USA), p.~55, 1998.

\bibitem{krachkovsky_lee:1997}
V.~Y. Krachkovsky and Y.~X. Lee, ``Decoding for interleaved {Reed-Solomon}
  schemes,'' {\em Trans. Magn.}, vol.~33, pp.~2740--2743, September 1997.

\bibitem{schmidt_sidorenko_bossert:2006b}
G.~Schmidt, V.~R. Sidorenko, and M.~Bossert, ``Decoding {Reed--Solomon} codes
  beyond half the minimum distance using shift-register synthesis.'' to appear
  in Proc. IEEE Intern. Symposium on Inf. Theory, 2006.

\bibitem{interlando_palazzo:1995}
J.~C. Interlando and R.~{Palazzo Jr.}, ``Multisequence generation and decoding
  of cyclic codes over {$Z_q$},'' in {\em Proc. IEEE Intern. Symposium on Inf.
  Theory}, (Whistler, Canada), p.~277, 1995.

\bibitem{amand:2004}
M.~A. Armand, ``Multisequence shift register synthesis over commutative rings
  with identity with applications to decoding cyclic codes over integer residue
  rings.,'' {\em IEEE Trans. Inform. Theory}, vol.~50, no.~1, pp.~220--229,
  2004.

\bibitem{sakata:2005}
S.~Sakata, ``Multiple-sequence {BM} algorithm can be replaced by a succession
  of single-sequence {BM} algorithm,'' in {\em Proc. IEEE Intern. Symposium on
  Inf. Theory}, (Adelaide, Australia), pp.~1967--1971, 2005.

\bibitem{ding:1988}
C.~Ding, ``Proof of {Massey's} conjectured algorithm,'' in {\em Lecture Notes
  in Computer Science on Advances in Cryptology -- EUROCRYPT '88},
  (Springer-Verlag New York, Inc. New York, NY, USA), pp.~345--349, 1988.
\newblock ISBN 0-387-50251-3.

\bibitem{sakata:1989}
S.~Sakata, ``N-dimensional {BM} algorithm for multiple arrays and construction
  of multivariate polynomials with preassigned zeros,'' in {\em Proc. AAECC-6},
  vol.~357 of {\em Lecture Notes in Computer Science}, pp.~356--376, Berlin:
  Springer Verlag, 1989.

\bibitem{sakata:1998}
S.~Sakata, ``The {BM} algorithm and the {BMS} algorithm,'' in {\em Codes,
  Curves and Signals: Common Threads in Communications (A. Vardy, ed.)},
  pp.~39--52, Boston: Kluwer Academic Publishers, 1998.
\newblock ISBN 0-792-38374-5.

\end{thebibliography}
