Girsh, Eduard Alekseevich

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de diciembre de 2021; las comprobaciones requieren 4 ediciones .
Eduard Alekseevich Girsh
Fecha de nacimiento 26 de diciembre de 1973 (48 años)( 1973-12-26 )
Lugar de nacimiento Blagovéshchensk
País  Rusia
Esfera científica matemáticas
Lugar de trabajo Departamento de San Petersburgo del Instituto Matemático. V. A. Steklov RAS , Universidad Académica de San Petersburgo - Centro Científico y Educativo de Nanotecnología RAS
alma mater Universidad Estatal de San Petersburgo
Titulo academico Doctor en Ciencias Físicas y Matemáticas
consejero científico E. Ya. Dantsin
Estudiantes SI Nikolenko
Premios y premios Premio de la Fundación Dinastía para Jóvenes Matemáticos
Sitio web logic.pdmi.ras.ru

Eduard Alekseevich Girsh (nacido el 26 de diciembre de 1973 , Blagoveshchensk , URSS ) es un matemático ruso , especialista en informática teórica .

Investigador principal de la rama de San Petersburgo del Instituto Matemático. V. A. Steklova RAS (POMI RAS) , Doctor en Ciencias Físicas y Matemáticas, Profesor de la Academia Rusa de Ciencias , fundador de la serie de conferencias CSR (Simposio Internacional de Ciencias de la Computación en Rusia) [1] , uno de los fundadores de la competencia SAT [ 2] .

Biografía

En 1990 se graduó en el Liceo de Física y Matemáticas No. 239 ( San Petersburgo ) e ingresó a la Facultad de Matemáticas y Mecánica de la Universidad Estatal de San Petersburgo en el Departamento de Apoyo Matemático para Computadores, donde se graduó en 1995.

En 1995 ingresó a la escuela de posgrado del Laboratorio de Lógica Matemática, POMI RAS . En 1998 defendió su tesis doctoral sobre "Estimaciones teóricas del tiempo de ejecución de algoritmos para el problema de la satisfacibilidad de fórmulas booleanas" bajo la supervisión de E. Ya. Dantsin.

En 2011 defendió su tesis doctoral sobre el tema "Complejidad de la lógica proposicional".

Desde 1999 hasta el presente, ha estado trabajando en POMI RAS como investigador líder en el Laboratorio de Lógica Matemática.

De 2000 a 2010, trabajó en la Universidad Estatal de San Petersburgo como profesor asociado en el Departamento de Informática.

De 2008 a 2018, trabajó en el Departamento de Matemáticas y Tecnologías de la Información de la Universidad Académica de San Petersburgo como profesor, actuó como suplente. Jefe del Departamento de Ciencias y supervisó la dirección de formación de los maestros "Informática Teórica".

Fue miembro de los comités de programa de las conferencias ESA, CSR, WoLLIC, IWPEC, SAT, MFCS, STACS. Era miembro del editor. revistas universitarias Journal on Satisfiability, Boolean Modeling and Computation y International Journal of Computer Mathematics.

Actividad científica

Los intereses científicos y los principales resultados de Eduard Alekseevich Hirsch se relacionan con los algoritmos y la teoría de la complejidad computacional . Los principales resultados de E. A. Hirsch incluyen nuevos algoritmos para el problema de la satisfacibilidad de una fórmula booleana , límites inferiores exponenciales para sistemas de prueba semialgebraicos, construcciones de algoritmos heurísticos óptimos.

Algoritmo para el problema de satisfacibilidad k-CNF (k-SAT) propuesto por E. A. Girsh junto con E. Ya. Dantsin, A. Goerdt, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning en 2002 , sigue siendo el algoritmo determinista más rápido para este problema [3] .

En el trabajo conjunto de E. A. Hirsch con D. Yu. Grigoriev y D. V. Pasechnik, se desarrolló la teoría de los sistemas de prueba semialgebraicos, sistemas formales que se utilizan para probar tautologías , que se basan en la representación de expresiones lógicas mediante polinomios. Se han probado los límites inferior y superior para algunos de estos sistemas.

Junto con D. M. Itsykson, desarrolló la teoría de los aceptadores heurísticos: algoritmos de recepción que a veces pueden cometer errores en algunas entradas. Este enfoque nos permite describir una gama más amplia de problemas que los algoritmos tradicionales sin errores. Para los aceptores heurísticos que resuelven algún problema, se prueba la existencia incondicional de un algoritmo óptimo (optimización puntual).

Premios y reconocimientos

Bibliografía

Notas

  1. ↑ Página oficial de las conferencias de Informática en Rusia . Consultado el 8 de diciembre de 2013. Archivado desde el original el 29 de noviembre de 2013.
  2. ↑ Página de competencia del SAT . Consultado el 8 de diciembre de 2013. Archivado desde el original el 12 de febrero de 2005.
  3. ↑ M. Pătraşcu; R.Williams. Sobre la posibilidad de algoritmos SAT más rápidos  (neopr.)  // Actas del XXI Simposio Anual ACM-SIAM sobre Algoritmos Discretos. - 2010. - S. 1065-1075 .
  4. ↑ Premio de la Fundación Dinastía para Jóvenes Matemáticos (enlace inaccesible) . Consultado el 8 de diciembre de 2013. Archivado desde el original el 30 de septiembre de 2013. 
  5. ↑ Mejores trabajos ICALP . Consultado el 8 de diciembre de 2013. Archivado desde el original el 20 de marzo de 2014.
  6. ↑ Ganadores del concurso SAT 2003 . Fecha de acceso: 8 de diciembre de 2013. Archivado desde el original el 4 de marzo de 2016.

Enlaces

  Ir al elemento de Wikidata  sitios temáticos
En catálogos bibliográficos