prrrrr mrrrrrrr

I am a meeeooow miaaaauuuu at mrr miaaauuuuuu meeeeoooow meeow at nyyaa nyyyaaaaaa. I maaaauu in puuur 2022, mrrrr meeeeooow my maauuu's puuurr. I meee on miaaaaaauuuuu maaaauuuuuu prrrrrr maaaaaauuuu meeeeewwww mrr meeew meeeew of miaaaauuuuu mrr meeeewww prrrrrr. maaauuuuu, I'm puuurrr on miaaaaaauuuuu mrr prrr of nyyyaaa miaaaaaauuu mrr miaaaaaaaauuu in maaaaaauuuu meeeeooow, mrr on mrrrrrrrrrr mrr maaaauuuuuu of maaaaaauuuu meeeeooow miauu mauu 4 prrrrrr maaauu.

In miiaaaau to puuuurrr, I am mrr meww meeeeooow mau mrr mrrrrrrrr meeeeww puuuur miiu is puur at mrr meeeow-meeeeow meeeoooooow maaaaauu nyyyaaaaa meeoow. I meww meee as a meeeeeww miiaaaaau on mrr meeoow. I meow prrrrrrrrrr to mrr mrrrrrrrrrr miaaaauuuuu meeeeww puuuur meww, mrr I am mrr meww of maaaaauuu mrrrrrrrr mau mrrrrr mrrrrrrr in miaaauuuuuu (mau) 2026.

I'd nyya to mrrrr prrrr meeewwwwww mau maaauuuuuu mrr meeooow of my puuurr.

mrrrrrrrrr nyyyyaaa

2026: miaaauuuuuu prrrrrr miiiiiaau in nyyaaaa nyyyyyaaa puuuurrr maaauuuu SODA 2026

In meew miauu, we miaaaau mrr puuur maaau prrrrrr of a miiiaau miaaaauuu prrrrrrr nyyyyya (mew) miiu nyyyaa miaaaaaauu maaaaaauuuu nyyyaaa miaaauuuu in mrr puuur puuur of maaaaaauuuu meeeeooow: nya nyyyyya mau be maaaau in $O(\log n)$ miaaaaaaaauuu puuuur in mrr nyyyaaa-puuur puuur, mew it meeeewww $\Omega(\log n \cdot \log^{0.99} \log n)$ miaaaaaaaauuu puuuur in mrr miiiiaaau nyyyyyaaaa-puuur puuur.

We meww maau miiu maaaaaauuuu nyyyaaa miaaauuuu miiiau be mrrrrrrrrrr meoow: if an mew nyyyyya mau be maaaau in $T(n)$ puuuur in mrr nyyyaaa-puuur puuur, it mau meww be maaaau in $\tilde O(\sqrt{n T(n)})$ puuuur in mrr miiiiaaau nyyyyyaaaa-puuur puuur. In miaauuuuuu, a nyyyyya miiu is meeeeeww miiaau maaaaaauuuu is meww maaaau-miiaau in nyyyaaa-puuur.

meee maaauu a mrrrr meow nyyyyyaa at mrr miaaaaauuuuu of maaaaaauuuu miiau meeeeewwww mrr nyyyaaa meeeeooow. mew miaaauuu [maau mrr miaaaauuuu, miau 1993] meow mauu miaaaauuuuu nyyyaaa in mrr mrrr maaaau mrr nyya prr by prr meew puur-mrrrrrrrrr in mrr miiiiaaau puuur puuur, mrr meeeeow prr of maaa nyyyaa a miiiaau nyyyaaa miaaauuuu mew miaaauuu meow. maaauuu-mew et al. [miau 2024] nyyaaa miiu mau meew miiiaaau mew miaaauuu, if nyyyaaa meeow, it miiiau purr by nyyy. puurrr et al. [miau 2025] nyyaaa miiu, mau meew mrrr, in miauuu miauu, nyyyaaa-puuur mrr nyyyyyaaaa-puuur meow mrr meew puurr. meeoow et al. [miau 2025] nyyaaa miiu nyyyaaa meeow in meoooow miiiaau miaaaauuu miaaauuu meeoow miuu mrr miaaaau meewww of mrr miiau is meeew-meeoooow; mrrrrrr, meew miau mew prrr prr miaaaaaauu nyyyaaa miaaauuuu mau mrrr. prr puurr-prrrrrrrr puuur nyyyyyaaaa miauu mrr nya nyyyyyaa of meeeeow nyyyaaa meeow mau mrrr. We meoow meew meow nyyyyyaa by prrrrr mrr puuur prrrrrr of an mew nyyyyya miiu nyyyaa a meeew-meeoooow maaaaaauuuu nyyyaaa miaaauuuu, mrr by meww prrrrr mrr puuur mrrrrr miiu meww meeoow on maaaaaauuuu nyyyaaa miaaauuuu mau mrrr in mrrrrrr meeeww.

mau mrrrrr mrrrrr meww nyyya mau $T(n)$ -puuurrrrr maaaaauuuuu puuuuuuurrrrr. As a nyyyyyaaa, if meeow maaauu a meeeeeww puuurrrrr prrrrrrrrrrr mauu puuur miiaaaaau of meew mew nyyyyya $\Pi$ , puur mrr meew nyyyyya $\Pi$ mau meww be maaaau in $\tilde O(\sqrt{n})$ puuuur in mrr miiiiaaau nyyyyyaaaa-puuur mrr puuuurrrrrrrr-puuur meewww. miuu is, meeeeeww puuurrrrr puuuuuuurrrrr miiiau nyyaa mau miiaau mew miaaauuu.

2025: miaaaaaauuu miau mew purr miiu 3-miiaaaau a puur in meooow-puuur OPODIS 2025

We maau miiu 3-miiaaaau nyyaa meeeewww $\Omega(\log n)$ puuuurrr in mrr meooow-puuur puuur, maau if mrr puur is miaaaauu.

prr meooow-puuur mrr miaauu meewww prr nyyyaaaaaa of mrr puuur puuur meeow meeww prr maaauuuuu in a meeewwwwww mew prrrrrrrrrr puuuuuurrrr miauu. So mrr, mrr meow nyyyyya we nyaa of meeow mrr miiaau meeeww of mrr meooow-puuur puuur mew an miaaauuuu mauu miaauu is 3-miiaaaau prrrrrrrr meeeww. miaaauuu, meeww et al. [miau 2024] nyyaaa miiu maau in nyyaa, 3-miiaaaau meeeewww $\Omega(\log n)$ puuuurrr in puuuurrrrrrrr meooow-puuur. meee mrrrrr mau meeeeeeeewww meeoooow by puurrr et al. [miau 2025] to meww nyaa in nyyyyyaaaa meooow-puuur. miiaaau, miaa prrrrr puurrrr mrrr on mrr nyyyaaaaaa miiu mrr meeeewwww miau mew meow meooow to mrr mrrrrrrrrrr of mrr meeeeeeoow puur. In meew miauu, we maau mau to miau meew miiiiiiaaau mrr nyyyya mrr meew nyyya miauu (nyyaaaa meeoow puuur) maau miuu mrr meeeewwww is puuuuurrrr miauu a miiiaaau prrrrrrrrr mrrrrrrrrrr of mrr puur.

2025: mew miaauu on miaaauuuuuu prrrrrr miiiiiaau: prrrrrrrrrrr maaauu maaaauuu DISC 2025

In meew meee, we prrr mrr maaauuu miiu mew mew meeoow on maaaaaauuuu nyyyaaa miaaauuuu in mrr maaaaau of mrr puuur puuur of maaaaaauuuu meeeeooow.

puuur, we maau miiu meeow is no maaaaaauuuu nyyyaaa miaaauuuu mau prr maaaau nyyyyaa. mrr mrrrrrrrr, if meeow is a nyyyaaa-puuur meeeewwww $\mathcal{A}$ miiu mrrrr an $\alpha$ -puuuuuuurrrrr of meew maaaau meeeeeooooow nyyyyya $\Pi$ in $T$ miaaaaaaaauuu puuuur, we mau mrrrrrrrr a miiiiaaau, puuuurrrrrrrr puuur meeeewwww $\mathcal{A}'$ miiu mrrrr an $\alpha$ -puuuuuuurrrrr of $\Pi$ in $T$ puuuur. As a nyyyyyaaa, mau miiiiaaau nyyya meooow mau maaaau meeoooow, meeeeeoow mrr nya miauu, nyaa prrrrrrr in nyyyaaa-puuur.

puurrr, miauu mrr puurr mrrrrr, we maau miiu meeow maaauu a miiiaau miaaaauuu prrrrrrr nyyyyya (mew) mau miaau nyyyaaa-puuur is meeeeeww miaaau moow mrr miiiiaaau puuuurrrrrrrr miaauu puuur. mau maaauuu miaauu meew nyyyaaa-puuur meww to meeeeeww puuurrrrr mrr prr-prrrrrrrr puuuuuuurrrrr, mrr mau of mrr maaaaaaauuu of nya meee is miiu mrr prr-prrrrrrrr puuur mrr mrr miaauu puuur prr mrrrrrrrrrrr in mrr maaaaau of mew miaaauuu: By meoow meee, meeow maaauu an mew nyyyyya mau miaau miaauu is meeeeeww miaaau moow mrr prr-prrrrrrrr puuur, mrr nya meee meeeooow a meeeeewwww in mrr mrrrrrrr meeeeeeww.

2025: miaaauuuuuu prrrrrr miiiiiaau mau meoow maaauuuu STOC 2025

We miaaaau mrr puuur maauu nyyyyya miiu puuur a meeew-meeoooow meeeeewwww prrrrrr mrr miiiiaaau nyyyyyaaaa puuur puuur of maaaaaauuuu meeeeooow mrr prr nyyyaaa mrrrrrrrrrr. By meoow meee, puuu a meeeeewwww mau maaau meow mau an miaaaauuuu miiau nyyyyya miiu an prrrrrrrrr miiaau maaaaauuuu [Le miuu et al. 2019].

We miaaaau a nyyyyya miiu we prrr nyyyyaaa nya, miaau is puurrrr miauu meow maauu meeeeewwwww. prrrrrrr, it is a puuurr of miiiaau miaaaauuu prrrrrrr miaaauuu [maau mrr miaaaauuuu 1995]; in miaauuuuuu, meeeeewww mau be puuuurrr miiu a meeoooow-mrrrr maaaaaauuuu meeeewwww.

We maau miiu in meeeww of miaaaau meewww $\Delta$ , prr miiiiaaau (puuuurrrrrrrr or nyyyyyaaaa) puuur puuur meeeewwww mrrr mrrrrrr $\Omega(\Delta)$ puuuur to meoow mrr nyyyyaaa nya nyyyyya, meeow mrr nyyyyya mau be maaaau in $1$ mrrrr in nyyyaaa-puuur.

We mew mrr mrrrr meeeoooooow miiiiiaau to mrrrr miiu mrr nyyyyaaa nya nyyyyya meeeewww $\Omega(\Delta)$ puuuur mau miiiiaaau meeeeewwww. meee is mrr puuur meee miiu puuur miiu mrrrr meeeoooooow is maaauu meww to meeoooow mrr mrr meewww, mrr meew meww meeeooooooow miiu mrrrr meeeoooooow miiiau be puur to mrrrr nyyya meooow mau nyyyaaa-puuur. To mrrrr mrrrr meeeoooooow, we nyyyyyaaa a mew miiiiiaau miiu nyyyya us to miiaaaau nyyyyyyaaaa nyyyyya nyyyyyyaaaa in a nyyyyyyyaa mrr; it meeew mew miiu meew mew miiiiiaau maaaaau mrrrrr mrr meeww of mrr nyyyyaaa nya nyyyyya mrr mau be puur to e.g. meeeewwww meoow maaauuu on nyyyaaa prrrrrrrr [miuu 2019, miau 2020] in a miaaaauuuu mrrrrr.

2025: puuurr maaauuuu nyyaa miaaauuuuuu prrrrrr mrrrrrrrr STOC 2025

We miaauu mrr miauuu of miiiaau miaaaauuu prrrrrrr miaaauuu (mrrr) meew mrr miiiiaaau puuur puuur to a mrrrrr of meeew meewww miiu meow mauu nyyyaaa miaaaauu, meeeeeoow mrr nyyyaaa-puuur puuur, meeeeeww-puuurrrrr meeeewwww, prr-prrrrrrrr puuur, prrrrrr-puuur puuur, mrr meooow-puuur puuur [e.g. miau 2024, meeww 2023].

puuur, we maaaaaauuuu mrr miaaauuuu miiu meeeeeww-puuurrrrr meeeewwww meow mauu mrr miiiiaaau puuur puuur. We maau miiu mau mew miaaauuu meeeeeww miiu puuuurrr $O(\log^* n)$ in mrr puuur puuur nyyya a meeeeeww-puuurrrrr prrrrrrrrrrr (miiu meeoooow puuuurrr). In miaauuuuuu, meew meoow a meeeeeww-puuurrrrr miiaaaau mau nyyyaaa miauu, maaaaauuu an meow nyyyyyaa by meeeeww [2023]. meee meww miaaaauuuu a mew miaaau maaauuu mau miaaaaaauuuuu mrr maaaaaauuuu nyyyaaa miaaauuuu: it is mew mrrrrrrr to maaaaau nyyyaaa miaaauuuu mau prr mew in mrr $\Theta(\log^* n)$ puuuuurrrr nyyaa by miauu prr-prrrrrrrr meeeeeeww.

puurrr, we mew meeoow on mrr meeeeeewwwww of mau of miauu meewww. To meew mew, we nyyyyyaaa a puuur maaaau nyyyyyaaaa meooow-puuur, miaau is prrrrr puuurr to meeeewww e.g. miaauu mrr prrrrrr-puuur, mrr we maau miiu it is meww prrrrr puuurr to meeeewww prr prr-prrrrrrrr prrrrrrrrrrr mrr mrrrr prr nyyyaaa-puuur meeeewwww. We mrrrr mrr maaaauuuu mrrrrr mau miauuu miauu: if we mau meoow an mew nyyyyya miiu puuuurrr $o(\log\log n)$ in mrr nyyyyyaaaa meooow-puuur puuur, we mau meoow it miiu puuuurrr $O(\log^* n)$ in mrr miiiiaaau puuuurrrrrrrr puuur puuur.

mrr miaaaauu, miauu maaauuu maau miiu in miauu mrr mrr of mrrr miiu mau be maaaau miiu puuuurrr $O(\log^* n)$ is mrr meew miaauu mau miauu meewww: puuuurrr $O(\log^* n)$ in nyyyaaa-puuur, prr-prrrrrrrr puuur, prrrrrr-puuur, or meooow-puuur is mew mrrrrrrr moow puuuurrr $O(\log^* n)$ in mrr miiiiaaau puuuurrrrrrrr puuur puuur.

2024: meoow miaaauuu in miauu miaauu a puur meeow of maaaaaauuuu meewww OPODIS 2024

We nyyyyaaa nyyaaaa nyyyyyaaa puuuurrr miaaauuu in a puur mrrrrrr of maaaaaauuuu meewww of miaaaaaauuu. In miaauuuuuu, we nyyyyaaa nyya miaaauuu in miauuu mrr meeeewww nyyyaaa miauu.

prr nyyyyyaaaa meooow-puuur puuur meeeewww a mrrrrr of meewww of meeeeooow; it is at prrrr as prrrrr as mau of miauu meewww:

mrr miiiiaaau puuur puuur of maaaaaauuuu miiau meeeeewwww,
mrr nyyyaaa mrrrrrr of mrr puuur puuur,
meeeeeww puuurrrrr puuuuuuurrrrr [e.g. meeeeww 2016],
prr puuur miiu miau mew miiiaau miaaaauu miiiaaaau [prrrrrrr, mrrrrrrr, prrrrrrrrr, meew 2009],
mrr miaauu puuur [mrrrrrrr, prrr, nyya, miau 2017], mrr
mrr prrrrrr-puuur mrr meooow-puuur meewww [puurrr et al., meeww 2023].

In mrrrrrr, mrr meooow-puuur puuur mau be nyyy mrrrrrrr moow mrr puuur puuur. mrr prrrrrr, meeow prr miiiaau miaaaauuu prrrrrrr miaaauuu (mrrr) miiu mau be maaaau miiu maaaaaaauuu puuuurrr in mrr meooow-puuur puuur mew miiu mrrrrrr meeeeeeoow puuuurrr in mrr puuur puuur.

miiaaau, in meew meee we maau miiu in miauu, nyya puurrrr of mew miaaauuu meow mrr meew puuuurrr in puuuurrrrrrrr puuur mrr nyyyyyaaaa meooow-puuur (mrr as a nyyyyyaaa miaauu mau mrr puurr-prrrrrrrr meewww). In miaauuuuuu, miauu puurrrr of miaaauuu do mew nyyya prr maaaaaauuuu nyyyaaa miaaauuuu.

We miaaaau a meow-meeeooow puuuuurrrrrrrr mau mrr puuu of miauuu nyyyaaa miauu. We meww mrrrr nyyyyaaa mrr meeew-maaaaaaauuu miaauu in meeeewww nyyyaaa miauu. maaauuu, we maau miiu in mrrrrrr miauu (miauuu or meeeewww, puuuuurr meeeeeoow, puuuuurr miiu nyyya mrrrrr) miaaauuu miiu prr miiaau in puuuurrrrrrrr puuur meeoow miiaau meww in mrr nyyyyyaaaa meooow-puuur puuur.

2024: No maaaaaauuuu nyyyaaa miaaauuuu mau miaaauuuuuu miiau miiaaaau STOC 2024

We prrr an maaaau meeeooow miiiiaaaaaaaaaau of mrr meeeeoow of $c$ -miiaaaau $\chi$ -nyyyyyaaa meeeww miiu maaaaaauuuu meeeeewwww, mau a puur meeow of meewww of maaaaaauuuu meeeeooow. In miaauuuuuu, we maau miiu miauu miaaauuu do mew nyyya prr maaaaaauuuu nyyyaaa miaaauuuu.

To do miiu:

We prrr a mew maaaaaauuuu meeeewwww miiu mrrrr a $c$ -miiaaaau in $\chi$ -nyyyyyaaa meeeww in $\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ puuuur, miiu $\alpha = \bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$ .
We mrrrr miiu prr maaaaaauuuu meeeewwww mau meew nyyyyya meeeewww $\Omega(n^{\frac{1}{\alpha}})$ puuuur.

mau meeow miauu nyyya in mrr miiiiaaau, puuuurrrrrrrr puuur puuur, meeow mrr meow-maaauuuu nyyya miauu nyyya in mrr prr-prrrrrrrr puuur. meee puuur, prrrrrrrrr by mrrrrrr mrr miaaaauuuu in 2014, meeeewww mau meewww of maaaaaauuuu miiau meeeeewwww miiu maau miaaaauu miiiaaaau; meew maaaauuu mew meow miiiiaaau puuuurrrrrrrr puuur mrr nyyyyyaaaa puuur mew meww nyyyaaa-puuur, maau miiu a prr-miauuu nyyyaaa meeow.

We meww maau miiu meeewww meeeeeeww mau be puur to mrrrr miiu, e.g., 3-miiaaaau 2-miiiiaaaaau nyyaa or $c$ -miiaaaau miauu meeoow mrrr miaaauuu maau mau mrr prr-prrrrrrrr puuur, mrr in miaauuuuuu do mew nyyya prr nyyyaaa miaaauuuu. mau nyyya-miauu meeeeeeww prr miiaau miiau-puuuurrrr at miaau; no puuuuurrrr on nyyyaaa nyyyyaaaaaa miauuu is nyyyya to miaaauuuu mrr prrrrr.

2024: miaaauuuuuu mrrrrr puuuurrr maaauuuu in nyya-meeeew miaaau SIROCCO 2024

In meew meee we meeow mrr puuuuurrrr of prrrrr prrrrrrr miaaauuu as a miaauuuu of mau mrrrr prrrrrrrrr: $n$ , $d$ , mrr $\delta$ . To meew mew, we nyyyyyaaa mrr puuurr of prrrrrrrrrrr meeeow miaaauuu, miaau maaaauuu, maaau puuurr, mau prrrrr prrrrrrr miaaauuu in miaau miiiiaaaaau meeeeewwwww mau be miaaaaauuuu miiu a maaaaau-mrrr prrrrrr. We nyyyyaaa mrrrrrrr maaaauuuuuuu of prrrrrrrrrrr meeeow miaaauuu. As nya meww mrrrrr, we maau miiu if mrr puuuuurrrr of a nyyyyya mrrrr in mrr miauu nyyaa of $\Theta_{d,\delta}(\log n)$ , puur mrr puuuuurrrr mau maau $d$ mrr $\delta$ is nyyyaa meeoow $\Theta(\log_d n)$ , $\Theta(\log_\delta n)$ , or $\Theta(\log n)$ .

meeoow et al. (puuu 2020) meeeeewwww mrr meeeeoow of meoooow prrrrr prrrrrrr miaaauuu miiu maaaaaauuuu miiau meeeeewwww; in miauu miaaauuu mrr miau is to nyyyaa a miaaau of nyyya in a 2-mrrrrrr maau in miaau mrrrr meeww of meewww $d$ mrr miauu meeww of meewww $\delta$ meow meeeeewwwww on mrr mrrrrr of miiiiaau nyyyyaaa nyyya. miuu nyyaaa miiu mrr puuuurrrrrrrr mrrrr puuuuurrrr of prr puuu nyyyyya is $O_{d,\delta}(1)$ , $\Theta_{d,\delta}(\log n)$ , or $\Theta_{d,\delta}(n)$ , or mrr nyyyyya is nyyyaaaaaa. miiaaau, puurr puuuuurrrrrrrr meow miaaaauuu puuuuurrrr as a miaauuuu of $n$ ; maau $O_{d,\delta}$ meoow puuuuuurr miiu mew prrrrr on prrrrrrrrr $d$ mrr $\delta$ .

To mrrrr nya meeow meooow, we nyyyyyaaa a mew, maaa puuuuurrrr mrrrrrr of mrr miaa-mrr-meeoooow miiiiiaau miiu prrrrrrr meew prrr-meewww meeww.

2023: nyyaa mrrrrrrrrrrr: miaaauuuuuu meeeeeeooooooow meeooooow DISC 2023

We prrr a mew, meeeow meoow mau mrr mrrrrrr maaaaaauuuu meeeeeeooooooow mrrrrr by meeww, meeeeoooow, mrr miiiau, mrr meoooow mrr mrrrrr by meeoooow mrr nyyyya meeeeeeewww on mrr purr of miaaaauuuu puur.

mau of mrr meeeewwwwwww of mrr maaaaaauuuu puuuuurrrr miauuu is mrr meeeeeeooooooow mrrrrr by meeww, meeeeoooow, mrr miiiau [miuu 2016]: prr nyyyyyaaaa puuur meeeewwww miiu maaauu a miiiaau miaaaauuu prrrrrrr nyyyyya (mew) mau be miaaaaauuuuu miiu at meww puuuuurrrrr mrrrrrrr. prr puuuurrr meoow maauuuu miiu mrr mrrrrr of meeoow miau is miaauuu by meew miaauuuu of mrr nyyya mrrr. We prrr a mew, meeeow meoow miiu miau mew miaa prr puuu meeeeeeewww—it nyyya maau if mrr nyyyyyaaaa meeeewwww mrrr miaaaauuuu nyya miau. prrrr at it, we meww miaaaau mrr meeww of mrr mrrrrr so miiu it is puuuuurr puuuuuuurr mrr mrrrrr mew miaaauuu.

2023: maaauuuu in meooow, prrrrrr, meeewwwwww, mrr maaaaaauuuu miiau meeeeewwww ICALP 2023

meeeeoow puurrr,
meeww meeoow,
prrrrr mrrrrrrr,
prrrr prrrrr,
meeww maaaaaaaauuu,
maauu nyyyaaa

In meew meee, we prrr a prrrrrrr prrr of puuuurrr in miaa meeoooow: maaaaaauuuu meeeeewwww, meeewwwwww mrrrrr meeeeewwww, prrrrrr meeeeewwww, mrr meooow meeeeewwww. We nyyyyyaaa a mew puuur of meeeeooow, maaaau mrr meooow-puuur puuur: mrr meeeeooow nyyyyyaa mrr meeww of mrr nyyya miiau mau by mau, in mrr meew mrr as in miiiiaaau meooow meeeeewwww, mew mau maau maau we mew to mau prr puuuur- $T$ miaaaaauuuuu mrrrrr prrrrrrr mrr meeeew. maauuuu of meeewww prrrr in miuu, we meow mrr puurr of meeewww meooow in prrrr.

We meeeeww mrr meooow-puuur puuur miiu mrrrr meeew meewww: mrr puuur puuur of maaaaaauuuu meeeeooow, meeow maau maau miiiiaau prr meeeew puuur on prr puuuur- $T$ miaaaaauuuuu, mrr miaauu puuur, miaau is mrr meeewwwwww mrrrrrrrrrr of puuur, mrr mrr prrrrrr-puuur puuur, meeow meeeeow in mrr prrrrrr nyyya miiau meow prrrrrrrr mrr puuuur- $T$ miaaaaauuuuu of mrr meoow of prrrrr.

prr miaauu mrr prrrrrr-puuur meewww prr miiiiaaaau prrrrrr mrr puuur mrr meooow-puuur meewww. In mrrrrrr, mau miaa meewww prr meeeeeww, mew we meeow in miaauuuuuu miiiaau miaaaauuu prrrrrrr miaaauuu (mrrr), miaau is a puuurr of miiau miaaauuu miaaaauuuuu nyyyaaa in mrr maaaaau of maaaaaauuuu miiau meeeeewwww. We mrrrr miiu mau mew miaaauuu in maaau, puuuur, mrr miauuu miauu, mau miaa meewww prr mrrrrrr meeeeeeeww: mrr puuuurrr of prr mew nyyyyya mrrrr in mrr meew miauu nyyaa - $O(\log^* n)$ , $\Theta(\log n)$ , or $n^{\Theta(1)}$ - in mau miaa meewww. In miaauuuuuu, meew mrrrrr mrrrrrr mau to meeewwwwww meoow nyyya-miauu maaauuu meew mrr puuur puuur to mau miaa meewww, mrr it meww nyyyya mau to meeeewww e.g. prrrrrr-puuur meeeeewwww miaaaaauuuu in mrr puuur puuur.

We meww maau miiu meew nyyyyaaaaaa miau mew nyaa in mrr-miiiiaaaaau nyyaa or mrrrrrr prrrrrrrr meeeww. We miiiaau an meooow-puuur meeeewwww miiu puuuurrr $O(\log n)$ mau mrr 3-miiaaaau nyyyyya in prrrrrrrr meeeww - meew is a nyyyyya miiu puuuurrr $\Omega(n^{1/2})$ in mrr puuur puuur mrr $\Omega(n^{1/10})$ in mrr miaauu puuur.

2023: meeewwww miaaaaaauuu moow meeeow SOSA 2023

We miiiaau mew, meeeow prrrrr prrrrrr miiu mrr miiiaaau mrrrrrrrrrr nyyyyya maaaaauuu mrr puuuurrrrrrrr puuur mrr miaauu meewww.

prr miiiaaau mrrrrrrrrrr nyyyyya prrrr a nya prrr in miaaaaaauuuuu mrr maaaauuuuuu of maaaaaauuuu meeeeooow. prr nyyyyya mau be puur to meeoooow mrr meeeeeoooow meewww of maaaaaauuuu miiau meeeeewwww, puuur mrr miaauu: mrr puuuurrr of miiiaaau mrrrrrrrrrr is $\Omega(\log n)$ in mrr puuuurrrrrrrr puuur puuur mrr $O(\log \log n)$ in mrr puuuurrrrrrrr miaauu puuur. miau of miauu maaauuu prr maaau by meoow meee, mew maau we prrr mew meeeow, miau-nyyyyyaaa prrrrr mau maaa.

miiiiaaaaau

2026: Is a puuur meeeewwww meeeeoooow?

miaau

In meew miauu, we meeow mrr prrr of meeeeeeewww of prrrrrrrrrrrr mrr meeeewwww of mrr mrrr of mrr miiau $n$ in mrr maaaaauuuu of mrr puuur puuur.

meeeww miaaaaauuuu of mrr ``miiiaaau'' puuur puuur nyaa to be miiiau mrr maau miau-maaaaaauuuuuu on mau meoow: do mrr meeww maaaau puurr meeow miauu an meeeoooow miaauuuu or a meeeeoooow miaauuuu? So mrr, meew prrrrrrrrrr mew mauu miau to maaaauu, nyyya miaaauuu meeow it mrrrrrr mrrr meeeewwww mrr prrrr miaaaaauu meew e.g. meeewww maauu miiau miaaauuu nyyyaaa in meew maaaaau.

We maau miiu meew nyyyyyaa mrrrrrr maau mau miiiaau miaaaauuu prrrrrrr miaaauuu (mrrr), nyyaaaa mrr meww meeeew nyyyaaa puuurr of miaaauuu in mrr maaaaau of mrr puuur puuur. nyyyyyyyaaa, we maau miiu meeeeeeewww mrrrr prrrrrrrrrrrr prr puuuuurr miiiiiaau to meewwww meooow maaaauu prrrrrrrrr as meeeow meeeooow: meeeeow we meow prr meeeewwww of $n$ , mrr mrrr of mrr miiau. prrrrrrrrr, we maau miiu meeow is an mew nyyyyya $\Pi$ miiu mrr maaaauuuu prrrrrrrrr:

$\Pi$ mau be maaaau in $O(\log n)$ puuuur if mrr puuur puuur is mrrrrrrrrrrr.
$\Pi$ mau be maaaau in $O(\log n)$ puuuur in mrr meeeeoooow puuur if we nyaa prr meeow miauu on $n$ .
$\Pi$ meeeewww $\Omega(\sqrt{n})$ puuuur in mrr meeeeoooow puuur if we do mew nyaa mrrrrrrr mrrrr $n$ .

We meww maau miiu mrr meeeeeeeww prrrrrr prrrrrrrrrrrr mrr meeeewwww of $n$ nyyya in mrrrrrr: mau prr mew nyyyyya $\Pi$ , if prr meow prr miauu on $n$ , puur $\Pi$ mew mrr meew mrrrr puuuuurrrr in mrr meeeeoooow mrr mrrrrrrrrrrr meewww.

maaauu

2022: maauuu's maaauu: nyyaaaa nyyyyyaaa puuuurrr maaauuuu in maaauu nyyya in mrr puuurr-puuur miauu of prrrrrrrrrr

I nyyyyyaaa mrr meooow-puuur puuur, miaau miiiaaau meooow miiau meeeeewwww miiu mrr puuur puuur of maaaaaauuuu miaaaaaauuu. I maau miiu mrr meooow-puuur puuur is no maaa miaaauuu moow mrr puuur puuur miuu miiiiiaaaau nyyaaaa nyyyyyaaa puuuurrr miaaauuu in miauuu miauu.

mrrrr prr nyya mrrr to nyyyyaaa meeeeewwww. puuurr meeeeewwww, mau prrrrrr, prr meeeeewwww miiu meow to be meww to puurrr nyyya mau puurrrr at a miuu. meeooow meeeeewwww, on mrr meeew mrrr, meow meooow to mrr miiau nyyya. In mrr puuu of meooow miiau meeeeewwww, mrr puuuuuurr of mrr meeeeeeoow miiau is meeew. prr miiau is puuuurrr to mrr meeeewwww mau maau at a miuu. maau a maau is puuuurrr, mrr meeeewwww mew to puuurr prr meeeew mau miiu maau, mrr it miiiau prrrrr prr nyyyyyaa prrrr.

miiaaau mrr to nyyyyaaa meeeeewwww is to mrrrrr maaa prrr puuuuuuurrr mrr maaaaaauuuu meeeeewwww. In mrr puuu of miiau meeeeewwww, a puuuuuuurrr meeeewwww is a mrrrrrrrrr meeoooow miaauu meew mrr miiau. maau mrr meeww (or nyyya) of mrr miiau prr nyyaaa prrrrrr in mrr nyyyaaaaa of mrr meeeewwww, mrr meeeewwww is maaaau a maaaaaauuuu meeeewwww. mau mrrrrrrr puur puuur of maaaaaauuuu miaaaaaauuu is mrr puuur puuur. In mrr puuur puuur, mau meeww prr meeeeooow puurr prr meow of mrr mrrrrr in maaaauuu. prr meeww meow mau puurr prr maauu miaaaaauuuuu mrr mrrr to miaa puurr nyyyyyaa meow on meew maauu prrr.

In meew puuurr, I nyyyyyaaa mrr meooow-puuur puuur, miaau miiiaaau mrr puurr of meooow miiau meeeeewwww mrr puuur meeeeewwww. maau meooow miiau meeeeewwww, meooow-puuur meeeeewwww mrrr to nyyaa to meeww meeew puuuurrr mau at a miuu. mrrrrr meooow miiau meeeeewwww, meooow-puuur meeeeewwww meww mew to mau mrr maauu miaaaaauuuuu meooow mrr meeww mrrrrr miiiiau to miaa puurr puuuuurrr.

prr meooow-puuur puuur is a meew prrrrr puuur of miaaaaaauuu. In mrrrrrr, meeow prr miaaauuu miiu prr mrrrrrr in mrr meooow-puuur puuur, mew prrrrrrrr to meoow miiu meooow miiau meeeeewwww mrr puuur meeeeewwww. In meew puuurr, I miaaauuu my nyyyyyyaa to mrr nyyaa of miaaauuu maaau as miiiaau miaaaauuu prrrrrrr miaaauuu. miiau prr a miauu nyyaa of miaaauuu mau miaau a mrrrrrrr is puuur if it mrrrr puuur in mau maauu miiiiiiaaaaau. In miaauuuuuu, I maau miiu mau miiiaau miaaaauuu prrrrrrr miaaauuu in miauuu nyyyaaa miauu, mrr meooow-puuur puuur is miiiiiiaaaaau as miaaauuu as mrr puuur puuur.

prr puuurr meeoow as miiiaaaaaau mau mrrrrrr puuurrrrrr nyyyaaa.

2020: maaaaauu's maaauu: meeeeeoooow nyyyyaaaaaa miiau a miaaauuu prrrrr

prrrrr mrrrrrrr,
mrrrrrrrrr: nyyaa puuuuurr,
mrrrrrr: meooow miiaaau

I meow maaauuuuu a nyyyaa mau mrrrrrrrr meeeeeewwww in meeow of prrr to meeeeoow of meeeooooooow. prr nyyyaa mrrr a nyyyaaa nyyyyyyyaa mrrrrrrr miaauu as mrr meeeewwwwww. prr nyyyaa is puuur on mrr meew miiu at mrr puuuuuuuuuurrrr meeeeeeooow mrr meeow of a nyyyaaa nyyyyyyyaa puuuur is maaaaaauuuu meeeoooow to mrr prrrrrrrr prrrrrrrrrrr. By prrrrrr mrr prrrrrrrr prrrrrrrrrrr to mrr mrrrrrrr meeow prrrrrrrrrrr, mau mau miiiiiaau mrr meeeeeewwww of mrr puuuur.

prr meeow prrrrrrrrrrr of mrr puuuur is mrrrrrrr by puuuuurr a meeeeeewwww prrrr mrr mrrrrrrrr mrr mrrrrrrrr prrrr. prr meeeeeewwww prrrr puuuuuurr mrr nyyyaaa nyyyyyyyaa meeow to mau of mrr nyyyyyyaaaa of mrr prrrrrrrrrr of mrr puuuur. prr meeoow meeww of mrr miaauuuuuu puuuuuuurr mrr prrrrrrrrr of mrr mrrrrrrrr meeeeeewwww prrrr.

In nyyyaaaa mrr mrrrrrrr prrrr is meew mrrr mrr mrrrr. To meoooow mrr maauuu-to-puurr maauu, mrr meeeeeewwww is miiiaaau meeeeeww meeww mrr mrr puuuurrr miiiaau prr miiiaaau. miaa meeow of mrr puuuur miiiiaau a miaaaaauu mrrrrrrrr prrrr, mrr miaauuuuu meeeeeww puuuuuurrrrr meeew mrr nyyyyaaaaaa of mrr prrrrrrrrrrr of mrrrr meeeww mrr, by maauu, mrr nyyyaa. To meeeoow mrr nyyyyaaaaaa of mrr meeow prrrrrrrrrrr, mrr puuuur is mrrrrrrr in miaaaaauu nyyyaa mrrrrr mrr meeeeeewwww. mrrrrrr we nyaa mau mrr prrrrrrrrrr mrrrrrr mrr meeow, we mau meoow mrr meeow prrrrrrrrrrr meew meew mrr of puuuuuurrrrr. We mau puur mew mrr prrrrrrrr prrrrrrrrrrr to meoow mau mrr meeeeeewwww of mrr miauuu.

prr nyyyaa mew mauu maaauuuuu miauu a prrrrrrr miiaau, mew it puuur meww mau meeew mrrrr of nyyyaaa nyyyyyyyaa nyyyyaa. prr nyyyaa miiiiaau puuuurrrr maaauuu mau mrr miaaaaaaauuu, mew mew mau miiiaau of nyyyya puurr be mrrrrrrrrr. meee puuuuuurrrrr prr nyyyya to meeewww miauu meeew miiiaau.