Girsh, Eduard Alekseevič

Eduard Alekseevič Girsh (narozený 26. prosince 1973 , Blagoveščensk , SSSR ) je ruský matematik , specialista na teoretickou informatiku .

Přední vědecký pracovník petrohradské pobočky Matematického institutu. V. A. Steklova RAS (POMI RAS) , doktorka fyzikálních a matematických věd, profesorka Ruské akademie věd , zakladatelka série konferencí CSR (International Computer Science Symposium in Russia) [1] , jeden ze zakladatelů soutěže SAT [ 2] .

Životopis

V roce 1990 absolvoval Fyzikální a matematické lyceum č. 239 ( Petrohrad ) a nastoupil na Matematicko-mechanickou fakultu St. Petersburg State University na katedře matematické podpory počítačů, kterou absolvoval v roce 1995.

V roce 1995 nastoupil na postgraduální školu Laboratoře matematické logiky POMI RAS . V roce 1998 obhájil doktorskou práci na téma "Teoretické odhady doby běhu algoritmů pro problém splnitelnosti booleovských vzorců" pod vedením E. Ya.Dantsina.

V roce 2011 obhájil doktorskou disertační práci na téma „Složitost výrokové logiky“.

Od roku 1999 do současnosti působí v POMI RAS jako vedoucí vědecký pracovník Laboratoře matematické logiky.

V letech 2000 až 2010 působil na St. Petersburg State University jako docent na katedře informatiky.

V letech 2008 až 2018 působil na katedře matematických a informačních technologií Petrohradské akademické univerzity jako profesor, působil jako zástupce. Vedoucí katedry vědy a dohlížel na směr přípravy magistrů "Teoretická informatika".

Byl členem programových výborů konferencí ESA, CSR, WoLLIC, IWPEC, SAT, MFCS, STACS. Byl členem redakce. vysokoškolské časopisy Journal on Satisfiability, Boolean Modeling and Computation a International Journal of Computer Mathematics.

Vědecká činnost

Vědecké zájmy a hlavní výsledky Eduarda Alekseeviče Hirsche se týkají algoritmů a teorie výpočetní složitosti . Mezi hlavní výsledky E. A. Hirsche patří nové algoritmy pro problém splnitelnosti booleovského vzorce , exponenciální dolní odhady pro semialgebraické důkazové systémy, konstrukce optimálních heuristických algoritmů.

Algoritmus pro problém splnitelnosti k-CNF (k-SAT) navržený E. A. Girshem spolu s E. Ya. Dantsinem, A. Goerdtem, R. Kannanem, J. Kleinbergem, C. Papadimitriou, P. Raghavanem, U. Schoningem v roce 2002 , je stále nejrychlejším deterministickým algoritmem pro tento problém [3] .

Ve společné práci E. A. Hirsche s D. Yu Grigorievem a D. V. Pasechnikem byla vyvinuta teorie semialgebraických důkazových systémů - formálních systémů, které se používají k dokazování tautologií , které jsou založeny na reprezentaci logických výrazů pomocí polynomů. U některých takových systémů byla prokázána dolní a horní hranice.

Spolu s D. M. Itsyksonem vyvinul teorii heuristických akceptorů - přijímacích algoritmů, které mohou někdy dělat chyby na některých vstupech. Tento přístup nám umožňuje popsat širší rozsah problémů než tradiční bezchybné algoritmy. Pro heuristické akceptory řešící nějaký problém je prokázána bezpodmínečná existence optimálního algoritmu (bodová optimalita).

Ceny a ocenění

• Cena nadace Dynasty pro mladé matematiky [4]
• Cena za nejlepší článek Evropské asociace pro teoretickou informatiku (EATCS) [5]
• Ceny na mezinárodních soutěžích programů na řešení problému splnitelnosti booleovských vzorců (2002-2003 - cena za nejmenší nevyřešený nesplnitelný vzorec, 2003 - cena za nejlepší program v kategorii náhodných vzorců) [6] .

Bibliografie

• EA Hirsch; D. Itsykson; I. Monachov; Malý. O optimálních heuristických randomizovaných semirozhodovacích postupech s aplikacemi pro důkaz složitosti a kryptografie  //  Teorie výpočetních systémů : deník. - Springer, 2012. - Sv. 51 . - S. 179-195 . - doi : 10.1007/s00224-011-9354-3 .
• E. Dantsin; A. Goerdt; EA Hirsch; R. Kannan; J. Kleinberg; C. papadimitriou; P. Raghavan; U. Schoning.  A Deterministický (2−2 / (k+1))^n Algoritmus pro k-SAT založený na místním vyhledávání  // Teoretická informatika : deník. - Elsevier, 2002. - Sv. 289/1 . - str. 69-83 . - doi : 10.1016/S0304-3975(01)00174-8 .
• EA Hirsch. Nové horní hranice nejhorších případů pro SAT  //  Journal of Automated Reasoning : deník. - Kluwer Academic Publishers, 2000. - Sv. 24(4) . - S. 397-420 . - doi : 10.1023/A:1006340920104 .
• D. Grigorjev; EA Hirsch; DV Pasechnik. Složitost semi-algebraických důkazů  (neopr.)  // Moscow Mathematical Journal. - 2002. - T. 2 (4) . - S. 647-679 . - doi : 10.1007/3-540-45841-7_34 .
• E. Dantsin; EA Hirsch. Horní hranice nejhoršího případu // Handbook of Satisfiability. Hranice v umělé inteligenci a  aplikacích . — IOS Press, 2009. - Sv. 185. - S. 403-424. — ISBN 978-1-58603-929-5 .

Poznámky

1. ↑ Oficiální stránka konferencí Computer Science in Russia . Získáno 8. prosince 2013. Archivováno z originálu dne 29. listopadu 2013. (neurčitý)
2. ↑ Stránka soutěže SAT . Získáno 8. prosince 2013. Archivováno z originálu 12. února 2005. (neurčitý)
3. ↑ M. Pătraşcu; R. Williams. O možnosti rychlejších SAT algoritmů  (neopr.)  // Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. - 2010. - S. 1065-1075 .
4. ↑ Cena nadace Dynasty pro mladé matematiky (nepřístupný odkaz) . Získáno 8. prosince 2013. Archivováno z originálu 30. září 2013. (neurčitý) 
5. ↑ Nejlepší práce ICALP . Získáno 8. prosince 2013. Archivováno z originálu dne 20. března 2014. (neurčitý)
6. ↑ Vítězové soutěže SAT za rok 2003 . Datum přístupu: 8. prosince 2013. Archivováno z originálu 4. března 2016. (neurčitý)

Odkazy

• Osobní stránka
• Eduard Alekseevich Girsh na webu POMI RAS.
• Katedra matematických a informačních technologií, St. Petersburg Academic University
• Oficiální stránka konferencí Computer Science in Russia
• Edward A. Hirsch ve společnosti DBLP.
• Kurzy E. A. Girshe na stránkách Computer Science Club v POMI RAS.
• Eduard Girsh: „Bereme ty, kteří jsou schopni vědecké práce“ na web Trinity Variant.
• Eduard Girsh: „V Rusku nemáme sobě rovného“ na stránce „Věda a technika Ruské federace“.

Tematické stránky	Matematická genealogie zbMATH Otevřeno Všeruský matematický portál
V bibliografických katalozích	J9U : 987007447562105171 LCCN : nb2006012781 NKC : xx0049112 VIAF : 47985842 WorldCat VIAF : 47985842