Projekto 09.3.3-LMT-K-712-02-0167 "Koncentracijos nelygybių tyrimas ir jų taikymai algoritmų teorijoje" įgyvendinimo metu sukurta produkcija
| Vykdytojas | Vilniaus universitetas |
| Produkto sritis | Švietimas ir mokslas |
| Produkto rūšys | Tyrimai, studijos |
Tyrimo metu nagrinėtos atsitiktinių dydžių sumos koncentracijos nelygybės, taikant Berry - Esseno nelygybę tuo atveju, kai neveikia indukcija. Koncentracijos nelygybės pritaikytos 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 planuota atsakyti, kokioms sąlygoms esant galioja ši hipotezė.
Projekto įgyvendinimo metu pasiekti tyrimų rezultatai skelbiami mokslinėje produkcijoje.
Mokslo straipsniai:
- D. Dzindzalieta, F. Götze. Halfspaces with influential variable. (Theory of Probability & Its Applications, 65(1), 114–120.).
- D. Dzindzalieta, T. Juškevičius. A non-uniform Littlewood-Offord inequality. (In: Discrete Mathematics. Volume 343, Issue 7, July 2020, 111891.)