stringtranslate.com

Pedro Gacs

Péter Gács (pronunciación húngara: ['pe:ter 'ga:tʃ]; nacido el 9 de mayo de 1947), también conocido profesionalmente como Peter Gacs , es un matemático y científico informático húngaro - estadounidense , profesor y miembro externo de la Academia Húngara de Ciencias. Es muy conocido por su trabajo en computación confiable, aleatoriedad en computación, complejidad algorítmica , probabilidad algorítmica y teoría de la información .

Carrera

Peter Gacs asistió a la escuela secundaria en su ciudad natal, luego obtuvo un diploma (MS) en la Universidad Loránd Eötvös en Budapest en 1970. Gacs comenzó su carrera como investigador en el Instituto de Matemáticas Aplicadas de la Academia Húngara de Ciencias . [1] Obtuvo su doctorado de la Universidad Goethe de Frankfurt en 1978. A lo largo de sus estudios tuvo la oportunidad de visitar la Universidad Estatal de Moscú y trabajar con Andrey Kolmogorov y su estudiante Leonid A. Levin . Hasta 1979 fue investigador visitante asociado en la Universidad de Stanford . Fue profesor asistente en la Universidad de Rochester desde 1980 hasta 1984, cuando se trasladó a la Universidad de Boston , donde recibió la titularidad en 1985. Ha sido profesor titular desde 1992. [2]

Trabajar

Gacs ha hecho contribuciones en muchos campos de la informática. Fueron Gács y László Lovász quienes primero llevaron el método del elipsoide a la atención de la comunidad internacional en agosto de 1979 al publicar las pruebas y algunas mejoras del mismo. [3] [4] [5] Gacs también hizo contribuciones en el teorema de Sipser-Lautemann . [6] Su principal contribución y enfoque de investigación se centraron en los autómatas celulares y la complejidad de Kolmogorov.

Trabajos sobre autómatas celulares

Su contribución más importante en el campo de los autómatas celulares , además de la regla GKL (regla de Gacs-Kurdyumov-Levin), es la construcción de un autómata celular unidimensional fiable, presentando así un contraejemplo a la conjetura de tasas positivas . [7] La ​​construcción que propuso es multiescalar y compleja. [8] Más tarde, la misma técnica se utilizó para la construcción de conjuntos de teselado aperiódicos. [9]

Trabajo sobre teoría de la información algorítmica y complejidad de Kolmogorov

Gacs fue autor de varios artículos importantes en el campo de la teoría de la información algorítmica y sobre la complejidad de Kolmogorov . Junto con Leonid A. Levin , estableció propiedades básicas de la complejidad de prefijo, incluyendo la fórmula para la complejidad de pares [10] y para las deficiencias de aleatoriedad, incluyendo el resultado redescubierto más tarde y ahora conocido como lema de exceso amplio . [11] [12] Demostró que la correspondencia entre complejidad y probabilidad a priori que se cumple para la complejidad de prefijo ya no es cierta para la complejidad monótona y la probabilidad a priori continua. [13] [14] En la teoría relacionada de la aleatoriedad algorítmica, demostró que cada secuencia es reducible por Turing a una aleatoria (el resultado ahora conocido como teorema de Gacs-Kucera, ya que fue demostrado independientemente por Antonin Kucera). [14] Más tarde, él (con coautores) introdujo la noción de distancia algorítmica y demostró su conexión con la complejidad condicional. [15] [14]

Fue uno de los pioneros de la estadística algorítmica, [16] introdujo una de las versiones cuánticas para la complejidad algorítmica, [17] estudió las propiedades de la aleatoriedad algorítmica para espacios generales [18] [19] y clases generales de medidas. [20] Algunos de estos resultados se tratan en sus estudios de la teoría de la información algorítmica. [21] [22] También demostró resultados sobre el límite entre la teoría de la información clásica y algorítmica: el ejemplo seminal que muestra la diferencia entre información común y mutua (con János Körner ). [23] Junto con Rudolf Ahlswede y Körner, demostró el lema de la explosión . [24]

Referencias

  1. ^ "Lista de personas que trabajaron en el Instituto Renyi". Instituto de Matemáticas Alfréd Rényi . Consultado el 5 de diciembre de 2020 .
  2. ^ "Bio". Departamento de Informática de la Universidad de Boston . Consultado el 5 de diciembre de 2020 .
  3. ^ Kolata, Gina Bari (2 de noviembre de 1979). "Matemáticos asombrados por el descubrimiento ruso". Science . 206 (4418): 545–546. Bibcode :1979Sci...206..545B. doi :10.1126/science.206.4418.545. JSTOR  1749236. PMID  17759415.
  4. ^ Gács, Peter; Lovász, Laszlo (1981), König, H.; Korte, B.; Ritter, K. (eds.), "Algoritmo de Khachiyan para programación lineal", Programación matemática en Oberwolfach , vol. 14, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 61–68, doi :10.1007/bfb0120921, ISBN 978-3-642-00805-4, consultado el 27 de noviembre de 2020
  5. ^ Shenitzer, Abe y John Stillwell, eds. Evoluciones matemáticas . MAA, 2002.
  6. ^ Lautemann, Clemens (8 de noviembre de 1983). "BPP y la jerarquía polinómica". Information Processing Letters . 17 (4): 215–217. doi :10.1016/0020-0190(83)90044-3. ISSN  0020-0190.
  7. ^ Gács, Peter (1 de abril de 2001). "Autómatas celulares fiables con autoorganización". Revista de física estadística . 103 (1): 45–267. arXiv : math/0003117 . Código Bibliográfico :2001JSP...103...45G. doi :10.1023/A:1004823720305. ISSN  1572-9613. S2CID  2434448.
  8. ^ Gray, Lawrence F. (1 de abril de 2001). "Guía del lector sobre el artículo "Positive Rates" de Gacs". Revista de física estadística . 103 (1): 1–44. Bibcode :2001JSP...103....1G. doi :10.1023/A:1004824203467. ISSN  1572-9613. S2CID  14256431.
  9. ^ Durand, Bruno; Romashchenko, Andrei; Shen, Alexander (1 de mayo de 2012). "Conjuntos de mosaicos de punto fijo y sus aplicaciones". Revista de Ciencias de la Computación y de Sistemas . En conmemoración de Amir Pnueli. 78 (3): 731–764. arXiv : 0910.2415 . doi : 10.1016/j.jcss.2011.11.001 . ISSN  0022-0000. S2CID  3024979.
  10. ^ Peter Gacs. Sobre la simetría de la información algorítmica. Doklady Akademii Nauk SSSR , 218(6):1265–1267, 1974. En ruso.
  11. ^ Peter Gacs. Expresiones exactas para algunas pruebas de aleatoriedad. Z. Math. Log. Grdl. M. , 26:385–394, 1980.
  12. ^ Downey, Rodney G. y Denis R. Hirschfeldt. Aleatoriedad y complejidad algorítmicas. Springer, 2010
  13. ^ Peter Gacs. Sobre la relación entre la complejidad descriptiva y la probabilidad algorítmica. Theoretical Computer Science, 22:71–93, 1983. Versión corta: Proc. 22nd IEEE FOCS (1981) 296-303
  14. ^ abc Li, Ming y Paul Vitányi. Introducción a la complejidad de Kolmogorov y sus aplicaciones. Vol. 3. Nueva York: Springer, 2008.
  15. ^ Charles H. Bennett, Peter Gacs, Ming Li, Paul MB Vitanyi y Woiciech Zurek. Distancia de la información. IEEE Transactions on Information Theory , 44(4):1407–1423, 1998. (La versión preliminar apareció en STOC'97, arXiv:1006.3520.) Según Google Scholar, este artículo ha sido citado 687 veces hasta abril de 2021 [1]
  16. ^ Peter Gacs, John Tromp y Paul MB Vitanyi. Estadística algorítmica. IEEE Transactions on Information Theory , 47:2443–2463, 2001. arXiv:math/0006233[math.PR]. Versión corta con título similar en Algorithmic Learning Theory , LNCS 1968/2000.
  17. ^ Aditi Dhagat, Peter Gacs y Peter Winkler. Sobre jugar a las "veinte preguntas" con un mentiroso. En Actas del tercer simposio anual ACM-SIAM sobre algoritmos discretos , SODA'92, páginas 16-22, Filadelfia, PA, EE. UU., 1992. Sociedad de Matemáticas Industriales y Aplicadas.
  18. ^ Peter Gacs. Prueba uniforme de aleatoriedad algorítmica en un espacio general. Theoretical Computer Science , 341(1-3):91–137, 2005.
  19. ^ Peter Gacs, Mathieu Hoyrup y Cristóbal Rojas. Aleatoriedad en espacios de probabilidad computable: un punto de vista dinámico. Theory of Computing Systems , 48:465–485, 2011. 10.1007/s00224-010-9263-x, arXiv:0902.1939. También apareció en STACS 2009.
  20. ^ Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas y Alexander Shen. Aleatoriedad con respecto a una clase de medidas. Actas del Instituto Steklov de Matemáticas , 274(1):34–89, 2011. En inglés y ruso, también en arXiv:1103.1529.
  21. ^ Peter Gacs. Notas de clase sobre complejidad descriptiva y aleatoriedad. Informe técnico, Universidad de Boston, Departamento de Ciencias Informáticas, Boston, MA 02215, 2009. www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf.
  22. ^ Thomas M. Cover, Peter Gacs y Robert M. Gray. Contribuciones de Kolmogorov a la teoría de la información y la complejidad algorítmica. The Annals of Probability , 17(3):840–865, 1989.
  23. ^ Peter Gacs y Janos Korner. La información común es mucho menor que la información mutua. Problemas de control e investigación, 2:149–162, 1973.
  24. ^ Ahlswede, Gacs, Körner Límites de probabilidades condicionales con aplicaciones en comunicación multiusuario, Z. Wahrsch. y Verw. Gebiete 34, 1976, 157-177