Girsh, Eduard Alekseevich

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. december 2021; checks kræver 4 redigeringer .
Eduard Alekseevich Girsh
Fødselsdato 26. december 1973 (48 år)( 1973-12-26 )
Fødselssted Blagoveshchensk
Land  Rusland
Videnskabelig sfære matematik
Arbejdsplads Sankt Petersborg Afdeling for Matematisk Institut. V. A. Steklov RAS , St. Petersburg Academic University - Scientific and Educational Center for Nanotechnology RAS
Alma Mater St. Petersburg State University
Akademisk grad Doktor i fysiske og matematiske videnskaber
videnskabelig rådgiver E. Ya. Dantsin
Studerende S. I. Nikolenko
Priser og præmier Dynasty Foundation Award for unge matematikere
Internet side logic.pdmi.ras.ru

Eduard Alekseevich Girsh (født 26. december 1973 , Blagoveshchensk , USSR ) er en russisk matematiker , specialist i teoretisk datalogi .

Ledende forsker i St. Petersborg-afdelingen af ​​Matematisk Institut. V. A. Steklova RAS (POMI RAS) , doktor i fysiske og matematiske videnskaber, professor i det russiske videnskabsakademi , grundlægger af konferenceserien CSR (International Computer Science Symposium in Russia) [1] , en af ​​grundlæggerne af SAT-konkurrencen [ 2] .

Biografi

I 1990 dimitterede han fra Physics and Mathematics Lyceum nr. 239 ( St. Petersburg ) og kom ind på Fakultetet for Matematik og Mekanik ved St. Petersburg State University ved Institut for Matematisk Support for Computere, som han dimitterede i 1995.

I 1995 gik han ind på forskerskolen ved Laboratory of Mathematical Logic, POMI RAS . I 1998 forsvarede han sin ph.d.-afhandling om "Teoretiske estimater af køretiden for algoritmer for problemet med tilfredsstillelse af booleske formler" under supervision af E. Ya. Dantsin.

I 2011 forsvarede han sin doktorafhandling om emnet "Complexity of propositional logic".

Fra 1999 til i dag har han arbejdet hos POMI RAS som førende forsker ved Laboratoriet for Matematisk Logik.

Fra 2000 til 2010 arbejdede han ved St. Petersburg State University som lektor ved Institut for Informatik.

Fra 2008 til 2018 arbejdede han ved Institut for Matematisk og Informationsteknologi ved St. Petersburg Academic University som professor, fungerede som stedfortræder. Leder af Institut for Videnskab og overvågede retningen af ​​uddannelse af mestre "Teoretisk informatik".

Han var medlem af programudvalgene for ESA, CSR, WoLLIC, IWPEC, SAT, MFCS, STACS konferencer. Var medlem af redaktøren. kollegiale tidsskrifter Journal on Satisfiability, Boolean Modeling and Computation og International Journal of Computer Mathematics.

Videnskabelig aktivitet

Eduard Alekseevich Hirschs videnskabelige interesser og hovedresultater relaterer sig til algoritmer og teorien om beregningsmæssig kompleksitet . De vigtigste resultater af E. A. Hirsch inkluderer nye algoritmer til problemet med tilfredsstillelse af en boolsk formel , eksponentielle nedre grænser for semi-algebraiske bevissystemer, konstruktioner af optimale heuristiske algoritmer.

Algoritme for k-CNF-tilfredshedsproblemet (k-SAT) foreslået af E. A. Girsh sammen med E. Ya. Dantsin, A. Goerdt, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning i 2002 , er stadig den hurtigste deterministiske algoritme til dette problem [3] .

I det fælles arbejde af E. A. Hirsch med D. Yu. Grigoriev og D. V. Pasechnik blev teorien om semi-algebraiske bevissystemer udviklet - formelle systemer, der bruges til at bevise tautologier , som er baseret på repræsentationen af ​​logiske udtryk ved hjælp af polynomier. Nedre og øvre grænser er blevet bevist for nogle sådanne systemer.

Sammen med D. M. Itsykson udviklede han teorien om heuristiske acceptorer – modtagelsesalgoritmer, der nogle gange får lov til at lave fejl på nogle input. Denne tilgang giver os mulighed for at beskrive en bredere vifte af problemer end traditionelle fejlfrie algoritmer. For heuristiske acceptorer, der løser et eller andet problem, er den ubetingede eksistens af en optimal algoritme (punktvis optimalitet) bevist.

Priser og priser

Bibliografi

Noter

  1. ↑ Officiel side for Computer Science in Russia-konferencer . Hentet 8. december 2013. Arkiveret fra originalen 29. november 2013.
  2. ↑ SAT konkurrence side . Hentet 8. december 2013. Arkiveret fra originalen 12. februar 2005.
  3. ↑ M. Pătraşcu; R. Williams. Om muligheden for hurtigere SAT-algoritmer  (neopr.)  // Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. - 2010. - S. 1065-1075 .
  4. ↑ Dynasty Foundation Award for Young Mathematicians (utilgængeligt link) . Hentet 8. december 2013. Arkiveret fra originalen 30. september 2013. 
  5. ↑ Bedste ICALP-papirer . Hentet 8. december 2013. Arkiveret fra originalen 20. marts 2014.
  6. ↑ Vindere af SAT-konkurrence 2003 . Dato for adgang: 8. december 2013. Arkiveret fra originalen 4. marts 2016.

Links

  Gå til Wikidata-elementet  Tematiske steder
I bibliografiske kataloger