Akademik Veri Yönetim Sistemi
THEORETICAL COMPUTER SCIENCE, cilt.520, ss.111-123, 2014 (SCI-Expanded)
Probabilistic simultaneous polynomial reconstruction algorithm of Bleichenbacher, Kiayias, and Yung is extended to the polynomials whose degrees are allowed to be distinct. Specifically, for a finite field F, positive integers n, r, t and distinct elements z(1), z(2), ... , z(n) is an element of F, we present a probabilistic algorithm which can recover polynomials p(1), p(2), p(r) is an element of F[x] of degree less than k(1), k(2), ... , k(r) respectively for a given instance < y(i), (1, ... ,) y(i,r)>(n)(i=1) satisfying p(i)(z(i)) = y(i,l) for all I is an element of {1,2, ... , r} and for all i is an element of I subset of {1,2, ... , n} such that vertical bar I vertical bar = t with probability at least 1 - n-t/vertical bar F vertical bar and with time complexity at most 0(rn(4)) if t >= max{k(1), k(2), ... , k(r), n+Sigma(r)(j=1)k(j)/r+1}. Next, by using this algorithm, we present a probabilistic decoder for interleaved Reed-Solomon codes. It is observed that interleaved Reed-Solomon codes over F with rate R can be decoded up to burst error rate r/r+1 (1 - R) probabilistically for an interleaving parameter r. Then, it is proved that q-folded Hermitian codes over F-q2q with rate R can be decoded up to error rate q/q+1 (1 - R) probabilistically. (C) 2013 Elsevier B.V. All rights reserved.