On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner
|
Descargar SCORM
Este recurso ha sido solicitado 1 veces (0 veces en los últimos 31 días).
Para poder solicitar este recurso debe identificarse como usuario de la biblioteca
|
| |
Ver
Detalles del recurso
|
|
|
On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner
|
| Id. |
20740995 |
| Titulo |
On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner |
| Autor(es) |
Goldwasser, Shafi
|
| Localización |
http://arxiv.org/abs/cs/0212056
Proceedings of the ICM, Beijing 2002, vol. 1, 105--115
|
| Versión |
1.0 |
| Estado |
Final
|
| Descripción |
Madhu Sudan's work spans many areas of computer science theory including
computational complexity theory, the design of efficient algorithms,
algorithmic coding theory, and the theory of program checking and correcting.
Two results of Sudan stand out in the impact they have had on the mathematics
of computation. The first work shows a probabilistic characterization of the
class NP -- those sets for which short and easily checkable proofs of
membership exist, and demonstrates consequences of this characterization to
classifying the complexity of approximation problems. The second work shows a
polynomial time algorithm for list decoding the Reed Solomon error correcting
codes.
This short note will be devoted to describing Sudan's work on
probabilistically checkable proofs -- the so called {\it PCP theorem} and its
implications.
|
| Palabras clave |
Computer Science - Computational Complexity
|
| Tipo de recurso |
Texto Narrativo
|
| Tipo de Interactividad |
Expositivo
|
| Nivel de Interactividad |
muy bajo
|
| Audiencia |
Estudiante
Profesor
Autor
|
| Estructura |
Atomic |
| Coste |
no
|
| Copyright |
sí
|
| Requerimientos técnicos |
Browser: Any
|
| Fecha de contribución |
24-mar-2007 |
| Contacto |
|
|
|
|
|
Valoración de los usuarios
No hay ninguna valoración para este recurso. Sea el primero en
valorar este recurso.
|
|
|
|
