CONFERENCE
Konferencē iekļautie DF zinātnieku darbi:
1. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs, "Separations in Query Complexity Based on Pointer Functions".
Raksta tēma: lielākā iespējamā priekšrocība, kāda kvantu vai varbūtisko algoritmu var būt salīdzinājumā ar determinētiem algoritmiem. Gan kvantu, gan varbūtisko algoritmu gadījumā tiek atrastas skaitļošanas problēmas, kurām tiek sasniegta lielāka priekšrocība nekā līdz šim zināmā. Šis ir pirmais uzlabojums, kas šajā jautājumā sasniegts kopš 1996. gada (kvantu algoritmu gadījumā) un 1986. gada (varbūtisko algoritmu gadījumā).
2. Aleksandrs Belovs and Eric Blais, "A Polynomial Lower Bound for Testing Monotonicity".
Raksta tēma: algoritmi, kas nosaka, vai Būla funkcija ir monotona (mainot mainīgā vērtību no 0 uz 1 funkcijas vērtība var tikai pieaugt) vai tālu no monotonas. Pirmo reizi pierādīts apakšējais novērtējums algoritmiem, kas risina šo skaitļošanas uzdevumu, kas ir tuvs labākā zināmā algoritma sarežģītībai (polinomiāli saistīts ar to).
Abus rakstus prezentēja rakstu līdzautori: Troy Lee (Singapūra) un Eric Blais (Waterloo, Kanāda).
1. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs, "Separations in Query Complexity Based on Pointer Functions".
Raksta tēma: lielākā iespējamā priekšrocība, kāda kvantu vai varbūtisko algoritmu var būt salīdzinājumā ar determinētiem algoritmiem. Gan kvantu, gan varbūtisko algoritmu gadījumā tiek atrastas skaitļošanas problēmas, kurām tiek sasniegta lielāka priekšrocība nekā līdz šim zināmā. Šis ir pirmais uzlabojums, kas šajā jautājumā sasniegts kopš 1996. gada (kvantu algoritmu gadījumā) un 1986. gada (varbūtisko algoritmu gadījumā).
2. Aleksandrs Belovs and Eric Blais, "A Polynomial Lower Bound for Testing Monotonicity".
Raksta tēma: algoritmi, kas nosaka, vai Būla funkcija ir monotona (mainot mainīgā vērtību no 0 uz 1 funkcijas vērtība var tikai pieaugt) vai tālu no monotonas. Pirmo reizi pierādīts apakšējais novērtējums algoritmiem, kas risina šo skaitļošanas uzdevumu, kas ir tuvs labākā zināmā algoritma sarežģītībai (polinomiāli saistīts ar to).
Abus rakstus prezentēja rakstu līdzautori: Troy Lee (Singapūra) un Eric Blais (Waterloo, Kanāda).
- <link http: acm-stoc.org stoc2016>Par konferenci
![](https://www.facebook.com/sharer/sharer.php?app_id=957173808510696&sdk=joey&display=popup&ref=plugin&src=share_button&u=https%3A%2F%2Feztf.lu.lv%2Fen%2Fabout-us%2Fnews%2Fdetail-view%2Ft%2F94086%2F&picture=https%3A%2F%2Feztf.lu.lv%2Ffileadmin%2Fuser_upload%2Flu_portal%2Fprojekti%2Fdf%2Fzinas%2FSTOC_2016.png&description=No 19. līdz 21. jūnijam Kembridžā, Masačūsetsas štatā, ASV notiek viena no divām pasaules vadošajām konferencēm datorzinātnes teorijā - "ACM Symposium on the Theory of Computing (STOC 2016)". Šogad konferences programma ietver divus DF zinātnieku darbus.){kind=link}