# How Can Context Help?
Exploring Joint Retrieval of Passage and Personalized Context

Hui Wan
IBM Research AI
<EMAIL_ADDRESS>
Hongkang Li
Rensselaer Polytechnic Institute
<EMAIL_ADDRESS>
Songtao Lu
IBM Research AI
<EMAIL_ADDRESS>
Xiaodong Cui
IBM Research AI
<EMAIL_ADDRESS>
Marina Danilevsky
IBM Research AI
<EMAIL_ADDRESS>

###### Abstract

The integration of external personalized context information into document-
grounded conversational systems has significant potential business value, but
has not been well-studied. Motivated by the concept of personalized context-
aware document-grounded conversational systems, we introduce the task of
context-aware passage retrieval. We also construct a dataset specifically
curated for this purpose. We describe multiple baseline systems to address
this task, and propose a novel approach, Personalized Context-Aware Search
(PCAS), that effectively harnesses contextual information during passage
retrieval. Experimental evaluations conducted on multiple popular dense
retrieval systems demonstrate that our proposed approach not only outperforms
the baselines in retrieving the most relevant passage but also excels at
identifying the pertinent context among all the available contexts. We
envision that our contributions will serve as a catalyst for inspiring future
research endeavors in this promising direction.

##  1 Introduction

With the recent developments in AI, the world has witnessed an eruption of
chatbots deployed with LLMs (large language models), such as ChatGPT, BARD
Cohen et al. (2022), BlenderBot Shuster et al. (2022b), which often generate
texts indistinguishable from human fluency. However, chatbots powered by
parameter-based LLMs are known to generate factually incorrect statements - a
problem regardless of the model size Shuster et al. (2021). By leveraging an
external corpus of knowledge, retrieval augmented systems Dinan et al. (2018);
Lewis et al. (2020); Karpukhin et al. (2020), including document-grounded
dialogue systems Roller et al. (2020); Shuster et al. (2022b, a); Cohen et al.
(2022), have demonstrated several advantages compared to pure parameter-based
systems. For instance, grounding responses on external knowledge bases have
been shown to reduce hallucinations across a variety of retrieval systems and
model architectures Shuster et al. (2021).

A document-grounded conversational system, particularly in the enterprise
setting, is likely to have access to a significant amount of contextual
information, whether as a knowledge base or a library of API calls. This
context may be temporal, such as the current date and time, or recent events;
or it may be user-specific, such as information about the user’s account,
profile, recent transactions, activity logs, etc. Without any such context, a
user’s question such as, "Am I eligible for this rebate?" would receive the
generic answer "You may be eligible for this rebate depending on where you
live," grounded only on the relevant documents. If the right context were also
retrieved and made available, the response could be instantly elevated to
"Yes, you are eligible since you live in Singapore." Furthermore, retrieving
the correct context information may serve to better understand the user’s
intent, and therefore improve the likelihood of identifying the correct
grounding document to use.

The significant challenge of choosing which context to retrieve has great
potential business value, but has not been well-studied. Including too much
contextual information may result in too much noise to the generation step, or
exceeding the LLM’s allowed input size. Including irrelevant contextual
information may degrade the generated response. Our motivating question can
thus be posed as follows: Given a user query (which itself may be
underspecified), a document collection, and a set of available contexts, how
can a document-grounded conversational system retrieve a good subset of
contexts to help answer the query, and can this process also help in
retrieving the most relevant grounding document(s)?

To this end, we propose a new task of personalized context-aware passage
retrieval for document-grounded dialogue, and create a dataset, ORCA-ShARC,
for this setting. We provide several baseline approaches, as well as develop a
novel approach, Personalized Context-Aware Search (PCAS), to address the task.

In order to showcase the efficacy of PCAS, we conduct extensive experiments on
multiple well-known retrieval systems. The results illustrate that PCAS not
only surpasses the baselines in retrieving the most relevant passage but also
excels in identifying the pertinent context. We hope that our advancements in
joint context-passage retrieval will serve as a catalyst, motivating future
research endeavors in this highly promising field.

##  2 Context-and-Passage Retrieval

We now formally define the task of context-passage retrieval, which involves
not only retrieving the relevant document from the external knowledge base,
but also selecting the relevant piece of context from all the available
contexts.

Formally, when a user $u$ engages in a conversation with the system, in
addition to the static document corpus $\mathcal{D}$, all the available
personalized context information $\mathcal{C}^{u}$ are accessible to the
system. There is also the conversation history composed of utterances that
have already occurred in this session between the user and the system:
$H=\\{r_{1}:X_{1},...,r_{i}:X_{i},...\\}$ where $r_{i}$ is the speaker role,
and $X_{i}$ is the utterances at the $i$-th turn, respectively. Since the
focus of our work is in context-passage retrieval rather than the conversation
history, in the rest of the paper, we simply consider a single turn user query
$q$ rather than $H$.

Given the input of a user query $q$, the task is to select 1) the most
relevant latent document $d$ from $\mathcal{D}$; and 2) the most relevant
latent context $c$ from $\mathcal{C}^{u}$, to help the system generate a good
response.

To evaluate the retrieved documents and context, we use standard retrieval
metrics, including binary rank-aware metrics MAP (mean average precision) and
decision support metrics Recall@$K$.

##  3 The ORCA-ShARC Dataset

To the best of our knowledge, there is no existing open-retrieval content-
grounded dialogue or QA datasets where each document-grounded example is
annotated with a set of context. To this end, we curate a dataset for the
proposed task in Section 2.

ShARC Saeidi et al. (2018) is a conversational QA dataset focusing on question
answering from given text and one piece of given context (scenario). OR-ShARC
Gao et al. (2021) is adapted from the ShARC dataset to an open-retrieval
setting, where the task is to retrieve the relevant text snippet from the
whole corpus. In OR-ShARC, each example is given one piece of relevant context
(scenario).

We create a dataset, ORCA-ShARC (Open-Retrieval Context-Aware ShARC), by
converting the OR-ShARC dataset into our task setting, where a set of contexts
is provided for each example. To create the set, we use the example’s original
relevant context, and expand the set by randomly sampling from all the
contexts appearing in the OR-ShARC dataset, as long as there is no
contradiction between contexts introduced (as judged by prompting FLAN_T5_3B
model Chung et al. (2022)). We include 10 pieces of context for each
example.111As the size of the context set grows, it naturally becomes harder
to add context without contradictions. A few examples could only support 6-9
pieces of context. Table 1 summarizes the statistics of the ORCA-ShARC dataset
and Table 2 provides an example.

# Documents (Rule Text Snippets) | 651
---|---
# Avg. Document Length | 38.5
# Avg. Pieces of Context | 9.94
# Training Examples | 17936
# Validation Examples | 1105
# Test Examples | 2373
Table 1: Summary statistics of ORCA-ShARC. Source URL |  https://www.gov.uk/winter-fuel-payment/eligibility
---|---
Scenario Set |  …
|  I am and have been an eligible veteran.
|  I live in the Swiss Alps.
|  I’m trying to export some boots.
|  …
Question |  Can I get Winter Fuel Payment?
Gold Snippet |  …you might still get the payment if both the following apply: * you live in Switzerland or a European Economic Area (EEA) country…
Gold Scenario |  I live in the Swiss Alps.
Table 2: An example from ORCA-ShARC. Note how the Scenario Set is expanded
from the one piece of gold Scenario originally annotated in OR-ShARC.

##  4 Approach

We compare our approach with three baselines, and use some of the most popular
neural retrieval systems to address the context-and-passage retrieval task on
the newly constructed dataset.

###  4.1 Baselines

We design and implement several baselines for the task. The approaches are
independent of the underlying retrieval systems. We use $score_{dq}(d,q)$,
$score_{cq}(c,q)$ and $score_{cd}(c,d)$ to represent the scores from the
retrievers to model the pairwise relevance of document $d$, query $q$, and
context $c$.

OR

{question + original relevant context} $\xrightarrow{}$ document: For
clarification, this is an experiment on the original OR-ShARC dataset as a
reference rather than a baseline. Knowing the original relevant context, the
passage retrieval task in OR-ShARC is easier than our task. In this
experiment, the original context is concatenated with the user question,
forming a new query $q^{\textrm{OR}}$ to retrieve documents based on
$score_{dq}(d,q^{\textrm{OR}})$.

B1

{question + all contexts} $\xrightarrow{}$ document: A baseline that
concatenates the user question together with all available contexts to form a
new query $q^{\textrm{B1}}$ and retrieve documents based on
$score_{dq}(d,q^{\textrm{B1}})$.

B2

question $\xrightarrow{}$ document; document $\xrightarrow{}$ context: A
baseline that uses the user question to retrieve documents based on
$score_{dq}(d,q)$, then uses the top predicted documents to select contexts
based on $score_{cd}(c,d)$.

B3

question $\xrightarrow{}$ context; {question + predicted context}
$\xrightarrow{}$ document: A baseline that uses the user question to select
contexts based on $score_{cq}(c,q)$, then concatenates the user question with
the top-1 predicted context to form a new query $q^{\textrm{B3}}$ and
retrieves documents based on $score_{dq}(d,q^{\textrm{B3}})$.

###  4.2 PCAS Approach

We propose a novel approach, PCAS, that jointly predicts the document and the
context as a pair, based on the relevance of the document to both the query
and the context.

First, we use the user question $q$ to retrieve the top $K$ document
candidates based on $score_{dq}(d,q)$. Then, for each document $d$, we select
the context that is most relevant to it based on $score_{dc}(d,c)$. Last but
not least, a convex combination score
$\lambda*score_{dq}(d,q)+(1-\lambda)*score_{dc}(d,c)$ is used to select the
most relevant pair $(d,c)$ where $0<\lambda<1$. The underlying intuition is as
follows: the user question might not contain sufficient information for the
system to understand the intent and retrieve the gold document. However, the
system will partially know the intent, and has a good chance of including the
best document in the top-$K$ list. Matching the top-$K$ documents with the
user’s actual situation, which is captured in the contexts, will greatly help
decipher the user’s true intent and retrieve the gold document.

##  5 Experimental Results

We evaluate the baselines and PCAS in a $0$-shot context-and-passage retrieval
task on the ORCA-ShARC dataset. We conduct experiments using several popular
pretrained modern neural retrieval systems including a late-interaction
retrieval model ColBERT Khattab and Zaharia (2020); Santhanam et al. (2021),
single-vector retrieval models DPR Karpukhin et al. (2020), ANCE Xiong et al.
(2021a) and Sentence BERT (S-BERT) Reimers and Gurevych (2019) with
DistilBERT-TAS-B model Sanh et al. (2019); Hofstätter et al. (2021) .

For ColBERT, we adapt the code from the ColBERT repository
222https://github.com/stanford-futuredata/ColBERT. From the BEIR Thakur et al.
(2021) repository333https://github.com/beir-cellar/beir, we get the pretrained
model names, as well as the code for the other dense retrieval systems. We use
the py_trec toolVan Gysel and de Rijke (2018)
444https://github.com/cvangysel/pytrec_eval for evaluation.

In Table 3, we present the document retrieval results and the context
selection results (limited to the approaches that predict the context: B2, B3
and PCAS). For the same approach, the results largely varies across the
retrievers, due to the distinct models and different pre-training data and
processes. For example, DPR results are on the low side, especially for B3
document metrics, because it involves two chained retrieval steps that amplify
this effect. B1 yields the lowest accuracy across the board, mainly due to the
noise introduced by including all the contexts without discrimination.
Importantly, we observe that when the original relevant context is unknown,
our proposed PCAS approach achieves better retrieval results than all
baselines, which indicates that jointly considering the documents and contexts
can improve the performances of both document and context retrieval. Note that
the PCAS results are close to the OR experiment in which the original relevant
context is given. This suggests that PCAS can identify the relevant and
important contexts for the query, with no need for users to specify any
contexts. Furthermore, the comparison between B2 and B3 illustrates that the
retrieval process of $q\rightarrow d\rightarrow c$ is better than
$q\rightarrow c\rightarrow d$ , which supports the motivation of our PCAS
design.

| documents | contexts
---|---|---
Methods | R@1 | R@5 | M@5 | R@1
OR | 60.81 | 84.25 | 70.52 | NA
ColBERT | B1 | 34.93 | 59.82 | 44.47 | NA
B2 | 55.57 | 90.77 | 70.30 | 27.24
B3 | 52.85 | 78.01 | 62.34 | 20.90
PCAS | 59.19 | 90.77 | 71.78 | 25.79
OR | 31.58 | 54.93 | 40.78 | NA
DPR | B1 | 14.84 | 35.66 | 22.24 | NA
B2 | 28.96 | 51.67 | 38.38 | 32.13
B3 | 18.91 | 38.73 | 25.94 | 31.58
PCAS | 30.04 | 56.02 | 38.81 | 32.49
OR | 58.37 | 84.52 | 68.69 | NA
ANCE | B1 | 41.18 | 73.85 | 53.01 | NA
B2 | 44.98 | 77.29 | 55.35 | 37.74
B3 | 42.53 | 75.48 | 55.46 | 31.04
PCAS | 52.85 | 83.26 | 65.71 | 41.36
OR | 68.15 | 91.40 | 77.55 | NA
S-BERT | B1 | 45.43 | 75.84 | 57.00 | NA
B2 | 55.57 | 91.04 | 68.57 | 39.01
B3 | 53.30 | 82.26 | 63.53 | 23.44
PCAS | 63.53 | 91.04 | 74.28 | 42.80
Table 3: Evaluation for document retrieval (first three columns) and context
retrieval (last column) on the ORCA-ShARC validation set. R@K denotes Recall@K
scores. M@5 denotes MAP@5 scores. NA means that this approach does not
retrieve context.

##  6 Related Work

Our proposed task is different from the work on context-aware QA Seonwoo et
al. (2020); Taunk et al. (2023) in which QA is done on a given document and no
retrieval is involved. On the other hand, context-aware QA can be considered
as the next step following our task.

Our work is closely related to the work on contextual information retrieval
MERROUNI et al. (2019). The major difference from our work is that the tasks
in this line of work do not involve selecting of relevant context. The form of
context being used is structured and in a few pre-defined genres, whereas we
leverage a set of unstructured contexts. There is also no joint relevance
modeling of both context and content with respect to the query. Our task and
approach is also different from contextual recommendation systems (on which
Tourani et al. (2023) recently presents their work), which does not involve
user questions or queries.

Our proposed data and task are also related to open domain question answering
(Kwiatkowski et al., 2019; Lewis et al., 2020; Min et al., 2020; Qu et al.,
2020; Izacard and Grave, 2021; Li et al., 2021; Xiong et al., 2021b; Yu et
al., 2021), open-retrieval conversational QA (Qu et al., 2020; Gao et al.,
2021), and open-retrieval document-grounded dialogues Feng et al. (2021).
However, none of these datasets and tasks include external context
information. The lone exception is OR-SHARC, which provides one relevant
context for each example and does not involve any selection of relevant
context from a larger set.

Finally, our work is related to Multi-Session Chat (MSC) Qian et al. (2021), a
dataset consisting of multiple chat sessions, created for studying how to
utilize information outside of the current conversation session. Similarly, Xu
et al. (2022) recently leveraged retrieval-augmented methods to select useful
contexts from previous chat sessions. However, the datasets in both works are
not document-grounded, and retrieving documents jointly with contextual
information is not explored.

##  7 Conclusion

This work proposes the task of context-aware passage retrieval and creates a
dataset based on OR-ShARC. We also present a novel approach for integrating
external context information into the retrieval aspect of document-grounded
conversational systems. The proposed PCAS method effectively combines both the
document-query relevance and contextual relevance. We conduct experimental
evaluations on popular retrieval systems, including ColBERT, DPR, ANCE, and
S-BERT. The results demonstrate that incorporating external context
information through PCAS brings significant improvement on passage retrieval
and achieves higher MAP and Recall@$K$ than baseline models.

The proposed retrieval paradigm opens up avenues for future research and
extensions. Several potential directions include extending the PCAS method to
the training process, integrating downstream modules such as response
generation, and creating real-world context datasets with the inclusion of
human feedback. These topics offer promising directions for the community to
explore and advance the field further.

## Limitations

Although the motivation for our work is to improve the quality of conversation
systems that could be grounded on both document content and contextual
information, in this work we focus exclusively on the task of retrieving the
content and context. We do not evaluate the resulting generative responses to
the user query, which is the actual final desired outcome, though we are
working on doing so in the near future.

There are no publicly available datasets that are suited to the context-aware
passage retrieval task. To the best of our knowledge, some of the related
datasets do not have a passage retrieval setting, the rest of them either do
not have annotated context set, or have a few limited genre contexts which
does not serve our motivation with rich context from various business
applications. This leads us to create a dataset by ourselves. Experimenting on
only one dataset may limit the more generalizable conclusions we can draw.

The size of the context set that we construct is limited. In a realistic
setting, it is likely that the number of available contexts is much greater,
and more heterogeneous in nature rather than the short unstructured text
available from the OR-ShARC dataset. More work is needed to discover how our
approach scales to these settings.

## Ethics Statement

To the best of our knowledge, we have not identified any immediate ethical
concerns or negative societal consequences arising from this work, in
accordance with the ACL ethics policy. The dataset we created does not involve
generating any data with LLMs, hence does not impose any risk of non-factual
or harmful content.

We hope our work may serve as an inspiration for the community to utilize the
newly created dataset and further enhance retrieval performance. In the
future, it may be necessary to tread carefully when incorporating user context
in a real-world setting, for example to not cause consternation about how much
a system may know about a given user.

## Acknowledgements

This work was partly supported by the Rensselaer-IBM AI Research Collaboration
(http://airc.rpi.edu), part of the IBM AI Horizons Network
(http://ibm.biz/AIHorizons).

## References

  * Chung et al. (2022) Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei. 2022.  Scaling instruction-finetuned language models.
  * Cohen et al. (2022) Aaron Daniel Cohen, Adam Roberts, Alejandra Molina, Alena Butryna, Alicia Jin, Apoorv Kulshreshtha, Ben Hutchinson, Ben Zevenbergen, Blaise Hilary Aguera-Arcas, Chung ching Chang, Claire Cui, Cosmo Du, Daniel De Freitas Adiwardana, Dehao Chen, Dmitry (Dima) Lepikhin, Ed H. Chi, Erin Hoffman-John, Heng-Tze Cheng, Hongrae Lee, Igor Krivokon, James Qin, Jamie Hall, Joe Fenton, Johnny Soraker, Kathy Meier-Hellstern, Kristen Olson, Lora Mois Aroyo, Maarten Paul Bosma, Marc Joseph Pickett, Marcelo Amorim Menegali, Marian Croak, Mark Díaz, Matthew Lamm, Maxim Krikun, Meredith Ringel Morris, Noam Shazeer, Quoc V. Le, Rachel Bernstein, Ravi Rajakumar, Ray Kurzweil, Romal Thoppilan, Steven Zheng, Taylor Bos, Toju Duke, Tulsee Doshi, Vincent Y. Zhao, Vinodkumar Prabhakaran, Will Rusch, YaGuang Li, Yanping Huang, Yanqi Zhou, Yuanzhong Xu, and Zhifeng Chen. 2022.  Lamda: Language models for dialog applications.  In _arXiv_.
  * Dinan et al. (2018) Emily Dinan, Stephen Roller, Kurt Shuster, Angela Fan, Michael Auli, and Jason Weston. 2018.  Wizard of wikipedia: Knowledge-powered conversational agents.  In _International Conference on Learning Representations_.
  * Feng et al. (2021) Song Feng, Siva Sankalp Patel, Hui Wan, and Sachindra Joshi. 2021.  MultiDoc2Dial: Modeling dialogues grounded in multiple documents.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 6162–6176, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Gao et al. (2021) Yifan Gao, Jingjing Li, Chien-Sheng Wu, Michael R. Lyu, and Irwin King. 2021.  Open-retrieval conversational machine reading.
  * Hofstätter et al. (2021) Sebastian Hofstätter, Sheng-Chieh Lin, Jheng-Hong Yang, Jimmy Lin, and Allan Hanbury. 2021.  Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling.  In _Proc. of SIGIR_.
  * Izacard and Grave (2021) Gautier Izacard and Edouard Grave. 2021.  Distilling knowledge from reader to retriever for question answering.  In _International Conference on Learning Representations_.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Khattab and Zaharia (2020) Omar Khattab and Matei Zaharia. 2020.  Colbert: Efficient and effective passage search via contextualized late interaction over bert.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 39–48.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019.  Natural questions: A benchmark for question answering research.  _Transactions of the Association for Computational Linguistics_ , 7:452–466.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 9459–9474. Curran Associates, Inc.
  * Li et al. (2021) Yongqi Li, Wenjie Li, and Liqiang Nie. 2021.  A graph-guided multi-round retrieval method for conversational open-domain question answering.  _arXiv preprint arXiv:2104.08443_.
  * MERROUNI et al. (2019) Zakariae ALAMI MERROUNI, Bouchra FRIKH, and Brahim OUHBI. 2019.  Toward contextual information retrieval: A review and trends.  _Procedia Computer Science_ , 148:191–200.  The Second International Conference on Intelligent Computing in Data Sciences, ICDS2018.
  * Min et al. (2020) Sewon Min, Julian Michael, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2020.  AmbigQA: Answering ambiguous open-domain questions.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 5783–5797, Online. Association for Computational Linguistics.
  * Qian et al. (2021) Hongjin Qian, Zhicheng Dou, Yutao Zhu, Yueyuan Ma, and Ji-Rong Wen. 2021.  Learning implicit user profile for personalized retrieval-based chatbot.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 1467–1477.
  * Qu et al. (2020) Chen Qu, Liu Yang, Cen Chen, Minghui Qiu, W Bruce Croft, and Mohit Iyyer. 2020.  Open-retrieval conversational question answering.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 539–548.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-bert: Sentence embeddings using siamese bert-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics.
  * Roller et al. (2020) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Kurt Shuster, Eric M. Smith, Y-Lan Boureau, and Jason Weston. 2020.  Recipes for building an open-domain chatbot.
  * Saeidi et al. (2018) Marzieh Saeidi, Max Bartolo, Patrick Lewis, Sameer Singh, Tim Rocktäschel, Mike Sheldon, Guillaume Bouchard, and Sebastian Riedel. 2018.  Interpretation of natural language rules in conversational machine reading.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2087–2097, Brussels, Belgium. Association for Computational Linguistics.
  * Sanh et al. (2019) Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019.  Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter.  In _NeurIPS $EMC^{2}$ Workshop_.
  * Santhanam et al. (2021) Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. 2021.  Colbertv2: Effective and efficient retrieval via lightweight late interaction.
  * Seonwoo et al. (2020) Yeon Seonwoo, Ji-Hoon Kim, Jung-Woo Ha, and Alice Oh. 2020.  Context-aware answer extraction in question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2418–2428.
  * Shuster et al. (2022a) Kurt Shuster, Mojtaba Komeili, Leonard Adolphs, Stephen Roller, Arthur Szlam, and Jason Weston. 2022a.  Language models that seek for knowledge: Modular search & generation for dialogue and prompt completion.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 373–393, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Shuster et al. (2021) Kurt Shuster, Spencer Poff, Moya Chen, Douwe Kiela, and Jason Weston. 2021.  Retrieval augmentation reduces hallucination in conversation.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 3784–3803, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Shuster et al. (2022b) Kurt Shuster, Jing Xu, Mojtaba Komeili, Da Ju, Eric Michael Smith, Stephen Roller, Megan Ung, Moya Chen, Kushal Arora, Joshua Lane, Morteza Behrooz, William Ngan, Spencer Poff, Naman Goyal, Arthur Szlam, Y-Lan Boureau, Melanie Kambadur, and Jason Weston. 2022b.  Blenderbot 3: a deployed conversational agent that continually learns to responsibly engage.
  * Taunk et al. (2023) Dhaval Taunk, Lakshya Khanna, Siri Venkata Pavan Kumar Kandru, Vasudeva Varma, Charu Sharma, and Makarand Tapaswi. 2023.  Grapeqa: Graph augmentation and pruning to enhance question-answering.  In _Companion Proceedings of the ACM Web Conference 2023_ , pages 1138–1144.
  * Thakur et al. (2021) Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. 2021.  BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models.  In _Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2)_.
  * Tourani et al. (2023) Ali Tourani, Hossein A. Rahmani, Mohammadmehdi Naghiaei, and Yashar Deldjoo. 2023\.  Capri: Context-aware interpretable point-of-interest recommendation framework.
  * Van Gysel and de Rijke (2018) Christophe Van Gysel and Maarten de Rijke. 2018.  Pytrec_eval: An extremely fast python interface to trec_eval.  In _SIGIR_. ACM.
  * Xiong et al. (2021a) Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021a.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  In _International Conference on Learning Representations_.
  * Xiong et al. (2021b) Wenhan Xiong, Xiang Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Scott Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oguz. 2021b.  Answering complex open-domain questions with multi-hop dense retrieval.  In _International Conference on Learning Representations_.
  * Xu et al. (2022) Jing Xu, Arthur Szlam, and Jason Weston. 2022.  Beyond goldfish memory: Long-term open-domain conversation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 5180–5197, Dublin, Ireland. Association for Computational Linguistics.
  * Yu et al. (2021) Shi Yu, Zhenghao Liu, Chenyan Xiong, Tao Feng, and Zhiyuan Liu. 2021.  Few-shot conversational dense retrieval.  In _International ACM SIGIR Conference_.

##  Appendix A Appendix

###  A.1 Experimental setups

Models Used

We use the models “facebook-dpr-question_encoder-multiset-
base”555https://huggingface.co/facebook/dpr-question_encoder-multiset-base and
“facebook-dpr-ctx_encoder-multiset-
base”666https://huggingface.co/facebook/dpr-ctx_encoder-multiset-base for DPR
Karpukhin et al. (2020), “msmarco-roberta-base-ance-
firstp”777https://huggingface.co/sentence-transformers/msmarco-roberta-base-
ance-firstp for ANCE Xiong et al. (2021a), and “msmarco-distilbert-base-
tas-b”888https://huggingface.co/sentence-transformers/msmarco-distilbert-base-
tas-b Sanh et al. (2019); Hofstätter et al. (2021) for Sentence BERT Reimers
and Gurevych (2019). We use the ColBERT model from Beir website
999https://public.ukp.informatik.tu-
darmstadt.de/thakur/BEIR/models/ColBERT/msmarco.psg.l2.zip.

Hyper-parameters

On the validation set, for DPR, ANCE, and S-BERT, we set $\lambda=0.6$ and
$beam=7,\ 7,\ ,5$ for these three systems, respectively. “$beam$” means the
number of top document candicates retrieved using $score_{dq}(d,q)$ in the
first step of the PCAS approach. Please see Section 4.2 for more details. On
the test set, for DPR, ANCE, and S-BERT, we keep $\lambda=0.6$ and all
$beam$’s equal to $5$. For ColBERT, we set $\lambda=0.55$ and $beam$ to $5$ on
both test set and validation set.

###  A.2 Results on the test set

We present evaluation results for document retrieval on the test set with
systems in Section 4 in Table 4. We notice that the performance of the
baselines are not stable on the test set across different retrievers. For
example, with S-BERT, OR yields much better results than B2, but with ColBERT,
B2 performs much better than OR, whereas the difference between B2 and OR in
document retrieval is whether to concatenate the given "gold" context to the
query. This indicates that there might be noisy data in the test set, and the
characteristic of late interaction in ColBERT might be at a disadvantage in
the test set data. It also explains why B2 outperforms both OR and PCAS with
ColBERT.

| documents | contexts
---|---|---
Methods | R@1 | R@5 | M@5 | R@1
OR | 66.16 | 85.08 | 73.32 | NA
ColBERT | B1 | 39.36 | 60.30 | 47.40 | NA
B2 | 70.50 | 93.30 | 79.09 | 34.77
B3 | 58.49 | 78.85 | 66.49 | 28.87
PCAS | 67.09 | 93.30 | 77.07 | 32.79
OR | 33.21 | 56.38 | 41.70 | NA
DPR | B1 | 17.28 | 33.46 | 22.99 | NA
B2 | 29.25 | 57.10 | 39.31 | 34.13
B3 | 23.30 | 41.93 | 29.89 | 33.59
PCAS | 29.92 | 58.96 | 40.24 | 35.74
OR | 63.55 | 83.52 | 71.20 | NA
ANCE | B1 | 49.73 | 72.19 | 58.08 | NA
B2 | 59.80 | 83.73 | 68.72 | 45.51
B3 | 54.45 | 77.24 | 62.95 | 36.83
PCAS | 59.92 | 83.73 | 68.94 | 45.89
OR | 69.91 | 89.13 | 77.38 | NA
S-BERT | B1 | 47.32 | 75.18 | 57.90 | NA
B2 | 60.94 | 88.50 | 72.42 | 42.98
B3 | 55.29 | 78.13 | 63.85 | 28.70
PCAS | 66.75 | 88.50 | 75.29 | 44.88
Table 4: Evaluation results for document retrieval (first three columns) and
context retrieval (last column) on the ORCA-ShARC test set. R@K denotes
Recall@K scores. M@5 denotes MAP@5 scores. NA (not applicable) means that this
approach does not involve retrieving context.


Northeastern University<EMAIL_ADDRESS>Xuangui Huang [500]Theory of
computation Problems, reductions and completeness Supported by NSF CCF award
1813930.

###### Acknowledgements.

The author thanks Emanuele Viola for helpful discussions.John Q. Open and Joan
R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016
CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Space Hardness of Solving Structured Linear Systems

Xuangui Huang

###### Abstract

We show that if the probabilistic logarithmic-space solver or the
deterministic nearly logarithmic-space solver for undirected Laplacian
matrices can be extended to solve slightly larger subclasses of linear
systems, then they can be use to solve all linear systems with similar space
complexity. Previously Kyng and Zhang [7] proved similar results in the time
complexity setting using reductions between approximate solvers. We prove that
their reductions can be implemented using constant-depth, polynomial-size
threshold circuits.

###### keywords:

linear system solver, logarithmic space, threshold circuit

###### category:

##  1 Introduction

One of the oldest mathematical problems is to solve a linear system, that is
to find a solution $\mathbf{x}$ satisfying $\mathbf{A}\mathbf{x}=\mathbf{b}$
given an $n\times n$ matrix $\mathbf{A}$ and a $n$-dimensional vector
$\mathbf{b}$ as input. In the RealRAM model this can be done in
$O(n^{\omega})$ time, where $\omega\leq 2.3728$ [4] is the matrix
multiplication constant. Much faster algorithms exist for approximately
solving linear systems when $\mathbf{A}$ is the Laplacian of undirected
graphs. Indeed recent breakthroughs showed that it can be done in nearly
linear time [13, 2]. Kyng and Zhang [7] further showed that if such solvers
can be extended to nearly linear time solvers for some classes slightly larger
than undirected Laplacians, we can also solve general linear systems in nearly
linear time.

In this paper we are interested in the space complexity of this problem. For
general linear systems Ta-shma gave a quantum algorithm using logarithmic
space [14]. For undirected Laplacian, Doron et al. showed that it has a
probabilistic logarithmic-space algorithm [3] and hence a deterministic
$O(\log^{3/2}n)$-space algorithm by a well-known space-efficient
derandomization result [12]. This was improved later to $\widetilde{O}(\log
n)$ by Murtagh et al [10].

###  1.1 Our results

We prove a space hardness version of Kyng and Zhang’s results [7], showing
space hardness of approximate linear system solvers for some classes slightly
larger than undirected Laplacians, namely multi-commodity Laplacians, 2D Truss
Stiffness Matrices, and Total Variation Matrices.

######  Theorem 1.1.

Suppose that for multi-commodity Laplacians, 2-D Truss Stiffness Matrices, or
Total Variation Matrices, the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}$
can be approximately solved in (nearly) logarithmic space with logarithmic
dependence on condition number $\kappa$ and accuracy
$\mathrm{\varepsilon}^{-1}$ (even if it only works in expectation or with high
probability), then any linear systems with polynomially bounded integers and
condition number can be solved in (nearly) logarithmic space with high
accuracy (in expectation or with high probability, respectively).

This shows that if the probabilistic logspace solver for undirected Laplacian
in [3], or the deterministic $\widetilde{O}(\log n)$-space one in [10], can be
extended to solve any of these three slightly larger subclasses of linear
systems, we would have a surprising result that all linear systems can be
approximately solved in probabilistic logspace or in deterministic
$\widetilde{O}(\log n)$-space. Pessimistically speaking the theorem means that
it is very hard to get space efficient algorithms for these subclasses, as it
is as difficult as solving all linear systems in a space efficient way. On the
bright side, we actually prove that any progress on solving these subclasses
using less space will immediately translate into similar progress for solving
all linear system using less space.

Kyng and Zhang [7] proved their results via reductions from approximate
solvers of general linear systems to those of three subclasses. In this paper
we prove Theorem 1.1 by proving that their reductions can be carried out in a
space efficient manner. Indeed we prove a much stronger result that their
reductions can be implemented in $\mathsf{TC}^{0}$ circuits, which are
constant-depth polynomial-size unbounded-fan in circuits with
$\mathsf{MAJORITY}$ and $\neg$ gates. It shows that these reductions are
actually highly parallelizable.

We denote $\mathcal{G}$ as the class of all matrices with integer valued
entries. In the context of solving linear systems, an all-zero row or column
can be trivially handled, so we can assume without loss of generality that
matrices in $\mathcal{G}$ has at least one non-zero entry in every row and
column. For 2-commodity matrices $\mathcal{MC}_{2}$, we have two set of
variables $X$ and $Y$ of the same size, and the equations are scalings of
$x_{i}-x_{j}=0$, $y_{i}-y_{j}=0$, and $x_{i}-y_{i}-(x_{j}-y_{j})=0$, where
$x_{i},x_{j}\in X$ and $y_{i},y_{j}\in Y$. This generalizes undirected
Laplacians, as the incidence matrices of undirected Lapacians only have
equations of the form $x_{i}-x_{j}=0$ for $x_{i},x_{j}\in X$.

Our main technical result proves that the reduction from $\mathcal{G}$ to
$\mathcal{MC}_{2}$ in [7] is $\mathsf{TC}^{0}$-computable.

######  Theorem 1.2.

There is a $\mathsf{TC}^{0}$-reduction from approximately solving
$\mathcal{G}$ to approximately solving $\mathcal{MC}_{2}$.

In [7] it is shown that the matrix produced by this reduction is also a 2D
Truss Stiffness Matrix as well as a Total Variation Matrix, therefore Theorem
1.2 also works for these classes. Also note that this reduction is a Karp-
style reduction, i.e. it requires only one linear system solve and uses the
solution in a black-box way. That is why Theorem 1.1 still applies if the
solver only works in expectation or with high probability.

We also show $\mathsf{TC}^{0}$-computability of the reductions in [7] to some
more restrictive subclasses of $\mathcal{MC}_{2}$, including
$\mathcal{MC}^{>}_{2}$, the exact class we have to solve when we use Interior
Point Methods for 2-commodity problems, as explained in the Kyng and Zhang’s
full paper [8]. They also showed that the promise problem of deciding if a
vector is in the image of a matrix or $\mathrm{\varepsilon}$-far from the
image can be directly reduced to approximately solving linear systems.
Combining with the above results, this shows that the promise problem can be
reduced to approximately solving the above-mentioned subclasses in
$\mathsf{TC}^{0}$.

##  2 Simplified reductions in $\mathsf{TC}^{0}$: the easy parts

Throughout this paper we use the sign-magnitude representation to encode a
$w$-bit signed integer $z\in[-2^{w+1}+1,2^{w+1}-1]$ into a sign bit, $0$ for
positive and $1$ for negative, and $w$ bits for $|z|$ in binary. Note that in
this method, $0$ has two representations and we accept both.

For simplicity we first prove the special case for the reduction from exact
solver of $\mathcal{G}$ to exact solver of $\mathcal{MC}_{2}$.

######  Theorem 2.1.

Given an $m\times n$ $w$-bit matrix $\mathbf{A}\in\mathcal{G}$ and a vector
$\mathbf{b}$ as input, we can compute in $\mathsf{TC}^{0}$ an $O(nmw\log
n)\times O(nmw\log n)$ $O(w\log n)$-bit matrix
$\mathbf{A}^{\prime}\in\mathcal{MC}_{2}$ and a vector $\mathbf{b}^{\prime}$
such that:

  * •

$\mathbf{A}\mathbf{x}=\mathbf{b}$ has a solution if and only if
$\mathbf{A}^{\prime}\mathbf{x}^{\prime}=\mathbf{b}^{\prime}$ has a solution;

  * •

if $\mathbf{A}^{\prime}\mathbf{x}^{\prime}=\mathbf{b}^{\prime}$ has a solution
$\mathbf{x}^{\prime}$, then we can compute $\mathbf{x}$ in $\mathsf{TC}^{0}$
from $\mathbf{x}^{\prime}$ so that $\mathbf{A}\mathbf{x}=\mathbf{b}$.

As in [7], this reduction is split into several steps using the following
classes of matrices.

######  Definition 2.2 ([7]).

  * •

Let $\mathcal{G}_{z}\subset\mathcal{G}$ denote the class of matrices with
integer valued entries such that every row has zero row sum;

  * •

Let $\mathcal{G}_{z,2}\subset\mathcal{G}_{z}$ denote the class of matrices
with integer valued entries such that every row has zero row sum, and for each
row the sum of positive coefficients is a power of $2$.

######  Lemma 2.3.

There are $\mathsf{TC}^{0}$-reductions for exact solvers of the following
classes:

  1. (i)

from $\mathcal{G}$ to $\mathcal{G}_{z}$;

  2. (ii)

from $\mathcal{G}_{z}$ to $\mathcal{G}_{z,2}$;

  3. (iii)

from $\mathcal{G}_{z,2}$ to $\mathcal{MC}_{2}$.

Lemma 2.3 (iii) is the main reduction in this paper (same as in [7]), which
will be proved in the next section. In the remaining of this section we prove
Lemma 2.3 (i) and (ii).

#### From $\mathcal{G}$ to $\mathcal{G}_{z}$

######  Proof 2.4 (Proof sketch).

Given a matrix $\mathbf{A}\in\mathcal{G}$, we can define a matrix
$\mathbf{A}^{\prime}$ with one more column by
$\mathbf{A}^{\prime}=\begin{pmatrix}\mathbf{A}&-\mathbf{A}\mathbf{1}\end{pmatrix}$.
Obviously $\mathbf{A}^{\prime}\in\mathcal{G}_{z}$, and
$\mathbf{A}\mathbf{x}=\mathbf{b}$ has a solution if and only if
$\mathbf{A}^{\prime}\mathbf{x}^{\prime}=\mathbf{b}$ has a solution. We can
also recover $\mathbf{x}\in\mathbb{R}^{n}$ from
$\mathbf{x}^{\prime}\in\mathbb{R}^{n+1}$ by taking the first $n$ rows of
$\mathbf{x}^{\prime}$ and minus each of them by $\mathbf{x}^{\prime}_{n+1}$.
The following results about additions imply that $\mathbf{A}^{\prime}$ can be
calculated in $\mathsf{TC}^{0}$, and we can recover $\mathbf{x}^{\prime}$ from
$\mathbf{x}$ in $\mathsf{AC}^{0}$ (for simplicity we ignore the precision
problem here).

######  Fact 1.

  * •

Addition of $2$ $w$-bit numbers has $\mathsf{AC}^{0}$ circuit of size
$\mathrm{{poly}}(w)$ (c.f. [1]);111$\mathsf{AC}^{0}$ circuits are constant-
depth polynomial-size unbounded-fan in circuits with $\wedge$, $\vee$, and
$\neg$ gates.

  * •

Addition of $n$ $w$-bit numbers has $\mathsf{TC}^{0}$ circuit of size
$\mathrm{{poly}}(n,w)$ [6].

#### From $\mathcal{G}_{z}$ to $\mathcal{G}_{z,2}$

######  Proof 2.5 (Proof sketch).

Given an $m\times n$ $w$-bit signed-integer matrix
$\mathbf{A}^{\prime}\in\mathcal{G}_{z}$, we just need to add two more columns
to make the sum of positive (and negative) entries in each row to the closet
power of $2$. This can be done in $\mathsf{TC}^{0}$ in the following way. For
each row $1\leq i\leq m$, we calculate the sum of positive entries $s_{i}$ by
checking the sign bit then do the iterated addition in $\mathsf{TC}^{0}$ by
Fact 1. We then take $s=\max s_{i}$, which can be computed in
$\mathsf{AC}^{0}$ given $s_{i}$’s. $s$ has at most $O(w\log n)$ bits so given
$s$ by searching brute-forcely in $\mathsf{AC}^{0}$ we can find the minimum
$k$ s.t. $2^{k}\geq s$. Therefore by Fact 1 we can calculate
$a_{i}=2^{k}-s_{i}$ in $\mathsf{AC}^{0}$ given $s_{i}$. Then for each row $i$
we add $a_{i}$ and $-a_{i}$ to the last two columns of $\mathbf{A}^{\prime}$
to get $\mathbf{A}^{\prime\prime}$. Additionally we need to add a new row to
$\mathbf{A}^{\prime\prime}$ (and to $\mathbf{b}^{\prime\prime}$ accordingly)
to zero out the last two variables we just added: set the last two entries
into $1$ and $-1$, and set all other entries $0$, and also add a $0$ entry to
$\mathbf{b}^{\prime}$ to get $\mathbf{b}^{\prime\prime}$.

Obviously we have $\mathbf{A}^{\prime\prime}\in\mathcal{G}_{z,2}$, and
$\mathbf{A}^{\prime}\mathbf{x}^{\prime}=\mathbf{b}^{\prime}$ has a solution
iff
$\mathbf{A}^{\prime\prime}\mathbf{x}^{\prime\prime}=\mathbf{b}^{\prime\prime}$
has a solution. We can easily recover $\mathbf{x}^{\prime}$ from
$\mathbf{x}^{\prime\prime}$ by taking the first $n$ rows.

For the next section we need the following definition.

######  Definition 2.6.

We say a matrix $\mathbf{A}\in\mathcal{G}_{z}$ is _$w$ -bounded_ if for each
row the sum of positive coefficients is at most $2^{w}$. Note that in such
matrix every entry is a $w$-bit signed integer.

Note that the reduction from $\mathcal{G}$ to $\mathcal{G}_{z}$ reduces an
$m\times n$ $w$-bit matrix $\mathbf{A}$ into an $m\times(n+1)$ $O(w\log
n)$-bounded matrix $\mathbf{A}^{\prime}$, then the reduction from
$\mathcal{G}_{z}$ to $\mathcal{G}_{z,2}$ reduces $\mathbf{A}^{\prime}$ into an
$(m+1)\times(n+3)$ $O(w\log n)$-bounded matrix $\mathbf{A}^{\prime\prime}$.

##  3 Simplified main reduction in $\mathsf{TC}^{0}$

The main reduction in [7] uses the pair-and-replace scheme to transform a
linear system in $\mathcal{G}_{z,2}$ to a $2$-commodity equation system. The
main idea is to use $\mathcal{MC}_{2}\mathtt{Gadget}$s consisting of
$\mathcal{MC}_{2}$ equations to replace pairs of variables in the original
linear system round-by-round according to the bit representation of their
coefficients. A simplified version of the gadget, implicitly given in [7], is
as follows.

######  Definition 3.1 (Simplified $\mathcal{MC}_{2}\mathtt{Gadget}$).

Define $\mathcal{MC}_{2}\mathtt{Gadget}(t,t^{\prime},j_{1},j_{2})$ to be the
following set of 2-commodity linear equations representing
“$2x_{t}=x_{j_{1}}+x_{j_{2}}$”:

$\displaystyle x_{t}-x_{t^{\prime}+1}$ $\displaystyle=0$ $\displaystyle
x_{t^{\prime}+2}-x_{j_{2}}$ $\displaystyle=0$ $\displaystyle
y_{t^{\prime}+1}-y_{t^{\prime}+3}$ $\displaystyle=0$ $\displaystyle
y_{t^{\prime}+4}-y_{t^{\prime}+2}$ $\displaystyle=0$ $\displaystyle
x_{t^{\prime}+3}-x_{j_{1}}$ $\displaystyle=0$ $\displaystyle
x_{t}-x_{t^{\prime}+4}$ $\displaystyle=0$ $\displaystyle
x_{t^{\prime}+4}-y_{t^{\prime}+4}-(x_{t^{\prime}+3}-y_{t^{\prime}+3})$
$\displaystyle=0$ $\displaystyle
x_{t^{\prime}+1}-y_{t^{\prime}+1}-(x_{t^{\prime}+2}-y_{t^{\prime}+2})$
$\displaystyle=0.$

For convenience we use an extra parameter $t^{\prime}$ to keep track of new
variables that are only used in the gadgets.

Correctness of this gadget can be easily verified by summing up all the
equations in it.

We now present a simplified reduction from exactly solving $\mathcal{G}_{z,2}$
to exactly solving $\mathcal{MC}_{2}$ in Algorithm 1. We use $\mathbf{A}_{i}$
to denote the $i$-th row of $\mathbf{A}$.

1

Input : a $w$-bounded $m\times n$ matrix $\mathbf{A}\in\mathcal{G}_{z,2}$ and
$\mathbf{c}\in\mathbb{R}^{n}$.

Output : a $w$-bit $m^{\prime}\times n^{\prime}$ matrix
$\mathbf{B}\in\mathcal{MC}_{2}$ and $\mathbf{d}\in\mathbb{R}^{n}$.

2 $m^{\prime}\leftarrow m$, $n^{\prime}\leftarrow n$

3 $n_{g}\leftarrow 0$

4 // # of new variables used only in the $\mathcal{MC}_{2}\mathtt{Gadget}$s

5 for  _$i\leftarrow 1$ to $m$_ do

6 for  _$s\in\\{+,-\\}$_ do

7 for  _$k\leftarrow 1$ to $w$_ do

8 while  _strictly more than 1 entry in $\mathbf{A}_{i}$ has sign $s$ and the
$k$-th bit being $1$_ do

9 Let $j_{1},j_{2}$ be the first and second indices of such entries in
$\mathbf{A}_{i}$

10 In $\mathbf{A}_{i}$, replace $2^{k}(x_{j_{1}}+x_{j_{2}})$ by
$2^{k+1}x_{n^{\prime}+1}$ (thus adding one column to the right of
$\mathbf{A}$)

11 Add the coefficients of
$\mathcal{MC}_{2}\mathtt{Gadget}$(_$n^{\prime}+n_{g}+1$ ,
$n^{\prime}+n_{g}+1$, $j_{1}$, $j_{2}$_) to $\mathbf{C}$

12 $n^{\prime}\leftarrow n^{\prime}+1$

13 $n_{g}\leftarrow n_{g}+4$

14 $m^{\prime}\leftarrow m^{\prime}+8$

15

16 end while

17

18 end for

19

20 end for

21

22 end for

23$n^{\prime}\leftarrow 2\times(n^{\prime}+n_{g})$

24 Stack $\mathbf{C}$ in the bottom of $\mathbf{A}$ and fill in $0$’s to get
$\mathbf{B}$

25 Add $m^{\prime}-m$ $0$’s under $\mathbf{c}$ to get $\mathbf{d}$

26

Algorithm 1 Simplified
$\textsc{Reduce}\mathcal{G}_{z,2}\textsc{To}\mathcal{MC}_{2}$

Note that in $\mathcal{MC}_{2}$ we have two input variables sets $X$, $Y$ of
the same size. That is why we have to multiply $n^{\prime}$ by 2 at last in
the reduction. But here we will only use variables in $Y$ in the
$\mathcal{MC}_{2}\mathtt{Gadget}$s, and all the other $Y$ variables are
unused. For convenience we arrange the variables in the following way.

######  Remark 3.2 (Arrangement of variables).

In $\mathbf{B}$ we put all the variables in $X$ before those in $Y$. More
importantly, we put those $X$ variables that are only used in the gadgets
behind all those $x_{n^{\prime}+1}$ in Line 1. Equivalently it can be viewed
as the following process. We first run Algorithm 1 virtually before Line 1 to
get $n^{\prime}$, which is the number of $X$ variables ignoring those only
used in the gadgets. Then we run it again on the original input, starting with
$n_{g}$ being this value, and in Line 1 we use
$\mathcal{MC}_{2}\mathtt{Gadget}(n^{\prime}+1,n_{g},j_{1},j_{2})$ instead.

We give an example showing how the reduction works under this arrangement.

######  Example 3.3.

We show how the reduction runs on $3x_{1}+5x_{2}+x_{3}+7x_{4}-16x_{5}=0$:

$\displaystyle 00011x_{1}+00101x_{2}+00001x_{3}+00111x_{4}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{1}+x_{2}-2x_{6}=0}\leavevmode\nobreak\ $
$\displaystyle
00010x_{1}+00100x_{2}+00001x_{3}+00111x_{4}+00010x_{6}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{3}+x_{4}-2x_{7}=0}\leavevmode\nobreak\ $
$\displaystyle
00010x_{1}+00100x_{2}+00110x_{4}+00010x_{6}+00010x_{7}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{1}+x_{4}-2x_{8}=0}\leavevmode\nobreak\ $
$\displaystyle
00100x_{2}+00100x_{4}+00010x_{6}+00010x_{7}+00100x_{8}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{6}+x_{7}-2x_{9}=0}\leavevmode\nobreak\ $
$\displaystyle 00100x_{2}+00100x_{4}+00100x_{8}+00100x_{9}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{2}+x_{4}-2x_{10}=0}\leavevmode\nobreak\ $
$\displaystyle 01000x_{10}+00100x_{8}+00100x_{9}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{8}+x_{9}-2x_{11}=0}\leavevmode\nobreak\ $
$\displaystyle 01000x_{10}+01000x_{11}-10000x_{5}=0$
$\displaystyle\xrightarrow{x_{10}+x_{11}-2x_{12}=0}\leavevmode\nobreak\ $
$\displaystyle 10000x_{12}-10000x_{5}=0.$

We are only eliminating the positive coefficient variables in this example for
simplicity. In the first round we use new variables (and the corresponding
gadgets) $x_{6}$ and $x_{7}$ to eliminate the first bit, getting the equation
$2x_{1}+4x_{2}+6x_{4}+2x_{6}+2x_{7}=0$. These two generated variables are then
eliminated in the second round by $x_{9}$, in addition to $x_{8}$ for the
second bit. In the third round we use $x_{10}$ and $x_{11}$. Finally in the
fourth round we use $x_{12}$ and get the equation after the reduction
$16x_{12}-16x_{5}=0$, with $\mathcal{MC}_{2}\mathtt{Gadget}$s representing
$2x_{6}=x_{1}+x_{2}$, $2x_{7}=x_{3}+x_{4}$, $2x_{8}=x_{1}+x_{4}$,
$2x_{9}=x_{6}+x_{7}$, $2x_{10}=x_{2}+x_{4}$, $2x_{11}=x_{8}+x_{9}$, and
$2x_{12}=x_{10}+x_{11}$.

Correctness of this simplified reduction follows easily by correctness of the
gadget, as our transformation preserves the original solution. Moreover, given
a solution $\mathbf{x}^{*}$ such that $\mathbf{B}\mathbf{x}^{*}=\mathbf{d}$
where $\mathbf{B}$ and $\mathbf{d}$ are obtained from running Algorithm 1 on
input $\mathbf{A}$ and $\mathbf{c}$, we can easily get the solution to the
original equation system $\mathbf{A}\mathbf{x}=\mathbf{c}$ by simply taking
the first $n$ elements in $\mathbf{x}^{*}$. It is also easy to get
$\mathbf{d}$ from $\mathbf{c}$ if we can calculate $m^{\prime}$ in
$\mathsf{TC}^{0}$.

In the remaining of this section we are going to prove that Algorithm 1 can be
implemented in $\mathsf{TC}^{0}$. For $1\leq i\leq m$, $1\leq k\leq w$, we
define

$\displaystyle\mathtt{Len}^{+}_{i}(\mathbf{A})$ $\displaystyle=\text{ log of
sum of positive coefficients in $\mathbf{A}_{i}$},$
$\displaystyle\mathtt{CountBit}^{+}_{i,k}(\mathbf{A})$
$\displaystyle=\\#\text{ of positive coefficient variables in the original
$\mathbf{A}_{i}$ with the $k$-th bit $1$},$
$\displaystyle\mathtt{NumGadget}^{+}_{i,k}(\mathbf{A})$
$\displaystyle=\\#\text{ of $\mathcal{MC}_{2}\textsc{Gadget}$s used for
$\mathbf{A}_{i}$ to eliminate the $k$-th bit}$
$\displaystyle\phantom{=\\#}\text{ of positive coefficient variables},$

and similarly $\mathtt{Len}^{-}_{i}(\mathbf{A})$,
$\mathtt{CountBit}^{-}_{i,k}(\mathbf{A})$,
$\mathtt{NumGadget}^{-}_{i,k}(\mathbf{A})$ for the negative coefficient
variables.

######  Example 3.4.

For the above example, we have $\mathtt{Len}^{+}_{i}(\mathbf{A})=5$, and the
following values for each $k$.

Table 1: Values of $\mathtt{CountBit}^{+}_{i,k}(\mathbf{A})$ and $\mathtt{NumGadget}^{+}_{i,k}(\mathbf{A})$ for Example 3.3 $k$ | $1$ | $2$ | $3$ | $4$ | $5$
---|---|---|---|---|---
$\mathtt{CountBit}^{+}_{i,k}(\mathbf{A})$ | $4$ | $2$ | $2$ | $0$ | $0$
$\mathtt{NumGadget}^{+}_{i,k}(\mathbf{A})$ | $2$ | $2$ | $2$ | $1$ | $0$

We have the following simple but crucial properties for these values.

######  Claim 2.

  1. (i)

$\mathtt{Len}^{s}_{i}(\mathbf{A})\leq w$ for all $s\in\\{+,-\\}$, $1\leq i\leq
m$;

  2. (ii)

$\mathtt{CountBit}^{s}_{i,k}(\mathbf{A})\leq n$ for all $s\in\\{+,-\\}$,
$1\leq i\leq m$, $1\leq k\leq w$;

  3. (iii)

For all $s\in\\{+,-\\}$, $1\leq i\leq m$,

$\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})=\begin{cases}2^{-(k+1)}\sum_{k^{\prime}=1}^{k}2^{k^{\prime}}\mathtt{CountBit}^{s}_{i,k^{\prime}}(\mathbf{A})&\text{
for }1\leq k\leq\mathtt{Len}^{s}_{i}(\mathbf{A})-1,\\\ 0&\text{ for
}\mathtt{Len}^{s}_{i}(\mathbf{A})\leq k\leq w,\end{cases}$

thus $\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})\leq O(n)$;

  4. (iv)

$m^{\prime}=m+8\sum_{i=1}^{m}\sum_{s\in\\{+,-\\}}\sum_{k=1}^{w}\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})\leq
O(nmw)$;

  5. (v)

$n^{\prime}=2n+10\sum_{i=1}^{m}\sum_{s\in\\{+,-\\}}\sum_{k=1}^{w}\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})\leq
O(nmw)$.

######  Proof 3.5.

(i) and (ii) are trivial by definition. (iv) and (v) are straightforward from
Algorithm 1 and (iii). For (iii), note that in each round for $k$ we will
eliminate all the variables generated in the previous round for $k-1$ by
construction (ignoring those variables that are only used in the gadgets),
therefore we have
$\mathtt{NumGadget}^{s}_{i,1}(\mathbf{A})=\mathtt{CountBit}^{s}_{i,1}(\mathbf{A})/2$
and
$\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})=(\mathtt{CountBit}^{s}_{i,k}(\mathbf{A})+\mathtt{NumGadget}^{s}_{i,k-1}(\mathbf{A}))/2$
for $2\leq k\leq\mathtt{Len}^{s}_{i}(\mathbf{A})-1$. Here we rely on the
property that the sum of positive (and negative) coefficients in each row is a
power of $2$ to ensure that $\mathtt{NumGadget}^{s}_{i,k}(\mathbf{A})$ as
calculated in this way are always integers. Then by induction we get the
formula.

Note that in (iii) $2^{-(k+1)}$ and $2^{k^{\prime}}$ are just right and left
shifts, which can be easily implemented in the circuit model. Combining Claim
2 and Fact 1, we can see that all of these values can be computed in
$\mathsf{TC}^{0}$ for all $i,k,s$, i.e. the depths of the $\mathsf{TC}$
circuits are absolute constants independent of $i$, $k$, and $s$.

######  Lemma 3.6 (Informal).

  * •

$\mathtt{Len}^{s}_{i}$, $\mathtt{CountBit}^{s}_{i,k}$, and
$\mathtt{NumGadget}^{s}_{i,k}$ have $\mathsf{TC}^{0}$ circuits of size
$\mathrm{{poly}}(n,w)$ for all $i,k,s$;

  * •

$n^{\prime},m^{\prime}$ has $\mathsf{TC}^{0}$ circuits of size
$\mathrm{{poly}}(n,m,w)$.

Now we can prove that the reduction from $\mathcal{G}_{z,2}$ to
$\mathcal{MC}_{2}$ can be done in $\mathsf{TC}^{0}$. We represent the input
matrix $\mathbf{A}$ explicitly by giving all its entries in sign-magnitude
form, and the output matrix $\mathbf{B}$ implicitly by outputting the entry of
$\mathbf{B}$ in row $i$ column $j$ with $i$,$j$ as additional inputs.

######  Theorem 3.7.

There is a $\mathsf{TC}^{0}$ circuit family
$\\{C_{n,m,w}\\}_{n,m,w\in\mathbb{N}}$ of size $\mathrm{{poly}}(n,m,w)$ with
$(O(nmw)+O(\log nmw))$-bit input and $O(w)$-bit output such that:

  * •

the first $O(nmw)$ bits of input represent a $w$-bounded $m\times n$ matrix
$\mathbf{A}\in\mathcal{G}_{z,2}$ in sign-magnitude form, the next $O(\log
nmw)$ bits of input represent an index $i$, and the last $O(\log nmw)$ bits
represent another index $j$;

  * •

for $i\leq m^{\prime}$ and $j\leq n^{\prime}$ where $m^{\prime},n^{\prime}\leq
O(nmw)$ is calculated as in Algorithm 1 on $\mathbf{A}$, the output represents
the entry of $\mathbf{B}$ (in sign-magnitude form) in row $i$ column $j$ as
calculated by Algorithm 1 on $\mathbf{A}$; otherwise it represents $0$.

######  Proof 3.8.

Consider the $i$-th row of $\mathbf{B}$, we need to know the equation it
corresponds to. Because we put those equations of
$\mathcal{MC}_{2}\mathtt{Gadget}$s behind the modified equations of
$\mathbf{A}$, we have two cases:

  * •

$i\leq m$: in this case, the equation is $\mathbf{A}_{i}$ after the
transformation, which has the form $C(x_{j_{+}}-x_{j_{-}})=\mathbf{c}_{i}$
with $C=\underbrace{100\cdots 0}_{\mathtt{Len}^{+}_{i}(\mathbf{A})\text{
bits}}$ in binary since our transformation does not change the sum of positive
(and negative) coefficients in $\mathbf{A}$. What remains is to calculate the
indices $j_{+}$ and $j_{-}$ in $\mathsf{TC}^{0}$.

Let
$\mathtt{SumNumG}^{s}_{i}(\mathbf{A})=\sum_{k=1}^{w}\mathtt{NumGadget}^{s}_{i,k}$
for all $s\in\\{+,-\\}$ and $1\leq i\leq m$. For each $s\in\\{+,-\\}$, there
are two cases:

    * –

No new variable is added, i.e. $\mathtt{SumNumG}^{s}_{i}(\mathbf{A})=0$: there
is only one entry in the original $\mathbf{A}_{i}$ with the corresponding sign
thus $j_{s}$ is the index of this entry. We search for this entry to get its
index, which can be implemented in $\mathsf{AC}^{0}$ because there are $n$
possibilities.

    * –

Some new variables are added: then $j_{s}$ is the index of the last added new
variable, ignoring those only in $\mathcal{MC}_{2}\mathtt{Gadget}$s. It can be
calculated by

$\displaystyle
j_{s}=\begin{cases}n+\mathtt{SumNumG}^{+}_{i}(\mathbf{A})+\sum_{i^{\prime}=1}^{i-1}\sum_{s^{\prime}\in\\{+,-\\}}\mathtt{SumNumG}^{s^{\prime}}_{i^{\prime}}(\mathbf{A})&\text{
if }s=+,\\\
n+\sum_{i^{\prime}=1}^{i}\sum_{s^{\prime}\in\\{+,-\\}}\mathtt{SumNumG}^{s^{\prime}}_{i^{\prime}}(\mathbf{A})&\text{
if }s=-.\end{cases}$

$\mathtt{SumNumG}^{s}_{i}\in\mathsf{TC}^{0}$ by Fact 1 and Lemma 3.6 so both
$j_{+},j_{-}$ can be calculated in $\mathsf{TC}^{0}$ by Fact 1. Therefore we
can calculate the entries in row $i$ in $\mathsf{TC}^{0}$ for $i\leq m$.

  * •

$i>m$: in this case, this equation is in an
$\mathcal{MC}_{2}\mathtt{Gadget}(t,t^{\prime},j_{1},j_{2})$ gadget for some
$t,t^{\prime},j_{1},j_{2}$. We need to calculate $t,t^{\prime},j_{1}$, and
$j_{2}$ in $\mathsf{TC}^{0}$ then it is easy to recover the equation from the
offset in the gadget.

We can first calculate in $\mathsf{AC}^{0}$ the gadget’s index
$ind=\lfloor\frac{i-m-1}{8}\rfloor+1$ as $\lfloor\frac{\cdot}{8}\rfloor$ is
just ignoring the three least significant bits. By Algorithm 1 and Remark 3.2,
we know $t=n+ind$ thus it is $\mathsf{AC}^{0}$-computable, and we can also
calculate
$t^{\prime}=n+\sum_{i^{\prime}=1}^{m}\sum_{s^{\prime}\in\\{+,-\\}}\mathtt{SumNumG}^{s^{\prime}}_{i^{\prime}}(\mathbf{A})+4(ind-1)$
in $\mathsf{TC}^{0}$ by Fact 1.

Then we can calculate the number $i^{\prime}$, $k^{\prime}$, sign
$s^{\prime}\in\\{+,-\\}$, and number $\ell^{\prime}$ such that this gadget is
the $\ell^{\prime}$-th gadget we created to eliminate the $k^{\prime}$-th bit
of $\mathbf{A}_{i^{\prime}}$ for variables with sign $s^{\prime}$. More
specifically, we want to find the minimum $i^{\prime}$, $k^{\prime}$,
$s^{\prime}$ (where we treat ‘$+$’ $<$ ‘$-$’) such that

$\displaystyle\mathtt{PrefixSum}^{+}_{i^{\prime},k^{\prime}}(\mathbf{A})<ind\leq\mathtt{PrefixSum}^{+}_{i^{\prime},k^{\prime}}(\mathbf{A})+\mathtt{NumGadget}^{+}_{i^{\prime},k^{\prime}}$
$\displaystyle\text{ if }s^{\prime}=+,$
$\displaystyle\mathtt{PrefixSum}^{-}_{i^{\prime},k^{\prime}}(\mathbf{A})<ind\leq\mathtt{PrefixSum}^{-}_{i^{\prime},k^{\prime}}(\mathbf{A})+\mathtt{NumGadget}^{-}_{i^{\prime},k^{\prime}}$
$\displaystyle\text{ if }s^{\prime}=-,$

where

$\displaystyle\mathtt{PrefixSum}^{+}_{i^{\prime},k^{\prime}}(\mathbf{A})$
$\displaystyle=\sum_{i^{\prime\prime}=1}^{i^{\prime}-1}\sum_{s^{\prime\prime}\in\\{+,-\\}}\mathtt{SumNumG}^{s^{\prime\prime}}_{i^{\prime\prime}}(\mathbf{A})+\sum_{k^{\prime\prime}=1}^{k^{\prime}-1}\sum_{s^{\prime\prime}\in\\{+,-\\}}\mathtt{NumGadget}^{s^{\prime\prime}}_{i^{\prime},k^{\prime\prime}}(\mathbf{A}),$
$\displaystyle\mathtt{PrefixSum}^{-}_{i^{\prime},k^{\prime}}(\mathbf{A})$
$\displaystyle=\mathtt{PrefixSum}^{+}_{i^{\prime},k^{\prime}}(\mathbf{A})+\mathtt{NumGadget}^{+}_{i^{\prime},k^{\prime}}.$

There are $O(mw)$ possible choices for $i^{\prime}$, $k^{\prime}$,
$s^{\prime}$ and each condition is a prefix sum of
$\mathtt{NumGadget}^{s}_{i,k}$’s, therefore this can be done in
$\mathsf{TC}^{0}$ by a parallel comparison of $ind$ to the prefix sums of
$\mathtt{NumGadget}^{s}_{i,k}$’s. After getting $i^{\prime}$, $k^{\prime}$,
and $s^{\prime}$, we can get
$\ell^{\prime}=ind-\mathtt{PrefixSum}^{s^{\prime}}_{i^{\prime},k^{\prime}}$ by
Fact 1.

What remains is to calculate $j_{1}$ and $j_{2}$ from $i^{\prime}$,
$k^{\prime}$, $s^{\prime}$, and $\ell^{\prime}$. Note that when eliminating
the $k^{\prime}$-th bit of $\mathbf{A}_{i^{\prime}}$ for variables with sign
$s^{\prime}$, we first eliminate in pairs those variables in the original
$\mathbf{A}_{i^{\prime}}$ that have $1$ in the $k^{\prime}$-th bit before the
reduction (we call them _original pairs_), then eliminate in pairs those
generated in the previous round for $i^{\prime}$, $k^{\prime}-1$, and
$s^{\prime}$. The number of original pairs is given by
$p=\lfloor\mathtt{CountBit}^{s^{\prime}}_{i^{\prime},k^{\prime}}(\mathbf{A})/2\rfloor$,
computable in $\mathsf{TC}^{0}$. There are two cases:

    * –

$\ell^{\prime}\leq p$: $j_{1}$ and $j_{2}$ is the indices of variables in the
$\ell^{\prime}$-th original pairs, which are the indices of the
$(2\ell^{\prime}-1)$-th and $2\ell^{\prime}$-th variables in
$\mathbf{A}_{i^{\prime}}$ that have $1$ in the $k^{\prime}$-th bit. Similarly
as above, this can be done by a simple parallel comparison to prefix sums of
the $k^{\prime}$-th bits of variables in $\mathbf{A}_{i^{\prime}}$.

    * –

$\ell^{\prime}>p$: then $j_{1}$ and $j_{2}$ are the
$(2(\ell^{\prime}-p)-1)$-th and $2(\ell^{\prime}-p)$-th new variables
generated in the previous round, therefore
$j_{1}=\mathtt{PrefixSum}^{s^{\prime}}_{i^{\prime},k^{\prime}-1}(\mathbf{A})+2(\ell^{\prime}-p)-1$
and $j_{2}=j_{1}+1$.

However the second case above only works for even
$\mathtt{CountBit}^{s^{\prime}}_{i^{\prime},k^{\prime}}(\mathbf{A})$. When it
is odd, $\ell^{\prime}=p+1$ corresponds to a pair with the last original
variable in this round and the first generated variables in the previous
round, thus $j_{1}$ can be calculated as in the first case and
$j_{2}=\mathtt{PrefixSum}^{s^{\prime}}_{i^{\prime},k^{\prime}-1}(\mathbf{A})+1$.
Then for $\ell^{\prime}>p+1$, we have
$j_{1}=\mathtt{PrefixSum}^{s^{\prime}}_{i^{\prime},k^{\prime}-1}(\mathbf{A})+2(\ell^{\prime}-p)-2$
and $j_{2}=j_{1}+1$.

In conclusion, given $i$ as input, we can first check if $i\leq m^{\prime}$ in
$\mathsf{TC}^{0}$ by Lemma 3.6 and if so compute coefficients of
$\mathbf{B}_{i}$ in $\mathsf{TC}^{0}$, therefore with $j$ as input, we check
if $j\leq n^{\prime}$ in $\mathsf{TC}^{0}$ and if so compute the entry of
$\mathbf{B}$ in row $i$ column $j$ in $\mathsf{TC}^{0}$.

##  4 Genearlization to approximate solvers, and more restrictive classes

Now we are going to generalize the above results of reductions for exact
solvers into those for approximate solvers, thus proving Theorem 1.2. First we
need the following result showing the power of $\mathsf{TC}^{0}$.

######  Fact 3.

Division and iterated multiplication are in $\mathsf{DLOGTIME}$-uniform
$\mathsf{TC}^{0}$ [5]. Moreover, we can approximate in $\mathsf{TC}^{0}$
functions represented by sufficiently nice power series, such as $\log$,
$\exp$, and $x^{1/k}$ [11, 9, 5].

######  Proof 4.1 (Proof sketch of Theorem 1.2).

Based on our proofs on the simplified reductions, we are going to prove that
the original reductions from $\mathcal{G}$ to $\mathcal{MC}_{2}$ in [7] can be
computed in $\mathsf{TC}^{0}$. In the context of approximate solvers, the
error $\mathrm{\varepsilon}$ that solvers are required to achieve is also part
of the instance. By Fact 3, all the errors in the reduced instances, as
defined in the reductions in Kyng and Zhang’s full paper [8], can be computed
in $\mathsf{TC}^{0}$ given the size, condition number, and bit-complexity of
the original matrix as parameters.

  * •

From $\mathcal{G}$ to $\mathcal{G}_{z}$: this reduction remains the same, but
now knowing the accuracy we can recover $\mathbf{x}^{\prime}$ from
$\mathbf{x}$ using fix-point arithmetic in $\mathsf{TC}^{0}$.

  * •

From $\mathcal{G}_{z}$ to $\mathcal{G}_{z,2}$: the only difference (besides
the calculation of accuracy) is that in the original reduction in [8, Section
7.2], in the last row of the reduced matrix $\mathbf{A}^{\prime}$ the last two
entries are set to be $w$ and $-w$ for some value $w$, instead of $1$ and $-1$
as in our simplified version. However $w$ is computable in $\mathsf{TC}^{0}$
by Fact 3 so the reduction is still computable in $\mathsf{TC}^{0}$.

  * •

From $\mathcal{G}_{z,2}$ to $\mathcal{MC}_{2}$: for approximate solvers we
will have to use the original $\mathcal{MC}_{2}\mathtt{Gadget}$ in [8, Section
4] consisting of ten $2$-commodity equations instead of eight and with
additional variables. So we need to modify the corresponding numbers in our
calculation, and in particular the gedget’s index becomes
$ind=\lfloor\frac{i-m-1}{10}\rfloor+1$, which is still
$\mathsf{TC}^{0}$-computable. Besides, the equations in the
$\mathcal{MC}_{2}\mathtt{Gadget}$ for eliminating the $k$-th bit of variables
with sign $s$ in $\mathbf{A}_{i}$ will be multiplied by a factor $-s\cdot
2^{k}\cdot w_{i}$, where
$w_{i}=\sqrt{10\sum_{s^{\prime}\in\\{+,-\\}}\mathtt{SumNumG}^{s}_{i}(\mathbf{A})}$,
as specified in Algorithm 1 of [8]. These factors can be calculated with
desired accuracy in $\mathsf{TC}^{0}$ by Fact 3. Therefore the reduction is
still computable in $\mathsf{TC}^{0}$.

Additionally in the second and third reduction, when recovering
$\mathbf{x}^{\prime}$ from $\mathbf{x}$ we need to check if the original
matrix $\mathbf{A}$ and vector $\mathbf{b}$ satisfy
$\mathbf{A}^{\top}\mathbf{b}=\mathbf{0}$ and simply return $\mathbf{0}$ if so.
This can be done in $\mathsf{TC}^{0}$ by Fact 1. In conclusion, we can reduce
the problem of approximately solving equations in $\mathcal{G}$ to
approximately solving equations in $\mathcal{MC}_{2}$ in $\mathsf{TC}^{0}$.

In [7] they also considered some more restrictive subclasses of
$\mathcal{MC}_{2}$. Intuitively, the set of _strict $2$-commodity matrices_
$\mathcal{MC}^{>0}_{2}\subset\mathcal{MC}_{2}$ is the class of 2-commodity
equations $\mathbf{A}$ such that for every pair $i,j$, equation
$x_{i}-x_{j}=0\in\mathbf{A}$ iff equation $y_{i}-y_{j}=0\in\mathbf{A}$ iff
equation $x_{i}-y_{i}-(x_{j}-y_{j})=0\in\mathbf{A}$. The set of strict
$2$-commodity matrices with integer entries is denoted by
$\mathcal{MC}^{>0}_{2,\mathbb{Z}}$. They showed that reductions from
approximately solving $\mathcal{MC}_{2}$ to approximately solving
$\mathcal{MC}^{>0}_{2}$, and from $\mathcal{MC}^{>0}_{2}$ to
$\mathcal{MC}^{>0}_{2,\mathbb{Z}}$. We are going to show that these reductions
can be computed in $\mathsf{TC}^{0}$.

#### From $\mathcal{MC}_{2}$ to $\mathcal{MC}^{>0}_{2}$

######  Proof 4.2 (Proof sketch).

The reduction, as defined in [8, Section 5.1], runs by checking for each pair
$i,j$ that are involved in some equation in $\mathbf{A}$ if any of the three
types of equations is missing and add it if so. The added equations will be
multiplied by a factor that is computable in $\mathsf{TC}^{0}$. Obviously the
resulting equation systems is in $\mathcal{MC}^{>0}_{2}$. It is easy to see
that the number of added equations for each pair $i,j$ can be computed in
$\mathsf{AC}^{0}$, thus all the prefix sums of these numbers can be calculated
in $\mathsf{TC}^{0}$ simultaneously, and so we can determine the equations in
the reduced instance in $\mathsf{TC}^{0}$.

#### From $\mathcal{MC}^{>0}_{2}$ to $\mathcal{MC}^{>0}_{2,\mathbb{Z}}$

######  Proof 4.3 (Proof sketch).

In [8, Section 6] it is done by scaling up all the numbers in the matrix and
the vector by a factor of $2^{k}$, where $k$ is computable in
$\mathsf{TC}^{0}$ by Fact 3, then take the ceiling function on entries of the
matrix to convert them into integer entries, which also can be done in
$\mathsf{TC}^{0}$.

## References

  * [1] Peter Clote and Evangelos Kranakis.  Boolean Functions and Computation Models.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2002\.
  * [2] Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu.  Solving SDD linear systems in nearly _m_ log${}^{\mbox{1/2}}$_n_ time.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 343–352, 2014.
  * [3] Dean Doron, François Le Gall, and Amnon Ta-Shma.  Probabilistic logarithmic-space algorithms for laplacian solvers.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA, pages 41:1–41:20, 2017.
  * [4] François Le Gall.  Powers of tensors and fast matrix multiplication.  In International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014, pages 296–303, 2014\.
  * [5] William Hesse, Eric Allender, and David A. Mix Barrington.  Uniform constant-depth threshold circuits for division and iterated multiplication.  J. Comput. Syst. Sci., 65(4):695–716, 2002.
  * [6] Neil Immerman and Susan Landau.  The complexity of iterated multiplication.  In Proceedings: Fourth Annual Structure in Complexity Theory Conference, University of Oregon, Eugene, Oregon, USA, June 19-22, 1989, pages 104–111, 1989.
  * [7] Rasmus Kyng and Peng Zhang.  Hardness results for structured linear systems.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 684–695, 2017.
  * [8] Rasmus Kyng and Peng Zhang.  Hardness results for structured linear systems.  CoRR, abs/1705.02944, 2017.  arXiv:1705.02944.
  * [9] Alexis Maciel and Denis Thérien.  Efficient threshold circuits for power series.  Inf. Comput., 152(1):62–73, 1999.
  * [10] Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil P. Vadhan.  Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 801–812, 2017.
  * [11] John H. Reif and Stephen R. Tate.  On threshold circuits and polynomial computation.  SIAM J. Comput., 21(5):896–908, 1992.
  * [12] Michael E. Saks and Shiyu Zhou.  RSPACE(S) \subseteq dspace(s${}^{\mbox{3/2}}$).  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 344–353, 1995.
  * [13] Daniel A. Spielman and Shang-Hua Teng.  Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems.  SIAM J. Matrix Analysis Applications, 35(3):835–885, 2014.
  * [14] Amnon Ta-Shma.  Inverting well conditioned matrices in quantum logspace.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 881–890, 2013.


for all $f\in{\mathcal{H}}_{1}$. In particular, $\sum_{k\geq 1}\langle
f\,,\,f_{k}\rangle\,f_{k}(\cdot)$ defines a continuous function, and, for
almost all $x\in[0,1]$,

$f(x)\;=\;\sum_{k\geq 1}\langle f\,,\,f_{k}\rangle\,f_{k}(x)\;.$ (A.13)

###### Proof.

By (A.9), $f$ belongs to ${\mathcal{H}}_{R}$. By Schwarz inequality,

$\Big{(}\sum_{k\geq 1}\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}\,\Big{)}^{2}\;\leq\;\sum_{k\geq
1}\lambda_{k}\,\big{|}\,\langle f\,,\,f_{k}\rangle\,\big{|}^{2}\;\sum_{k\geq
1}\frac{1}{\lambda_{k}}\;\cdot$

The second sum is finite by (A.3) and the first one is finite by (A.10). This
proves the first assertion.

Since each function $f_{k}$ is continuous, and a summable sum of continuous
functions is continuous, $\sum_{k\geq 1}\langle
f\,,\,f_{k}\rangle\,f_{k}(\cdot)$ defines a continuous function. As
$(f_{k}:k\geq 1)$ forms an orthonormal basis of ${\mathscr{L}}^{2}([0,1])$,
$f=\sum_{k\geq 1}\langle f\,,\,f_{k}\rangle\,f_{k}$ as an identity in
${\mathscr{L}}^{2}([0,1])$. In particular, these functions are equal almost
everywhere. ∎

Denote by
$\color[rgb]{.2,0.2,.8}\definecolor[named]{pgfstrokecolor}{rgb}{.2,0.2,.8}(P^{(R)}_{t}:t\geq
0)$ the semigroup in ${\mathscr{L}}^{2}([0,1])$ generated by the Robin
Laplacian: For any function $f\in{\mathscr{L}}^{2}([0,1])$, $t>0$,

$P^{(R)}_{t}f\;=\;\sum_{k\geq 1}e^{-\lambda_{k}t}\,\langle
f\,,\,f_{k}\rangle\,f_{k}\;.$ (A.14)

In particular, for each $t\geq 0$, $P^{(R)}_{t}$ is a symmetric operator in
${\mathscr{L}}^{2}([0,1])$ and $P^{(R)}_{t}f\in C^{\infty}([0,1])$ for all
$f\in{\mathscr{L}}^{2}([0,1])$. Moreover, as $P^{(R)}_{t}$ is symmetric, by
(A.10), $P^{(R)}_{t}$ is a contraction in ${\mathcal{H}}_{R}$ and
${\mathscr{L}}^{2}([0,1])$:

$\begin{gathered}\|\,P^{(R)}_{t}f\,\|^{2}_{{\mathcal{H}}_{R}}\;=\;\sum_{k\geq
1}e^{-2\lambda_{k}t}\,\lambda_{k}\,|\,\langle
f\,,\,f_{k}\rangle\,|^{2}\;\leq\;\|\,f\,\|^{2}_{{\mathcal{H}}_{R}}\;,\\\
\|\,P^{(R)}_{t}f\,\|^{2}_{2}\;=\;\sum_{k\geq 1}e^{-2\lambda_{k}t}\,|\,\langle
f\,,\,f_{k}\rangle\,|^{2}\;\leq\;\|\,f\,\|^{2}_{2}\;.\end{gathered}$ (A.15)

Let $f\in{\mathscr{L}}^{2}([0,1])$ be given by $f=\sum_{k\geq 1}\langle
f\,,\,f_{k}\rangle\,f_{k}$. For each $t>0$, there exists a finite constant
$C_{0}(t)$ such that

$\displaystyle\|\,P^{(R)}_{t}f\,\|^{2}_{\infty}\;\leq\;C_{0}(t)\,\|\,f\,\|^{2}_{2}\;,\quad\|\,P^{(R)}_{t}f\,\|^{2}_{{\mathcal{H}}_{R}}\;\leq\;C_{0}(t)\,\|\,f\,\|^{2}_{2}\;.$
(A.16)

Indeed, by (A.10) and since $P^{(R)}_{t}$ is symmetric and
$P^{(R)}_{t}f_{k}=e^{-\lambda_{k}t}f_{k}$,

$\|\,P^{(R)}_{t}f\,\|^{2}_{{\mathcal{H}}_{R}}\;=\;\sum_{k\geq
1}\lambda_{k}\,e^{-2\lambda_{k}t}\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}^{2}\;\leq\;C_{0}(t)\,\sum_{k\geq
1}\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}^{2}\;=\;C_{0}(t)\,\|\,f\,\|^{2}_{2}$

for some finite constant $C_{0}(t)$. On the other hand, by Schwarz inequality
and (A.5),

$\|\,P^{(R)}_{t}f\,\|^{2}_{\infty}\;=\;\Big{\|}\,\sum_{k\geq
1}e^{-\lambda_{k}t}\,\langle
f\,,\,f_{k}\rangle\,f_{k}\,\Big{\|}^{2}_{\infty}\;\leq\;\sum_{k\geq
1}e^{-2\lambda_{k}t}\sum_{k\geq 1}\,\langle
f\,,\,f_{k}\rangle^{2}\;=\;C_{0}(t)\,\|\,f\,\|^{2}_{2}$

for some finite constant $C_{0}(t)$.

######  Lemma A.2.

There exists a finite constant $C_{0}$ such that

$\|\,P^{(R)}_{t}f\,-\,f\,\|_{2}\;\leq\;C_{0}\,t^{1/3}\,\,\|\,f\,\|_{{\mathcal{H}}_{R}}$

for all $t\geq 0$, $f\in{\mathcal{H}}_{R}$.

###### Proof.

Since $(f_{k}:k\geq 1)$ is an orthonormal basis of ${\mathscr{L}}^{2}([0,1])$,

$\|\,P^{(R)}_{t}f\,-\,f\,\|^{2}_{2}\;=\;\sum_{k\geq
1}\big{[}\,e^{-\lambda_{k}\,t}\,-\,1\,\big{]}^{2}\,\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}^{2}\;.$

Fix $k_{0}\geq 1$. Since the sequence $\lambda_{k}$ increases, the right-hand
side can be bounded by

$\big{[}\,e^{-\lambda_{k_{0}}\,t}\,-\,1\,\big{]}^{2}\sum_{k=1}^{k_{0}-1}\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}^{2}\;+\;\frac{1}{\lambda_{k_{0}}}\,\sum_{k\geq
k_{0}}\lambda_{k}\,\big{|}\,\langle f\,,\,f_{k}\rangle\,\big{|}^{2}\;.$

The first sum is bounded by $\|\,f\,\|^{2}_{2}$. In view of (A.10), the second
one is bounded by $\|\,f\,\|^{2}_{{\mathcal{H}}_{R}}$ so that

$\|\,P^{(R)}_{t}f\,-\,f\,\|^{2}_{2}\;\leq\;\big{[}\,1\,-\,e^{-\lambda_{k_{0}}\,t}\,\big{]}^{2}\,\|\,f\,\|^{2}_{2}\;+\;\frac{1}{\lambda_{k_{0}}}\|\,f\,\|^{2}_{{\mathcal{H}}_{R}}\;.$

As $1-e^{-x}\leq x$, $x>0$, and since, by (A.9), $\|\,f\,\|_{2}\leq
C_{0}\|\,f\,\|_{{\mathcal{H}}_{r}}$ for some finite constant $C_{0}$,

$\|\,P^{(R)}_{t}f\,-\,f\,\|^{2}_{2}\;\leq\;\Big{\\{}\,C_{0}\,(\,\lambda_{k_{0}}\,t\,)^{2}\;+\;\frac{1}{\lambda_{k_{0}}}\,\Big{\\}}\,\|\,f\,\|^{2}_{{\mathcal{H}}_{R}}\;.$

To complete the proof, it remains to choose $k_{0}$ such that
$\lambda^{-3}_{k_{0}}\sim t^{2}$. ∎

######  Lemma A.3.

There exists a finite constant $C_{0}$ such that

$\|\,P^{(R)}_{t}f\,-\,f\,\|_{\infty}\;\leq\;C_{0}\,t^{1/5}\,\,\|\,f\,\|_{{\mathcal{H}}_{R}}$

for all $t\geq 0$, $f\in C([0,1])\cap{\mathcal{H}}_{R}$.

###### Proof.

Fix $x\in[0,1]$. Since $f$ is continuous, by (A.13) and (A.5),

$\big{\\{}\,P^{(R)}_{t}f(x)\,-\,f(x)\,\big{\\}}^{2}\;\leq\;C_{0}\,\Big{(}\,\sum_{k\geq
1}\big{[}\,1\,-\,e^{-\lambda_{k}\,t}\,\big{]}\,\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}\,\Big{)}^{2}$

for some finite constant $C_{0}$. By Schwarz inequality and (A.10), the right-
hand is bounded by

$C_{0}\,\sum_{k\geq
1}\frac{1}{\lambda_{k}}\,\big{[}\,1\,-\,e^{-\lambda_{k}\,t}\,\big{]}^{2}\,\sum_{k\geq
1}\lambda_{k}\,\big{|}\,\langle
f\,,\,f_{k}\rangle\,\big{|}^{2}\;=\;C_{0}\,\|\,f\,\|^{2}_{{\mathcal{H}}_{R}}\,\sum_{k\geq
1}\frac{1}{\lambda_{k}}\,\big{[}\,1\,-\,e^{-\lambda_{k}\,t}\,\big{]}^{2}\;.$

It remains to estimate the sum. Fix $k_{0}\geq 1$. Since the sequence
$\lambda_{k}$ increases, as $1-e^{-x}\leq x$, $x>0$, by (A.3), the sum is less
than or equal to

$C_{0}\,\big{[}\,1\,-\,e^{-\lambda_{k_{0}}\,t}\,\big{]}^{2}\;+\;\sum_{k\geq
k_{0}}\frac{1}{\lambda_{k}}\;\leq\;C_{0}\,\Big{\\{}\,(k^{2}_{0}\,t)^{2}\;+\;\frac{1}{k_{0}}\,\Big{\\}}$

for some finite constant $C_{0}$. It remains to choose $k_{0}$ such that
$k_{0}^{5}\sim t^{-2}$. ∎

##  Appendix B Heat equations with mixed boundary conditions

We present in this section some result on the initial-boundary value problems
(1.1), (4.3). Denote by
$\color[rgb]{.2,0.2,.8}\definecolor[named]{pgfstrokecolor}{rgb}{.2,0.2,.8}{\mathcal{H}}^{1}={\mathcal{H}}^{1}([0,1])$
the Hilbert space obtained by completing the space $C^{1}([0,1])$ endowed with
the scalar product $\langle\,\cdot\,,\,\cdot\,\rangle_{{\mathcal{H}}^{1}}$
defined by

$\langle\,f\,,\,g\,\rangle_{{\mathcal{H}}^{1}}\;=\;\langle\,f\,,\,g\,\rangle\;+\;\langle\,\nabla
f\,,\,\nabla g\,\rangle\;.$ (B.1)

Denote by
$\color[rgb]{.2,0.2,.8}\definecolor[named]{pgfstrokecolor}{rgb}{.2,0.2,.8}\|f\|_{{\mathcal{H}}^{1}}$
the norm induced by the scalar product
$\langle\,\cdot\,,\,\cdot\,\rangle_{{\mathcal{H}}^{1}}$. Fix a function
$\phi\in{\mathscr{L}}^{2}([0,1])$, and consider the initial-boundary problem

$\begin{cases}\partial_{t}u\,=\,\Delta u\\\ (\nabla
u)(t,0)\,=\,A^{-1}\,u(t,0)\\\ (\nabla u)(t,1)\,=\,-\,B^{-1}\,u(t,1)\\\
u(0,\cdot)\,=\,\phi(\cdot)\;.\end{cases}$ (B.2)

######  Definition B.1.

A function $u$ in ${\mathscr{L}}^{2}([0,T];{\mathcal{H}}^{1})$ is said to be a
generalized (or weak) solution in the cylinder $[0,T]\times[0,1]$ of the
equation (B.2) if

$\displaystyle\int_{0}^{1}u_{t}\,H_{t}\;dx\;-\;\int_{0}^{1}\phi\,H_{0}\;dx\;-\;\int_{0}^{t}ds\,\int_{0}^{1}u_{s}\,\partial_{s}H_{s}\;dx$
$\displaystyle\quad=\;-\int_{0}^{t}ds\,\int_{0}^{1}\nabla u_{s}\,\nabla
H_{s}\;dx\;-\;\int_{0}^{t}\big{\\{}\,\frac{1}{B}\,u_{s}(1)\,H_{s}(1)\,+\,\frac{1}{A}\,u_{s}(0)\,H_{s}(0)\,\big{\\}}\;ds$

for every $0<t\leq T$, function $H$ in $C^{1,2}([0,T]\times[0,1])$.

######  Theorem B.2.

For each $\phi\in{\mathscr{L}}^{2}([0,1])$, there exists one and only one
generalized solution to (B.2). Moreover,

  * (a)

The solution is smooth in $(0,\infty)\times[0,1]$ and can be represented as
$u(t,x)=(P^{(R)}_{t}\phi)(x)$, where $P^{(R)}_{t}$ is the semigroup associated
to the Robin Laplacian.

  * (b)

For all $(t,x)\in{\mathbb{R}}_{+}\times[0,1]$,

$\min\\{\,0\,,\,{\rm
ess\,inf}\,\phi\,\\}\,\leq\,u(t,x)\,\leq\,\max\\{\,0\,,\,{\rm
ess\,sup}\,\phi\,\\}\;.$ (B.3)

  * (c)

If $\phi(x)\leq b$ for some $b>0$, then, for each $t_{0}>0$ there exists
$\epsilon>0$ such that $u(t,x)\leq b-\epsilon$ for all
$(t,x)\in[t_{0},\infty)\times[0,1]$. Analogously, if $\phi(x)\geq a$ for some
$a<0$, then, for each $t_{0}>0$ there exists $\epsilon>0$ such that
$u(t,x)\geq a+\epsilon$ for all $(t,x)\in[t_{0},\infty)\times[0,1]$.

  * (d)

If $\phi$ belongs to $C([0,1])\cap{\mathcal{H}}_{1}$, then the solution
belongs to $C([0,\infty)\times[0,1])$.

###### Proof.

Existence and uniqueness of generalized solutions, as well as their
representation in terms of the semigroup $P^{(R)}_{t}$ is the content of
Theorems 1 and 3 in [23, Section VI.2].

We turn to (B.3). Assume first that $\phi$ belongs to ${\mathcal{H}}_{1}$. By
(A.9), $\phi\in{\mathcal{H}}_{R}$, and, by Lemma A.3, $u(t)$ converges to
$\phi$ in ${\mathscr{L}}^{\infty}([0,1])$ as $t\to 0$. Since the solution is
smooth in $(0,\infty)\times[0,1]$, by the maximum principle stated in Theorems
2 and 3 of [24, Chapter 3],

$\min\\{\,0\,,\,\inf_{0\leq y\leq
1}u(t_{0},y)\,\\}\,\leq\,u(t,x)\,\leq\,\max\\{\,0\,,\,\sup_{0\leq y\leq
1}u(t_{0},y)\,\\}$

for all $(t,x)\in[t_{0},\infty)\times[0,1]$. Letting $t_{0}\to 0$, as
$u(t_{0})$ converges to $\phi$ in ${\mathscr{L}}^{\infty}([0,1])$, yields
(B.3).

To extend this result to $\phi\in{\mathscr{L}}^{2}([0,1])$, we consider a
sequence $\phi_{n}\in{\mathcal{H}}_{1}$ which converges to $\phi$ in
${\mathscr{L}}^{2}([0,1])$ and such that ${\rm
ess\,inf}\,\phi\,\leq\,\phi_{n}(x)\,\leq\,{\rm ess\,sup}\,\phi$ for all $0\leq
x\leq 1$. Denote by $u^{n}$ the solution to (B.2) with initial condition
$\phi_{n}$. Fix $t>0$. By the result for initial conditions in
${\mathcal{H}}_{1}$,

$\displaystyle\min\\{\,0\,,\,{\rm
ess\,inf}\,\phi\,\\}\;\leq\;\min\\{\,0\,,\,\inf_{0\leq y\leq
1}\phi_{n}(y)\,\\}$
$\displaystyle\quad\;\leq\;u^{n}(t,x)\;\leq\;\max\\{\,0\,,\,\sup_{0\leq y\leq
1}\phi_{n}(y)\,\\}\,\leq\,\max\\{\,0\,,\,{\rm ess\,sup}\,\phi\,\\}\;.$

for all $0\leq x\leq 1$. By (A.16), $u^{n}(t)$ converges to $u(t)$ in
${\mathscr{L}}^{\infty}([0,1])$. This completes the proof of (B.3).

Assume that $\phi(x)\leq b$ for some $b>0$. By (B.3), $u(t,x)\leq b$ for all
$t\geq 0$, $0\leq x\leq 1$. Fix $t_{0}>0$, and assume that $\max_{0\leq x\leq
1}u(t_{0},x)=b$. As $b>0$, the boundary conditions imply that the maximum
cannot be attained at the boundary. On the other hand, if it is attained at
the interior, by Theorem 2 of [24, Chapter 3] and by the smoothness of the
solution, $u(t,x)=b$ for all $(t,x)\in(0,t_{0}]\times[0,1]$. This is not
possible at the boundary. Therefore, $\max_{0\leq x\leq 1}u(t_{0},x)<b$. By
the maximum principle, this bound can be extended to all
$(t,x)\in[t_{0},\infty)\times[0,1]$. The same argument applies to the lower
bound.

Assertion (d) follows from Lemma A.3 and the representation of the solutions.
∎

It follows from the previous result that the operator $P^{(R)}_{t}$ is a
contraction in ${\mathscr{L}}^{\infty}([0,1])$: for all $t\geq 0$,
$f\in{\mathscr{L}}^{\infty}([0,1])$,

$\|\,P^{(R)}_{t}f\,\|_{\infty}\;\leq\;\|\,f\,\|_{\infty}\;.$ (B.4)

Recall from (1.5) that we denote by $\bar{\rho}\in{\mathscr{M}}_{\rm ac}$ the
unique stationary solution to the equation (1.1).

######  Definition B.3.

Fix $\gamma\in{\mathscr{L}}^{2}([0,1])$. A function $u$ in
${\mathscr{L}}^{2}([0,T];{\mathcal{H}}^{1})$ is said to be a generalized (or
weak) solution in the cylinder $[0,T]\times[0,1]$ of the equation (1.1) if
$u(t,x)-\bar{\rho}$ is a generalized solution to the initial-boundary problem
(B.2) with initial condition $\gamma-\bar{\rho}$.

Therefore, a function $u$ in ${\mathscr{L}}^{2}([0,T];{\mathcal{H}}^{1})$ is a
generalized solution in the cylinder $[0,T]\times[0,1]$ of the equation (1.1)
if

$\displaystyle\int_{0}^{1}u_{t}\,H_{t}\;dx\;-\;\int_{0}^{1}\gamma\,H_{0}\;dx\;-\;\int_{0}^{t}ds\,\int_{0}^{1}u_{s}\,\partial_{s}H_{s}\;dx=\;-\int_{0}^{t}ds\,\int_{0}^{1}\nabla
u_{s}\,\nabla H_{s}\;dx$
$\displaystyle\quad\;-\;\int_{0}^{t}\Big{\\{}\,\frac{1}{B}\,[\,u_{s}(1)-\beta\,]\,H_{s}(1)\,+\,\frac{1}{A}\,[\,u_{s}(0)-\alpha\,]\,H_{s}(0)\,\Big{\\}}\;ds$

for every $0<t\leq T$, function $H$ in $C^{1,2}([0,T]\times[0,1])$.

######  Theorem B.4.

Fix $\gamma\in{\mathscr{L}}^{2}([0,1])$. There exists a unique generalized
solution to (1.1). The solution is smooth in $(0,\infty)\times[0,1]$ and
satisfies the bounds

$\min\\{\,\alpha\,,\,{\rm
ess\,inf}\,\gamma\,\\}\,\leq\,u(t,x)\,\leq\,\max\\{\,\beta\,,\,{\rm
ess\,sup}\,\gamma\,\\}$ (B.5)

for all $(t,x)\in[0,\infty)\times[0,1]$. Moreover, if
$\gamma\in{\mathscr{M}}_{\rm ac}$, for all $0<t_{0}\leq T$ there exists
$\epsilon>0$ such that $\epsilon\leq u(t,x)\leq 1-\epsilon$ for all
$(t,x)\in[t_{0},\infty)\times[0,1]$. Finally, the solution is continuous in
$[0,\infty)\times[0,1]$ if $\gamma$ belongs to
$C([0,1])\cap{\mathcal{H}}_{1}$.

###### Proof.

The proof of this result is similar to the one of Theorem B.2. ∎

######  Lemma B.5.

Let $\gamma$, $(\gamma_{n}:n\geq 1)$ be a sequence of density profiles in
${\mathscr{M}}_{\rm ac}$. Assume that $\gamma_{n}$ converges to $\gamma$ in
${\mathscr{M}}_{\rm ac}$. Let $u$, $u^{n}$ be the weak solutions to (1.1) with
initial conditions $\gamma$, $\gamma_{n}$, respectively. Then, for all
$t_{0}>0$, $u^{n}(t)$ converges to $u(t)$ in $C^{2}([0,1])$ uniformly in
$t\in[t_{0},\infty)$.

###### Proof.

Fix $t_{0}>0$. By Definition B.3, Theorem B.2.(a) and (A.14), for every $t\geq
0$,

$u^{n}(t)\,-\,u(t)\;=\;P^{(R)}_{t}(\gamma_{n}-\gamma)\;=\;\sum_{k\geq
1}e^{-\lambda_{k}t}\,\langle\gamma_{n}-\gamma\,,\,f_{k}\rangle\,f_{k}\;.$

By this identity and the hypothesis, since $\gamma$, $\gamma_{n}$ are bounded,
$u^{n}(t)$ converges to $u(t)$ in $C([0,1])$, uniformly for $t\geq t_{0}$.
Taking the Laplacian on both sides of this identity produces on the right-hand
side an extra factor $-\,\lambda_{k}$. Hence, $\Delta u^{n}(t)$ converges to
$\Delta u(t)$ in $C([0,1])$, uniformly for $t\geq t_{0}$. Uniform convergence
in $C^{2}([0,1])$ follows from the two previous convergences. ∎

######  Remark B.6.

Fix $k\geq 1$. The same proof yields that, for all $t_{0}>0$, $u^{n}(t)$
converges to $u(t)$ in $C^{2k}([0,1])$, uniformly in $t\in[t_{0},\infty)$.

We conclude this section defining weak solutions to equation (4.3) and stating
a result on existence and uniqueness.

######  Definition B.7.

Fix $\gamma\in{\mathscr{L}}^{1}([0,1])$, $H\in C^{0,1}([0,T]\times[0,1])$. A
function $u$ in ${\mathscr{L}}^{2}([0,T];{\mathcal{H}}^{1})$ is said to be a
generalized, or weak, solution in the cylinder $[0,T]\times[0,1]$ of the
equation (4.3) if

$\displaystyle\int_{0}^{1}u_{t}\,G_{t}\;dx\;-\;\int_{0}^{1}\gamma\,G_{0}\;dx\;-\;\int_{0}^{t}ds\,\int_{0}^{1}u_{s}\,\partial_{s}G_{s}\;dx$
(B.6) $\displaystyle\quad\;=\;\int_{0}^{t}ds\,\int_{0}^{1}\big{\\{}\,-\,\nabla
u_{s}\,\nabla G_{s}\,+\,2\,\sigma(u_{s})\,\nabla H_{s}\,\nabla
G_{s}\,\big{\\}}\;dx$
$\displaystyle\quad\;+\;\int_{0}^{t}\big{\\{}\,{\mathfrak{p}}_{\beta,B}(u_{s}(1),H_{s}(1))\,G_{s}(1)\,+\,{\mathfrak{p}}_{\alpha,A}(u_{s}(0),H_{s}(0))\,G_{s}(0)\,\big{\\}}\;ds$

for every $0<t\leq T$ and function $G$ in $C^{1,2}([0,T]\times[0,1])$.

Next result is taken from [19]

######  Theorem B.8.

Fix $\gamma\in{\mathscr{M}}_{\rm ac}$ and $H$ in $C^{0,1}([0,T]\times[0,1])$.
Then, there exists a unique weak solution to (4.3). Moreover, $0\leq
u(t,x)\leq 1$ a.s. in $[0,T]\times[0,1]$.

Acknowledgements: The last author wishes to thank D. Gabrielli for fruitful
discussions.

## References

  * [1] C. Bahadoran: A quasi-potential for conservation laws with boundary conditions. ArXiv e-prints arXiv:1010.3624v1 (2010)
  * [2] R. Baldasso, O. Menezes, A. Neumann, R. R. Souza: Exclusion process with slow boundary. J. Stat. Phys. 167, 1112–1142 (2017).
  * [3] L. Bertini, A. De Sole, D. Gabrielli, G. Jona–Lasinio, C. Landim: Macroscopic fluctuation theory for stationary non equilibrium state. J. Statist. Phys. 107, 635–675 (2002).
  * [4] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio and C. Landim: Large Deviations for the Boundary Driven Symmetric Simple Exclusion Process. Mathematical Physics, Analysis and Geometry 6: 231-267 (2003).
  * [5] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, C. Landim; Action functional and quasi-potential for the Burgers equation in a bounded interval, Commun. Pure Appl. Math. 64 649–696 (2011).
  * [6] L. Bertini, A. De Sole, D. Gabrielli, G. Jona-Lasinio, C. Landim; Macroscopic Fluctuation Theory. Rev. Modern Phys. 87, 593–636 (2015).
  * [7] L. Bertini, D. Gabrielli, G. Jona–Lasinio, C. Landim: Thermodynamic Transformations of Non-equilibrium States. J. Statist. Phys. 149, 773–802 (2012).
  * [8] L Bertini, C Landim, M Mourragui: Dynamical large deviations for the boundary driven weakly asymmetric exclusion process. Ann. Probab. 37, 2357–2403 (2009)
  * [9] T. Bodineau, B. Derrida, V. Lecomte, F. van Wijland: Long range correlations and phase transitions in non-equilibrium diffusive systems. J. Stat. Phys. 133, 1013–1031 (2008).
  * [10] T. Bodineau and G. Giacomin: From Dynamic to Static Large Deviations in boundary Driven Exclusion Particle Systems. Stochastic Procss. Appl. 110, 67–81 (2004).
  * [11] G. Bunin, Y. Kafri, D. Podolsky: Cusp singularities in boundary-driven diffusive systems.J.Stat.Phys. 152, 112–135 (2013).
  * [12] B. Derrida: Non-equilibrium steady states: fluctuations and large deviations of the density and of the current. J. Stat. Mech. Theory Exp. 2007, P07,023 (2007).
  * [13] B. Derrida: Microscopic versus macroscopic approaches to non-equilibrium systems. J. Stat. Mech. Theory Exp. 2011, P01,030 (2011).
  * [14] B. Derrida, O. Hirschberg, T Sadhu: Large deviations in the symmetric simple exclusion process with slow boundaries. J. Stat. Phys. (2021) doi.org/10.1007/s10955-020-02680-3
  * [15] B. Derrida, J. L. Lebowitz, E. R. Speer: Large deviation of the density profile in the steady state of the open symmetric simple exclusion process, J. Statist. Phys. 107, 599–634 (2002).
  * [16] I. Ekeland, R. Temam: Convex Analysis and Variational Problems, North-Holland, Amsterdam, 1976.
  * [17] J. Farfán: Static large deviations of boundary driven exclusion processes. arXiv:0908.1798.
  * [18] J. Farfán, C. Landim, K. Tsunoda; Static large deviations for a reaction-diffusion model. Probab. Th. Rel. Fields. 174, 49–101 (2019).
  * [19] T. Franco, P. Gonçalves, C. Landim, A. Neumann: Dynamical large deviations for boundary driven symmetric exclusion processes in weak contact with reservoirs. preprint (2021)
  * [20] R. Frassek, C. Giardina, J. Kurchan: Duality and hidden equilibrium in transport models.ArXive-prints arXiv:2004.12796 (2020)
  * [21] C. Kipnis and C. Landim: Scaling limits of interacting particle systems. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Volume 320. Springer-Verlag, Berlin (1999).
  * [22] C. Landim. K.Tsunoda: Hydrostatics and dynamical large deviations for a reaction-diffusion model. Ann. l’Institut Henri Poincaré, Probab. Stat. 54, 51–74 (2018).
  * [23] V. P. Mikhaïlov: Partial Differential Equations, 2nd edition, Nauka, Moscow, 1983.
  * [24] M. H. Protter and H. F. Weinberger: Maximum Principles in Differential Equations Springer–Verlag, New York, 1984
  * [25] W. A. Strauss: Partial Differential Equations: An Introduction John Wiley & Sons, Inc., ISBN 13 978-0470-05456-7, 2008
  * [26] E. Zeidler, Applied Functional Analysis: applications to mathematical physics, Series Applied mathematical sciences, volume 108, Springer-Verlag, ISBN 0-387-94442-7, 1995.
  * [27] E. Zeidler,  Nonlinear Functional Analysis and its Applications. II/A, Linear Monotone Operators and II/B Nonlinear Monotone Operators.  Springer-Verlag, Berlin, 1980\.