The ACM Special Interest Group on Applied Computing is dedicated to further the interests of computing professionals engaged in the design and development of new computing applications, interdisciplinary applications areas, and applied research. The conference provides a forum for discussion and exchange of new ideas addressing computational algorithms and complex applications. This goal is reflected in the wide spectrum of application areas and tutorials designed to provide a variety of discussion topics during this event. 收起

The ACM Special Interest Group on Applied Computing is dedicated to further the interests of computing professionals engaged in the design and development of new computing applications, interdisciplinary applications areas, and applied research. The conference provides a forum for discussion and exchange of new ideas addressing computational algorithms and complex applications. This goal is reflected in the wide spectrum of application areas and tutorials designed to provide a variety of discussion topics during this event. 收起

1. Given n distinct elements α1,...,αn from a field F, and n subsets S1,...,Sn of F each of size at

1. Given n distinct elements α1,...,αn from a field F, and n subsets S1,...,Sn of F each of size at most l, the list decoding algorithm of Guruswami and Sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(αi) ∈ Si for every i, as long as l < ? n/k ?. We show that the performance of this algorithm is the best possible in a strong sense; specifically, we show that when l = ? n/k ?, the list of output polynomials can be super-polynomially large in n. One way to interpret our result is the following. The algorithm in [7] can, when given as input $n'$ distinct pairs (βi,∈i) ∈ F² (the βi's need not be distinct), find and output all degree k polynomials p such that p(βi) = γi for at least $t$ values of i, provided t > √k n'. By our result, an improvement to the Reed-Solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the βi's (for example, their (near) distinctness).
2. For Reed-Solomon codes of block length $n$ and dimension k where k = n^δ for small enough δ, we exhibit an explicit received word r with a super-polynomial number of Reed-Solomon codewords that agree with it on $(2 - ε) k locations, for any desired ε > 0 (we note agreement of k is trivial to achieve). Such a bound was known earlier only for a non-explicit center. We remark that finding explicit bad list decoding configurations is of significant interest --- for example the best known rate vs. distance trade-off is based on a bad list decoding configuration for algebraic-geometric codes [14] which is unfortunately not explicitly known.

1. Given n distinct elements α1,...,αn from a field F, and n subsets S1,...,Sn of F each of size a

1. Given n distinct elements α1,...,αn from a field F, and n subsets S1,...,Sn of F each of size at most l, the list decoding algorithm of Guruswami and Sudan [7] can in polynomial time output all polynomials p of degree at most k which satisfy p(αi) ∈ Si for every i, as long as l < ⌈ n/k ⌉. We show that the performance of this algorithm is the best possible in a strong sense; specifically, we show that when l = ⌈ n/k ⌉, the list of output polynomials can be super-polynomially large in n. One way to interpret our result is the following. The algorithm in [7] can, when given as input $n'$ distinct pairs (βi,∈i) ∈ F² (the βi's need not be distinct), find and output all degree k polynomials p such that p(βi) = γi for at least $t$ values of i, provided t > √k n'. By our result, an improvement to the Reed-Solomon list decoder of [7] that works with slightly smaller agreement, say t > √kn' - k/2, can only be obtained by exploiting some property of the βi's (for example, their (near) distinctness).
2. For Reed-Solomon codes of block length $n$ and dimension k where k = n^δ for small enough δ, we exhibit an explicit received word r with a super-polynomial number of Reed-Solomon codewords that agree with it on $(2 - ε) k locations, for any desired ε > 0 (we note agreement of k is trivial to achieve). Such a bound was known earlier only for a non-explicit center. We remark that finding explicit bad list decoding configurations is of significant interest --- for example the best known rate vs. distance trade-off is based on a bad list decoding configuration for algebraic-geometric codes [14] which is unfortunately not explicitly known.