\documentclass[11pt,notitlepage]{article}
\usepackage[all]{xy}
\usepackage[english,greek]{babel}
\usepackage{dbnsymb, amsmath, amssymb, multicol, stmaryrd, pifont,
  amscd, colortbl, mathtools, wasysym, needspace, import, longtable,
  overpic, bbm, pdfpages, array, blkarray, setspace
}
\usepackage{graphicx}
\usepackage[export]{adjustbox} % Follows https://tex.stackexchange.com/questions/6073/scale-resize-large-images-graphics-that-exceed-page-margins
\usepackage{tensor}
\usepackage{txfonts}	% for the likes of \coloneqq.
\usepackage{fontawesome} % for \faPlay
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{utfsym}	% for the likes of \car=\usym{1F697}
\usepackage[textwidth=8.5in,textheight=11in,centering]{geometry}
\parindent 0in
\usepackage[makeroom]{cancel}

\usepackage[inline]{enumitem}
\setlist{nosep}
\setlist[itemize]{left=0pt .. 10pt}
\setlist[enumerate]{left=0pt .. 12pt}

% Following http://tex.stackexchange.com/a/847/22475:
\usepackage[setpagesize=false]{hyperref}
\hypersetup{colorlinks,
  linkcolor={blue!50!black},
  citecolor={blue!50!black},
  urlcolor={blue!50!black}
}

% Following http://tex.stackexchange.com/questions/59340/how-to-highlight-an-entire-paragraph
\usepackage[framemethod=tikz]{mdframed}

\usepackage[T1]{fontenc}

\usepackage[yyyymmdd]{datetime}

\def\myurl{http://www.math.toronto.edu/~drorbn}
\def\thistalk{Tokyo-230911}
\def\title{Rooting the BKT for FTI}

\def\navigator{{
  \href{\myurl}{Dror Bar-Natan}:
  \href{\myurl/Talks}{Talks}:
  \href{\myurl/Talks/\thistalk/}{\thistalk}:
}}
\def\thanks{{Thanks for inviting me to UTokyo!}}
\def\webdef{{{\greektext web}$\coloneqq$\href{http://drorbn.net/tok2309}{http://drorbn.net/tok2309}}}
\def\web#1{{\href{\myurl/Talks/\thistalk/#1}{{\greektext web}/\linebreak[0]#1}}}
\def\titleA{{\title}}
\def\titleB{{\title}}
\def\titleC{{\title}}

\definecolor{mblue}{HTML}{E0E0FF}
\definecolor{mgray}{HTML}{B0B0B0}
\definecolor{morange}{HTML}{FFA50A}
\definecolor{mpink}{HTML}{FFE0E0}
\definecolor{myellow}{HTML}{FFFF00}
\def\blue{\color{blue}}
\def\gray{\color{gray}}
\def\mgray{\color{mgray}}
\def\morange{\color{morange}}
\def\pink{\color{pink}}
\def\magenta{\color{magenta}}
\def\purple{\color{purple}}
\def\red{\color{red}}
\def\yellowm#1{{\setlength{\fboxsep}{0pt}\colorbox{yellow}{$#1$}}}
\def\myellowm#1{{\setlength{\fboxsep}{0pt}\colorbox{myellow}{$#1$}}}
\def\mpinkm#1{{\setlength{\fboxsep}{0pt}\colorbox{mpink}{$#1$}}}
\def\mbluem#1{{\setlength{\fboxsep}{0pt}\colorbox{mblue}{$#1$}}}
\def\cbox#1#2{{\setlength{\fboxsep}{0pt}\colorbox{#1}{#2}}}

\def\arXiv#1{{\href{http://arxiv.org/abs/#1}{{\tiny arXiv:}\linebreak[0]{#1}}}}

\def\qed{{\linebreak[1]\null\hfill\text{$\Box$}}}

\def\act{{\hspace{-1pt}\sslash\hspace{-0.75pt}}}
\def\ad{\operatorname{ad}}
\def\Ad{\operatorname{Ad}}
\def\aft{$\overrightarrow{\text{4T}}$}
\def\AS{\mathit{AS}}
\def\bbZZ{{\mathbb Z\mathbb Z}}
\def\CW{\text{\it CW}}
\def\diag{\operatorname{diag}}
\def\eps{\epsilon}
\def\FL{\text{\it FL}}
\def\Hom{\operatorname{Hom}}
\def\IHX{\mathit{IHX}}
\def\mor{\operatorname{mor}}
\def\PvT{{\mathit P\!v\!T}}
\def\remove{\!\setminus\!}
\def\STU{\mathit{STU}}
\def\SW{\text{\it SW}}
\def\TC{\mathit{TC}}
\def\tr{\operatorname{tr}}
\def\vT{{\mathit v\!T}}

\def\bara{{\bar a}}
\def\barb{{\bar b}}
\def\barF{{\bar F}}
\def\bart{{\bar t}}
\def\barT{{\bar T}}
\def\barX{{\bar X}}
\def\bbC{{\mathbb C}}
\def\bbE{{\mathbb E}}
\def\bbe{\mathbbm{e}}
\def\bbH{{\mathbb H}}
\def\bbN{{\mathbb N}}
\def\bbO{{\mathbb O}}
\def\bbQ{{\mathbb Q}}
\def\bbR{{\mathbb R}}
\def\bbZ{{\mathbb Z}}
\def\bcA{{\bar{\mathcal A}}}
\def\calA{{\mathcal A}}
\def\calC{{\mathcal C}}
\def\calD{{\mathcal D}}
\def\calF{{\mathcal F}}
\def\calG{{\mathcal G}}
\def\calH{{\mathcal H}}
\def\calI{{\mathcal I}}
\def\calK{{\mathcal K}}
\def\calL{{\mathcal L}}
\def\calM{{\mathcal M}}
\def\calO{{\mathcal O}}
\def\calP{{\mathcal P}}
\def\calR{{\mathcal R}}
\def\calS{{\mathcal S}}
\def\calT{{\mathcal T}}
\def\calU{{\mathcal U}}
\def\fraka{{\mathfrak a}}
\def\frakb{{\mathfrak b}}
\def\frakg{{\mathfrak g}}
\def\frakh{{\mathfrak h}}
\def\tilE{\tilde{E}}
\def\tilq{\tilde{q}}

\def\tDelta{\tilde{\Delta}}
\def\tf{\tilde{f}}
\def\tF{\tilde{F}}
\def\tg{\tilde{g}}
\def\tI{\tilde{I}}
\def\tm{\tilde{m}}
\def\tR{\tilde{R}}
\def\tsigma{\tilde{\sigma}}
\def\tS{\tilde{S}}
\def\tSW{\widetilde{\SW}}

\def\car{\reflectbox{\usym{1F697}}}
\def\rac{\usym{1F697}}

\newcommand{\pluseq}{\mathrel{{+}{=}}}
\newcommand{\minuseq}{\mathrel{{-}{=}}}

% From http://tex.stackexchange.com/questions/154672/how-to-get-a-medium-sized-otimes
\DeclareMathOperator*{\midotimes}{\text{\raisebox{0.25ex}{\scalebox{0.8}{$\bigotimes$}}}}

%%%

\def\Abstract{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\red\bf Abstract.} Following joint work with Itai Bar-Natan, Iva
Halacheva, and Nancy Scherich, I will show that the Best Known Time
(BKT) to compute a typical Finite Type Invariant (FTI) of type $d$ on a
typical knot with $n$ crossings is roughly equal to $n^{d/2}$, which is
roughly the square root of what I believe was the standard belief before,
namely about $n^d$.
}}}}

\def\Acknowledgement{{\raisebox{2mm}{\parbox[t]{3.96in}{\small
{\red\bf Acknowledgement.} This work was partially supported by NSERC
grant RGPIN-2018-04350 and by the Chu Family Foundation (NYC).
}}}}

\def\CarsWisdom{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\bf\red My Primary Interest.} Strong, fast, homomorphic knot and tangle invariants.
\hfill\web{Nara}, \web{Kyoto}, \web{Tokyo}
}}}}

\def\Conventions{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\bf\red Conventions.} $\bullet$ $\underbar{n}\coloneqq\{1,2,\ldots,n\}$.
$\bullet$ For complexity estimates we ignore constant and logarithmic terms:
$n^3 \sim 2023d!(\log n)^dn^3$.
}}}}

\def\Key{{\raisebox{2mm}{\parbox[t]{1.96in}{
{\bf\red A Key Preliminary.} Let $Q\subset\underbar{n}^l$ be an enumerated
subset, with $1\ll q=|Q|\ll n^l$. In time $\sim q$ we can set up a lookup
table of size $\sim q$ so that we will be able to compute $|Q\cap R|$
in time $\sim 1$, for any rectangle $R\subset\underbar{n}^l$.

{\bf\red Fails.} $\bullet$ Count after $R$ is presented. $\bullet$
Make a lookup table of $|Q\cap R|$ counts for all $R$'s.
}}}}

\def\Unfail{{\raisebox{1mm}{\parbox[t]{3.96in}{
\parshape 1 0in 1.84in
{\bf\red Unfail.} Make a restricted lookup table of the form
\[ \left\{\ \underset{\text{dyadic}}{R}\to\underset{>0}{|Q\cap R|}\ \right\}. \]
%\[ \left\{\ \underset{\text{dyadic}}{R}\to|Q\cap R|\ \right\}, \]
%but only for {\em dyadic} $R$'s.

\parshape 1 0in 1.84in
$\bullet$  Make the table
by running through $x\in Q$, and for each one increment
by $1$ only the entries for dyadic $R\ni x$ (or create such an entry, if it
didn't exist already). This takes $q\cdot(\log_2n)^l\sim q$ ops.

\begin{itemize}
\item Entries for empty dyadic $R$'s are not needed and not created.
\item Using standard sorting techniques, access takes $\log_2 q\sim1$ ops.
\item A general $R$ is a union of at most $(2\log_2n)^l\sim 1$ dyadic ones, so counting
  $|Q\cap R|$ takes $\sim 1$ ops.
\end{itemize}

}}}}

\def\Generalization{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\bf\red Generalization.} Without changing the conclusion, replace counts
$|Q\cap R|$ with summations $\sum_R\theta$, where $\theta\colon\underbar{n}^l\to V$ is
supported on a sparse $Q$, takes values in a vector space $V$ with $\dim V\sim 1$, and 
in some basis, all of its coefficients are ``easy''.
}}}}

\def\varphidef{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\bf\red Definitions.} Let $\calG\coloneqq\bbQ\langle\text{Gauss Diagrams}\rangle$, with
$\calG_d$ / $\calG_{\leq d}$ the diagrams with exactly / at most $d$ arrows. Let
$\varphi_d\colon\calG\to\calG_d$ be
$\displaystyle \varphi_d \colon G \mapsto \sum_{D\subset G,\ |D|=d}D =
\sum_{D\in\binom{G}{d}}D$,
and let $\varphi_{\leq d}=\sum_{e\leq d}\varphi_e$.

\parshape 1 0in 1.5in
Naively, it takes $\binom{n}{d}\sim n^d$ ops to compute $\varphi_d$.
}}}}

\def\GPV{{\raisebox{2.4mm}{\parbox[t]{3.96in}{
\parshape 4 0in 2.8in 0in 2.8in 0in 2.8in 0in 3.96in
{\bf\red The \cite{GPV} Theorem.} A knot invariant is finite type of type $d$ iff
it is of the form $\omega\circ\varphi_{\leq d}$ for some $\omega\in\calG_{\leq d}^*$.
\begin{itemize}
\item $\Leftarrow$ is easy; $\Rightarrow$ is hard and IMHO not well understood.
\item $\varphi_{\leq d}$ is not an invariants and not every $\omega$ gives an invariant!
\item The theory of finite type invariants is very rich. Many knot invariants factor
through finite type invariants, and it is possible that they separate knots.
\item We need a fast algorithm to compute $\varphi_{\leq d}$!
\end{itemize}
}}}}

\def\Main{{\raisebox{2mm}{\parbox[t]{3.96in}{
{\bf\red Our Main Theorem.} On an $n$-arrow Gauss diagram, $\varphi_d$ can be computed in
time $\sim n^{\lceil d/2 \rceil}$.

{\red Proof.} With $d=p+l$ ($p$ for ``put'', $l$ for ``lookup''), pick $p$ arrows and look
up in how many ways the remaining $l$ can be placed in between the legs of the first $p$:
}}}}

\def\Details{{\raisebox{1mm}{\parbox[t]{3.96in}{
To reconstruct $D=P\#_\lambda L$ from $P$ and $L$ we need a non-decreasing ``placement
function'' $\lambda\colon\underline{2l}\to\underline{2p+1}$.
\[
  \varphi_d(G) = \sum_{D\in\binom{G}{d}}D
  = \binom{d}{p}^{-1}
    \sum_{P\in\binom{G}{p}}
    \sum_{\text{non-decreasing }\atop\lambda\colon\underline{2l}\to\underline{2p+1}}
    \sum_{L\in\binom{G}{l} \atop L_i\in(P_{\lambda(i)-1}, P_{\lambda(i)})}
    P\#_\lambda L
\]
\vskip -1mm
Define $\theta_G\colon\underline{2n}^{2l}\to\calG_{l}$ by
\[
  (L_1,\ldots,L_{2l}) \mapsto \begin{cases}
    L & \text{if $(L_1,\ldots,L_{2l})$ are the ends of some $L\subset G$} \\
    0 & \text{otherwise}
  \end{cases}
\]
and now
$\displaystyle
  \varphi_d(G) = \binom{d}{p}^{-1}
    \sum_{P\in\binom{G}{p}}
    \sum_{\text{non-decreasing }\atop\lambda\colon\underline{2l}\to\underline{2p+1}}
    P\#_\lambda\left(
      \sum_{\prod_i(P_{\lambda(i)-1}, P_{\lambda(i)})} \theta_G
    \right)
$
\newline can be computed in time $\sim n^p+n^l$. Now take $p=\lceil d/2\rceil$.\qed
}}}}

\def\yarnballs{{\raisebox{2mm}{\parbox[t]{3.96in}{
\parshape 6 0in 1.88in 0in 1.88in 0in 1.88in 0in 1.88in 0in 1.88in 0in 3.96in
{\bf\red Question} (\cite{BBHS}, \web{Fields}). For computations, planar
projections are better than braids (as likely $l\sim n^{3/2}$). But are
yarn balls better than planar projections (here likely $n\sim L^{4/3}$)?
}}}}

\def\refs{{\raisebox{6mm}{\parbox[t]{3.95in}{
%{\red\bf References.}
{\scriptsize
%\par\vspace{-3mm}
\renewcommand{\section}[2]{}%
\begin{thebibliography}{}
\setlength{\parskip}{0pt}
\setlength{\itemsep}{0pt plus 0.3ex}

\bibitem[BBHS]{BBHS} D.~Bar-Natan, I.~Bar-Natan, I.~Halacheva, and N.~Scherich,
  {\em Yarn Ball Knots and Faster Computations,}
  J.\ of Appl.\ and Comp.\ Topology (to appear), \arXiv{2108.10923}.

\bibitem[GPV]{GPV} M.~Goussarov, M.~Polyak, and O.~Viro,
  {\em Finite type invariants of classical and virtual knots,}
  Topology {\bf 39} (2000) 1045--1068, \arXiv{math.GT/9810073}.

\end{thebibliography}}
}}}}

\pagestyle{empty}

\begin{document} \latintext
%\setlength{\jot}{0ex}
\setlength{\abovedisplayskip}{0.5ex}
\setlength{\belowdisplayskip}{0.5ex}
\setlength{\abovedisplayshortskip}{0ex}
\setlength{\belowdisplayshortskip}{0ex}

\begin{center}
\null\vfill\input{Rooting1.pdftex_t}\vfill\null
\end{center}

\end{document}

\endinput

