Projekto pavadinimas Koncentracijos nelygybių tyrimas ir jų taikymai algoritmų teorijoje

Projekto kodas Nr. 09.3.3-LMT-K-712-02-0167

Podoktorantūros stažuotės vadovas prof. Artūras Dubickas

Podoktorantūros stažuotojas dr. Dainius Dzindzalieta

Projekto įgyvendinimo laikotarpis 2017-12-04 – 2019-12-03

Projekto tikslas - koncentracijos nelygybių taikymas algoritmų teorijoje. Projekto tyrimo metu bus nagrinėjamos atsitiktinių dydžių sumos koncentracijos nelygybės ir nagrinėjamas naujas koncentracijos nelygybių įrodinėjimo būdas taikant Berry - Esseno nelygybę tuo atveju, kai neveikia indukcija. Koncentracijos nelygybės bus pritaikomos sprendžiant algoritmų sudėtingumo uždavinius. Pavyzdžiui, Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio savo straipnyje Testing halfspaces sukonstravo algoritmą, kuris patikrina, ar duota Būlio funkcija yra nutolusi nuo Būlio pustiesės funkcijos, t.y. funkcijos, kurios forma f(x) = sgn(wx-h), per epsilon, per polinominį (1/epsilon) laiką, kuris nepriklauso nuo n. Jie suformulavo hipotezę, jog jei Būlio pustiesės funkcijos koeficientai elgiasi reguliariai, tai ir jos Furje koeficientai elgiasi atitinkamai. Tyrimo metu planuojama atsakyti, kokioms sąlygoms esant galioja ši hipotezė. Taikant naujus metodus, planuojama gauti kur kas efektyvesnius, (asimptotiškai) optimalius greičius. Tolimesnis koncentracijos nelygybių nagrinėjimas yra naudingas algoritmų sudėtingumo tyrimuose. Projekto įgyvendinimo metu bus užmegzti ryšiai su užsienio mokslininkais, bus ištobulintas naujas metodas, leidžiantis įrodyti optimalias koncentracijos nelygybes, suformuluojamos naujos hipotezės, atrandami nauji koncentracijos nelygybių pritaikymo būdai algoritmų sudėtingumo tyrimuose.

Finansavimo šaltinis - Projektas finansuojamas iš Europos socialinio fondo lėšų pagal priemonės Nr. 09.3.3-LMT-K-712 „Mokslininkų, kitų tyrėjų, studentų mokslinės kompetencijos ugdymas per praktinę mokslinę veiklą“ veiklą “Stažuočių po doktorantūros studijų skatinimas”.