Recently added articles from Foundations and Trends in Theoretical Computer Science:
Algorithmic results in list decoding.(Brief article)
Dec 01, 2006; Guruswami, Venkatesan ... Abstract Error-correcting codes are used to cope with the corruption of data by noise during communication or storage. A code uses an encoding procedure that judiciously introduces redundancy into the data to produce an associated codeword. The redundancy built into the ...
1 Introduction.(Part I General Literature)
Dec 01, 2006; Guruswami, Venkatesan ... 1.1 Codes and noise models Error-correcting codes enable reliable transmission of information over a noisy communication channel. The idea behind error-correcting codes is to encode the message to be transmitted into a longer, redundant string (called a codeword) and then ...
2 Definitions and terminology.(Part I General Literature)
Dec 01, 2006; Guruswami, Venkatesan ... 2.1 Basic coding terminology We review the terminology that will be needed and used throughout the survey. Facility with basic algebra concerning finite fields and field extensions is assumed, though we recap some basic notation and facts at the end of this Chapter. Some comfort ...
3 Combinatorics of list decoding.(Part I General Literature)
Dec 01, 2006; Guruswami, Venkatesan ... In this chapter, we prove combinatorial results concerning list-decodable codes, and study the relation between the list decodability of a code and its other basic parameters such as minimum distance and rate. We will show that every code can be list decoded using small lists beyond half ...
4 Decoding Reed-Solomon codes.(Part I General Literature)
Dec 01, 2006; Guruswami, Venkatesan ... In this chapter, we will present a list decoding algorithm for Reed-Solomon codes that can decode up to the Johnson radius, namely a fraction 1 - [square root of 1 - [delta]] of errors, where [delta] is the relative distance. Since [delta] = 1 - R for RS codes of rate R, this enables us to ...
5 Graph-based list-decodable codes.(Part I General Literature)
Dec 01, 2006; Guruswami, Venkatesan ... In this chapter, we briefly survey some non-algebraic, graph-theoretic approaches to constructing list-decodable codes and decoding them. Besides providing an interesting alternate approach for list decoding, these results also give linear-time encodable and list-decodable codes. The rate ...
6 Folded Reed-Solomon codes.(Part II Achieving List Decoding Capacity)
Dec 01, 2006; Guruswami, Venkatesan ... This part of the survey gives some exciting recent progress that achieves the capacity of list decoding over large alphabets. In this chapter, we present a simple variant of Reed-Solomon codes called folded Reed-Solomon codes for which we can beat the 1 - [square root of R] decoding ...
7 Achieving capacity over bounded alphabets.(Part II Achieving List Decoding Capacity)
Dec 01, 2006; Guruswami, Venkatesan ... The capacity-achieving codes from the previous chapter have two main shortcomings: (i) their alphabet size is a large polynomial in the block length, and (ii) the bound on worst-case list size as well as decoding time complexity grows as [n.sup.[omega](1/[epsilon])], where [epsilon] is the ...
8 Concluding thoughts.(Part II Achieving List Decoding Capacity)
Dec 01, 2006; Guruswami, Venkatesan ... We have surveyed the topic of list decoding with a focus on the recent advances in decoding algorithms for Reed-Solomon codes and close variants, culminating with a presentation of how to achieve the list decoding capacity over large alphabets. We conclude by mentioning some interesting ...
Acknowledgments.(Part II Achieving List Decoding Capacity)
Dec 01, 2006; Guruswami, Venkatesan ... The author thanks Madhu Sudan and the anonymous reviewer for a careful reading of the manuscript and for their very useful comments on improving the quality and coverage of the ...
References.(Part II Achieving List Decoding Capacity)
Dec 01, 2006; Guruswami, Venkatesan ... [1] N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth, "Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs," IEEE Transactions on Information Theory, vol. 38, pp. 509-516, 1992. [2] N. Alon and F. R. K. Chung, "Explicit construction ...
A survey of lower bounds for satisfiability and related problems.(Author abstract)
Dec 15, 2006; van Melkebeek, Dieter ... Abstract Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was ...
1 Introduction.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... Satisfiability is the problem of deciding whether a given Boolean formula has at least one satisfying assignment. It is the first problem that was shown to be NP-complete, and is possibly the most commonly studied NP-complete problem, both for its theoretical properties and its ...
2 Preliminaries.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... This chapter describes the machine models we use and introduces our notation for complexity classes. It establishes natural complete problems which capture the complexity of some of the models in a very tight way, e.g., satisfiability in the case of nondeterministic computations. ...
3 Common structure of the arguments.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... This chapter describes the common fabric of the lower bounds presented in this survey. All of the arguments share the same high-level structure, which can be characterized as indirect diagonalization. Indirect diagonalization is a technique to separate complexity classes. In the ...
4 Deterministic algorithms.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... In this chapter, we discuss lower bounds on deterministic machines. We first derive the results for nondeterministic linear time, implying lower bounds for satisfiability, and then cover closely related classes and corresponding problems. 4.1 Satisfiability Our goal ...
5 Nondeterministic algorithms.(A Survey of Lower Bounds for Satifiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... In this chapter, we discuss how the lower bound arguments from Section 4.1 for deterministic machines can be adapted to co-nondeterministic machines, resulting in the lower bounds for tautologies on nondeterministic machines as stated in Theorem 1.5. Following the paradigm of ...
6 Somewhat-nonuniform algorithms.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... This chapter investigates what the paradigm of indirect diagonalization from Chapter 3 can say about lower bounds for satisfiability in nonuniform models. We revisit the results from previous sections and show that, modulo some loss in parameters, certain uniformity requirements can be ...
7 Randomized algorithms.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... This chapter describes the known lower bounds on randomized machines with bounded error. The simplest problems for which we have nontrivial results are [[summation].sub.2]SAT in the case of two-sided error, and tautologies in the case of one-sided error. We first discuss those results and ...
8 Quantum algorithms.(A Survey of Lower Bounds for Satisfiability and Related Problems)
Dec 15, 2006; van Melkebeek, Dieter ... This chapter describes the known time and space lower bounds on quantum models, namely for MajMajSAT. They follow from similar lower bounds on randomized machines with unbounded error. We first describe the latter results and then show how they translate to the quantum setting. ...
