-
La informática teórica aborda los fundamentos matemáticos del campo de la computación. Plantea preguntas como: "¿Este problema puede resolverse mediante computación?" y "Si este problema puede resolverse mediante computación, ¿cuánto tiempo y cuántos recursos se requieren?". También explora cómo diseñar algoritmos eficientes. Todas las tecnologías de computación que influyen en nuestra vida son posibles gracias a los algoritmos. Comprender los principios de los algoritmos potentes y eficientes profundiza nuestro entendimiento no solo de la informática, sino también de las leyes de la naturaleza. La informática teórica es conocida como un campo que presenta interesantes desafíos intelectuales y que, a menudo, no está relacionado de manera directa con la mejora de aplicaciones prácticas de la computación; sin embargo, las innovaciones de investigación en esta área han impulsado avances en casi todos los campos, como la criptografía, la biología computacional, el diseño de redes, el aprendizaje automático y la computación cuántica.
-
En esencia, las computadoras son sistemas deterministas. Si se aplica un conjunto de instrucciones algorítmicas a una entrada específica, el cálculo queda determinado de forma única y, en particular, también la salida. Es decir, los algoritmos deterministas siguen patrones predecibles. En cambio, la aleatoriedad implica la ausencia de patrones bien definidos o de predictibilidad en los eventos/resultados. Como el mundo en el que vivimos parece estar lleno de eventos aleatorios —como los sistemas meteorológicos o los fenómenos biológicos y cuánticos—, los científicos de la computación han reforzado los algoritmos para que puedan realizar elecciones aleatorias durante el proceso de cálculo, con el fin de mejorar su eficiencia. De hecho, muchos problemas para los que no se conocen algoritmos deterministas eficientes han sido resueltos eficientemente mediante algoritmos probabilísticos (aunque con una pequeña probabilidad de error, que puede reducirse eficientemente). Pero, ¿es la aleatoriedad algo esencial, o puede eliminarse? ¿Qué calidad de aleatoriedad se necesita para el éxito de los algoritmos probabilísticos?
-
El Dr. Avi Wigderson ha liderado la investigación en informática teórica durante 40 años y ha realizado contribuciones fundamentales para entender el papel de la aleatoriedad y la seudoaleatoriedad en la computación. Los científicos de la computación descubrieron una conexión notable entre la aleatoriedad y la dificultad computacional (la identificación de problemas naturales para los que no existen algoritmos eficientes). El Dr. Wigderson, junto con sus colegas, llevó a cabo una serie de trabajos sumamente influyentes sobre el intercambio de dificultad por aleatoriedad. Demostraron que, bajo supuestos computacionales estándar y ampliamente aceptados, todos los algoritmos probabilísticos de tiempo polinomial pueden eliminar eficientemente la aleatoriedad (es decir, pueden volverse completamente deterministas). En otras palabras, la aleatoriedad no es esencial para la computación eficiente. Esta serie de investigaciones revolucionó nuestra comprensión del papel de la aleatoriedad en la computación y la manera en que pensamos sobre ella.
Contribuciones del Dr. Wigderson
-
"Hardness vs. Randomness" (coescrito con Noam Nisan): este artículo introdujo, entre otras cosas, un nuevo tipo de generador seudoaleatorio y demostró que es posible una simulación determinista eficiente de algoritmos aleatorizados bajo supuestos mucho más débiles que los conocidos hasta entonces.
-
"BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (coescrito con László Babai, Lance Fortnow y Noam Nisan): este artículo demostró, usando "hardness amplification", que bounded-error probabilistic polynomial time (BPP) puede simularse en tiempo subexponencial para infinitas longitudes de entrada bajo supuestos más débiles.
-
"P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (coescrito con Russell Impagliazzo): este artículo presentó un generador seudoaleatorio más potente con una compensación entre dificultad y aleatoriedad esencialmente óptima.
-
Más allá de sus investigaciones relacionadas con la aleatoriedad, el Dr. Wigderson también ha ejercido liderazgo intelectual en varias otras áreas de la informática teórica, como las pruebas interactivas con múltiples verificadores, la criptografía y la complejidad de circuitos.
Opinión de GN⁺
-
El trabajo de Wigderson, que demostró desde una perspectiva matemática la relación entre la aleatoriedad y la complejidad computacional, tiene gran relevancia en cuanto a la intersección entre la informática y las matemáticas. En particular, demostrar que muchos algoritmos que dependían de la aleatoriedad en realidad pueden implementarse de forma idéntica de manera determinista se considera una apertura de nuevos horizontes para la informática.
-
Además, el enfoque matemático sobre la relación entre eficiencia y dificultad también parece perfilarse como un tema importante de investigación en informática teórica. La idea de que, cuanto más difícil es un problema, mayor podría ser la posibilidad de que exista un algoritmo más eficiente en proporción a esa dificultad es una intuición poco evidente.
-
Por otro lado, el hecho de que el profesor Wigderson haya enfatizado la convergencia entre las matemáticas y la informática para el desarrollo de la informática teórica, y que también se haya esforzado en formar a nuevas generaciones, parece ser un gran ejemplo para la continuidad académica. En particular, su trayectoria de haber recibido tanto el Premio Abel de matemáticas como el Premio Turing de ciencias de la computación puede considerarse un caso simbólico que muestra la importancia de la informática teórica.
1 comentarios
Comentarios de Hacker News
Avi Wigderson recibió el ACM A.M. Turing Award 2023. Fue reconocido por sus contribuciones fundamentales a la teoría de la computación, en particular por reformular la comprensión del papel de la aleatoriedad en la computación, y por ejercer liderazgo intelectual durante décadas en el campo de las ciencias de la computación teóricas.
Wigderson ha sido una figura líder en áreas como teoría de la complejidad computacional, algoritmos y optimización, aleatoriedad y criptografía, computación paralela y distribuida, combinatoria y teoría de grafos, además de servir como vínculo entre las ciencias de la computación teóricas y las matemáticas y las ciencias.
Uno de los principales logros de Wigderson fue descubrir la sorprendente relación entre la aleatoriedad y la dificultad computacional. Su investigación reveló que la aleatoriedad no es necesariamente indispensable para la computación eficiente.
En 2021 también recibió el Abel Prize, lo que le da una trayectoria singular al haber obtenido los máximos honores tanto en matemáticas teóricas/abstractas como en ciencias de la computación.
Su libro "Mathematics and Computation" fue publicado recientemente y está recibiendo muy buenas críticas.
Según sus resultados de investigación, si una proposición puede demostrarse, entonces también es posible una prueba de conocimiento cero (
zero-knowledge proof), y al aplicar seudonúmeros aleatorios a algoritmos probabilísticos se puede obtener un algoritmo determinista eficiente para el mismo problema. Esto sugiere que podría reducirse en gran medida la complejidad de modelos de computación probabilística, como los usados en IA.