\section{Introduction}\label{sec:intro}
Is more data always more effective than better annotation?  Is it always cheaper just to obtain and use data with mid-quality annotation than improve annotation quality over a smaller dataset?
Traditionally, to researchers grounded in linguistics, it seemed obvious that higher quality and richer annotation should be better. But with the advent of ``Big Data'',
the common wisdom
seem to have shifted toward more data;
Deep Learning continued this trend (see examples in Section~\ref{sec:intro-data}).

We re-examine these questions
using two types of natural language processing (NLP) tasks:
\textbf{(1)}
 supervised
thematic role prediction
(given a predicate and an argument's word span; here only its syntactic head word)
and word prediction (given a predicate and a role); and
\textbf{(2)}
psycholinguistic tasks outside the explicit  training objective: rating the thematic fit between a verb and its potential arguments.
These tasks have a large body of work in computational linguistics (see section \ref{sec:semmodel}).

We examine the trade-offs  in training models
designed to accomplish these tasks
through modeling events and their participants in  a large corpus (task (1) above). The trade-off we focus on is using more data with
mediocre
linguistic annotations versus little
data with higher-quality
annotations.
For the former,
we replicate a PropBank-based model of \newcite{hong-2018-learn-event-rep} using increasing subsets of their training data,
a large corpus with machine-predicted annotations of mediocre quality.
For the latter, we replace some
annotation layers with  equivalent layers generated by higher quality linguistic tools.
Our model implementation differs from  \newcite{hong-2018-learn-event-rep} in
how missing role information and unknown (out-of-vocabulary) roles are represented.
Our replicated baseline is stronger than theirs.

We also test whether  training on the higher quality data keeps yielding better models as training set size increases.
Last, we also look at the trade-offs in training models over increasingly richer, more fine-grained, but potentially sparser semantic role annotation.

\subsection{The conundrum of data}\label{sec:intro-data}

Our
first goal
is to revisit a widely held assumption in the NLP community: mediocre machine-predicted annotation  yields at scale better (or equivalent) models than high quality annotations (manual or state-of-the-art machine-predicted) whose scale is much smaller, due to compute, cost, and time constraints.
\newcite{mcclosky:2006-self-train} and \newcite{foster++:2007-BNC-self-train}, \textit{inter alia},
use self-training%
\footnote{Augmenting
few
manual annotations with ones predicted by a prior version of the same parser over a large text.}
to improve syntactic parsing -- as an alternative to manually annotating more data -- in same or different domain/genre.
\newcite{petrov++:2010:uptraining} show that using  100k machine-predicted constituency parses to train a new dependency parser contributed the equivalent of
2k manually annotated parses. Manually annotating is slower and more expensive but better by definition.

However, despite growing amounts of annotated and unannotated textual resources, a number of tasks with traditional linguistic levels of representation remain a challenge, with unsatisfactory performance in various research areas and applications: artificial intelligence (AI), machine reading / knowledge graph population, chatbots and natural language understanding (NLU), as well as computational psycholinguistic modeling and computational linguistics.

How do quality and quantity affect our above-mentioned semantic and psycholinguistic tasks?

\subsection{Semantic modeling}
\label{sec:semmodel}
Our second goal
is to explore ways to improve semantic modeling and the representations used for this modeling.  We use \term{semantic modeling} to refer to
tasks at the intersection of NLP and psycholinguistics that have to do with representing and processing generalized event knowledge \citep{pustejovsky1991,zarcone2011}
. The underlying tasks include:

\newterm{Semantic role labeling (SRL)}
is the task of annotating text according to semantic frames and their roles as defined in frameworks such as FrameNet, VerbNet, or PropBank~\cite{framenet-Baker++:1998,verbnet-SchulerPalmer:2005,propbank-PalmerGildeaKingsbury:2005}.
For example, given `I cut the cake with...' (1) `marzipan' or (2) `a knife',  the role
\term{Instrument/A3-MNR} is normally desired for (2) but not for (1).

\newterm{Role prediction}:
a simplified SRL task we use here. Instead of a sentence, the input is just a verb $v$ and a noun $n$; optionally additional nouns and their thematic relation (role) with $v$; the expected output is the most likely thematic role of $n$ with $v$ in the same event.%
\footnote{A similar task -- only without the input nouns -- is the
    \newterm{(role) selectional preference} of the verb: what roles are more likely with this verb? E.g., `cut': \term{Agent/Arg0, Patient/Arg1, Instrument/Arg3-MNR}.
}

\newterm{Slot / Role filling}
\footnote{We interchangeably refer to it here as \newterm{word prediction}.}
given a predicate (typically a verb) and a thematic role, what word or phrase would be most appropriate for that role? This task can be viewed as the complement of SRL (given the word or phrase, what is its role?).

\newterm{Thematic fit}:
Given a predicate and a role (say, `cut' + \term{Instrument}), how well would a speaker of a given language (here, English) find `knife' or `spoon'
fitting to the given role?
And by extension:
given a
subset of a predicate and arguments (optionally also modifiers), can we predict the typicality level of the most recently added member to the rest of the given subset? This is often an abstraction of sentence comprehension (in humans): our {\it thematic fit} estimation changes as we hear more of the uttered sentence \citep{amsel2015close}.

Indirect thematic fit estimation learning from SRL annotations has shown promising results \cite{hong-2018-learn-event-rep,tilk2016event,santus2017measuring}.
Following \newcite{hong-2018-learn-event-rep} and others, we consider only the arguments' syntactic heads together with their semantic roles
\footnote{We also follow them in using the simplified ProbBank roles (\term{A0, A1, ...}), unlike much of the thematic fit literature that uses \term{Agent, Patient,} etc. \cite{dowty1991thematic}.
}
Given a new role,
predict the fitness level of all known words and
use the score of the given filler in the full score distribution as a fitness rating. (We also look at the complement: given a new word, predict the fitness of each possible role). These predictions are scored relative to human
judgments (see Section~\ref{sec:bg}).

\subsection{Contributions}
Exploring the data requirements of modeling human semantic representations allows us to revisit the question of the inherent difficulty of semantic tasks:
does semantic processing simply require more annotated data to achieve high quality, or
has it not been represented in a way conducive for computers to learn adequately?

We look into how annotation quality and
quantity (both the number of semantic frames
and the number of sentences)
affect learning. We also explore annotation granularity,
taking thematic role set granularity (number of roles in model) as a test case.
We often see that modelers  focus on only the two most frequent PropBank
semantic arguments (Arg0 and Arg1) and ignore the rest or lump the rest together under a catch-all tag. Similarly, they focus on only few modifiers (e.g.,
\newcite{tilk2016event} and \newcite{hong-2018-learn-event-rep} use 2 core roles and 3 modifiers).
We therefore trained models with increasing numbers of
thematic role types
 (the predicate, its core arguments, and often-optional, non-core arguments or modifiers), using the better taggers, parsers, and labelers, and observed changes in prediction quality.

To summarize our main contributions, we
\vspace{-9pt}
\begin{enumerate}[noitemsep]
    \item test how quality of annotation affects supervised role/word prediction, as training set size increases. We show in small to large sizes that the mediocre  annotation method
    is \textit{not} as useful as better quality annotation.

    \item test how quality of annotation affects thematic fit estimation as an application of our models that is not part of the training objective.
    We show  that quality increases with training size but surprisingly, variance is high even in larger sizes, leaving no clear winner annotation.

    \item claim that the high variance of the (indirectly optimized for) thematic fit estimation makes it more difficult to interpret conclusions from previous studies that did not report it.

    \item show new state-of-the-art results on role and word prediction, as well as thematic fit estimate correlations.

    \item tease apart effects of quality and quantity;
    tease apart
    the number of training sentences from the number of training frames (the semantic frames annotated in these sentences).

    \item  test how annotation  granularity (role set size)
    affects thematic fit (and role/word prediction)

    \item provide a new, open-data, large lexical semantic (and syntactic) resource in English, revising and expanding the previously published RW-Eng \cite{sayeed2018}.

\end{enumerate}

\section{Background and related work}\label{sec:bg}
\paragraph{Thematic fit norms}
take the form of averaged human-rated plausibility scores for a verb, a noun, and the noun's thematic role.
For example, we ask human raters: how well does "sword" fit as an instrument with
the verb "cut"?  Thematic fit norms are a subset of semantic feature/property fit norms that pertain to verb-argument relations.  Exploring thematic fit allows for exploring the structure of the human lexicon and for exploring generalizations about affordances and the relationship between world knowledge and compositional semantics.

\citet{mcrae1998modeling} collected an early set of thematic fit norms.
Human raters were asked
to use a 7-point Likert scale
to judge the fit of particular nouns with particular verbs in given roles.  These  plausibility judgements focused mainly on \term{Agent-Patient} roles.  Later \citet{ferretti2001integrating} provided norms for \term{Instrument} and \term{Location} roles.

\citet{pado2007integration} and \citet{pado2009probabilistic} sought to develop a probabilistic model of thematic fit.  In the process, they collected additional \term{Agent-Patient} norms for a limited, balanced subset of verb-noun pairs chosen by frequency in the Penn Treebank \cite{PTB-Marcus++:1993}.    Together, in addition to later efforts focusing on verb polysemy \citep{greenberg2015verb}, these collected norms form an empirical basis for modeling
human semantic expectations, albeit limited to roles that are relatively frequent and easily understood by raters.

\paragraph{Distributional modeling of thematic fit}
Early work in thematic fit modeling  emphasized building partially or fully supervised corpus-based models \cite{pado2007dependency,herdagdelen2009bagpack}. The question arises whether less task-specific, less supervised models can be used to model the semantic generalizations that would underpin a robust thematic fit model. \citet{baroni2010distributional} proposed the Distributional Memory (DM) approach,  a very high-dimensional  tensor space representation that memorizes the frequency of numerous syntactic relations between lexical items in a large corpus  consisting of UkWaC \cite{ferraresi2008introducing}, the British National Corpus \cite[BNC]{british2007british}, and Wikipedia.

\citet{sayeed2016thematic} applied the DM approach to relation features based in an early form of neural SRL tagger \cite[SENNA]{collobert2011natural}.  This and Baroni and Lenci's syntax-based features were combined synergistically to produce thematic fit correlation scores superior to the result of each individually. The DM models were constructed without any reference to the evaluation data and can be considered unsupervised in that sense.  However, their reliance on matrix multiplications made them difficult to extend to evaluating multiple roles simultaneously due to sparsity. They are also difficult to parameterize for finding optimal models.

\citet{tilk2016event} and \citet{hong-2018-learn-event-rep} worked to supplant DM approaches with neural networks.  Their models train ``event'' embeddings with a preselected roleset, representing an entire semantic frame as input.
Some
of the role ``slots'' can be left empty, allowing for a variable number of arguments to be tested.  \citet{hong-2018-learn-event-rep} applied a two-task training objective (limited SRL and role-filler noun prediction) to train NN models that not only performed well on thematic fit ratings, but also on several additional semantic tasks (e.g., event similarity and multiple-role compositionality).

\citet{sayeed2016thematic}, \citet{tilk2016event}, and \citet{hong-2018-learn-event-rep} all depend on the
"Rollenwechsel-English", aka "RW-eng" corpus, hereafter \vi~\citep{sayeed2018},
and use almost all of the corpus to train their models.
Our work builds on the work of \citet{hong-2018-learn-event-rep},
but differs in role set implementation,  some hyper-parameter settings, and minor other technical details.
Our work also builds on \vi\ and extends it with newer annotation layers.
One of the things we test is  whether the quantity of data used for these models is necessary to achieve those results, particularly on the
thematic fit task.

\section{Dataset}\label{sec:dataset}
In order to explore the topics raised in Section~\ref{sec:intro}, we used the above-mentioned large-scale \vi\ corpus.
It is annotated with a fast-but-outdated SRL tagger and syntactic parser. We added new annotation layers with higher quality, more modern taggers and parser (hereafter \vii, "Our annotations").
We replicated baseline models on \vi\  and trained new models on \vii, as detailed in Section~\ref{sec:experiments}.

\subsection{Text and \vi\  Annotations}
The \vi\ corpus
\cite{sayeed2018}
consists of the SENNA-derived SRL output over 78M sentences from 2.3M documents.  The documents come from the BNC and ukWaC.  SENNA extracts multiple predicates per sentence and, for each predicate, it identifies spans of text representing noun phrases that fill PropBank
roles for that predicate.  For every document, sentence, and predicate in that sentence, \vi\
contains XML-formatted information on the corresponding SENNA output.  In particular, it uses a series of head-finding heuristics \cite{sayeed2016thematic}
to identify the syntactic heads of the role-filling spans---typically noun phrases, which can contain complex constituents such as subordinate clauses, but the SRL role spans could also cover only fractions of syntactic constituents, hence the need for a heuristic beyond only using a parser.

\subsection{Our Annotations (\vii)}
NLP often contains ``pipelines'' of serial annotation processes, such as:
tokenization and morphological analysis (including lemmatization or stemming),
syntactic parsing,
and a final processing such as machine translation,
NLU (for chatbots), and sometimes SRL.
As mentioned in Section~\ref{sec:intro},
until about ten years ago, a rule of thumb often held: better quality of intermediate processing results in better quality at the end, although improvements are not linear, and small intermediate gains do not always translate to gains at the end of the pipeline.

Here we set to test out the new rule-of-thumb of the last decade for the case of thematic role prediction, slot filling (word prediction), and thematic fit estimation. We replaced annotation layers from older tools
with annotations based on more recent tools (see below),
introducing a
non-negligible improvement in intermediate annotation quality.

The first step in doing so is to determine a consistent tokenization schema across all annotation layers, as some taggers either expect a certain schema or apply their own even if input text is largely tokenized.
We iteratively modified our tokenization schema to reduce token count mismatch between the new layers from over 20\% of sentences to less than 1\%.
Once we reached this low mismatch ratio, we marked and excluded the fewer mismatched cases from our experiments.

We  added the following new annotation layers:

\paragraph{Lemmas by a newer morphological analyser: Morfette v0.4.4} \cite{chrupala-etal-2008-learning-morfette,chrupala-2011-efficient-morfette},
precompiled
by
Djam\'e
Seddah,\footnote{We thank Djam\'e Seddah for making it available to us.} who included a transformed xtag lexicon \cite{seddah-spmrl-2013-overview}. Training was done on the Penn Treebank~\cite{PTB-Marcus++:1993}, using the Collins split.

\paragraph{Syntactic parses by a newer parser: spaCy 2.0.13} \cite{spacy-honnibal-johnson:2015:EMNLP,spacy2}.\footnote{https://spacy.io}
We forced spaCy to use our own tokenization
instead of its own.

\paragraph{Semantic frames by a newer SRL tagger: LSGN} \cite{lsgn-he-2016-2018},  an end-to-end BiLSTM-based SRL tagger using ElMo embeddings \citep{Peters:2018}. It gets 86\% F1 score on the CoNLL05 WSJ test set, compared to SENNA's 75\%.
For each semantic frame, we aligned the spaCy parses to each argument span in order to find the syntactic head of the span, using a similar heuristic as
in \vi.
We only used the heads for modeling (see Section~\ref{sec:experiments}).
We aligned each token in the argument span across all layers (surface word-form, Morfette lemma, spaCy lemma and entity (NER) tag, etc.)

\subsection{Train / dev / test split}\label{sec:split}
Of about 3500 files, few (less than 0.4\%) were discarded due to processing issues, leaving us with 3490 files.
Due to the fact that the corpus is comprised of more than one source, we  assigned 16 files as the development set, and 16 as the test set, chosen uniformly\footnote{%
Dev files:  [ 217, 435, 651, 868,  1085, 1302, 1519, 1736,
             1953, 2170, 2387, 2604,  2821, 3038, 3255, 3472].
Test files: [ 218, 436, 652, 869,  1086, 1303, 1520, 1737,
             1954, 2171, 2388, 2605,  2822, 3039, 3256, 3473].
             }.
The rest of the files were used as the full training set.
Subsets of this training set were each chosen uniformly too,
to emulate availability of smaller training sets.
This split departs from \newcite{hong-2018-learn-event-rep}, which used the last 0.4\% (14 files) as the test set, the immediately preceding 0.4\% as the dev set, and the rest for training.

\subsection{Additional test sets}\label{sec:thematic-fit-tests}
We also tested our models on the above-mentioned thematic fit test sets, \textit{without} optimizing on them:

\newterm{Padó-all:} A human-rated thematic fit score dataset collected with psycholinguistic motivations, created by \newcite{pado2007integration} and containing 414 verb-noun-role triplets, where every two triplets differ only in the role, one of \{\term{Arg0, Arg1, Arg2}\}.

\newterm{McRae-all:} A similar dataset with human scores, created by \newcite{mcrae1998modeling}, containing 1,444 such triplets, grouped in pairs similarly, but the roles are only \{\term{Arg0, Arg1}\}, and the words are less frequent  (a harder task).

\section{Experiments}\label{sec:experiments}

\subsection{Baseline Model Configuration}
For our baseline (\vi-based models), we used a multi-task residual network (ResNet) model \citep{he2016deep,jegou2010product}. Our implementation is similar to the best reported model in \newcite{hong-2018-learn-event-rep}, called ResRofa-MT, for ease of comparison.\footnote{We thank Xudong Hong for his help.}
One task was \newterm{role prediction}, given a verb, a (typically noun) word, and zero or more  $\langle$role,word$\rangle$ pairs.
For example, given `cut' and `knife', predict \textit{Instrument}, or in PropBank's roles: \textit{A3-MNR}.
A second task was \newterm{word prediction} (slot / role filling), given the word's role, the verb,  and the zero or more $\langle$role,word$\rangle$ pairs.
For example,  given `cut' and \textit{A3-MNR}, predict `knife'.
For both tasks we could optionally provide more input, say, $\langle$\textit{A1},`cake'$\rangle$.
Aside from having different prediction layer per task, the tasks shared the same neural network (and parameters).
Apart from software engineering differences,
the most notable difference in our implementation is having two separate labels for \textit{missing role} and \textit{unknown role} instead of one for both. The former is used to mark the absence of a certain role from the annotated frame instance. The latter is used as a catch-all for sparser roles not explicitly represented. The baseline role set was comprised of \textit{PRD, Arg0, Arg1, ArgM-TMP, ArgM-LOC, ArgM-MNR}: the predicate, PropBank's arguments 0 and 1,  the temporal, location, and manner modifiers (and \textit{missing role} and \textit{unknown role}).

For faster training time, we used a batch size of
1024
samples (unless otherwise specified) with the
risk of too coarse updates. We kept a simple setting of 0.1 learning rate and no decay.
We applied the same vocabulary pruning to the top 50k most frequent lemma forms as \newcite{hong-2018-learn-event-rep} did.

\begin{table*}[!hbt]
    \centering
    \begin{small}
    \begin{tabular}{cccccccc}
        \hline
        Training & & & & \multicolumn{2}{c}{$\rho_\text{Padó}$}  & \multicolumn{2}{c}{$\rho_\text{McRae}$} \\
        sample & & & & & & & \\
        (\# trials) & Version & Role acc. & Word acc. & final & max & final & max\\
        \hline
        \multirow{2}{*}{0.1\% (3)} & \vi & .8857 $\pm$ .0009 & .0435 $\pm$ .0001 & .2760 $\pm$ .0331 & .2760 $\pm$ .0331 & .1924 $\pm$ .0110 & .1968 $\pm$ .0124 \\
        & \vii & .9102 $\pm$ .0063 & .1029 $\pm$ .0007 & .3149 $\pm$ .0308  & .3257 $\pm$ .0412  & .1934 $\pm$ .0044 & .2065 $\pm$ .0057  \\
        \hline
        \multirow{2}{*}{1\% (5)} & \vi & .9332 $\pm$ .0006 & .0819 $\pm$ .0002 & .5150 $\pm$ .0299 &  .5230 $\pm$ .0141 & .3142 $\pm$ .0079 & .3157 $\pm$ .0069 \\
        & \vii & .9656 $\pm$ .0001 & .1416 $\pm$ .0002 & .4850 $\pm$ .0135 & .4975 $\pm$ .0141  & .3368 $\pm$ .0130 & .3398 $\pm$ .0118\\
        \hline
\multirow{2}{*}{10\% (3)} & \vi & .9419 $\pm$ .0017 & .0941 $\pm$ .0005 & .5166 $\pm$ .0345 & .5368 $\pm$ .0020 & .3996 $\pm$ .0206 & .4126 $\pm$ .0091\\
        & \vii & .9715 $\pm$ .0010 & .1541 $\pm$ .0045 & .5229 $\pm$ .0227 & .5623 $\pm$ .0227 & .3935 $\pm$ .0192 & .3981 $\pm$ .0223 \\
        \hline
\multirow{2}{*}{20\% (3)} & \vi & .9445 $\pm$ .0003 & .0982 $\pm$ .0011 & .5219 $\pm$ .0069 & .5306 $\pm$ .0073 & .4314 $\pm$ .0123 & .4381 $\pm$ .0032 \\
        & \vii & .9733 $\pm$ .0004 & .1621 $\pm$ .0048 & .5363 $\pm$ .0035  & .5494 $\pm$ .0111 & .4322 $\pm$ .0232 & .4385 $\pm$ .0257 \\
        \hline

    \end{tabular}
    \end{small}
    \caption{\vi\  vs \vii: model MTRFv4Res, train \% out of 3490 text files, dev/test size = 16 text files each,
    batch=1024 unless specified. (\# runs in parentheses).
    \shwTrn{\#itr: number of epochs till early stop.}
    Role/word prediction accuracy (acc.); Spearman's rank correlation ($\rho$) for Padó-all and McRae-all.
    final:score of last saved model; max: maximal score in any epoch.
    }
    \label{tab:v1-vs-v2}
\end{table*}

\subsection{\vi\  vs \vii\ experiments}\label{sec:v1-vs-v2}
We trained and evaluated models in the above configuration  with increasing training set size
 (see Section~\ref{sec:split}), measured in percentage of total number of available training sentences.
For each training set size, we trained few models on \vi\  and same number of models on \vii.

Table~\ref{tab:v1-vs-v2} shows that role prediction accuracy increases with training set size as expected and surpasses 90\% at 1\% of the training set for \vi\ and already at 0.1\% for \vii. At 10\% of the training, it reaches mid-90s for \vi\ and high-90s for \vii, with small further gains at 20\%.%
\footnote{The full dataset size was prohibitive for training given our computing resources.}
The advantage of \vii\ was kept throughout but decreased from over 5-6\% (absolute) at 0.1\% size to 3-4\% at higher training set sizes.
Word prediction accuracy followed similar trends, but \vii--\vi\ gaps there remained about 6\% in all set sizes.%
\footnote{Preliminary experiments, having varying sized of dev and test sets, showed the same pattern: \vii\ advantage.}

We also tested the models on two thematic fit tasks on which the models were not trained, using the additional test sets described in Section~\ref{sec:thematic-fit-tests}.
Variance over multiple training runs per model was not reported in the relevant literature, so the high variance we see on both
Padó-all%
\footnote{In Padó-all
evaluations, test set target \term{Arg2} was mapped to \textit{unknown-role}, since it was not in the model's role set
(McRae-all only has \term{Arg0,Arg1} targets).}
and McRae-all
is a novel finding.%
\footnote{We trained 5 models for each version in small training sizes, and 3 for each in large sizes, due to resource limitations.}
We report both the best- and last-epoch results for these tasks on the rightmost two columns of Table~\ref{tab:v1-vs-v2}.
We see  \vii\ advantage on Padó-max 10\% and 20\% but not at lower sizes. Padó-final results are mixed, particularly at 10\%-training, as are the results on McRae (both last and best).
We see clear training size effects on McRae(best+last), but not on Padó (except in the smallest size).

The \vi\  results on the 10\% and 20\% subsets are our closest replication of \newcite{hong-2018-learn-event-rep}, modulo the above-mentioned role representation.

\begin{table*}[!hbt]
    \centering
    \begin{small}
    \begin{tabularx}{\textwidth}{Xp{.61in}p{.0in}p{1.05in}p{0.98in}p{.80in}p{.88in}}
        \hline
        Name & Role set & \shwTrn{\#itr}
        & Role acc. \shwTrn{tr/} dev/test & Word acc. \shwTrn{tr/} dev/test & $\rho_\text{Padó}$~final/max & $\rho_\text{McRae}$~final/max \\
        \hline

        2Args3Mods  &
            baseline &
            \shwTrn{18} &
            \shwTrn{.9790 /} \textbf{.9653 / .9656} &
            \shwTrn{.1548 /} .1393 / .1414 &
            .4765 /.4840 & .3205 / .3240 \\
        \hline
        3Args3Mods &
            +Arg2 &
            \shwTrn{18} &
            \shwTrn{.9753 /} {.9595 / .9596} &
            \shwTrn{.1714 /} .1544 / .1563 &
            \textbf{.5056 / .5150} & .3340 / .3340 \\
        3Args4Mods &
            +AM-MOD &
            \shwTrn{19} &
            \shwTrn{.9758 /} {.9606 / .9609} &
            \shwTrn{.1780 /} .1631 / .1661 &
            .4663 / .4928 & .3261 / .3373 \\
        3Args5Mods &
        +AM-ADV &
        \shwTrn{19} &
        \shwTrn{.9688 /} .9513 / .9516 &
        \shwTrn{.1805 /} .1665 / .1691 &
        .4838 / .5024 & .3381 / .3407\\
        3Args6Mods &
        +AM-DIS &
        \shwTrn{19} &
            \shwTrn{.9679 /} .9503 / .9510 &
            \shwTrn{.1828 /} .1683 / .1712 &
            .4742 / .4851 & .3357 / .3370 \\
        3Args7Mods &
        +AM-NEG &
        \shwTrn{19} &
            \shwTrn{.9681 /} .9506 / .9512 &
            \shwTrn{.1874 /} .1742 / .1768 &
            .4808 / .4886 & .3357 / .3385 \\
        all.args+mods &
            all-roles &
            \shwTrn{19} &
            \shwTrn{.9632 /} .9450 / .9459 &
            \shwTrn{.1918 /} \textbf{.1783 / .1810} &
            .4833 / .5109 & .3205 / .3209 \\
        \hline

        3Args3Mods &
            +Arg2 &
            \shwTrn{18} &
            \shwTrn{.9753 /} .9595 / .9596 &
            \shwTrn{.1714 /} .1544 / .1563 &
            .5056 / .5150 & .3340 / .3340 \\

        4Args3Mods & +Arg3 &
            \shwTrn{18} &
            \shwTrn{.9747 /} .9580 / .9585 &
            \shwTrn{.1732 /} .1557 / .1582 &
            .5007 / .5119 & .3365 / .3394 \\
        5Args3Mods
        & +Arg4 &
            \shwTrn{18} &
            \shwTrn{.9738 /} .9574 / .9576 &
            \shwTrn{.1737 /} .1559 / .1583 &
            .4901 / .5108 & \textbf{.3473 / .3473} \\
        6Args3Mods
        & +Arg5 &
            \shwTrn{18} &
            \shwTrn{.9738 /} .9577 / .9579 &
            \shwTrn{.1734 /} .1560 / .1582 &
            .4925 / .5237 & .3166 / .3182 \\
         \hline
    \end{tabularx}
    \end{small}
    \caption{Increasing role set granularity (\vii): model MTRFv4Res, train size = 1\% of 3490 text files; dev/test size, batch size and metrics same as in Table~\ref{tab:v1-vs-v2}.

    Top half: adding next role in descending role frequency.
    Lower half: adding only arguments (skipping modifiers).
    In each half, the roleset in each row is a superset of the  previous row.
    }
    \label{tab:add-arg2}
    \vspace{-6pt}
\end{table*}

\begin{table}[!hbt]
    \centering
    \begin{small}
    \begin{tabular}{rl}
        \hline
        Count & Label \\
        \hline
        2,120,947	&	ARG1	\\
        1,234,063	&	PRD	\\
        1,090,751	&	ARG0	\\
        688,268	&	ARG2	\\
        380,294	&	ARGM-TMP	\\
        257,056	&	ARGM-MOD	\\
        227,040	&	ARGM-ADV	\\
        220,502	&	ARGM-MNR	\\
        194,532	&	ARGM-LOC	\\
        95,724	&	ARGM-DIS	\\
        87,036	&	ARGM-NEG	\\
        68,156	&	ARGM-PRP	\\
        39,780	&	ARGM-DIR	\\
        35,938	&	ARGM-ADJ	\\
        31,004	&	ARG3	\\
        27,850	&	ARGM-CAU	\\
        22,092	&	ARG4	\\
        18,254	&	ARGM-EXT	\\
        13,456	&	ARGM-PRD	\\
        9,108	&	ARGM-LVB	\\
        5,540	&	ARGM-GOL	\\
        3,826	&	ARGM-COM	\\
        3,460	&	ARGM-PNC	\\
        1,686	&	ARGM-REC	\\
        12	&	ARG5	\\
\hline
    \end{tabular}
    \end{small}
    \caption{SRL label counts in dev set}
    \label{tab:srl-label-counts}
\end{table}

\begin{table}[!bt]
    \centering
    \begin{tabular}{|l|r|r|}
        \hline
        \textbf{data set} & \textbf{previous (\vi)}& \textbf{this (\vii)}  \\
        \hline
        \textbf{training 10\%} & 16,889,581  &        20,151,313 \\
        \textbf{dev}           &    766,333  &           915,473 \\
        \textbf{test}          &    767,325  &           919,365 \\

        \hline

    \end{tabular}
    \caption{Number of frame annotations in \vi\ vs. \vii}
    \label{tab:v1-vs-v2-annot}
    \vspace{-16pt}
\end{table}

\subsection{Roleset Granularity (on \vii)}

Model design includes decisions about features and their granularity. Generally, fine-grained features provide sharper, more accurate distributions of underlying phenomena, but their values, especially at the distribution ``tail'', suffer from higher sparsity, which may lead to difficulty in learning them well and hence lower performance overall.
This tension between granularity and sparsity exists also for the case of role set granularity.
Many studies have chosen the coarser side, using only few thematic roles. For example, \newcite{hong-2018-learn-event-rep}, which we take as our main baseline, use only 2 arguments and 3 modifiers, within the PropBank framework---in itself already a framework with  a coarse role set (compared to VerbNet and FrameNet).

We tested the effect of increasing role set granularity. In other words:
is less (less coarse role set) more (higher quality)?
We analyzed the distribution of the roles in the dev set (see Table~\ref{tab:srl-label-counts}) and expanded the role set one role at a time, according to their frequency (more frequent first). For training run time economy, all models in this subsection were trained on 1\% of the \vii\ data.

The first semantic role to be added was \term{Arg2}. Note that now in Padó-all
evaluations, \term{Arg2} is no longer mapped to \textit{unknown-role}.
See Table~\ref{tab:add-arg2}.
It turns out that while role set prediction accuracy slightly dropped, word prediction accuracy actually improved by more than 1\%. Same trend held also for Padó-all (about 3\% gain in Spearman's correlation) and McRae-all (over 1\%).
This stands in contrast to preliminary experiments  on \vi.\footnote{Hong, personal communication.}

Next down the role list, we added \term{ArgM-MOD}.
While we saw a slight gain in word prediction accuracy, we saw a drop in Padó-all and perhaps a slight drop in McRae-all. However, adding \term{ArgM-ADV} resulted in a drop in role prediction but gains in the thematic fit tasks.
Adding \term{ArgM-DIS} resulted in some drop on the thematic fit tasks, while adding \term{ArgM-NEG} yielded relative gains in word prediction and Padó-all.
Adding all  roles to the model (\term{all.args+mods}) yielded mixed results: a further small drop in role prediction (in fact, no model outperformed the baseline on this task), a pronounced gain in word prediction (highest result even compared to Table~\ref{tab:v1-vs-v2}!), and lower scores on the thematic fit tasks compared to adding only \term{Arg2}.

Modifiers are often more freely optional, and are not considered core arguments of the semantic frame.
We therefore also tested the effects of only adding core arguments to the baseline roleset (see bottom part of Table~\ref{tab:add-arg2}).
Adding \term{Arg3} resulted in no much change in any task, compared to \term{+Arg2}.
Adding \term{Arg4} yielded a gain on Padó-all last result (but not the maximal result).
Adding \term{Arg5} resulted in a clear drop on the thematic fit tasks, which is expected: \term{Arg5} is very sparse, so its learnability is low, and roleset confusability is higher due to increased number of roles.
However, we take differences on Padó-all and McRae-all with a grain of salt, given the above-mentioned high variability.

\section{Discussion and Analysis}
The advantage of \vii-trained models over \vi-trained models for role and word prediction in every training size
undermines
the NLP community's widely-held working assumption that mediocre is always preferable
at scale.
It supports our hypothesis that sometimes
better annotations yield better results, even at scale,
compared to baselines of reasonable mediocrity.
While we do not know if this holds also in the limit, this finding is worth keeping in mind even with today's very large datasets.

To validate our claim that \vii\ annotations are much better than \vi,
we randomly sampled
8
sentences, and counted
the difference in number of frames,
number of roles/arguments,
and number of wrong roles between the two datasets.
\vii\ had a clear advantage over \vi\ in identifying frames and roles, with almost no cases in which \vi\ did better.
This advantage held in both the number of cases and the number of sentences with offending cases (63--75\%).
Both \vi\ and \vii\ had few wrong roles, similar in number, with perhaps a slight advantage to \vi\ (one case).%
\footnote{Note that for verification speed, we only verified correctness of \vii's \term{Arg0, Arg1}; the rest we assumed correct.}
Due to the small sample size and evaluation method, we take the findings above as mainly qualitative, but still strongly supporting our assumption of \vii\ advantage.

Was \newterm{quality} the only factor?
Several aspects here:
\textbf{(a)} better argument span and role prediction in LSGN in \vii\ compared to SENNA in \vi, together with
\textbf{(b)} the greater \textit{quantity} of predicted frames with LSGN,
compounded by
\textbf{(c)} better parsing quality of spaCy in \vii\ compared to Malt in \vi, and
\textbf{(d)} Morfette's better lemma analysis.

As for \newterm{quantity},
it turns out
it may have also played a role:
we compared the number of semantic frame annotations in the 10\% training subset, and found out \vi\ has less than 84\% of
\vii's,
for the same underlying sentences (Table~\ref{tab:v1-vs-v2-annot}).
We  call it \newterm{frame quantity}  to tease it apart from  \newterm{sentence quantity}: the number of (underlying) sentences used for training. Perhaps the better SRL and parser quality contributed both to the increase in number of frames as well as to the number of
correctly extracted syntactic head words (one per argument, using better aligned parses).

Was the \vii\ advantage mainly due to frame quantity?
1\%-training \vii\ outperforming 10\%-training \vi\ on role and word prediction,
even though the former was trained on an
eighth of the number of frames
(and tenth of the sentences), suggests otherwise. This trend repeated with
0.1\%
\vii\ outperforming 1\%
\vi\ on word prediction.
Higher quality annotations resulted in large \textit{savings} in training sentence quantity
for similar prediction quality.

How does our implementation fare compared to \newcite{hong-2018-learn-event-rep}?
Our \vii\ maximal result on Padó-all (59.9\% best single run, 56.2\% averaged) outperforms their reported 53\% with only 10\% of their data.
On McRae-all our maximal result (45.9\% best single run, 43.9\% averaged)
outperforms their reported 42.5\%,
despite having less frequent
pred-arg
combinations.
Our \vii\ outperforms their reported 94.7\% role
accuracy, even at 1\% of their training data, presumably
due to our
separating the
\term{unknown role} from \term{missing role}.

Could we have reached even higher results? Our model setting is on the simpler side with only two tasks, one of which is role prediction with accuracy approaching 100\% (therefore, after a few iterations,
largely only the other task  affects the learning). More complex models or additional tasks (and/or modern word embeddings) are likely to do even better on the word prediction and the thematic fit tasks.
However our focus in this work was not on creating the best model, but on exploring the effects of annotation quality and quantity up to large scale.

Did the effort of creating \vii\ pay off also for the \textbf{psycholinguistic task}? We see a clear, but rather small gain in Padó-all on the larger subsets (10\%, 20\%). In McRae-all the gain is actually on the smaller subsets, and goes away on the larger ones. Therefore, we conclude that
for
improving indirectly-supervised psycholinguistic tasks, the cost-effectiveness of this exercise is questionable, but it still suggests that progress can be made in resource-constrained environments through limited improvements in label accuracy.

As for \newterm{annotation granularity}, adding \term{Arg2} to the baseline's role set showed clear gains across the board (except perhaps in role prediction), which may seem surprising at first:
\textbf{(a)} the role prediction task is now harder (larger role set) yet accuracy did not drop by much. This could be due to the increased thematic homogeneity in the catch-all role tag.
\textbf{(b)} Word prediction (slot-filling) was not expected to be affected, since the embeddings are not relearned in our setting. But gains may show if many words tend to assume only certain roles (e.g., be Arg2-centric).
\textbf{(c)} Role prediction in Padó-all should have also been harder, therefore showing lower correlation scores. But recall that baseline scores are not directly comparable here because all roles but Arg0 and Arg1 were mapped to Arg2 for the evaluation of Padó-all, a mapping which was no longer needed once we added Arg2 to the role set.
\textbf{(d)} gain in McRae-all is surprising at first because McRae-all only has Arg0 and Arg1 targets, so adding Arg2 could only distract from these targets. But recall we have a catch-all role, and adding Arg2 to the role set made the catch-all role distribution more focused, and therefore presumably less prone to mix-ups with Arg0 and Arg1 -- especially since McRae-all contains less frequent words, which makes them harder to learn.

Adding the next modifiers in order of descending frequency (top part of Table~\ref{tab:add-arg2}) yielded
consistent monotonous gains in word prediction, with the \term{all-roles} model, trained on 1\% of the training set, performing even better than larger subset models in Table~\ref{tab:v1-vs-v2}. This seems to support  finer-grained representation. However, curiously, adding only core arguments (lower half of Table~\ref{tab:add-arg2}) did not make a noticeable difference on this task.
Adding the next modifiers after \term{Arg2} did not improve Padó-all, which is expected, since it only contains arguments 0-2.
But the top result of \term{+Arg4} on McRae-all is surprising: this test only has \term{Arg0, Arg1} targets. We suspect this result is an outlier even given the high variance, but further investigation is in order.

\paragraph{Ethical considerations}
This work used two large corpora (the
BNC and ukWaC);
hence
 it is not practical to completely account for all the data in the corpus.
The BNC is a curated corpus, but
part of their transcribed conversations were recorded without prior consent of all recorded individuals. This is no longer an acceptable conduct in Great Britain and many other countries.
Our annotated corpus (\vii) clearly marks the source of each sentence, so those who wish to exclude BNC data can easily do so.
Insofar as future work keeps that in mind, we believe there to be minimal scope for direct misuse of our results.

\section{Conclusions and Future Work}
We set out to test  the NLP community's widely-held assumption that mediocre linguistic annotation at scale is as good as better annotation.
We saw that models trained on better lemmas, syntactic parses, and SRL tags (our \vii) did better than the baseline (\vi) using older technology at all training set sizes, and even at scale -- on both (directly supervised) role and word prediction.
We also saw ``training dataset savings'' potential: training on smaller sets with better annotations yielded sometimes better results than training on datasets with less advanced annotations that were~2 to~10 times larger in size (with McRae-all being a notable exception).
To better understand that, we teased apart contributions of annotation quality and quantity, and their interplay. We further teased apart sentence quantity from frame quantity.

We saw a
high variance in thematic fit estimation,  to the point where in one task (Padó-all) \vii\ advantages over \vi\ only showed in larger training set sizes, while in another task (McRae-all) no advantages were seen. Given the small-to-no gains in these tasks relative to \vi, the cost-effectiveness of re-annotating with better tools is questionable for the indirect supervision setting.

We saw  all tasks benefited from increasing the training sentence set size, at least until 10\% of our large corpus (except perhaps Padó-all beyond 1\%). Future work should check if larger sizes can yield even better results.
Even at 10\% of the training, our \vii\ model set a new record in indirectly supervised thematic fit estimation on Padó-all,
and at 20\% a new record also on McRae-all (both \vi, \vii).

We also saw that refining the semantic role set granularity helps in thematic fit tasks (and word prediction). On Padó-all, best results  were achieved already by adding \term{Arg2}, but surprisingly  on McRae-all
by adding \term{Arg2-4}. Adding all roles yielded best results on word prediction.
These are novel results.

Last, but not least, we introduced a new open-data annotated corpus.%
\footnote{Available
at
\url{http://yuvalmarton.com/RW-Eng}}
We believe this new corpus will be useful to the NLP community beyond our reported experiments. Future work involves studies with existing and new annotation layers,
e.g., combining \vi+\vii\ parses, \vi+\vii\ SRL tags, and replicating these experiments with various  word embeddings and different network architectures.
Future work should also explore different optimization objectives or additional tasks in the multi-task setting,
since role prediction seems too easy (reaches accuracy in high 90s early on), while the word prediction objective may be too hard,
although the latter can be ameliorated with better word embeddings and a loss function based on the vector distance between predicted and target words.
We also plan to add new thematic fit tasks with multiple simultaneous role-fillers  \citep{bicknell2010effects,vassallo2018event}.

\section{Acknowledgements}
A. Sayeed's involvement in this research was funded by a Swedish Research Council (VR) grant (2014-39) for the Centre for Linguistic Theory and Studies in Probability (CLASP).
We thank the reviewers for helping us make this paper clearer.

\section{Bibliographical References}\label{reference}

\bibliographystyle{lrec2022-bib}


\section*{Acknowledgements}
We are grateful to Ely Porat and Shay Golan for insightful conversations about the dynamic $k$-mismatch problem at an early stage of this work.
\bibliographystyle{plainurl}

\section{Introduction}

The development of dynamic data structures for string problems has become a topic of renewed interest in recent years (see, for example,~\cite{Amir2020,Amir2021,Amir2019,amir2019longest,Charalampopoulos2020,charalampopoulos2020faster,clifford2018upper,GKKLS,KK22} and references therein).
Our focus will be on approximate pattern matching, where the general problem is as follows:
Given a pattern  of length $m$ and a longer text of length $n$,  return the value of a distance function between the pattern and substrings of the text.

We develop a new dynamic data structures for a thresholded version of the Hamming distance function, known as the $k$-mismatch function.  In this setting, we only need to report the Hamming distance if does not exceed $k$. The $k$-mismatch problem is well studied in the offline setting, where all alignments of the pattern with the text substring that meet this threshold must be found.
In 1980s, an $\mathcal{O}(nk)$-time algorithm was given~\cite{TCS:LanVis86}, and this stood as the record for a over a decade.
However, in the last twenty years, significant progress has been made.
In a breakthrough result, Amir et al.~\cite{SODA:AmiLewPor00} gave $\mathcal{O}(n\sqrt{k \log k})$-time and $\mathcal{O}\big(n + \frac{k^3 \log k}{m}\big)$-time algorithms, which were subsequently improved to $\mathcal{O}(n\log^{\mathcal{O}(1)}m + \frac{nk^2\log{k}}{m})$ time~\cite{SODA:CFPST16}, $\mathcal{O}\big(n\log^2{m} \log{\sigma}+\frac{nk\sqrt{\log{m}}}{\sqrt{m}}\big)$ time~\cite{gawrychowski2018towards}, and finally to $\mathcal{O}\big(n+\min\big(\frac{nk\sqrt{\log m}}{\sqrt{m}}, \frac{nk^2}{m}\big)\big)$ time~\cite{chan2020approximating}.

In the dynamic $k$-mismatch problem, there
are two input strings: a pattern $P$ of length $m$ and a text $T$ of length $n\ge m$.
For a query at index $i$, the data structure
must return the Hamming distance between $P$ and $T[i\ldots i+m)$ if the Hamming distance is less than $k$, and $\infty$ otherwise.
The queries can be interspersed with updates of the
form $\Update(S,i,x)$, which assign $S[i]:=x$, where $S$ can be either the pattern or the text. There are two naive approaches
for solving the dynamic problem. The first is to rerun a static offline
algorithm after each update, and then have constant-time queries. The second is to simply modify the input at each update  and compute the Hamming distance naively for each query. Our goal is to perform better than these naive solutions.

We primarily focus on the case when $n=\Theta(m)$ (in general, one can partition the text into $\Theta(\frac{n}{m})$ overlapping blocks of length $\Theta(m)$).
When $k=m$ and $\sigma=n^{o(1)}$, known upper bounds and conditional lower bounds match up to a subpolynomial factor:
There exists a dynamic data structure with an $\mathcal{O}(\sqrt{n \log n} \cdot \sigma)$ upper bound for both updates and queries and an almost matching $n^{1/2-\Omega(1)}$ lower bound~\cite{clifford2018upper}
conditioned on the hardness of the online matrix-vector multiplication problem.
Although there is no existing work directly on the dynamic $k$-mismatch problem we consider,  it was shown very recently that a compact representation of all $k$-mismatch occurrences can be reported in $\tO{k^2}$ time\footnote{The $\tilde{\mathcal{O}}(\cdot)$ notation suppresses $\log^{\mathcal{O}(1)}n$ factors.} after each $\mathcal{O}(\log n)$-time update~\cite{charalampopoulos2020faster}.

We give three data structures for the dynamic $k$-mismatch problem. The first has update
time of $\tO{1}$ and a query time of $\tO{k}$.  The main tool we use is the dynamic strings data structure~\cite{GKKLS} which allows enumerating mismatches in $\mathcal{O}(\log n)$ time each.  The second has update time $\tO{k}$ and a query time of $\tO{1}$.
Here, we build on the newly developed generic solution for the static $k$-mismatch problem from~\cite{charalampopoulos2020faster}. The third data structure, optimized for $k\ge \sqrt{n}$, gives a trade-off between update and query times.  The overall approach is a lazy rebuilding scheme using the state-of-the-art offline $k$-mismatch algorithm. In order to achieve a fast solution, we handle instances with many and few $2k$-mismatch occurrences differently. Basing on combinatorial insights developed in the sequence of papers on the offline and streaming versions of the $k$-mismatch problem~\cite{chan2020approximating,SODA:CFPST16,CKP,gawrychowski2018towards,GKKP}, we are able to achieve update time $\tilde{\mathcal{O}}\Big(\frac{n}{k} +\sqrt{\frac{nk}{x}}\Big)$ and query time $\tO{x}$ for any trade-off parameter $x\in [1\mathinner{.\,.} k]$ provided at initialization.\footnote{Throughout this paper, we denote $[a\mathinner{.\,.} b]=\{i\in \mathbb{Z} : a\le i \le b\}$ and $[a\mathinner{.\,.} b)=\{i \in \mathbb{Z} : a \le i < b\}$.} To put the trade-off complexity in context, we note that, e.g., when $k = m$, this allows  achieving $U(n,k) = Q(n,k) = \tO{n^{2/3}}$, which improves upon an $\tO{n^{3/4}}$ bound presented in \cite{clifford2018upper} (where only the case of $k=m$ is considered).

We also show conditional lower bounds which are in most cases within subpolynomial factors of our upper bounds.  For the case where the text length is linear in the length of the pattern, we do this by reducing from the 3SUM conjecture~\cite{STOC:Patrascu10}.   However, in the case that the text is much longer than the pattern, our reduction requires the Online Matrix vector conjecture~\cite{STOC:HKNS15}. Interestingly the lower bound for the superlinear case is asymmetric between the query and update time.
\section{Lower Bounds}\label{sec:lb}
In this section, we give conditional lower bounds for the dynamic
$k$-mismatch problem based on the 3SUM conjecture~\cite{STOC:Patrascu10}.
For the 3SUM problem, we use the following definition.

\newcommand{\G}{\mathbf{G}}
\begin{definition}[3SUM Problem]
Given three sets $A,B,C\subseteq [-N\mathinner{.\,.} N)$ of total size $\size{A}+\size{B}+\size{C}=n$,
decide whether there exist $a\in A$, $b\in B$, $c\in C$ such that $a+b+c=0$.
\end{definition}

Henceforth, we consider algorithms for the word RAM model with $w$-bit machine words,
where $w=\Omega(\log N)$.
In this model, there is a simple $\bigO{n^2}$-time solution for the 3SUM problem. This can be improved by log factors~\cite{Baran2008}, with the current record being $\bigO{(n^2/\log^{2} n)(\log \log n)^{\mathcal{O}(1)}}$ time~\cite{chan2019more}.
\newcommand{\eps}{\varepsilon}
\begin{conjecture}[3SUM Conjecture]
For every constant $\eps > 0$, there is no Las-Vegas randomized algorithm
solving the 3SUM problem in $\mathcal{O}(n^{2-\eps})$ expected time.
\end{conjecture}

As a first step, we note that the 3SUM problem remains hard even if we allow for polynomial-time preprocessing
of $A$. The following reduction is based on~\cite[Theorem 13]{LWWW16}.
\begin{lemma}\label{lem:prepr}
Suppose that, for some constants $d\ge 2$ and $\eps>0$, there exists an algorithm that, after preprocessing integers $n,N\in \mathbb{Z}_+$ and a set $A\subseteq [-N\mathinner{.\,.} N)$ in $\mathcal{O}(n^d)$ expected time, given sets $B,C\subseteq [-N\mathinner{.\,.} N)$ of total size $|A|+|B|+|C|\le n$, solves the underlying instance of the 3SUM problem in expected $\mathcal{O}(n^{2-\eps})$ time. Then, the 3SUM conjecture fails.
\end{lemma}
\begin{proof}
We shall demonstrate an algorithm solving the 3SUM problem in $\mathcal{O}(n^{2-\hat{\eps}})$ time,
where $\hat{\eps} = \min(\frac12, \frac{\eps}{2(d-1)}) > 0$.
Let $g=\floor{n^{\frac{d-1.5}{d-1}}}$. We construct a decomposition $A=\bigcup_{i=1}^g A_i$ into disjoint subsets such that $|A_i|\le \ceil{\frac{1}{g}|A|}$ and $\max A_i < \min A_{i'}$ hold for $i,i'\in [1\mathinner{.\,.} g]$ with $i<i'$.
Similarly, we also decompose $B=\bigcup_{j=1}^g B_j$ and $C=\bigcup_{k=1}^g C_k$.

Next, we construct $T = \{(i,j,k)\in [1\mathinner{.\,.} g]^3: \min A_i + \min B_j+\min C_k \le 0 \le  \max A_i + \max B_j+\max C_k\}$. Observe that  if $a+b+c=0$ for $(a,b,c)\in A\times B\times C$,
then the triple $(i,j,k)\in [1\mathinner{.\,.} g]^3$ satisfying $(a,b,c)\in A_i\times B_j\times C_k$ clearly belongs to $T$.
Moreover, $T$ can be constructed in $\mathcal{O}(g^2 \log g + |T|)$ time by performing a binary search
over $k\in [1\mathinner{.\,.} g]$ for all $(i,j)\in [1\mathinner{.\,.} g]^2$.
To provide a worst-case bound on this running time, we shall prove that $|T|=\mathcal{O}(g^2)$.
For this, let us define the \emph{domination} order $\prec$ on $[1\mathinner{.\,.} g]^3$ so that $(i,j,k)\prec  (i',j',k')$
if and only if $i<i'$, $j<j'$, and $k<k'$.
Observe that $T$ is an $\prec$-antichain and that $[1\mathinner{.\,.} g]^3$ can be covered with $\mathcal{O}(g^2)$ $\prec$-chains.
Hence, $|T|=\mathcal{O}(g^2)$ holds as claimed.

Let $\hat{n}:=\ceil{\frac{1}{g}|A|}+\ceil{\frac{1}{g}|B|}+\ceil{\frac{1}{g}|C|}=\mathcal{O}(\frac{n}{g})$.
We preprocess $(\hat{n},N,A_i)$ for each $i\in [1\mathinner{.\,.} g]$,
at the cost of $\mathcal{O}(g \hat{n}^d) = \mathcal{O}(\frac{n^d}{g^{d-1}})=\mathcal{O}(\frac{n^d}{n^{d-1.5}})=\mathcal{O}(n^{1.5})$ time.
Then, for each triple $(i,j,k)\in T$, we solve the underlying instance of the 3SUM problem,
at the cost of $\mathcal{O}(g^2 \hat{n}^{2-\eps})=\mathcal{O}(g^2 \frac{n^{2-\eps}}{g^{2-\eps}})
= \mathcal{O}(n^{2-\eps} g^{\eps})=\mathcal{O}(n^{2-\eps+\eps\frac{d-1.5}{d-1}})
= \mathcal{O}(n^{2-\frac{\eps}{2(d-1)}})$ expected time in total. As noted above, it suffices to return YES if and only if at least one of these calls returns YES.\@
\end{proof}

\newcommand{\TSP}{3SUM$^+$}
Our lower bounds also rely on the following variant of the 3SUM problem.
\begin{definition}[\TSP\ Problem]
	Given three sets $A,B,C\subseteq [-N\mathinner{.\,.} N)$ of total size $\size{A}+\size{B}+\size{C}=n$,
	report all $c\in C$ such that $a+b+c=0$ for some $a\in A$ and $b\in B$.
\end{definition}

The benefit of using \TSP\ is that it remains hard for $N\ge n^{2+\Omega(1)}$ (as shown in~\cite{HU17});
in comparison, regular 3SUM is known to be hard only for $N\ge n^3$.
The following proposition generalizes the results of~\cite{HU17} (allowing for preprocessing of $A$); its proof relies on the techniques of~\cite{Baran2008}.

\begin{proposition}\label{thm:hsu}
Suppose that, for some constants $d\ge 2$ and $\eps,\delta>0$, there exists an algorithm
that, after $\mathcal{O}(n^d)$-time preprocessing of integers $n,N\in \mathbb{Z}_+$, with $N\le n^{2+\delta}$,
and a set $A\subseteq [-N\mathinner{.\,.} N)$, given sets $B,C\subseteq [-N\mathinner{.\,.} N)$ of total size $|A|+|B|+|C|\le n$,
solves the underlying \TSP\ instance in expected $\mathcal{O}(n^{2-\eps})$ time.
Then, the 3SUM conjecture fails.
\end{proposition}
\begin{proof}
We shall demonstrate an algorithm violating the 3SUM conjecture via \cref{lem:prepr}.
If the input instance already satisfies $N\le n^{2+\delta}$, there is nothing to do.
Thus, we henceforth assume $N>n^{2+\delta}$.
Let $v=\ceil{\log 3N}$ and $u=\floor{\log n^{2+\delta}}$.
In the preprocessing, we draw a uniformly random \emph{odd}
integer $\alpha\in [0\mathinner{.\,.} 2^{v})$,
which defines a hash function $h: \mathbb{Z} \to [0\mathinner{.\,.} 2^u)$
with $h(x)=\floor{\frac{\alpha x\bmod 2^{v}}{2^{v-u}}}$ for $x\in \mathbb{Z}$.
The key property of this function is that $(h(a)+h(b)+h(c)-h(a+b+c))\bmod 2^u\in \{0,-1,-2\}$ holds for all $a,b,c\in \mathbb{Z}$.
At the preprocessing stage, we also preprocess $(n,2^u,h(A))$ for the hypothetical \TSP\ algorithm
(note that $2^u \le n^{2+\delta}$).
Overall, the preprocessing stage costs $\mathcal{O}(n^d)$ time.

In the main phase, we solve the following \TSP\ instances, each of size at most $n$
and over universe $[-2^u\mathinner{.\,.} 2^u)$, denoting $X+y:=\{x+y: x\in X\}$:
\begin{itemize}
	\item $(h(A),h(B),h(C))$,
	\item $(h(A),h(B),h(C)-2^u+2)$,
	\item $(h(A),h(B),h(C)-2^u+1)$,
	\item $(h(A),h(B),h(C)-2^u)$,
	\item $(h(A),h(B)-2^u,h(C)-2^u+2)$,
	\item $(h(A),h(B)-2^u,h(C)-2^u+1)$,
	\item $(h(A),h(B)-2^u,h(C)-2^u)$;
\end{itemize}
this step costs $\mathcal{O}(n^{2-\eps})$ time.
Combining the results of these calls,
in $\mathcal{O}(n)$ time we derive \[S:=\{c\in C : h(a)+h(b)+h(c)\in \{0,2^u-2, 2^u-1,2^u,2\cdot 2^u-2,2\cdot 2^u-1,
2\cdot 2^u\}\}.\]
Finally, for each $c\in S$, we check in $\mathcal{O}(n)$ time whether $a+b+c=0$ holds for some $a\in A$ and $b\in B$. Upon encountering the first witness $c\in S$, we return YES.\@
If no witness is found, we return NO.\@

Let us analyze the correctness of this reduction.
If we return YES, then clearly $a+b+c=0$ holds for some $a\in A$, $b\in B$, and $c\in C$.
For the converse implication, suppose that $a+b+c=0$ holds for some $a\in A$, $b\in B$, and $c\in C$.
Then, $(h(a)+h(b)+h(c)-h(a+b+c))\bmod 2^u=(h(a)+h(b)+h(c))\bmod 2^u \in \{0,-1,-2\}$.
Given that $h(a),h(b),h(c)\in [0\mathinner{.\,.} 2^u)$,
this means that $h(a)+h(b)+h(c)\in \{0,2^u-2, 2^u-1,2^u,2\cdot 2^u-2,2\cdot 2^u-1,
2\cdot 2^u\}$, i.e., $c\in S$. Consequently, we are guaranteed to return
YES while processing $c\in S$ at the latest.

It remains to bound the expected running time.
For this, it suffices to prove that there are, in expectation, $\mathcal{O}(n^{1-\delta})$ triples $(a,b,c)\in A\times B\times C$ such that $a+b+c\ne 0$ yet $h(a)+h(b)+h(c) \in \{0,2^u-2, 2^u-1,2^u,2\cdot 2^u-2,2\cdot 2^u-1,
2\cdot 2^u\}$ (in particular, this means that, in expectation, $S$ contains at most $\mathcal{O}(n^{1-\delta})$ non-witnesses; verifying all of them costs $\mathcal{O}(n^{2-\delta})$ expected time in total).
Specifically, we shall prove that each triple satisfies the aforementioned condition with probability $\mathcal{O}(n^{-2-\delta})$.

Due to the fact that $(h(a)+h(b)+h(c)-h(a+b+c))\bmod 2^u \in \{0,-1,-2\}$,
the bad event holds only if $a+b+c\ne 0$ yet $h(a+b+c)\in \{0,1,2,2^u-2,2^u-1\}$.
Let $a+b+c=2^t \beta$ for an integer $t\in \mathbb{Z}_{\ge 0}$ and odd integer $\beta\in \mathbb{Z}$.
Due to $|a+b+c|\le 3N \le 2^v$, we must have $t\in [0\mathinner{.\,.} v)$.
\begin{itemize}
\item If $t > v-u+1$, then $h(a+b+c)$ is uniformly random odd multiple of $2^{t-v+u}$ within $[0\mathinner{.\,.} 2^u)$.
Hence, $\Pr[h(a+b+c)\in\{0,1,2,2^u-2,2^u-1\}]=0$.
\item If $t= v-u+1$, then $h(a+b+c)$ is a uniformly random odd multiple of $2$  within $[0\mathinner{.\,.} 2^u)$.
Hence, $\Pr[h(a+b+c)\in \{0,1,2,2^u-2,2^u-1\}]\le \frac{2}{2^{v-2}}=\frac{8}{2^v}$.
\item If $t= v-u$, then $h(a+b+c)$ is a uniformly random odd multiple of $1$ within $[0\mathinner{.\,.} 2^u)$.
Hence, $\Pr[h(a+b+c)\in\{0,1,2,2^u-2,2^u-1\}]\le \frac{2}{2^{v-1}}=\frac{4}{2^v}$.
\item If $t < v-u$, then $h(a+b+c)$ is a uniformly random element of  $[0\mathinner{.\,.} 2^u)$.
Hence, $\Pr[h(a+b+c)\in \{0,1,2,2^u-2,2^u-1\}]\le \frac{5}{2^{v}}$.
\end{itemize}
Overall, the probability is bounded by $\frac{8}{2^v} = \mathcal{O}(n^{-2-\delta})$.
\end{proof}

We are now in a position to give the lower bound for the dynamic $k$-mismatch problem.

\begin{theorem}\label{thm:3sum_lower}
	Suppose that, for some constants $p>0$, $\eps>0$, and $0<c<\frac12$,
	there exists a dynamic $k$-mismatch algorithm that solves instances satisfying $k=\ceil{m^c}$
	using initialization in $\mathcal{O}(n^p)$ expected time, updates in $\bigO{k^{1-\eps}}$ expected time, and	queries in $\bigO{k^{1-\eps}}$ expected time.
	Then, the 3SUM conjecture fails.
	This statement remains true when updates are allowed in either the pattern or the text (but not both).
\end{theorem}
\begin{proof}
	We shall provide an algorithm contradicting \cref{thm:hsu} for $\delta=\frac{1-2c}{2c}$
	and $d=\frac{p}{c}$.
	Suppose that the task is to solve a size-$\hat{n}$ instance of the \TSP\ problem
	with $A,B,C\subseteq [-N\mathinner{.\,.} N)$.
	We set $m=\ceil{\hat{n}^{1/c}}$ (so that $k=\ceil{m}^c \ge \hat{n}$), and $n=2m$,
	and we initialize a pattern to $P=\texttt{0}^m$ and a text to $T=\texttt{0}^{n}$.
	Observe that $m \ge \hat{n}^{1/c} \ge N^{\frac1{c(2+\delta)}} = N^{\frac{2}{1+2c}}$.
	If $N^{\frac{2}{1+2c}} < 2N$, then $N=\mathcal{O}(1)$, and we can afford to solve the \TSP\ instance naively.
	Otherwise, we are guaranteed that $m\ge 2N$,
	and we proceed as follows:
    \begin{itemize}
		\item we set $P[a+N]:=\texttt{1}$ for each $a\in A$;
		\item we set $T[2N-b]:=\texttt{1}$ for each $b\in B$.
	\end{itemize}
	Finally, for each element $c\in C$, we perform a query at position $c+N$,
	and report $c$ if and only if $\operatorname{HD}(P,T[c+N\mathinner{.\,.} c+N+m))< \operatorname{HD}(P, \texttt{0}^m)+\operatorname{HD}(T[c+N\mathinner{.\,.} c+N+m),\texttt{0}^m)$. Due to the fact that $\operatorname{HD}(P, \texttt{0}^m)+\operatorname{HD}(T[c+N\mathinner{.\,.} c+N+m),\texttt{0}^m) \le |A|+|B|\le \hat{n}=k$,
	this can be decided based on the answer to the query.
	Equivalently, we report $c\in C$ if and only if $P[i]=T[c+N+i]=\texttt{1}$ holds for some $i\in [0\mathinner{.\,.} N)$,
	i.e., $T[a+c+2N]=1$ for some $a\in A$, or, equivalently, $-a-c\in B$, i.e., $a+b+c=0$ for some $b\in B$.
	This proves the correctness of the algorithm.

	As for the running time, note that the preprocessing phase costs
	$\mathcal{O}(n^p)=\mathcal{O}(m^p)=\mathcal{O}(\hat{n}^{\frac{p}{c}})=\mathcal{O}(\hat{n}^d)$ expected time.
	The main phase, on the other hand, involves $\mathcal{O}(\hat{n})$ updates and queries,
	which cost $\mathcal{O}(\hat{n}\cdot k^{1-\eps})=\mathcal{O}(\hat{n}^{2-\eps})$ expected time in total.
	By \cref{thm:hsu}, this algorithm for \TSP\ would violate the 3SUM conjecture.

	If the updates are allowed in the text only, we set up the pattern during the preprocessing phase
	based on the fact that the target value of $P$ depends on $A$ only.
	If the updates are allowed in the pattern only, we exchange the roles of $A$ and $B$
	and set up the text during the preprocessing phase.
\end{proof}

Next, we note that the lower bound can be naturally extended to $c\ge \frac12$.

\begin{corollary}\label{cor:joint}
	Suppose that, for some constants $p>0$, $\eps>0$, and $0<c\le 1$,
	there exists a dynamic $k$-mismatch algorithm that solves instances satisfying $k=\ceil{m^c}$
	using initialization in $\mathcal{O}(n^p)$ expected time, updates in $\bigO{\min(\sqrt{m},k)^{1-\eps}}$ expected time, and	queries in $\bigO{\min(\sqrt{m},k)^{1-\eps}}$ expected time.
	Then, the 3SUM conjecture fails.
	This statement remains true when updates are allowed in either the pattern or the text (but not both).
\end{corollary}
\begin{proof}
	When $c<\frac12$, the result holds directly due to \cref{thm:3sum_lower}.
	When $c\ge \frac12$, we prove that the 3SUM conjecture would be violated
	through \cref{thm:3sum_lower} with $\hat{c}=\frac{1-\eps}{2-\eps}$ and $\hat{\eps}=\frac{\eps}{2}$.
	Since the $\hat{k}$-mismatch problem with $\hat{k}=\ceil{m}^{\hat{c}}$ can be simulated using an instance of the $k$-mismatch problem with $k=\ceil{m}^c$,
	we note that, in the former setting, the queries and updates can be hypothetically implemented in $\mathcal{O}((\sqrt{m})^{1-\eps})
	= \mathcal{O}(\hat{k}^{\frac{1-\eps}{2\hat{c}}})=\mathcal{O}(\hat{k}^{\frac{2-\eps}{2}})=\mathcal{O}(\hat{k}^{1-\hat{\eps}})$ expected time, violating the 3SUM conjecture via \cref{thm:3sum_lower}.
\end{proof}

\subsection{Lower Bound for \boldmath $m\ll n$}
While most of the work in this paper focuses on the case where the length of
the pattern is linear in the length of the text, for completeness, we provide
a lower bound that is only of interest when the pattern is considerably shorter.
Our lower bound is
conditioned on the Online Matrix-Vector Multiplication
conjecture~\cite{STOC:HKNS15}, which is often used
in the context of dynamic algorithms.

In the Online Boolean Matrix-Vector Multiplication (OMv) problem, we
are given as input a Boolean matrix $M\in\{0,1\}^{n\times n}$. Then, a
sequence $n$ vectors $v_1, \ldots, v_n\in \{0,1\}^n$ arrives in
an online fashion. For each such vector $v_i$, we are required to
output $Mv_i$ before receiving $v_{i+1}$.

\begin{conjecture}[OMv Conjecture~\cite{STOC:HKNS15}]\label{conj:OMv}
  For any constant $\epsilon>0$, there is no
  $\mathcal{O}(n^{3-\epsilon})$-time algorithm that solves OMv correctly with
  probability at least $\frac23$.
\end{conjecture}

We use the following simplified version of~\cite[Theorem
2.2]{STOC:HKNS15}.

\begin{theorem}[\cite{STOC:HKNS15}]\label{thm:gOMv}
	Suppose that, for some constants $\gamma,\eps>0$,
	there is an algorithm that, given as input a matrix
  $M\in \{0,1\}^{p\times q}$, with $q=\floor{p^{\gamma}}$, preprocesses $M$ in
  time polynomial in $p\cdot q$, and then, presented with a vector $v\in \{0,1\}^q$,
  computes $Mv$ in time $\mathcal{O}(p^{1+\gamma-\eps})$
  correctly with probability at least $\frac23$.
  Then, the OMv conjecture fails.
\end{theorem}

\cref{thm:gOMv} lets us derive our lower bound for the dynamic $k$-mismatch problem.

\begin{theorem}\label{thm:longtext}
	Suppose that, for some constants $\gamma,\eps>0$,
	there is a dynamic $k$-mismatch algorithm that solves instances
	satisfying $k= 2\floor{(\frac{n}{m})^\gamma}$,
	with preprocessing in $\mathcal{O}(n^{\mathcal{O}(1)})$ time, updates of the pattern in $\bigO{(\frac{n}{m})^{1-\eps}}$ time,
	and queries in $\bigO{k^{1-\eps}}$ time, providing correct answers with high probability.
	Then, the OMv conjecture fails.
\end{theorem}
\begin{proof}
    Given a matrix $M\in \{0,1\}^{p\times q}$, we
	set $m = 3q$, $n=3pq$, and $k=2q$ (so that $k=2q=2\floor{p^\gamma}=2\floor{(\frac{n}{m})^\gamma}$ holds).
	At the preprocessing phase, we initially set $P=\texttt{0}^{m}$ and $T=\texttt{0}^{n}$.
	As for the text, for each $i\in [0\mathinner{.\,.} p)$ and $j\in [0\mathinner{.\,.} q)$,
	we set $T[3iq+3j\mathinner{.\,.} 3iq+3j+3)$ to $\texttt{100}$ if $M[i,j]=0$
	and to $\texttt{111}$ if $M[i,j]=1$.

	When a vector $v$ arrives, the pattern is set as follows:
	for each $j\in [0\mathinner{.\,.} q)$, we set $P[3j\mathinner{.\,.} 3j+3)$ to $\texttt{001}$ if $v[j]=0$
	and  to $\texttt{111}$ if $v[j]=1$.
	This requires $\bigO{q}$ update calls to our dynamic data structure. Queries are then made
	at position $im$ for all $i\in [0\mathinner{.\,.} p)$. By definition of the Hamming distance,
	$\operatorname{HD}(\texttt{100},\texttt{001})=\operatorname{HD}(\texttt{100},\texttt{111})=\operatorname{HD}(\texttt{111},\texttt{001})=2$, whereas $\operatorname{HD}(\texttt{111},\texttt{111})=0$; therefore, the only time
	that the returned Hamming distance will be
	less than $k=2q$ is when $M[i,j]=v[j]=1$ for some $j\in [1\mathinner{.\,.} q]$, i.e., $(Mv)[i]=1$.
	Therefore, the OMv product can
	be computed by making $\bigO{p}$ queries and $\bigO{q}$ updates to the dynamic $k$-mismatch data structure as before.
	The total cost of these operations is $\mathcal{O}(pq^{1-\eps}+qp^{1-\eps})
	= \mathcal{O}(p^{1+\gamma(1-\eps)}+p^{1+\gamma-\eps})=\mathcal{O}(p^{1+\gamma-\min(1,\gamma)\eps})$.
	By \cref{thm:gOMv} with $\hat{\eps}=\min(1,\gamma)\eps$, this would violate the OMv conjecture.
\end{proof}

\section{Preliminaries}

In this section, we provide the required basic definitions.
We begin with the string distance metric which will be used throughout.

\begin{definition}[Hamming Distance]
The Hamming distance between two strings $S$, $R$ of the same length is defined as $\operatorname{HD}(S,R) = \size{\{i:S[i]\neq R[i]\}}.$
\end{definition}

From this point forward, for simplicity of exposition, we will assume that the pattern is half the length of the text. All our upper bounds are straightforward to generalise to a text whose length is linear in the length of the pattern.
In Theorem~\ref{thm:longtext}, we show higher lower bounds for the case where the text is much longer than the pattern.

We can now define the central dynamic data structure problem we consider in this paper.

\begin{definition}[Dynamic $k$-Mismatch Problem]
Let $P$ be a pattern of length $m$ and  $T$ be a text of length $n\le 2m$.
For $i\in [0\mathinner{.\,.} n-m]$, a query $\Query(i)$ must return $\operatorname{HD}(T[i\ldots i+m),P)$ if $\operatorname{HD}(T[i\ldots i+m),P)\le k$, and $\infty$ otherwise. The queries can be
interspersed with updates of the form $\Update(S,i,x)$ which assign $S[i]:=x$,
where $S$ can be the pattern or the text.
\end{definition}

For the remainder of the paper, we use $Q(n,k)$ and $U(n,k)$ to be the time
complexity of $\Query$ and $\Update$, respectively.
If $n > 2m$, then a standard reduction yields $\mathcal{O}(Q(m,k))$-time queries,
$\mathcal{O}(U(m,k))$-time updates in $T$, and $\mathcal{O}(\frac{n}{m}Q(m,k))$-time updates in $P$.
\section{Upper Bounds}
In this section, we provide three solutions of the dynamic $k$-mismatch problem.
We start with a simple application of dynamic strings resulting in $\tO{k}$ query time and $\tO{1}$ update~time.

The data structure of Gawrychowski et al.~\cite{GKKLS} maintains a dynamic family $\X$ of strings of total length $N$ supporting the following updates:\footnote{This data structure is Las-Vegas randomized, and the running times are valid with high probability with respect to $N$. A deterministic version, using~\cite{MISC:AlsBroRau00} and deterministic dynamic dictionaries, has an $\mathcal{O}(\log N)$-factor overhead in the running times, which translates to an $\mathcal{O}(\log n)$-factor overhead in the query and update times of all our randomized algorithms for the dynamic $k$-mismatch~problem.}
\begin{itemize}
    \item Insert to $\X$ a given string $S$ (in time $\mathcal{O}(|S|+\log N)$).
    \item Insert to $\X$ the concatenation of two strings already in $\X$ (in time $\mathcal{O}(\log N)$).
    \item Insert to $\X$ an arbitrary prefix or suffix of a string already in $\X$ (in time $\mathcal{O}(\log N)$).
\end{itemize}
Queries include $\mathcal{O}(1)$-time computation of the longest common prefix of two strings in $\X$.

\begin{theorem}\label{thm:fastU}
There exists a Las-Vegas randomized algorithm for the dynamic $k$-mismatch problem satisfying $U(n,k)=\bigO{\log{n}}$
and $Q(n,k)=\bigO{k\log {n}}$ with high probability.
\end{theorem}
\begin{proof}
We maintain a dynamic string collection $\X$ of~\cite{GKKLS} containing $P$ and $T$.
Given that a string $S'$ resulting from setting $S[i]:=x$ in a string $S\in \X$
is the concatenation of a prefix $S[0\mathinner{.\,.} i)$, the new character $x$,
and a suffix $S[i+1\mathinner{.\,.} |S|)$, it is straightforward to construct $S'$
with $\mathcal{O}(1)$ auxiliary strings added to $\X$.
Hence, we implement an update in $\mathcal{O}(\log n)$ time.

Armed with this tool, we perform dynamic $k$-mismatch queries by so-called ``kangaroo jumps''~\cite{TCS:LanVis86}. That, is we align the pattern with $T[i\mathinner{.\,.} i+m)$, where $i$ is the query position in the text $T$,
and we repeatedly extend the match we have found so far until we reach a fresh mismatch. Each longest common extension query can be implemented in $\mathcal{O}(\log n)$ time. For this, we extract the relevant suffixes of $P$ and $T$ (we insert them to $\X$ in $\mathcal{O}(\log n)$ time each) and ask for their longest common prefix (which costs $\mathcal{O}(1)$ time). As we stop once $k+1$ mismatches have been found or once we have reached the end of the text or pattern, the total query time is $\mathcal{O}(k \log n)$.
\end{proof}

\subsection{Faster Queries, Slower Updates}
Given the result above, a natural question is whether there exists an approach with an efficient
query algorithm, in return for a slower update algorithm. We answer affirmatively in this section
based on a recent work of Charalampopoulos et al.~\cite{charalampopoulos2020faster}.

\subsubsection{The PILLAR model}
\def\modelname{{\tt PILLAR}\xspace}
\def\fragmentco#1#2{[#1\mathinner{.\,.}#2)}
\def\accOpName{{\tt Access}\xspace}
\def\extractOpName{{\tt Extract}\xspace}
\def\lenOpName{{\tt Length}\xspace}
\def\perOpName{{\tt Period}\xspace}
\def\lceOpName{{\tt LCP}\xspace}
\def\lcbOpName{{\tt LCP$^R$}\xspace}
\def\lceOp#1#2{{\tt LCP}(#1, #2)}
\def\lcbOp#1#2{{\tt LCP}^R(#1, #2)}
\def\ipmOp#1#2{{\tt IPM}(#1, #2)}
\def\accOp#1#2{#1[#2]}

Charalampopoulos et al.~\cite{charalampopoulos2020faster} developed a generic static algorithm for the $k$-mismatch problem.
They formalized their solution using an abstract interface, called the \emph{\modelname model},
which captures certain primitive operations that can be
implemented efficiently in all settings considered in~\cite{charalampopoulos2020faster}.
Thus, we bound the
running times in terms of~\modelname operations---if the algorithm uses more time than
\modelname operations, we also specify the extra running time.

In the \modelname model, we are given a family of~strings $\X$ for preprocessing.
The elementary objects are fragments $X\fragmentco{\ell}{r}$ of~strings $X\in \X$.
Initially, the model provides access to each $X\in \X$ interpreted as $X\fragmentco{0}{|X|}$.
Other fragments can be obtained through an \extractOpName operation.
\begin{itemize}
    \item $\extractOpName(S,\ell,r)$: Given a fragment $S$ and positions $0 \le \ell \le r
        \le |S|$, extract the (sub)fragment $S\fragmentco{\ell}{r}$,
        which is defined as $X\fragmentco{{\ell'+\ell}}{\ell'+r}$ if $S=X\fragmentco{\ell'}{r'}$ for $X\in \X$.
\end{itemize}

\noindent
Furthermore, the following primitive operations are supported in the \modelname model:
\begin{itemize}
    \item $\lceOp{S}{T}$: Compute the length of~the longest common prefix of~$S$ and $T$.
    \item $\lcbOp{S}{T}$: Compute the length of~the longest common suffix of~$S$ and $T$.
    \item $\ipmOp{P}{T}$: Assuming that $|T|\le 2|P|$, compute the occurrences of $P$ in $T$, i.e., $\operatorname{Occ}(P,T)=\{i\in [0\mathinner{.\,.} |T|-|P|] : P = T[i\mathinner{.\,.} i+|P|)\}$ represented as an arithmetic progression
    \item $\accOpName(S,i)$: Retrieve the character $\accOp{S}{i}$.
    \item $\lenOpName(S)$: Compute the length $|S|$ of~the string $S$.
\end{itemize}

Among several instantiations of the model, Charalampopoulos et al.~\cite[Section 7.3]{charalampopoulos2020faster} showed that the primitive \modelname operations can be implemented in $\mathcal{O}(\log^2 N)$ time on top of the data structure for dynamic strings~\cite{GKKLS}, which we recalled above. Consequently, we are able to maintain two dynamic strings $P$ and $T$ subject to character substitutions, achieving $\mathcal{O}(\log^2 n)$-time elementary \modelname operations and $\mathcal{O}(\log n)$-time updates.

\begin{corollary}\label{cor:pillar_impl}
Let $T$ be a dynamic string of length $n$ and $P$ be a dynamic string of length $m\le n$,
both of which can be updated via substitutions of single characters.
There exists a Las-Vegas randomized data structure supporting the \modelname operations on $\X = \{T,P\}$ in $\mathcal{O}(\log^2 n)$ time w.h.p.~and updates in  $\mathcal{O}(\log n)$ time w.h.p.
\end{corollary}

\subsubsection{The Static $k$-Mismatch Problem}
The (static) $k$-mismatch problem consists in computing $\operatorname{Occ}_k(P,T)=\{i\in [0\mathinner{.\,.} n-m] :\allowbreak \operatorname{HD}(P,T[i\mathinner{.\,.} i+m))\le k\}$, with each position $i\in \operatorname{Occ}_k(P,T)$ reported along with the corresponding Hamming distance $d_i := \operatorname{HD}(P,T[i\mathinner{.\,.} i+m))$.
Charalampopoulos et al.~\cite[Theorem 3.1 and Corollary 3.5]{charalampopoulos2020faster} proved that $\operatorname{Occ}_k(P,T)$
admits a compact representation: this set can be decomposed into $\mathcal{O}\big(\frac{n}{m}\cdot k^2\big)$ disjoint arithmetic progressions so that occurrences in a single progression share the same Hamming distance~$d_i$.
Moreover, all the non-trivial progressions (i.e., progressions with two or more terms) share the same difference.
The following algorithm gives this compact representation on the output.

\begin{theorem}[{\cite[Main Theorem 8]{charalampopoulos2020faster}}]\label{thm:pillar_k}
There exists a \modelname-model algorithm that, given a pattern $P$ of length $m$, a text $T$ of length $n\ge m$, and
a positive integer $k\le m$, solves the $k$-mismatches problem in $\mathcal{O}(\frac{n}{m}\cdot k^2 \log \log k)$ time
using $\mathcal{O}(\frac{n}{m}\cdot k^2)$ \modelname operations.
\end{theorem}

\subsubsection{Warm-Up Algorithm}
Intuitively, the algorithm of \cref{thm:pillar_k} precomputes the answers to all queries $\Query(i)$ with $i\in [0\mathinner{.\,.} n-m]$.
Hence, a straightforward solution to the dynamic $k$-mismatch problem would be to maintain the data structure of \cref{cor:pillar_impl}, use the algorithm of \cref{thm:pillar_k} after each update, and then retrieve the precomputed answers for each query asked.
The data structure described below follows this strategy, making sure that the compact representation of $\operatorname{Occ}_k(P,T)$
is augmented with infrastructure for efficient random access.
\begin{proposition}
There exists a Las-Vegas algorithm for the dynamic $k$-mismatch problem satisfying $U(n,k)=\bigO{k^2 \log^2 n}$
and $Q(n,k)=\bigO{\log\log n}$ with high probability.
\end{proposition}
\begin{proof}
We maintain a \modelname-model implementation of $\X=\{P,T\}$ using \cref{cor:pillar_impl};
this costs $\mathcal{O}(\log n)$ time per update and provides $\mathcal{O}(\log^2 n)$-time primitive \modelname operations.

Following each update, we use \cref{thm:pillar_k} so that a space-efficient representation
of $\operatorname{Occ}_k(P,T)$ is computed in $\mathcal{O}(k^2 \log^2 n)$ time (recall that $m = \Theta(n)$).
This output is then post-processed as described below.
Let $q$ be the common difference of non-trivial arithmetic progression forming  $\operatorname{Occ}_k(P,T)$; we set $q=1$ if all progressions are trivial.
Consider the indices $i\in [0\mathinner{.\,.} n-m]$ ordered by $(i\bmod q, i)$, that is, first by the remainder modulo $q$ and then by the index itself.
In this ordering, each arithmetic progression contained in the output $\operatorname{Occ}_k(P,T)$
yields a contiguous block of indices $i$ with a common finite answer to queries $\Query(i)$.
The goal of post-processing is to store the sequence of answers using run-length encoding (with run boundaries
kept in a predecessor data structure).
This way, for each of the $\mathcal{O}(k^2)$ arithmetic progressions in $\operatorname{Occ}_k(P,T)$,
the corresponding answers $\Query(i)$ can be set in $\mathcal{O}(\log \log n)$ time to the common value $d_i$ reported along with the progression.
In total, the post-processing time is therefore $\mathcal{O}(k^2 \log \log n)$.

At query time, any requested value $\Query(i)$ can be retrieved in $\mathcal{O}(\log \log n)$ time.
\end{proof}

\subsubsection{Structural Insight}
In order to improve the update time, we bring some of the combinatorial insight from~\cite{charalampopoulos2020faster}.

A string is \emph{primitive} if it is not a string power with an integer exponent strictly greater than~$1$.
For a non-empty string $Q$, we denote by $Q^\infty$ an infinite string obtained by concatenating infinitely many copies of $Q$.
For an arbitrary string $S$, we further set $\operatorname{HD}(S,Q^*)=\operatorname{HD}(S,Q^\infty[0\mathinner{.\,.} |S|))$.
In other words, the $\operatorname{HD}(\cdot,\cdot^*)$ function generalizes $\operatorname{HD}(\cdot,\cdot)$ in that the second string is cyclically extended to match the length of the first one.
We use the same convention to define $M(S,Q^*)=\{i : S[i]\ne Q^\infty[i]\}=\{i : S[i] \ne Q[i\bmod |Q|]\}$.

\begin{proposition}[{\cite[Theorems 3.1 and 3.2]{charalampopoulos2020faster}}]\label{thm:char}
Let $P$ be a pattern of length $m$, let $T$ be a text of length $n\le \frac32 m$, and let $k\le m$ be a positive integer.
At least one of the following holds:
\begin{enumerate}
\item The number of $k$-mismatch occurrences of $P$ in $T$ is $|\operatorname{Occ}_k(P,T)| \le 864k$.
\item There is a primitive string $Q$ of length $|Q| \le \frac{m}{128k}$ such that $\operatorname{HD}(P,Q^*)<2k$.\label{it:per}
\end{enumerate}
Moreover, if $\operatorname{Occ}_k(P,T)\ne \emptyset$ and~\eqref{it:per}~holds, then a fragment $T'=T[\min \operatorname{Occ}_k(P,T)\mathinner{.\,.} m+\max \operatorname{Occ}_k(P,T))$
satisfies $\operatorname{HD}(T',Q^*)< 6k$ and every position in $\operatorname{Occ}_k(P,T')$ is a multiple~of~$|Q|$.
\end{proposition}

We also need a characterization of the values $\operatorname{HD}(P,T'[j|Q|\mathinner{.\,.} m+j|Q|))$.
\begin{proposition}[{\cite[Lemma 3.3 and Claim 3.4]{charalampopoulos2020faster}}]\label{prp:charmult}
Let $P$ be a pattern of length $m$, let $T$ be a text of length $n$,
and let $k\le m$ be a positive integer.
For any non-empty string $Q$ and non-negative integer $j \le \frac{n-m}{|Q|}$,
we have \[\operatorname{HD}(P,T[j|Q|\mathinner{.\,.} m+j|Q|)) = |M(P,Q^*)|+|M(T,Q^*)\cap [j|Q|\mathinner{.\,.} m+j|Q|)| - \mu_j,\]
where \[\mu_j = \sum\limits_{\rho\in M(P,Q^*),\tau \in M(T,Q^*)\;:\; \tau = j|Q|+\rho} 2-\operatorname{HD}(T[\tau],P[\rho]).\]
\end{proposition}

\subsubsection{Improved Solution}
The idea behind achieving $\mathcal{O}(k\log^2 n)$ update time is to run \cref{thm:pillar_k}
once every $k$ updates, but with a doubled threshold $2k$ instead of $k$.
The motivation  behind this choice of parameters is that if
the current instance $P,T$ is obtained by up to $k$ substitutions from a past instance $\bar{P},\bar{T}$,
then $\operatorname{HD}(P,\bar{P})+\operatorname{HD}(T,\bar{T})\le k$ yields $\operatorname{Occ}_k(P,T) \subseteq \operatorname{Occ}_{2k}(\bar{P},\bar{T})$.
Consequently, the algorithm may safely return $\infty$ while answering $\Query(i)$
for any position $i\notin \operatorname{Occ}_{2k}(\bar{P},\bar{T})$.

If the application of \cref{thm:pillar_k} identifies few $2k$-mismatch occurrences, then
we maintain the Hamming distances $d_i$ at these positions throughout the $k$ subsequent updates.
Otherwise, we identify $Q$ and $T'$, as defined in \cref{thm:char}, as well as the sets $M(P,Q^*)$, $M(T',Q^*)$,
and the values $\mu_j$ of \cref{prp:charmult}
so that the distances $\operatorname{HD}(P,T'[j|Q|\mathinner{.\,.} m+j|Q|))$ can be retrieved efficiently.

The latter task requires extending \cref{thm:pillar_k} so that the string $Q$
and the sets $M(P,Q^*)$, $M(T',Q^*)$ can be constructed
whenever there are many $k$-mismatch occurrences.
\begin{lemma}\label{lem:pillar_k}
    There exists a \modelname-model algorithm that, given a pattern $P$ of length $m$, a text $T$ of length $n\le \frac32 m$, and a positive integer $k\le m$, returns $\operatorname{Occ}_{k}(P,T)$
    along with the corresponding Hamming distances provided that $|\operatorname{Occ}_{k}(P,T)|\le 864k$,
    or, otherwise, returns the fragment $T'=T[\min \operatorname{Occ}_k(P,T)\mathinner{.\,.} m+\max \operatorname{Occ}_k(P,T))$,
    a string $Q$ such that $\operatorname{HD}(P,Q^*)<2k$, $\operatorname{HD}(T',Q^*)<6k$, and $\operatorname{Occ}_{k}(P,T')$ consists of multiples of $|Q|$,
    and sets $M(P,Q^*)$, $M(T',Q^*)$.
    The algorithm takes $\mathcal{O}(k^2 \log \log k)$ time plus $\mathcal{O}(k^2)$ \modelname operations.
\end{lemma}
\begin{proof}
First, we use \cref{thm:pillar_k} in order to construct $\operatorname{Occ}_k(P,T)$ in a compact representation
as $\mathcal{O}(k^2)$ arithmetic progressions.
Based on this representation, both $|\operatorname{Occ}_k(P,T)|$ and $T'$ can be computed in $\mathcal{O}(k^2)$ time.
If $|\operatorname{Occ}_{k}(P,T)|\le 864k$, then $\operatorname{Occ}_k(P,T)$ is converted to a plain representation (with each position
reported explicitly along with the corresponding Hamming distance).
Otherwise, we use the $\texttt{Analyze}(P,k)$ procedure of~\cite[Lemma 4.4]{charalampopoulos2020faster}.
This procedure costs $\mathcal{O}(k)$ time in the \modelname model, and it detects
a structure within the pattern $P$ that can be of one of three types.
A possible outcome includes a primitive string $Q$ such that $|Q|\le \frac{m}{128k}$ and $\operatorname{HD}(P,Q^*)<8k$.
Moreover, the existence of a structure of either of the other two types contradicts $|\operatorname{Occ}_{k}(P,T)|\le 864k$
(due to~\cite[Lemmas 3.8 and 3.11]{charalampopoulos2020faster}),
and so does $2k \le \operatorname{HD}(P,Q^*)<8k$ (due to~\cite[Lemma 3.14]{charalampopoulos2020faster}).
Consequently, we are guaranteed to obtain a primitive string $Q$ such that  $|Q|\le \frac{m}{128k}$ and $\operatorname{HD}(P,Q^*)<2k$, which are precisely the conditions in the second case of \cref{thm:char}.
Thus, we conclude that $\operatorname{HD}(T',Q^*)<6k$ and that $\operatorname{Occ}_{k}(P,T')$ consists of multiples of $|Q|$.
It remains to report $M(P,Q^*)$ and $M(T',Q^*)$.
For this task, we employ~\cite[Corollary 4.2]{charalampopoulos2020faster},
whose time cost in the \modelname model is proportional to the output size, i.e., $\mathcal{O}(k)$ for both instances.
\end{proof}

We are now ready to describe the dynamic algorithm based on the intuition above.
Initially, we only improve the \emph{amortized} query time from $\mathcal{O}(k^2\log^2 n)$ to $\mathcal{O}(k\log^2 n)$.
\begin{proposition}\label{prp:amort}
There exists a Las-Vegas randomized algorithm for the dynamic $k$-mismatch problem satisfying $Q(n,k)=\bigO{\log \log n}$ and $U(n,k)=\bigO{k + \log n}$ with high probability, except that every $k$th update costs $\bigO{k^2 \log^2 n}$ time~w.h.p.
\end{proposition}
\begin{proof}
The algorithm logically partitions its runtime into epochs, with $k$ updates in each epoch.
The first update in every epoch costs $\mathcal{O}(k^2 \log^2 n)$ time, and the remaining updates cost $\mathcal{O}(k + \log n)$ time.
A representation of $\X=\{P,T\}$ supporting the \modelname operations (\cref{cor:pillar_impl})
is maintained throughout the execution of the algorithm, while the remaining data is destroyed
after each epoch.

Once the arrival of an update marks the beginning of a new epoch,
we run the algorithm of \cref{lem:pillar_k} with a doubled threshold $2k$.
This procedure costs $\mathcal{O}(k^2 \log^2 n)$ time, and it may have one of two types of outcome.

The first possibility is that it returns a set $O:=\operatorname{Occ}_{2k}(P,T)$ of up to $1728k$ positions,
with the Hamming distance $d_i := \operatorname{HD}(P,T[i\mathinner{.\,.} i+m))$ reported along with each position $i\in O$.
Since $d_i > 2k$ for $i\notin O$ and any update may decrease $d_i$ by at most one,
we are guaranteed that $\Query(i)=\infty$ can be returned for $i\notin O$ for the duration of the epoch.
Consequently, the algorithm only maintains $d_i$ for $i\in O$.
For each of the subsequent updates, the algorithm iterates over $i\in O$ and checks if $d_i$
needs to be changed: If the update involves $P[j]$, then both the old and the new value of $P[j]$
are compared against $T[i+j]$. Similarly, if the update involves $T[j]$ and $j\in [i\mathinner{.\,.} i+m)$, then both the old and the new value of $T[j]$ are compared against $P[i-j]$.
Thus, the update time is $\mathcal{O}(k)$ and the query time is $\mathcal{O}(1)$.

The second possibility is that the algorithm of \cref{lem:pillar_k} results in a fragment $T'=T[\ell \mathinner{.\,.} r)$, a string $Q$, and the mismatching positions $M(P,Q^*)$ and $M(T',Q^*)$.
We are then guaranteed that each $2k$-mismatch occurrence of $P$ in $T$ starts at a position $i\in [\ell\mathinner{.\,.} r-m]$
congruent to $\ell$ modulo $|Q|$. We call these positions \emph{relevant}.
As in the previous case, $\Query(i)=\infty$ can be returned for irrelevant $i$ for the duration of the epoch.
The Hamming distances $d_i$ at relevant positions are computed using \cref{prp:charmult}.
For this, we maintain $M(P,Q^*)$, $M(T',Q^*)$, and all non-zero values $\mu_j$ for $j\in [0\mathinner{.\,.} \lfloor\frac{r-\ell-m}{|Q|}\rfloor]$. Moreover, $M(T',Q^*)$ is stored in a predecessor data structure,
and each element of $M(T',Q^*)$  maintains its rank in this set.
Every subsequent update affects at most one element of $M(P,Q^*)$ or $M(T',Q^*)$,
so these sets can be updated in $\mathcal{O}(1)$ time. Maintaining the predecessor data structure costs further $\mathcal{O}(\log \log n)$ time, and maintaining the ranks costs up to $\mathcal{O}(\operatorname{HD}(T',Q^*))$ time.
In order to update the values $\mu_j$, we proceed as follows.
If the update involves a character $P[\rho]$, we iterate over $\tau \in M(T',Q^*)$. If $j={\tau-\rho}{|Q|}$ is an integer between $0$ and  $\frac{r-\ell-m}{|Q|}$,
we may need to update the entry $\mu_j$ (which costs constant time).
An update involving $T[\ell+\tau]$ is processed in a similar way.
Overall, the update time is $\mathcal{O}(\log n + \operatorname{HD}(T',Q^*) +\operatorname{HD}(P,Q^*))=\mathcal{O}(\log n + k)$
because $\operatorname{HD}(P,Q^*)+\operatorname{HD}(T',Q^*)<2k+6k+k=9k$ holds for the duration of the epoch.

As for the query $\Query(i)$, we return $\infty$ if $i$ is irrelevant, i.e., $i < \ell$, $i > r-m$, or $i \not\equiv \ell \pmod{|Q|}$.
Otherwise, we set $j=\frac{i-\ell}{|Q|}$ and, according to \cref{prp:charmult}, return
$|M(P,Q^*)| + |M(T',Q^*)\cap [j|Q|\mathinner{.\,.} j|Q|+m)|-\mu_j$.
The second term is determined in $\mathcal{O}(\log \log n)$ time using the predecessor data structure
on top of $M(T',Q^*)$ as well as the rank stored for each element of this set.
\end{proof}

Finally, we show how to achieve \emph{worst-case} $\mathcal{O}(k\log^2 n)$ update time.
\begin{theorem}\label{thm:fastQ}
There exists a Las-Vegas randomized algorithm for the dynamic $k$-mismatch problem satisfying $Q(n,k)=\bigO{\log \log n}$ and $U(n,k)=\bigO{k \log^2 n}$ with high probability.
\end{theorem}
\begin{proof}
We maintain two instances of the algorithm of \cref{prp:amort}, with updates forwarded to both instances,
but queries forwarded to a single instance that is currently \emph{active}.

The algorithm logically partitions its runtime into epochs, with $\frac12k$ updates in each epoch.
For the two instances, the time-consuming updates are chosen to be the first updates of every even and odd epoch,
respectively. Once an instance has to perform a time-consuming update, it becomes inactive (it buffers the subsequent updates and cannot be used for answering queries) and stays inactive for the duration of the epoch.
The work needed to perform the time-consuming update is spread across the time allowance for the first half of the epoch, with the time allowance for the second half of the epoch used in order to clear the accumulated backlog of updates (by processing updates at a doubled rate).
During this epoch, the other (active) instance processes updates and queries as they arrive in $\mathcal{O}(k \log^2 n)$
and $\mathcal{O}(\log \log n)$ worst-case time, respectively.
\end{proof}

\subsection{Trade-off between Update Time and Query Time}
The next natural question is the existence of a trade-off between the run-times of~\cref{thm:fastQ,thm:fastU}.
Due to \Cref{thm:3sum_lower} (in \cref{sec:lb}), the answer is likely negative for $k\ll \sqrt{n}$.
Nevertheless, for $k\gg \sqrt{n}$, the trade-off presented below simultaneously achieves $Q(n,k),U(n,k)=k^{1-\Omega(1)}$.

We first recall some combinatorial properties originating from previous work on the $k$-mismatch problem~\cite{chan2020approximating,SODA:CFPST16,CKP,GKKP}.
The description below mostly follows~\cite[Section 3]{GKKP}.

\begin{definition}[\cite{SODA:CFPST16}]
Let $X$ be a string and let $d$ be a non-negative integer.
A positive integer $\rho\le |X|$ is a \emph{$d$-period} of $X$ if $\operatorname{HD}(X[\rho \mathinner{.\,.} |X|), X[0\mathinner{.\,.} |X| - \rho)) \le d$.
\end{definition}

Recall that $\operatorname{Occ}_k(P,T)=\{i: \operatorname{HD}(P,T[i\mathinner{.\,.} i+m))\le k\}$ for a pattern $P$ and text $T$.
\begin{lemma}[\cite{SODA:CFPST16}]\label{lem:aperiodic}
If $i,i'\in \operatorname{Occ}_k(P,T)$ are distinct, then $\rho:=|i'-i|$ is a $2k$-period of $P$.
Moreover, if $n\le 2m$, then $\rho$ is a $(8k+\rho)$-period of $T[\min \operatorname{Occ}_k(P)\mathinner{.\,.} m+\max\operatorname{Occ}_k(P))$.
\end{lemma}

Recall that the $L_0$-norm of a function $f:\mathbb{Z}\to \mathbb{Z}$ defined as $\|f\|_0=|\{x : f(x)\ne 0\}|$.
The \emph{convolution} of two functions $f,g:\mathbb{Z} \to \mathbb{Z}$ with finite $L_0$-norms is a function $f*g: \mathbb{Z} \to \mathbb{Z}$ such that \[[f*g](i)=\sum_{j\in \mathbb{Z}} f(j)\cdot g(i-j).\]
For a string $X$ over $\Sigma$ and a symbol $c\in \Sigma$, the \emph{characteristic function} of $X$ and $c$
is $X_c : \mathbb{Z} \to \{0,1\}$ such that $X_c(i)=1$ if and only if $X[i]=c$.
For a string $X$, let $X^R$ denote $X$ reversed.
The \emph{cross-correlation} of strings $X$ and $Y$ over $\Sigma$ is a function $X\otimes Y:\mathbb{Z}\to \mathbb{Z}$
such that  \[X\otimes Y = \sum_{c\in \Sigma} X_c * Y_c^R.\]

\begin{fact}[{\cite[Fact 7.1]{CKP}}]\label{fct:cross}
For $i\in [m-1\mathinner{.\,.} n)$, we have $[T\otimes P](i)=|P|-\operatorname{HD}(P, T(i-m\mathinner{.\,.} i])$.
For $i<0$ and for $i\ge m+n$, we have $[T\otimes P](i)=0$.
\end{fact}
By \cref{fct:cross}, $[T\otimes P](i+m-1)$ suffices to compute $\operatorname{HD}(P,T[i\mathinner{.\,.} i+m))$ for $i\in [0\mathinner{.\,.} n-m]$.
The \emph{backward difference} of a function $f:\mathbb{Z}\to \mathbb{Z}$ due to $\rho\in \mathbb{Z}_+$ is $\Delta_\rho[f](i)=f(i)-f(i-p)$.

\begin{observation}[{\cite[Observation~7.2]{CKP}}]\label{obs:supp}
    If a string $X$ has a $d$-period $\rho$, then \[\sum_{c\in \Sigma} \|\Delta_\rho[X_c]\|_0 \le 2(d+\rho).\]
\end{observation}
Our computation of $T\otimes P$ is based on the following lemma:
\begin{lemma}[See {\cite[Lemma 6]{GKKP}}]\label{lem:second}
    For every pattern $P$, text $T$, and positive integer $\rho$, we have
    $\Delta_{\rho}[\Delta_{\rho}[T\otimes P]] = \sum_{c\in \Sigma} \Delta_{\rho}[T_c]*\Delta_{\rho}[P_c^R]$.
Consequently, for every $i\in \mathbb{Z}$,
\[[T\otimes P](i) = \sum_{j=0}^\infty (j+1)\cdot \left[\sum_{c\in \Sigma}\Delta_{\rho}[T_c]*\Delta_{\rho}[P_c^R]\right](i-j\rho).\]
\end{lemma}

\begin{theorem}
There exists a deterministic algorithm for the dynamic $k$-mismatch problem with $U(n,k)=\mathcal{O}\Big(\sqrt{\frac{nk}{x}} + \frac{n}{k}\Big)$
and $Q(n,k)=\tO{x}$, where $x$ is a trade-off parameter that can be set in $[1\mathinner{.\,.} k]$.
\end{theorem}
\begin{proof}
We solve the problem using a lazy rebuilding scheme similar to that in the proof of \cref{thm:fastQ}.
Hence, we can afford update time $\tilde{\mathcal{O}}\Big(n + k\sqrt{n}\Big)$ every $k$ updates.
Thus, if an incoming update marks the beginning of a new epoch (lasting for $k$ updates),
we run a (static) $2k$-mismatch algorithm~\cite{chan2020approximating,gawrychowski2018towards}, resulting in $O:=\operatorname{Occ}_{2k}(P,T)$ and the Hamming distances $d_i = \operatorname{HD}(P,T[i\mathinner{.\,.} i+m))$ for each $i\in O$. This takes $\tO{n + k\sqrt{n}}$ time.
As in the proof of \cref{prp:amort}, since $\operatorname{Occ}_k(P,Q)\subseteq O$ holds for the duration of the epoch,
we can safely return $\infty$ for $\Query(i)$ with $i\notin O$.
We distinguish two cases.
\begin{description}
\item[$|O|\le \frac{n}{k}$:]
We maintain the distances $d_i$ for $i\in O$. As noted above, $\operatorname{Occ}_{k}(P,T)\subseteq O$ even after $k$ updates.
We now observe that any update requires only updating the mismatches for every element of $O$, with $\bigO{1}$ cost per element and $\bigO{\frac{n}{k}}$ total; the queries are handled by finding the answer stored for  $i\in O$, at $\tO{1}$ cost.
\item[$|O|> \frac{n}{k}$:] We set $\rho$ to be the distance between two closest elements of $O$;
we have $\rho\le k$  due to $|O|> \frac{n}{k}$. By \cref{lem:aperiodic}, $\rho$ is a $4k$-period of $P$ and a $17k$-period of $T':=T[\min O \mathinner{.\,.} m+\max O)$. Moreover, $\operatorname{Occ}_{k}(P,T)\subseteq O \subseteq [\min O\mathinner{.\,.} \max O]$
holds for the duration of the epoch, so all $k$-mismatch occurrences of $P$ in $T$ remain contained in $T'$.
\end{description}

We have thus reduced our problem to answering queries and performing updates for $P$ and $T'$.
Moreover, we have a positive integer $\rho\le k$ which is initially a $4k$-period of $P$ and a $17k$-period of $T'$,
and, after $k$ updates, it remains a $6k$-period of $P$ and $19k$-period of $T'$.
Let us define the \emph{weight} of $c\in \Sigma$ as $\|\Delta_{\rho}[P^R_c]\|_0 + \|\Delta_{\rho}[T'_c]\|_0$;
by \cref{obs:supp}, the total weight across $c\in \Sigma$ remains $\mathcal{O}(k)$.

We proceed as follows. We maintain $\Delta_{\rho}(P^R_c) * \Delta_{\rho}(T'_c)$ for each letter $c\in \Sigma$ separately, and the sum $\Delta_{\rho}[\Delta_{\rho}[T\otimes P]]=\sum_{c \in \Sigma} \Delta_{\rho}(P^R_c) * \Delta_{\rho}(T'_c)$.
For each remainder  $i\bmod \rho$, the values $\Delta_{\rho}[\Delta_{\rho}[T\otimes P]](i)$ are stored in a data structure that allows queries for prefix sums (both unweighted and weighted by $\floor{i/\rho}$)
so that $[T\otimes P](i)$ can be retrieved efficiently using \cref{lem:second}.
Every update to $P$ or $T$ incurs updates to $\Delta_{\rho}(P^R_c)$ or $\Delta_{\rho}(T'_c)$, in $\bigO{1}$ places in total (two for each letter involved in the substitution).
We buffer the updates to those convolutions of (potentially) sparse functions during subepochs of $x$ updates, and then we recompute values of $\Delta_{\rho}(P^R_c) * \Delta_{\rho}(T'_c)$ amortized during the next $x$ updates. We fix a threshold value $t$ (specified later), and iterate through letters $c \in \Sigma$.
\begin{itemize}
\item If a letter $c$ had weight at least $t$ or accumulated at least $t$ updates, we recompute the corresponding convolution from scratch, at the cost of $\tO{n}$ time per each such \emph{heavy} letter.
\item Otherwise, updates are processed one by one, at the cost of $\tO{t}$ time per update.
\end{itemize}
There are $\bigO{\frac{k+x}{t}}$ heavy letters, which is $\tO{\frac{k}{t}}$ since $x\le k$. Thus, the total cost $\tO{\frac{nk}{t}  + x t}$ is minimized when $t = \sqrt{\frac{nk}{x}}$ and gives $\tO{\sqrt{nkx}}$ time per subepoch, or $\tilde{\mathcal{O}}\Big(\sqrt{\frac{nk}{x}}\Big)$ time per update.

To perform queries, we retrieve $[T\otimes P](i+m-1)$ using \cref{lem:second} and the data structure maintaining
$\Delta_{\rho}[\Delta_{\rho}[T\otimes P]]$ to recover the number of matches last time we stored the convolutions.
Next, we scan through the list of at most $2x$ updates to potentially update the answer.
\end{proof}

To put the trade-off complexity in context, we note that e.g., when $k = m$, it is possible to achieve $U(n,k), Q(n,k) = \tO{n^{2/3}}$. This improves over $\tO{n^{3/4}}$ presented in~\cite{clifford2018upper}.