0000000000653857

AUTHOR

Aleksejs Zajakins

showing 2 related works from this author

Zemkvadrātisks algoritms koku ceļu apakšvirkņu uzdevumam

2021

Darbā tiek apskatīts garākās kopīgās apakšvirknes uzdevuma vispārinājums uz kokiem. Tiek apskatīti divi vienāda izmēra koki, kuru virsotnes ir marķētas ar vienas kopas elementiem. Garākā kopīgā apakšvirkne tiek meklēta pāri visiem ieejas koku ceļu pāriem. Galvenais rezultāts ir algoritms, kas risina apskatīto uzdevumu laikā $O(n \log^3 n)$, kur $n$ ir abu ieejas koku virsotņu skaits.

garākā kopīgā apakšvirknedinamiskā programmēšanaDatorzinātnegrafigarākā augoša apakšvirknekoki
researchProduct

All Classical Adversary Methods Are Equivalent for Total Functions

2017

We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity canno…

FOS: Computer and information sciencesKolmogorov complexity010102 general mathematicsBlock (permutation group theory)0102 computer and information sciencesFunction (mathematics)Computational Complexity (cs.CC)Adversary01 natural sciencesUpper and lower boundsTheoretical Computer ScienceCombinatoricsComputer Science - Computational ComplexityComputational Theory and Mathematics010201 computation theory & mathematicsPartial functionSensitivity (control systems)0101 mathematicsEquivalence (measure theory)MathematicsACM Transactions on Computation Theory
researchProduct