Girsh, Eduard Alekseevich

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 december 2021; kontroller kräver 4 redigeringar .
Eduard Alekseevich Girsh
Födelsedatum 26 december 1973 (48 år)( 1973-12-26 )
Födelseort Blagoveshchensk
Land  Ryssland
Vetenskaplig sfär matte
Arbetsplats Sankt-Petersburg Institutionen för det matematiska institutet. V. A. Steklov RAS , St. Petersburg Academic University - Scientific and Educational Center for Nanotechnology RAS
Alma mater St Petersburg State University
Akademisk examen Doktor i fysikaliska och matematiska vetenskaper
vetenskaplig rådgivare E. Ya. Dantsin
Studenter S. I. Nikolenko
Utmärkelser och priser Dynasty Foundation Award för unga matematiker
Hemsida logic.pdmi.ras.ru

Eduard Alekseevich Girsh (född 26 december 1973 , Blagoveshchensk , USSR ) är en rysk matematiker , specialist på teoretisk datavetenskap .

Ledande forskare vid Mathematical Institutes filial i St. Petersburg. V. A. Steklova RAS (POMI RAS) , doktor i fysikaliska och matematiska vetenskaper, professor i Ryska vetenskapsakademin , grundare av konferensserien CSR (International Computer Science Symposium in Russia) [1] , en av grundarna av SAT-tävlingen [ 2] .

Biografi

1990 tog han examen från Physics and Mathematics Lyceum nr. 239 ( St. Petersburg ) och gick in på fakulteten för matematik och mekanik vid St. Petersburg State University vid Institutionen för matematiskt stöd för datorer, som han tog examen 1995.

1995 gick han in på forskarskolan vid Laboratory of Mathematical Logic, POMI RAS . 1998 försvarade han sin doktorsavhandling om "Teoretiska uppskattningar av körtiden för algoritmer för problemet med tillfredsställelse av booleska formler" under ledning av E. Ya. Dantsin.

2011 disputerade han på sin doktorsavhandling på ämnet "Complexity of propositional logic".

Från 1999 till idag har han arbetat på POMI RAS som en ledande forskare vid Laboratory of Mathematical Logic.

Från 2000 till 2010 arbetade han vid St. Petersburg State University som docent vid institutionen för informatik.

Från 2008 till 2018 arbetade han vid Institutionen för matematisk och informationsteknologi vid St. Petersburg Academic University som professor, fungerade som suppleant. Chef för Institutionen för naturvetenskap och övervakade riktningen för utbildning av magister "teoretisk informatik".

Han var medlem i programkommittéerna för ESA, CSR, WoLLIC, IWPEC, SAT, MFCS, STACS konferenser. Var medlem i redaktören. kollegiala tidskrifter Journal on Satisfiability, Boolean Modeling and Computation och International Journal of Computer Mathematics.

Vetenskaplig verksamhet

Eduard Alekseevich Hirschs vetenskapliga intressen och huvudsakliga resultat relaterar till algoritmer och teorin om beräkningskomplexitet . Huvudresultaten av E. A. Hirsch inkluderar nya algoritmer för problemet med tillfredsställelse av en boolesk formel , exponentiella nedre gränser för semi-algebraiska bevissystem, konstruktioner av optimala heuristiska algoritmer.

Algoritm för k-CNF satisfiability problem (k-SAT) föreslagen av E. A. Girsh tillsammans med E. Ya. Dantsin, A. Goerdt, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schoning 2002 , är fortfarande den snabbaste deterministiska algoritmen för detta problem [3] .

I det gemensamma arbetet av E. A. Hirsch med D. Yu. Grigoriev och D. V. Pasechnik utvecklades teorin om semi-algebraiska bevissystem - formella system som används för att bevisa tautologier , som är baserade på representation av logiska uttryck med hjälp av polynom. Nedre och övre gränser har bevisats för vissa sådana system.

Tillsammans med D. M. Itsykson utvecklade han teorin om heuristiska acceptorer – mottagningsalgoritmer som ibland tillåts göra misstag på vissa ingångar. Detta tillvägagångssätt tillåter oss att beskriva ett bredare spektrum av problem än traditionella felfria algoritmer. För heuristiska acceptorer som löser något problem bevisas den ovillkorliga existensen av en optimal algoritm (punktvis optimalitet).

Priser och utmärkelser

Bibliografi

Anteckningar

  1. ↑ Officiell sida för datavetenskap i Ryssland-konferenser . Hämtad 8 december 2013. Arkiverad från originalet 29 november 2013.
  2. ↑ SAT-tävlingssida . Hämtad 8 december 2013. Arkiverad från originalet 12 februari 2005.
  3. ↑ M. Pătraşcu; R. Williams. Om möjligheten till snabbare SAT-algoritmer  (neopr.)  // Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. - 2010. - S. 1065-1075 .
  4. ↑ Dynasty Foundation Award för unga matematiker (otillgänglig länk) . Hämtad 8 december 2013. Arkiverad från originalet 30 september 2013. 
  5. ↑ Bästa ICALP-papper . Hämtad 8 december 2013. Arkiverad från originalet 20 mars 2014.
  6. ↑ 2003 SAT-tävlingsvinnare . Tillträdesdatum: 8 december 2013. Arkiverad från originalet 4 mars 2016.

Länkar

  Gå till Wikidata-objektet  Tematiska platser
I bibliografiska kataloger