# Calibrate and Refine! A Novel and Agile Framework for ASR-error Robust
Intent Detection

###### Abstract

The past ten years have witnessed the rapid development of text-based intent
detection, whose benchmark performances have already been taken to a
remarkable level by deep learning techniques. However, automatic speech
recognition (ASR) errors are inevitable in real-world applications due to the
environment noise, unique speech patterns and etc, leading to sharp
performance drop in state-of-the-art text-based intent detection models.
Essentially, this phenomenon is caused by the semantic drift brought by ASR
errors and most existing works tend to focus on designing new model structures
to reduce its impact, which is at the expense of versatility and flexibility.
Different from previous one-piece model, in this paper, we propose a novel and
agile framework called CR-ID for ASR error robust intent detection with two
plug-and-play modules, namely semantic drift calibration module (SDCM) and
phonemic refinement module (PRM), which are both model-agnostic and thus could
be easily integrated to any existing intent detection models without modifying
their structures. Experimental results on SNIPS dataset show that, our
proposed CR-ID framework achieves competitive performance and outperform all
the baseline methods on ASR outputs, which verifies that CR-ID can effectively
alleviate the semantic drift caused by ASR errors.

Index Terms: intent detection, human-computer interaction, spoken language
understanding

##  1 Introduction

Intent detection (ID), as one of the key tasks in spoken language
understanding, aims to identify users’ intents from their utterances. Driven
by advances in deep learning technology, the ID research has entered into a
stage of rapid development. Specifically, many classical methods like
convolutional neural network (CNN) [1, 2, 3], recurrent neural network (RNN)
[4, 5, 6], graph neural network (GNN) [7] and self-attention mechanism [8, 9]
have been explored for this task and obtained superb performance on benchmark
datasets. Moreover, pre-trained language models [10] have also been utilized
to better understand the meaning of the user sentences and thus could help to
classify the intents more accurately. Notwithstanding the favorable results of
these models, they often assume that automatic speech recognition (ASR) never
makes any mistakes. The training and testing of these ID models are both
conducted on error-free manual transcriptions, rather than ASR outputs.

Unfortunately, this overly idealistic setting would make it hard to deploy
existing ID models in real-world applications, where ASR errors are
unavoidable due to the complex conditions like environment noise and diverse
speaking styles or accents. As shown in the right side of Figure 1, although
pretrained language models (LMs) like BERT [11] and ELMo [12] could provide
more robust representations compared with static embeddings like Word2Vec
[13], they still suffer from sharp performance drop when tested on ASR
outputs. This is because the original representations of user utterances are
prone to be distorted by ASR errors (as shown in the left side of Figure 1),
which is named as semantic drift problem in this paper.

Recently, several studies were introduced to mitigate such semantic drift
problem. [14, 15, 16] proposed to remove the ASR component and extract
semantics directly from the speech signals in an end-to-end manner. Following
this trend, [17] applied the mask strategy to audio frames and utilized large-
scale unsupervised pre-training technique to learn acoustic representations
for SLU. However, compared with pipeline-based methods, these end-to-end
models are less interpretable and more data-hungry. In addition, the
annotation process of audio data is usually both expensive and time-consuming,
which is impractical for industrial applications.

Figure 1: Semantic drift problem (Left) and the comparison of different ID
models’ performance on manual transcriptions and ASR outputs (Right)

Therefore, some researchers proposed to utilize text and speech together for
SLU systems. For example, [18] proposed a novel ST-BERT and designed two new
cross-modal language modeling tasks to better learn the semantic
representations of speech and text modalities. [19] suggested to carry out
both speech and language understanding tasks during pre-training and
constructed a novel speech-language joint pre-training framework for SLU.
Though achieving excellent performance, they still require pre-training with
large-scale datasets, which are not available in some data scarce domains.

Another branch of ASR-error robust research is to reduce the impact of
semantic drift by considering the acoustic similarity between words [20] or
directly injecting phoneme information to the modeling process [21], which had
a similar motivation with ours. But most of them only focused on designing new
model structures for specific scenario, and usually show poor compatibility
with other methods. So far, designing a both versatile and flexible model has
still not been well explored in this research field.

Figure 2: Overview of the proposed CR-ID framework.

To overcome above-mentioned limitations, we propose a novel and agile
framework called Calibration and Refinement for Intent Detection (CR-ID).
Different from previous solutions, our approach decouples the semantic
calibration and intent classification process, thus any existing text-based
intent detection models could be incorporated into this framework and become
more robust to ASR errors. Specifically, we design two plug-and-play modules
to calibrate the semantic drift and refine the calibrated representation with
phonemic information, which provides useful signals for the intent
classification process. Our proposed framework will be further detailed in
section 2 and our main contributions could be summarized as follows:

  * •

We propose the CR-ID framework, which could effectively reduce the impact of
semantic drift on existing text-based intent detection models without any
structural modifications.

  * •

We design two plug-and-play modules, namely SDCM and PRM, to calibrate both
word-level and sentence-level representation for ASR outputs and utilize the
phonemic information to refine and enrich the calibrated representations.

  * •

We conduct comprehensive experiments on SNIPS dataset and the results show
that, compared with the best baseline model, the intent accuracy and Macro-F1
score of our proposed CR-ID are increased by 1.99% and 1.86% respectively,
which demonstrates the effectiveness of CR-ID on boosting the robustness of
existing ID model.

##  2 The Proposed Approach

In this section, we present our CR-ID, which is able to effectively and
flexibly alleviate the semantic drift problem without changing the structure
of classical text-based ID models. The overall architecture of CR-ID is
illustrated in Figure2, consisting of three main modules: Semantic Drift
Calibration Module (Sec. 2.1), Phonemic Refinement Module (Sec. 2.2), and
Intent Detection Module (Sec. 2.3).

###  2.1 Semantic Drift Calibration Module

SDCM aims to calibrate the distorted representations of ASR outputs and
minimize the negative impacts brought by semantic drift. To achieve this,
inspired by the great success of pretrained language models (PLM) and
finetuning techniques, we propose to adopt two PLM finetuning strategies,
namely confusion-aware finetuning and task-adaptive finetuning, which are
transformed from [20] and [22].

For confusion-aware finetuning, we first use both minimum edit-distance (MED)
and word confusion network (WCN) to extract acoustic confusion, which are
introduced by [20]. Due to space limitation, readers could check the details
from their paper. Taking the two different utterances $x_{1}$ and $x_{2}$ as
an example, we use $C=\left\\{c_{1},c_{2},\cdots,c_{|C|}\right\\}$ to denote
the set of all acoustic confusions, where
$c=\left\\{w_{t_{1}}^{x_{1}},w_{t_{2}}^{x_{2}}\right\\}$ consists of two
acoustically similar words $w_{t_{1}}^{x_{1}}$ and $w_{t_{2}}^{x_{2}}$.
Finally, we propose a new confusion loss to minimize the mean square error
(MSE) between the word-level representations and sentence-level
representations generated by pretrained language model as follows:

$\displaystyle\mathrm{L}_{\mathrm{ca}}\\!=\\!\frac{1}{|c|}\sum_{c\in
C}\sum_{i=0}^{1}\operatorname{MSE}\left(h_{t_{1},i}^{x_{1}},h_{t_{2},i}^{x_{2}}\right)+\operatorname{MSE}\left(h^{x_{1}},h^{x_{2}}\right)$
(1)

Task-adaptive finetuning is a widely used technique especially when domain
mismatch problem happens, which could effectively adapt pretrained LM from
general corpus to the target data. For example, given a pre-trained ELMo model
and a sentence $x=\left\\{w_{1},w_{2},\ldots,w_{|x|}\right\\}$, we could
directly use the pretraining loss of ELMo as the task-adaptive loss, which
could be written as:

$\displaystyle\mathrm{L}_{\mathrm{ta}}=\frac{1}{|x|}\sum_{t=1}^{|x|}-\log
p\left(w_{t}\mid w_{<t}\right)-\log p\left(w_{t}\mid w_{>t}\right)$ (2)

where $p\left(w_{t}\mid w_{<t}\right)$ and $p\left(w_{t}\mid w_{>t}\right)$
denote the probabilities of $w_{t}$ calculated from forward and backward
directions.

Eventually, we jointly finetune the LM using above-mentioned two strategies in
a multi-task learning manner and the final loss is as follows:

$\displaystyle L=L_{\mathrm{ta}}+\lambda L_{\mathrm{ca}}$ (3)

where $\lambda$ represents a balancing hyperparameter to control the
contribution of each finetuning strategy.

###  2.2 Phonemic Refinement Module

Phoneme is the smallest pronunciation unit in speech and the phoneme sequence
of each word can represent its acoustic information to some extent. Therefore,
we design PRM to refine and enrich the calibrated representation by injecting
phonemic information into the modeling process.

Firstly, each word $w_{t}$ in the ASR output $x_{asr}$ will be transformed
into a phoneme sequence
$P_{t}=\left\\{p_{1},p_{2},\cdots,p_{N_{w_{t}}}\right\\}$ via a grapheme to
phoneme (G2P) conversion algorithm [23], which highly depends on the
pronunciation dictionary. In this paper we adopt CMU pronunciation dictionary
[24] constructed by Carnegie Mellon University, which includes 39 types of
phonemes and covers more than 130,000 words as well as their corresponding
pronunciation information. Figure 2 also shows the process of converting the
word ”find” into a phoneme sequence ”F,AY1,N,D”. Note that for vowels like
”AY”, there is a stress marker behind them indicating which stress types it
belongs to. Generally, ”0” represents no stress, ”1” and ”2” represent primary
stress and secondary stress respectively, which could provide fine-grained
acoustic information for intent detection process. Then, each phoneme sequence
will be mapped into the embedding space and be further encoded by a BiLSTM
layer as follows:

$\displaystyle H_{w_{t}}=$ $\displaystyle
BiLSTM([e_{p_{1}},e_{p_{2}},\dots,e_{N_{w_{t}}}]),$ (4)

where $e_{p_{i}}$ denotes the embedding of the phoneme $p_{i}$ and $H_{w_{t}}$
represents the hidden representation matrix for word $w_{t}$.

In the end, average pooling method is conducted on these hidden representation
matrices to obtain the final acoustic embedding of the whole sentence $x_{i}$:

$\displaystyle H_{x_{asr}}^{acoustic}=$
$\displaystyle[h_{w_{1}},h_{w_{2}},\dots,h_{w_{N}}],$ (5) $\displaystyle
h_{w_{t}}=$ $\displaystyle Average(H_{w_{t}}),$ (6)

###  2.3 Intent Detection Module

As shown in Figure 2, the intent detection module is decoupled from other
modules, making it possible to incorporate any existing text-based intent
detection model to our proposed CR-ID framework. Therefore, we adopt a self-
attentive intent classification model inspired by [8] as the ID module. The
input of ID module is the concatenation of the calibrated word embedding
generated by SDCM and the acoustic embedding generated by PRM. BiLSTM is used
to model the long-term dependency in the utterance and the self attention
mechanism is adopted to capture the key information from the calibrated and
refined representations. Max pooling is utilized to obtain the final sentence-
level representation, which is further fed to a softmax classifier to predict
user’s intent.

Table 1: Overall performance on manual and ASR output. Bold scores represent
the highest results of all methods.

Model | Mannual | ASR output
---|---|---
ACC% | Macro-F1% | ACC% | Macro-F1%
Random | 96.87 | 96.91 | 78.60 | 79.87
GloVe | 97.15 | 97.18 | 77.12 | 77.70
Word2Vec | 96.73 | 96.81 | 76.14 | 77.02
FastText | 97.01 | 97.00 | 79.15 | 79.48
BERT (w/o Fine-tuning) | 96.43 | 96.44 | 80.40 | 80.81
BERT (w Fine-tuning) | 97.59 | 97.70 | 82.01 | 82.80
ELMo (w/o Fine-tuning) | 96.70 | 96.77 | 80.60 | 81.61
ELMo (w Fine-tuning) | 97.28 | 97.31 | 81.69 | 82.24
SpokenVec (MED) | 97.01 | 97.21 | 88.52 | 89.23
SpokenVec (WCN) | 97.04 | 97.12 | 89.55 | 89.97
CR-ID (MED) | 97.42 | 97.50 | 90.85 | 91.32
CR-ID (WCN) | 97.14 | 97.23 | 91.54 | 91.83

##  3 Experiments

###  3.1 Dataset

In [20], the authors used three datasets, namely SNIPS, ATIS and Smartlight,
for their experiments. However, both ATIS (with confusion words) and
Smartlight are not available for public because of the copyright issue.
Therefore, for fair comparison with the method proposed in [20], we directly
use their released version of SNIPS dataset to conduct all the experiments.
Different from the original SNIPS dataset, [20] extracted confusion words via
the two strategies introduced in Sec2.1 and added them to the original
dataset, which is convenient for researchers to reproduce their results and
make improvements on it. The readers could check the details of this dataset
in https://github.com/MiuLab/SpokenVec.

###  3.2 Baselines and Implementation Details

A number of ASR error robust ID models have been proposed in the past few
years. We do not compare with all of them because many previous methods are
not directly comparable due to the use of different model architectures.
Hence, we select SpokenVec [20] and construct several baselines that are fair
(use the same information, similar architectures, etc.) to compare with.
Specifically, we use the intent detection module (introduced in Sec 2.3) as
the base model, because the self-attentive intent detection model has already
achieved comparative performance on SNIPS dataset according to [25]. Then we
incorporate it with different word embedding techniques as the baselines.
Static Word Embedding. We use three pre-trained static word embeddings,
Word2Vec [13], GloVe [26] and FastText [27], as the embedding matrix to help
encode sentences. We also use a randomly initialized embedding matrix as a
comparison.
Contextual Word Embedding. We evaluate two pretrained language models, ELMo
and BERT, to obtain contextual word embeddings. And each LM is evaluated with
fixed and unfixed parameters respectively.
Implementation Details. For the ID base model, the dimension of BiLSTM and
self-attention layer are all set to 300, the number of heads is set to 8, the
batch size is 64. All ID base models are trained on the manual transcribed
training set for 50 epochs using Adam optimizer with learning rate as 3e-4,
and then tested on the manual transcriptions and ASR outputs respectively. For
the SDCM, for fair comparison with SpokenVec, we follow its setting and adopt
ELMo as the pretrained LM. We train the SDCM for 10 epochs with the batch size
of 32, learn rate of Adam set to 1e-4. For PRM, the dimension of the embedding
and BiLSTM hidden layers are all set to 50 and the PRM is jointly trained with
ID base model.

Table 2: Ablation study

Model | Mannual | ASR output
---|---|---
ACC% | Macro-F1% | ACC% | Macro-F1%
Full | 97.14 | 97.23 | 91.54 | 91.83
w/o acoustic embedding | 96.71 | 96.81 | 90.55 | 90.87
w/o confusion-aware fintuning strategy | 97.15 | 97.21 | 88.60 | 89.01
w/o task-adaptive finetuning strategy | 97.28 | 97.41 | 82.12 | 83.14

Table 3: Performance comparison of using different distance functions as the
confusion loss.The metric is accuracy.

Test data type | Confusion extraction type | Type of loss function
---|---|---
Cosine | L1 | MSE | Triplet
ASR | MED | 90.56 | 84.90 | 90.85 | 88.88
ASR | WCN | 90.82 | 88.26 | 91.54 | 90.10
Manual | MED | 96.55 | 92.71 | 97.42 | 96.40
Manual | WCN | 97.30 | 96.86 | 97.14 | 96.73

Figure 3: Parameter sensitivity of $\lambda$

###  3.3 Results and Analysis

The overall performance of the baselines and CR-ID are summarized in Table 1.
Note that as introduced in Sec 2.1 and Sec 3.1, the confusion word pairs could
be generated by minimum edit distance (MED) or word confusion network (WCN).
Hence, for SpokenVec and our proposed CR-ID, we also report the performance
variations using different confusion extraction methods in Table 1. Here are
some observations from the Table 1: when testing on the manual transcriptions,
the performance scores of all methods are very close, and the method based on
contextual word embedding is slightly better than the static counterparts.
However, the performances of all baselines except for SpokenVec drops sharply
on the ASR output, demonstrating the necessity to reduce the negative impacts
caused by semantic drift problem. CR-ID (WCN) achieved the best performance in
terms of both Accuracy and Macro-F1. Specifically, compared with the best
static word embedding based baselines, the Accuracy and Macro-F1 of CR-ID
(WCN) are increased by 12.39% and 11.96% respectively; compared with the best
contextual word embedding based baseline model, the performance are improved
by 9.5% and 9% respectively; even compared with the SpokenVec, which is a very
strong baseline, the performance gains still achieve 1.99% and 1.86%
respectively, demonstrating the effectiveness of our propose CR-ID framwork.

###  3.4 Ablation Study

In order to figure out the contribution of different modules in our proposed
CR-ID, we conduct ablation study for each plug-and-play module, as shown in
Table.2: 1) CR-ID w/o acoustic embedding, which only use SDCM for calibration;
2) CR-ID w/o confusion-aware finetuning strategy, where only task-adaptive
finetuning and PRM are reserved. 3) CR-ID w/o task-adaptive finetuning
strategy, where only confusion-aware finetuning and PRM are reserved. We
observe that all these components contribute to performance improvements when
testing on the ASR outputs. Specifically, task adaptive fine-tuning strategy
contributes the most to the robustness of ID module. When this strategy is
removed from the CR-ID, the accuracy and Macro-F1 are decreased by 9.42% and
8.69% respectively. And the confusion-aware finetuning strategy take the
second place. Without it, the accuracy and Macro-F1 are decreased by 2.94% and
2.82% respectively. Without acoustic embedding, the accuracy and Macro-F1 are
decreased by 0.99% and 0.96% respectively. Therefore, the combination of SDCM
and PRM could significantly improve the robustness of ID module to ASR errors.

In addition, we also explore the effect of different distance functions in the
confusion loss on model’s performance. Here we select three classical distance
functions (Equation 7,8,9) to subsitute the MSE in Equation 1, and the results
are shown in Table 3. We observe that MSE achieves the best performance under
most experimental settings, which is the reason why we finally choose MSE
distance for the confusion-aware finetuning strategy.

$\displaystyle\mathrm{L}_{\text{cos}}\\!=\\!\frac{1}{|C|}\sum_{c\in
C}\sum_{i=0}^{1}\left(1-\frac{h_{t_{1},i}^{x_{1}}\cdot
h_{t_{2},i}^{x_{2}}}{\left\|h_{t_{1},i}^{x_{1}}\right\|\left\|h_{t_{2},i}^{x_{2}}\right\|}\right)+\left(1-\frac{h^{x_{1}}\cdot
h^{x_{2}}}{\left\|h^{x_{1}}\right\|\left\|h^{x_{2}}\right\|}\right)$ (7)
$\displaystyle\mathrm{L}_{\mathrm{l1}}=\frac{1}{|C|}\sum_{c\in
C}\sum_{i=0}^{1}\left\|h_{t_{1},i}^{x_{1}}-h_{t_{2},i}^{x_{2}}\right\|_{1}+\left\|h^{x_{1}}-h^{x_{2}}\right\|_{1}$
(8)
$\displaystyle\begin{gathered}\mathrm{L}_{\\!\text{triplet}}\\!=\\!\frac{1}{|C|}\sum_{c\in
C}\sum_{i=0}^{1}\text{triplet}\left(h_{t_{1},i}^{x_{1}},h_{t_{2},i}^{x_{2}},h_{t_{3},i}^{x_{3}}\right)\\!+\\!\text{triplet}\left(\\!h^{x_{1}},\\!h^{x_{2}},\\!h^{x_{3}}\right)\\\
\text{triplet}(a,p,n)=\max\left\\{d\left(a_{i},p_{i}\right)-d\left(a_{i},n_{i}\right)+\text{margin},0\right\\}\\\
\quad d\left(x_{i},y_{i}\right)=\left\|x_{i}-y_{i}\right\|_{p}\end{gathered}$
(9)

###  3.5 Hyperparameter Sensitivity

In this section, we aim to analyze the effect of the balancing hyperparameter
$\lambda$ (in the Equation 3) on the performance of CR-ID. The results are
illustrated in Figure 3. It can be observed that for both CR-ID (MED) or CR-ID
(WCN), when $\lambda$ increases from 0.1 to 10, the model performance is
slightly improved, but when the $\lambda$ gets larger (e.g. larger than 15),
the performance of the model begins to decline. Therefore, for all the CR-ID
related experiments, we set $\lambda$ to 10 to better balance the impact of
task-adaptive finetuning and confusion-aware finetuning on model optimization.

##  4 Conclusion

In this paper, we propose a novel and agile framework, called CR-ID, for ASR
error robust intent detection. Two plug-and-play modules, namely SDCM and PRM,
are designed to calibrate both word-level and sentence-level representation
for ASR outputs and utilize the phonemic information to refine and enrich the
calibrated representations. Experimental results on SNIPS dataset show that
our proposed CR-ID outperform all baseline models on the ASR outputs,
demonstrating that our proposed framwork could effectively reduce the impact
of semantic drift on existing text-based intent detection models and boost
their robustness to ASR errors.

## References

  * [1] G. Tür, L. Deng, D. Hakkani-Tür, and X. He, “Towards deeper understanding: Deep convex networks for semantic utterance classification,” in _ICASSP_. IEEE, 2012, pp. 5045–5048.
  * [2] P. Xu and R. Sarikaya, “Convolutional neural network based triangular CRF for joint intent detection and slot filling,” in _ASRU_. IEEE, 2013, pp. 78–83.
  * [3] C. Zhang, W. Fan, N. Du, and P. S. Yu, “Mining user intentions from medical queries: A neural network based heterogeneous jointly modeling approach,” in _WWW_. ACM, 2016, pp. 1373–1384.
  * [4] S. V. Ravuri and A. Stolcke, “Recurrent neural network and LSTM models for lexical utterance classification,” in _INTERSPEECH_. ISCA, 2015, pp. 135–139.
  * [5] B. Liu and I. Lane, “Attention-based recurrent neural network models for joint intent detection and slot filling,” in _INTERSPEECH_. ISCA, 2016, pp. 685–689.
  * [6] Y. Wang, Y. Shen, and H. Jin, “A bi-model based RNN semantic frame parsing model for intent detection and slot filling,” in _NAACL-HLT (2)_. Association for Computational Linguistics, 2018, pp. 309–314.
  * [7] J. Hu, G. Wang, F. H. Lochovsky, J. Sun, and Z. Chen, “Understanding user’s query intent with wikipedia,” in _WWW_. ACM, 2009, pp. 471–480.
  * [8] S. Yolchuyeva, G. Németh, and B. Gyires-Tóth, “Self-attention networks for intent detection,” in _RANLP_. INCOMA Ltd., 2019, pp. 1373–1379.
  * [9] M. Chen, J. Zeng, and J. Lou, “A self-attention joint model for spoken language understanding in situational dialog applications,” _CoRR_ , vol. abs/1905.11393, 2019.
  * [10] Q. Chen, Z. Zhuo, and W. Wang, “BERT for joint intent classification and slot filling,” _CoRR_ , vol. abs/1902.10909, 2019.
  * [11] J. Devlin, M. Chang, K. Lee, and K. Toutanova, “BERT: pre-training of deep bidirectional transformers for language understanding,” in _NAACL-HLT (1)_. Association for Computational Linguistics, 2019, pp. 4171–4186.
  * [12] M. E. Peters, M. Neumann, M. Iyyer, M. Gardner, C. Clark, K. Lee, and L. Zettlemoyer, “Deep contextualized word representations,” in _NAACL-HLT_. Association for Computational Linguistics, 2018, pp. 2227–2237.
  * [13] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation of word representations in vector space,” in _ICLR (Workshop Poster)_ , 2013.
  * [14] Y. Chen, R. Price, and S. Bangalore, “Spoken language understanding without speech recognition,” in _ICASSP_. IEEE, 2018, pp. 6189–6193.
  * [15] P. Haghani, A. Narayanan, M. Bacchiani, G. Chuang, N. Gaur, P. J. Moreno, R. Prabhavalkar, Z. Qu, and A. Waters, “From audio to semantics: Approaches to end-to-end spoken language understanding,” in _SLT_. IEEE, 2018, pp. 720–726.
  * [16] L. Lugosch, M. Ravanelli, P. Ignoto, V. S. Tomar, and Y. Bengio, “Speech model pre-training for end-to-end spoken language understanding,” in _INTERSPEECH_. ISCA, 2019, pp. 814–818.
  * [17] P. Wang, L. Wei, Y. Cao, J. Xie, and Z. Nie, “Large-scale unsupervised pre-training for end-to-end spoken language understanding,” in _ICASSP_. IEEE, 2020, pp. 7999–8003.
  * [18] M. Kim, G. Kim, S. Lee, and J. Ha, “St-bert: Cross-modal language model pre-training for end-to-end spoken language understanding,” in _ICASSP_. IEEE, 2021, pp. 7478–7482.
  * [19] Y. Chung, C. Zhu, and M. Zeng, “SPLAT: speech-language joint pre-training for spoken language understanding,” in _NAACL-HLT_. Association for Computational Linguistics, 2021, pp. 1897–1907.
  * [20] C. Huang and Y. Chen, “Learning asr-robust contextualized embeddings for spoken language understanding,” in _ICASSP_. IEEE, 2020, pp. 8009–8013.
  * [21] Q. Chen, W. Wang, and Q. Zhang, “Pre-training for spoken language understanding with joint textual and phonetic representation learning,” in _Interspeech_. ISCA, 2021, pp. 1244–1248.
  * [22] J. Howard and S. Ruder, “Universal language model fine-tuning for text classification,” in _ACL (1)_. Association for Computational Linguistics, 2018, pp. 328–339.
  * [23] J. Park, Kyubyong Kim, “g2pe,” https://github.com/Kyubyong/g2p, 2019.
  * [24] J. Kominek and A. W. Black, “The CMU arctic speech databases,” in _SSW_. ISCA, 2004, pp. 223–224.
  * [25] L. Qin, T. Xie, W. Che, and T. Liu, “A survey on spoken language understanding: Recent advances and new frontiers,” in _IJCAI_. ijcai.org, 2021, pp. 4577–4584.
  * [26] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in _EMNLP_. ACL, 2014, pp. 1532–1543.
  * [27] A. Joulin, E. Grave, P. Bojanowski, M. Douze, H. Jégou, and T. Mikolov, “Fasttext.zip: Compressing text classification models,” _CoRR_ , vol. abs/1612.03651, 2016.


$1<1$; thus there must be some $m_{1}^{\star}\in M_{1}$ for which $\sum_{v\in
B}{S_{m_{i},v}}\geq\beta n$. Let $\mathcal{G}_{1}$ be the set of graphs for
which $H\in\mathcal{G}_{1}\iff m_{1}(H)=m_{1}^{\star}$; then on being given
any graph in $\mathcal{G}_{1}$, player $P_{1}$ will output $m_{1}^{\star}$.

We will now iterate over $i\in\\{2,\ldots,\Delta-1\\}$ and build a sequence of
messages $m_{1}^{\star},m_{2}^{\star},\ldots,m_{\Delta}^{\star}$, along with
sets of input graphs $\mathcal{G}_{1},\ldots,\mathcal{G}_{\Delta-1}$ on which
the protocol will send these messages. For each $i\in[\Delta]$, define
$\mathcal{T}_{m,i,i}=(T_{v,m,i})_{v\in B}$, where $T_{v,m,i}:=S_{m}\setminus
S_{m_{i-1}^{\star},i}$. Any coloring $\chi_{i}$ that $P_{i}$ outputs which is
compatible with all inputs leading to $m_{i}^{\star}$ will satisfy
$\chi_{i,v}\in T_{v,m,i}$. (If $\chi_{i,v}\in S_{m_{i-1}^{\star},i}$, then as
noted above there is a set of inputs where this will violate the edge coloring
constraint for $v$.) As argued for $M_{1}$, there must be some message
$m_{i}^{\star}\in M_{i}$ for which $\sum_{v\in B}|T_{v,m,i}|\geq\beta n$.

Finally, for each $v\in B$, define $R_{v}=[\beta\Delta]\setminus
S_{m_{\Delta-1}^{\star},v}$. Since
$S_{m_{\Delta-1}^{\star},v}=\sqcup_{i=1}^{\Delta-1}T_{v,m_{i}^{\star},i}$ we
will have $|R_{v}|\leq\beta\Delta-\beta(\Delta-1)=\beta$. On receiving
$m_{\Delta-1}^{\star}$, player $P_{\Delta}$ can only assign edge colors so
that edges incident on $v$ use colors in $R_{v}$; for any other color, there
is a input which uses it and which makes $P_{\Delta-1}$ send
$m_{\Delta-1}^{\star}$. If $G_{\Delta}$ were chosen uniformly at random from
its set of possible values, then the probability that $G_{\Delta}$ has an edge
coloring compatible with $\\{R_{v}\\}_{v\in m}$ is $\leq p(n,\Delta,\beta)$.
Since this is $<1$, there must exist a specific graph $G_{\Delta}^{\dagger}$
on which the protocol uses a color not in $R_{v}$ for some $v\in B$. We have
thus shown that if the protocol always uses fewer than $\log
1/p(n,\Delta,\beta)$ bits for its messages, it will give incorrect outputs for
some input.

We conclude:

$\displaystyle S\geq\log\frac{1}{p(n,\Delta,\beta)}=\Omega((2-\beta)^{3}n)$

∎

##  6 Supporting lemmas

######  Corollary 6.0 (Practical high-rate-distance-product binary codes, via
[SS96]).

For sufficiently large $t$, there is a binary code of length $t$ with rate
$\geq\frac{1}{4}t$, and distance $\geq\frac{1}{400}t$. The code can be
implemented with $poly(t)$ initial setup time and space, and $O(t^{2})$
encoding time.

###### Proof of Section 6.

Let $\epsilon=\sqrt{2}/20$. By [SS96] Theorem 19, there is a polynomial time
constructible family of codes of rate $1-2H(\epsilon)=0.2628\ldots\geq 1/4$,
and relative distance approaching $\epsilon^{2}=1/200$. In particular, for
sufficiently large code length $t$, the rate will be $\geq 1/4$ and the
relative distance will be $\geq 1/400$.

The expander codes described by [SS96], at code length $t$, require
$\operatorname{poly}(t)$ time to construct the expander graph used, and can be
encoded in $O(t^{2})$ time. ∎

######  Lemma 6.1.

Let $W$ be a nonnegative integral random variable where, for all
$k\in\mathbb{N}$, $\Pr[W\geq k]\leq 1/2^{k}$. Then
$\operatorname{\mathbb{E}}[W]\leq 1$; and furthermore, for all $t$ for which
$e^{t}\in[1,2)$:

$\displaystyle\operatorname{\mathbb{E}}[e^{tW}]\leq\frac{1}{2-e^{t}}$

###### Proof of Lemma 6.1.

First,

$\displaystyle\operatorname{\mathbb{E}}[W]=\sum_{k=0}^{\infty}\Pr[W\geq
k]\leq\sum_{k=0}1/2^{k+1}=1$

Next,

$\displaystyle\operatorname{\mathbb{E}}[e^{tW}]$
$\displaystyle=\sum_{k=0}^{\infty}e^{tk}\Pr[W=k]\leq\sum_{k=0}^{\infty}e^{tk}\frac{1}{2^{k+1}}=\frac{1}{2}\sum_{k=0}^{\infty}\left(\frac{e^{t}}{2}\right)^{k}=\frac{1}{2}\cdot\frac{1}{1-\frac{1}{2}e^{t}}=\frac{1}{2-e^{t}}$

The inequality step follows because:

$\displaystyle\sum_{k=0}^{\infty}e^{tk}\left(\frac{1}{2^{k+1}}-\Pr[W=k]\right)$
$\displaystyle=\sum_{k=0}^{\infty}e^{tk}\left((\frac{1}{2^{k}}-\frac{1}{2^{k+1}})-(\Pr[W\geq
k]-\Pr[W\geq k-1])\right)$
$\displaystyle=\sum_{k=0}^{\infty}e^{tk}\left(\frac{1}{2^{k}}-\Pr[W\geq
k]\right)-\sum_{k=0}^{\infty}e^{tk}\left(\frac{1}{2^{k+1}}-\Pr[W\geq
k-1]\right)$
$\displaystyle=\sum_{k=0}^{\infty}e^{tk}\left(\frac{1}{2^{k}}-\Pr[W\geq
k]\right)-\sum_{k=1}^{\infty}e^{t(k-1)}\left(\frac{1}{2^{k}}-\Pr[W\geq
k]\right)$ $\displaystyle=\left(\frac{1}{2^{0}-\Pr[W\geq
0]}\right)+\sum_{k=1}^{\infty}(e^{t}-e^{t(k-1)})\left(\frac{1}{2^{k}-\Pr[W\geq
k]}\right)$
$\displaystyle=0+\sum_{k=1}^{\infty}e^{t(k-1)}(e^{t}-1)\left(\frac{1}{2^{k}}-\Pr[W\geq
k]\right)\geq 0$

∎

By [Mor13] plus some algebra, for any $\epsilon>0$, a sequence of
$O\left(d^{3}+d\ln(\frac{1}{\epsilon})\right)$ Thorp shuffle steps will
produce a permutation on $[2^{d}]$ whose distribution has total variation
distance at most $\epsilon$ away from the uniform distribution. 444While there
exist more efficient switching networks that also permute sets whose sizes are
not powers of two, we use the result of [Mor13] here because it is simple to
work with. In particular, see the results claimed by [Czu15], although we
could not find the full version of that paper.

######  Lemma 6.2 (Random permutations through switching networks).

For any $C$ which is a power of 2, there is an explicit construction of an
$(\epsilon,s)$-wise independent random permutation, using $r=O(s(\log
C)^{4}\log\frac{1}{\epsilon})$ bits. Furthermore, we can evaluate $\sigma(i)$
and $\sigma^{-1}(i)$ in $O(s(\log C)^{4}\log\frac{1}{\epsilon}\log C)$ time.

###### Proof of Lemma 6.2.

Let $k=O(d^{3}+d\ln(1/\epsilon))$ be the constant for which $k$ Thorp shuffle
steps would permute $[C]=[2^{d}]$ within total variation distance of
$\epsilon$ of the uniform distribution over permutations on $[2^{d}]$.

The switching network $\mathcal{N}$ corresponding to the $k$ Thorp shuffle
steps has depth $k$ and uses exactly $kC/2$ gates. Assign each gate a unique
number in $[kC/2]$. Then given a uniformly random bit vector
$x\in\\{0,1\\}^{kC/2}$, we evaluate the switching network by having the gate
numbered $i$ switch its inputs iff $x_{i}=1$. A key property of switching
networks is that one can evaluate their action on a single input by only
evaluating one gate per layer – for this network, only $k$ gates. Reversing
the order in which the layers are applied will produce the inverse of the
original permutation. Thus, one can evaluate $\mathcal{N}(i)$ by reading only
$k$ entries of $x$, and similarly for and $\mathcal{N}^{-1}{i}$.

Now, say the bits of $x$ are the output of a hash function drawn from a
$ks$-wise independent hash family. (For example, using a family of [WC81], let
$h={\left\lceil{\log_{2}{kC/2}}\right\rceil}$, take the family of random
polynomials of degree $ks-1$ inside $\mathbb{F}_{2^{h}}$, and output the least
bit of the output. The polynomial coefficients can be encoded using
$ksh=O(ks\log(C))$ bits, and the polynomials evaluated at any point in
$O(ksh^{2})=O(ks(\log C)^{2})$ time.)

If $\pi$ is a uniformly random permutation on $[C]$, then for all lists of
distinct $h_{1},\ldots,h_{s}$, and all lists of distinct $j_{1},\ldots,j_{s}$,
we have

$\displaystyle\Pr[\bigwedge_{i\in[s]}\pi(h_{i})=j_{i}]=\frac{1}{\prod_{i\in[s]}(C-i+1)}$

Now, let $f:\\{0,1\\}^{kC/2}\times[C]\mapsto[C]^{k}$ be the function which
maps the gate-controlling vector $x\in\\{0,1\\}^{kC/2}$ and an input $a\in[C]$
to the path $b_{1},\ldots,b_{k}$ that $a$ takes through the switching network
$\mathcal{N}$ if its gates are configured according to $x$. The last node of
this path, $f(x,a)_{k}$ is the output of $\mathcal{N}$ given $x$ and $a$. Each
path $P=(a,b_{1},\ldots,b_{k})$ through the switching network corresponds to a
restriction $R_{P}\in\\{0,1,\star\\}^{kC/2}$ which has value $\star$ on gates
not touched by the path, and for each gate traversed by the path assigns
either $0$ or $1$ depending on whether a straight or switched configuration of
the gate is compatible with $P$. Since all paths through the network have
length $k$, $R_{P}$ only sets $k$ coordinates. Now, for each pair
$(a,b)\in[C]^{2}$, let

$\displaystyle\mathcal{F}_{a,b}=\\{R_{P}:P=(a,b_{1},\ldots,b_{k-1},b)\text{ is
a possible path}\\}$

Then, for lists $(h_{1},\ldots,h_{s})$, $(j_{1},\ldots,j_{s})$, define

$\displaystyle\mathcal{K}_{h_{1},\ldots,h_{s},j_{1},\ldots,j_{s}}=\\{R\in\\{0,1,\star\\}^{kC/2}:\forall
i\in[k],\exists T\in\mathcal{F}_{h_{i},j_{i}}\text{where $R$ is a minimal
refinement of $T$}\\}\,,$

i.e., the set of minimal restrictions for vectors in $\\{0,1\\}^{kC/2}$ which
completely determine the paths through the switching network of inputs
$(h_{1},\ldots,h_{s})$.

Now, let $Y\in\\{0,1\\}^{kC/2}$ be $ks$-wise independent, and
$X\in\\{0,1\\}^{kC/2}$ be fully independent. We have:

$\displaystyle\Pr[\bigwedge_{i\in[s]}f(Y,h_{i})_{k}=j_{i}]$
$\displaystyle=\sum_{R\in\mathcal{K}_{h_{1},\ldots,h_{s},j_{1},\ldots,j_{s}}}\Pr[Y\text{
compatible with $R$}]$
$\displaystyle=\sum_{R\in\mathcal{K}_{h_{1},\ldots,h_{s},j_{1},\ldots,j_{s}}}\Pr[X\text{
compatible with $R$}]$
$\displaystyle=\Pr[\bigwedge_{i\in[s]}f(X,h_{i})_{k}=j_{i}]$

where the second inequality follows because each restriction
$R\in\mathcal{K}_{h_{1},\ldots,h_{s},j_{1},\ldots,j_{s}}$ only constrains
$sk/2$ coordinates corresponding to the gates on the paths in the switching
network from $h_{1},\ldots,h_{s}$ to $j_{1},\ldots,j_{s}$ that it fixes.

Thus,

$\displaystyle\frac{1}{2}\sum_{\text{distinct $b_{1},\ldots,b_{k}$ in
$[C]$,}}\left|\Pr\left[\bigwedge_{i\in[s]}\\{f(X,h_{i})_{k}=j_{i}\\}\right]-\frac{1}{\prod_{i\in[s]}(C-i+1)}\right|=$
$\displaystyle\frac{1}{2}\sum_{\text{distinct $b_{1},\ldots,b_{k}$ in
$[C]$,}}\left|\Pr\left[\bigwedge_{i\in[s]}\\{f(Y,h_{i})_{k}=j_{i}\\}\right]-\frac{1}{\prod_{i\in[s]}(C-i+1)}\right|\leq\epsilon$

which proves that the switching network evaluated on $X$ produces outputs that
are $(\epsilon,s)$-wise independent. ∎

##  7 Regarding implementation

Several of the algorithms in this paper rely on the availability of oracle
randomness (i.e, having a long read only random string) in order to avoid the
space penalty of explicitly storing many independent random permutations. In
practice (where we assume cryptographic pseudo-random number generators
exist), it is straightforward to generate the bits of the oracle random string
on demand, ensuring that computationally bounded systems essentially cannot
produce hard inputs for the algorithm.

The randomized algorithms Algorithm 3 and Algorithm 8 both use the same idea
of trying and discarding (making unavailable for future use), either
immediately or periodically, a set of fresh colors chosen by iterating over a
random permutation. This construction has the downside that, since many colors
are discarded, the total number $C$ of colors in the algorithm might use must
be large. Instead of discarding colors, a possibly more efficient approach is
to retain, for each vertex, a pool of all the colors that were tried but not
used; this ensures that colors are only removed from consideration when they
have been used. The downside of retaining unused colors is an increased space
usage that is harder to prove upper bounds for. For the following two
algorithms, Algorithm 12 and Algorithm 13, for one-sided vertex arrival, and
edge arrival streams, we conjecture that they require $\widetilde{O}(n)$ and
$\widetilde{O}(n\sqrt{\Delta})$ bits of space with high probability, but have
not been able to prove this. The second algorithm in particular is rather
similar to an online edge coloring algorithm conjectured to use
$\Delta+O(\sqrt{\Delta}\log n)$ colors by [BMN92], in which each edge is
assigned a uniformly random color from the set of colors that no edges
incident to its endpoints have used.

Algorithm 12 A simple randomized algorithm for $(2\Delta-1)$-edge coloring in
the one-sided vertex arrival model which is conjectured to use
$O(n\log\Delta)$ space w.h.p.; and uses $\widetilde{O}(n\Delta)$ oracle random
bits

1:Input: Stream of one-sided vertex arrivals on $n$-vertex graph $G=(A\sqcup
B)$.

2:Let $C:=2\Delta-1$.

3:

4:Initialize():

5:for $z\in B$ do

6: $\sigma_{z}\leftarrow$ uniformly randomly chosen permutation over $[C]$

7: $h_{z}\leftarrow 1$

8: $F_{z}\leftarrow\emptyset$

9:

10:Process(vertex $a\in A$, adjacent edges $M_{a}$)

11:$S\leftarrow\emptyset$

12:for $\\{a,b\\}\in M_{a}$, in random order do

13: while $F_{b}\subseteq S$ do

14: $F_{b}\leftarrow F_{b}\cup\sigma_{b}[h_{b}]$

15: $h_{b}\leftarrow h_{b}+1$

16: Let $c$ be random color from $F_{b}\setminus S$

17: Assign color $c$ to edge $\\{a,b\\}$

18: $F_{b}\leftarrow F_{b}\setminus\\{c\\}$

19: $S\leftarrow S\cup\\{c\\}$

Algorithm 13 A simple randomized algorithm for $(2\Delta-1)$-edge coloring in
the edge arrival model which is conjectured to use
$O(n\sqrt{\Delta}\log\Delta)$ space w.h.p.; and uses $\widetilde{O}(n\Delta)$
oracle random bits

1:Input: Stream of edge arrivals on $n$-vertex graph $G=(V,E)$.

2:Let $C:=2\Delta-1$.

3:

4:Initialize:

5:for $v\in B$ do

6: $\sigma_{v}\leftarrow$ uniformly randomly chosen permutation over $[C]$

7: $h_{v}\leftarrow 1$

8: $F_{v}\leftarrow\emptyset$

9:

10:Process(edge $\\{x,y\\}$):

11:while $F_{x}\cap F_{y}=\emptyset$ do

12: $F_{x}\leftarrow F_{x}\cup\sigma_{x}[h_{y}]$

13: $h_{x}\leftarrow h_{x}+1$

14: $F_{y}\leftarrow F_{y}\cup\sigma_{y}[h_{y}]$

15: $h_{y}\leftarrow h_{y}+1$

16:Let $c$ be random color from $F_{x}\cap F_{y}$

17:Assign color $c$ to edge $\\{x,y\\}$

18:$F_{x}\leftarrow F_{x}\setminus\\{c\\}$

19:$F_{y}\leftarrow F_{y}\setminus\\{c\\}$

20:$S\leftarrow\emptyset$

## References

  * [AL12] Noga Alon and Shachar Lovett.  Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions.  In Proc. 16th International Workshop on Randomization and Approximation Techniques in Computer Science, pages 350–361. Springer, 2012\.
  * [AMSZ03] Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, and An Zhu.  Switch scheduling via randomized edge coloring.  In 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2003,, pages 502–512. IEEE, 2003.
  * [ASZZ22] Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh.  Simple Streaming Algorithms for Edge Coloring.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms (ESA 2022), volume 244 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:4, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [BDH+19] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh.  Streaming and massively parallel algorithms for edge coloring.  In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 15:1–15:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019\.
  * [BGW21] Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc.  Online edge coloring algorithms via the nibble method.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2830–2842. SIAM, 2021.
  * [BJWY20] Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev.  A framework for adversarially robust streaming algorithms.  In Proc. 39th ACM Symposium on Principles of Database Systems, page 63–80, 2020.
  * [BMM12] Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani.  Online graph edge-coloring in the random-order arrival model.  Theory of Computing, 8(1):567–595, 2012.
  * [BMN92] Amotz Bar-Noy, Rajeev Motwani, and Joseph Naor.  The greedy algorithm is optimal for on-line edge coloring.  Information Processing Letters, 44(5):251–253, 1992.
  * [BS23] Soheil Behnezhad and Mohammad Saneian.  Streaming edge coloring with asymptotically optimal colors.  arXiv preprint arXiv:2305.01714, 2023.
  * [CL21] Moses Charikar and Paul Liu.  Improved algorithms for edge colouring in the W-streaming model.  In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11-12, 2021, pages 181–183. SIAM, 2021.
  * [CMZ23] Shiri Chechik, Doron Mukhtar, and Tianyi Zhang.  Streaming edge coloring with subquadratic palette size.  arXiv preprint arXiv:2305.07090, 2023.
  * [CPW19] Ilan Reuven Cohen, Binghui Peng, and David Wajc.  Tight bounds for online edge coloring.  In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1–25. IEEE Computer Society, 2019.
  * [Czu15] Artur Czumaj.  Random permutations using switching networks.  In Proc. 47th Annual ACM Symposium on the Theory of Computing, pages 703–712, 2015.
  * [DEMR10] Camil Demetrescu, Bruno Escoffier, Gabriel Moruz, and Andrea Ribichini.  Adapting parallel algorithms to the w-stream model, with applications to graph problems.  Theoretical Computer Science, 411(44):3994–4004, 2010.
  * [DFR06] Camil Demetrescu, Irene Finocchi, and Andrea Ribichini.  Trading off space for passes in graph streaming problems.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pages 714–723. ACM Press, 2006.
  * [EFKM10] Martin R. Ehmsen, Lene M. Favrholdt, Jens S. Kohrt, and Rodica Mihai.  Comparing first-fit and next-fit for online edge coloring.  Theor. Comput. Sci., 411(16-18):1734–1741, 2010.
  * [EJ01] Thomas Erlebach and Klaus Jansen.  The complexity of path coloring and call scheduling.  Theoretical Computer Science, 255(1):33–50, 2001.
  * [FM18] Lene M. Favrholdt and Jesper W. Mikkelsen.  Online edge coloring of paths and trees with a fixed number of colors.  Acta Informatica, 55(1):57–80, 2018.
  * [FN03] Lene M. Favrholdt and Morten N. Nielsen.  On-line edge-coloring with a fixed number of colors.  Algorithmica, 35(2):176–191, 2003.
  * [GDP05] S. Gandham, M. Dawande, and R. Prakash.  Link scheduling in sensor networks: distributed edge coloring revisited.  In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., volume 4, pages 2492–2501 vol. 4, 2005\.
  * [GSS22] Christian Glazik, Jan Schiemann, and Anand Srivastav.  A one pass streaming algorithm for finding euler tours.  Theory of Computing Systems, pages 1–23, 12 2022.
  * [Hol81] Ian Holyer.  The np-completeness of edge-coloring.  SIAM Journal on Computing, 10(4):718–720, 1981.
  * [JP83] Kumar Joag-Dev and Frank Proschan.  Negative association of random variables, with applications.  Ann. Stat., 11(1):286–295, 1983.
  * [JURdW16] Tiago Januario, Sebastián Urrutia, Celso C. Ribeiro, and Dominique de. Werra.  Edge coloring: A natural model for sports scheduling.  European Journal of Operational Research, 254(1):1–8, 2016.
  * [KLS+22] Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, and Jakub Tarnawski.  Online edge coloring via tree recurrences and correlation decay.  In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 104–116. ACM, 2022.
  * [LS11] Luigi Laura and Federico Santaroni.  Computing strongly connected components in the streaming model.  In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems, pages 193–205. Springer Berlin Heidelberg, 2011.
  * [MG92] Jayadev Misra and David Gries.  A constructive proof of vizing’s theorem.  Information Processing Letters, 41(3):131–133, 1992.
  * [Mik15] Jesper W. Mikkelsen.  Optimal online edge coloring of planar graphs with advice.  In Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings, volume 9079 of Lecture Notes in Computer Science, pages 352–364. Springer, 2015.
  * [Mik16] Jesper W. Mikkelsen.  Randomization can be as helpful as a glimpse of the future in online computation.  In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 39:1–39:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [Mor13] Ben Morris.  Improved mixing time bounds for the thorp shuffle.  Combinatorics, Probability and Computing, 22(1):118–132, 2013.
  * [NSW23] Joseph Naor, Aravind Srinivasan, and David Wajc.  Online dependent rounding schemes.  CoRR, abs/2301.08680, 2023.
  * [RU94] Prabhakar Raghavan and Eli Upfal.  Efficient routing in all-optical networks.  In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC), pages 134–143, 1994.
  * [Sha49] Claude E. Shannon.  A theorem on coloring the lines of a network.  Journal of Mathematics and Physics, 28(1-4):148–152, 1949.
  * [SS96] Michael Sipser and Daniel A. Spielman.  Expander codes.  IEEE Transactions on Information Theory, 42(6):1710–1722, 1996\.
  * [SW21] Amin Saberi and David Wajc.  The greedy algorithm is not optimal for on-line edge coloring.  In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 109:1–109:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [Viz64] V. G. Vizing.  On an estimate of the chromatic class of a p-graph.  Discret Analiz, 3:25–30, 1964.
  * [WC81] Mark N. Wegman and Larry Carter.  New hash functions and their use in authentication and set equality.  J. Comput. Syst. Sci., 22(3):265–279, 1981.