text:
Communication complexity

In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines. The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) $$n$$-bit string $$x$$ and $$y$$. The goal is for Alice to compute the value of a certain function, $$f(x, y)$$, that depends on both $$x$$ and $$y$$, with the least amount of communication between them.

While Alice and Bob can always succeed by having Bob send his whole $$n$$-bit string to Alice (who then computes the function $$f$$), the idea here is to find clever ways of calculating $$f$$ with fewer than $$n$$ bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob.

This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts. In VLSI circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed between the different components during a distributed computation. The problem is also relevant in the study of data structures and in the optimization of computer networks. For surveys of the field, see the textbooks by and.

Formal definition
Let $$f: X \times Y \rightarrow Z$$ where we assume in the typical case that $$ X=Y=\{0,1\}^n $$ and $$ Z=\{0,1\}$$. Alice holds an $$n$$-bit string $$x \in X$$ while Bob holds an $$n$$-bit string  $$y \in Y$$. By communicating to each other one bit at a time (adopting some communication protocol which is agreed upon in advance), Alice and Bob wish to compute the value of $$f(x,y)$$ such that at least one party knows the value at the end of the communication. At this point the answer can be communicated back so that at the cost of one extra bit, both parties will know the answer. The worst case communication complexity of this communication problem of computing $$f$$, denoted as $$ D(f) $$, is then defined to be

 * $$ D(f) = $$ minimum number of bits exchanged between Alice and Bob in the worst case.

As observed above, for any function $$f: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$$, we have $$D(f) \leq n$$. Using the above definition, it is useful to think of the function $$f$$ as a matrix $$A$$ (called the input matrix or communication matrix) where the rows are indexed by $$x \in X$$ and columns by $$y \in Y$$. The entries of the matrix are $$A_{x,y}=f(x,y)$$. Initially both Alice and Bob have a copy of the entire matrix $$A$$ (assuming the function $$f$$ is known to both parties). Then, the problem of computing the function value can be rephrased as "zeroing-in" on the corresponding matrix entry. This problem can be solved if either Alice or Bob knows both $$x$$ and $$y$$. At the start of communication, the number of choices for the value of the function on the inputs is the size of matrix, i.e. $$2^{2n}$$. Then, as and when each party communicates a bit to the other, the number of choices for the answer reduces as this eliminates a set of rows/columns resulting in a submatrix of $$A$$.

More formally, a set $$R \subseteq X \times Y$$ is called a (combinatorial) rectangle if whenever $$(x_1,y_1) \in R$$ and $$(x_2,y_2) \in R$$ then $$(x_1,y_2) \in R$$. Equivalently, $$R$$ is a combinatorial rectangle if it can be expressed as $$R = M \times N$$ for some $$M \subseteq X$$ and $$N \subseteq Y$$. Consider the case when $$k$$ bits are already exchanged between the parties. Now, for a particular $$h \in \{0,1\}^k$$, let us define a matrix

 * $$T_{h} = \{ (x, y) : \text{ the }k\text{-bits exchanged on input } (x, y) \text{ is }h\}$$

Then, $$T_{h} \subseteq X \times Y$$, and it is not hard to show that $$T_{h}$$ is a combinatorial rectangle in $$A$$.

Example: EQ
We consider the case where Alice and Bob try to determine whether or not their input strings are equal. Formally, define the Equality function, denoted $$EQ : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$$, by $$EQ(x, y) = 1$$ if $$x = y$$. As we demonstrate below, any deterministic communication protocol solving $$EQ$$ requires $$n$$ bits of communication in the worst case. As a warm-up example, consider the simple case of $$x, y \in \{0, 1\}^3$$. The equality function in this case can be represented by the matrix below. The rows represent all the possibilities of $$x$$, the columns those of $$y$$.

In this table, the function only evaluates to 1 when $$x$$ equals $$y$$ (i.e., on the diagonal). It is also fairly easy to see how communicating a single bit divides someone's possibilities in half. When the first bit of $$y$$ is 1, consider only half of the columns (where $$y$$ can equal 100, 101, 110, or 111).

Theorem: D(EQ) = n
Proof. Assume that $$D(EQ) \leq n-1$$. This means that there exists $$x \neq x'$$ such that $$(x, x)$$ and $$(x', x')$$ have the same communication transcript $$h$$. Since this transcript defines a rectangle, $$f(x, x')$$ must also be 1. By definition $$x \neq x'$$ and we know that equality is only true for $$(a, b)$$ when $$a = b$$. This yields a contradiction.

This technique of proving deterministic communication lower bounds is called the fooling set technique.

Randomized communication complexity
In the above definition, we are concerned with the number of bits that must be deterministically transmitted between two parties. If both the parties are given access to a random number generator, can they determine the value of $$f$$ with much less information exchanged? Yao, in his seminal paper answers this question by defining randomized communication complexity.

A randomized protocol $$R$$ for a function $$f$$ has two-sided error.

\Pr[R(x,y) = 0] > \frac{2}{3}, \textrm{if }\, f(x,y) = 0 $$

\Pr[R(x,y) = 1] > \frac{2}{3}, \textrm{if }\, f(x,y) = 1 $$

A randomized protocol is a deterministic protocol that uses an extra random string in addition to its normal input. There are two models for this: a public string is a random string that is known by both parties beforehand, while a private string is generated by one party and must be communicated to the other party. A theorem presented below shows that any public string protocol can be simulated by a private string protocol that uses O(log n) additional bits compared to the original.

Note that in the probability inequalities above, the outcome of the protocol is understood to depend only on the random string; both strings x and y remain fixed. In other words, if R(x,y) yields g(x,y,r) when using random string r, then g(x,y,r) = f(x,y) for at least 2/3 of all choices for the string r.

The randomized complexity is simply defined as the number of bits exchanged in such a protocol.

Note that it is also possible to define a randomized protocol with one-sided error, and the complexity is defined similarly.

Example: EQ
Returning to the previous example of EQ, if certainty is not required, Alice and Bob can check for equality using only $O(\log n)$ messages. Consider the following protocol: Assume that Alice and Bob both have access to the same random string $$z \in \{0,1\}^n$$. Alice computes $$z \cdot x$$ and sends this bit (call it b) to Bob. (The $$(\cdot)$$ is the dot product in GF(2).) Then Bob compares b to $$z \cdot y$$. If they are the same, then Bob accepts, saying x equals y. Otherwise, he rejects.

Clearly, if $$x = y$$, then $$z \cdot x = z \cdot y$$, so $$Prob_z[Accept] = 1$$. If x does not equal y, it is still possible that $$z \cdot x = z \cdot y$$, which would give Bob the wrong answer. How does this happen?

If x and y are not equal, they must differ in some locations:

 * $$\begin{cases}

x = c_1 c_2 \ldots p  \ldots p'  \ldots x_n \\ y = c_1 c_2 \ldots q  \ldots q'  \ldots y_n \\ z = z_1 z_2 \ldots z_i \ldots z_j \ldots z_n \end{cases}$$

Where $x$ and $y$ agree, $$z_i * x_i = z_i * c_i = z_i * y_i$$ so those terms affect the dot products equally. We can safely ignore those terms and look only at where $x$ and $y$ differ. Furthermore, we can swap the bits $$x_i$$ and $$y_i$$ without changing whether or not the dot products are equal. This means we can swap bits so that $x$ contains only zeros and $y$ contains only ones:

 * $$\begin{cases}

x' = 0  0   \ldots 0   \\ y' = 1  1   \ldots 1   \\ z' = z_1 z_2 \ldots z_{n'} \end{cases}$$

Note that $$z' \cdot x' = 0$$ and $$z' \cdot y' = \Sigma_i z'_i$$. Now, the question becomes: for some random string $$z'$$, what is the probability that $$\Sigma_i z'_i = 0$$? Since each $$z'_i$$ is equally likely to be $0$ or $1$, this probability is just $$1/2$$. Thus, when $x$ does not equal $y$, $$Prob_z[Accept] = 1/2$$. The algorithm can be repeated many times to increase its accuracy. This fits the requirements for a randomized communication algorithm.

This shows that if Alice and Bob share a random string of length n, they can send one bit to each other to compute $$EQ(x,y)$$. In the next section, it is shown that Alice and Bob can exchange only $O(\log n)$ bits that are as good as sharing a random string of length n. Once that is shown, it follows that EQ can be computed in $O(\log n)$ messages.

Example: GH
For yet another example of randomized communication complexity, we turn to an example known as the gap-Hamming problem (abbreviated GH). Formally, Alice and Bob both maintain binary messages, $$x,y \in \{-1, +1\}^n$$ and would like to determine if the strings are very similar or if they are not very similar. In particular, they would like to find a communication protocol requiring the transmission of as few bits as possible to compute the following partial Boolean function,

\text{GH}_n(x, y) := \begin{cases} -1 & \langle x, y \rangle \leq \sqrt{n} \\ +1 & \langle x, y \rangle \geq \sqrt{n}. \end{cases} $$

Clearly, they must communicate all their bits if the protocol is to be deterministic (this is because, if there is a deterministic, strict subset of indices that Alice and Bob relay to one another, then imagine having a pair of strings that on that set disagree in $$\sqrt{n} - 1$$ positions. If another disagreement occurs in any position that is not relayed, then this affects the result of $$ \text{GH}_n(x, y)$$, and hence would result in an incorrect procedure.

A natural question one then asks is, if we're permitted to err $$1/3$$ of the time (over random instances $$ x, y$$ drawn uniformly at random from $$ \{-1, +1\}^n $$), then can we get away with a protocol with fewer bits? It turns out that the answer somewhat surprisingly is no, due to a result of Chakrabarti and Regev in 2012: they show that for random instances, any procedure which is correct at least $$2/3$$ of the time must send $$\Omega(n)$$ bits worth of communication, which is to say essentially all of them.

Public coins versus private coins
Creating random protocols becomes easier when both parties have access to the same random string, known as a shared string protocol. However, even in cases where the two parties do not share a random string, it is still possible to use private string protocols with only a small communication cost. Any shared string random protocol using any number of random string can be simulated by a private string protocol that uses an extra O(log n) bits.

Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error. This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.

Consider some random protocol P with a maximum error rate of 0.1. Let $$R$$ be $$100n$$ strings of length n, numbered $$r_1, r_2, \dots, r_{100n}$$. Given such an $$R$$, define a new protocol $$P'_R$$ which randomly picks some $$r_i$$ and then runs P using $$r_i$$ as the shared random string. It takes O(log 100n) = O(log n) bits to communicate the choice of $$r_i$$.

Let us define $$p(x,y)$$ and $$p'_R(x,y)$$ to be the probabilities that $$P$$ and $$P'_R$$ compute the correct value for the input $$(x,y)$$.

For a fixed $$(x,y)$$, we can use Hoeffding's inequality to get the following equation:

 * $$\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}$$

Thus when we don't have $$(x,y)$$ fixed:

 * $$\Pr_R[\exists (x,y):\ |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1$$

The last equality above holds because there are $$2^{2n}$$ different pairs $$(x,y)$$. Since the probability does not equal 1, there is some $$R_0$$ so that for all $$(x,y)$$:

 * $$|p'_{R_0}(x,y) - p(x,y)| < 0.1$$

Since $$P$$ has at most 0.1 error probability, $$P'_{R_0}$$ can have at most 0.2 error probability.

Collapse of Randomized Communication Complexity
Let's say we additionally allow Alice and Bob to share some resource, for example a pair of entangle particles. Using that ressource, Alice and Bob can correlate their information and thus try to 'collapse' (or 'trivialize') communication complexity in the following sense.

Definition. A resource $$R$$ is said to be "collapsing"'' if, using that resource $$R$$, only one bit of classical communication is enough for Alice to know the evaluation $$f(x,y)$$ in the worst case scenario for any Boolean function $$f$$. ''

The surprising fact of a collapse of communication complexity is that the function $$f$$ can have arbitrarily large entry size, but still the number of communication bit is constant to a single one.

Some resources are shown to be non-collapsing, such as quantum correlations or more generally almost-quantum correlations, whereas on the contrary some other resources are shown to collapse randomized communication complexity, such as the PR-box, or some noisy PR-boxes satisfying some conditions.

Distributional Complexity
One approach to studying randomized communication complexity is through distributional complexity.

Given a joint distribution $$\mu$$ on the inputs of both players, the corresponding distributional complexity of a function $$f$$ is the minimum cost of a deterministic protocol $$R$$ such that $$\Pr[f(x,y) = R(x,y)] \ge 2/3$$, where the inputs are sampled according to $$\mu$$.

Yao's minimax principle (a special case of von Neumann's minimax theorem) states that the randomized communication complexity of a function equals its maximum distributional complexity, where the maximum is taken over all joint distributions of the inputs (not necessarily product distributions!).

Yao's principle can be used to prove lower bounds on the randomized communication complexity of a function: design the appropriate joint distribution, and prove a lower bound on the distributional complexity. Since distributional complexity concerns deterministic protocols, this could be easier than proving a lower bound on randomized protocols directly.

As an example, let us consider the disjointness function DISJ: each of the inputs is interpreted as a subset of $$\{1,\dots,n\}$$, and DISJ($x$,$y$)=1 if the two sets are disjoint. Razborov proved an $$\Omega(n)$$ lower bound on the randomized communication complexity by considering the following distribution: with probability 3/4, sample two random disjoint sets of size $$n/4$$, and with probability 1/4, sample two random sets of size $$n/4$$ with a unique intersection.

Information Complexity
A powerful approach to the study of distributional complexity is information complexity. Initiated by Bar-Yossef, Jayram, Kumar and Sivakumar, the approach was codified in work of Barak, Braverman, Chen and Rao and by Braverman and Rao.

The (internal) information complexity of a (possibly randomized) protocol $R$ with respect to a distribution $μ$ is defined as follows. Let $$(X,Y) \sim \mu$$ be random inputs sampled according to $μ$, and let $Π$ be the transcript of $R$ when run on the inputs $$X,Y$$. The information complexity of the protocol is

\operatorname{IC}_\mu(R) = I(\Pi;Y|X) + I(\Pi;X|Y), $$

where $I$ denotes conditional mutual information. The first summand measures the amount of information that Alice learns about Bob's input from the transcript, and the second measures the amount of information that Bob learns about Alice's input.

The $ε$-error information complexity of a function $f$ with respect to a distribution $μ$ is the infimal information complexity of a protocol for $f$ whose error (with respect to $μ$) is at most $ε$.

Braverman and Rao proved that information equals amortized communication. This means that the cost for solving $n$ independent copies of $f$ is roughly $n$ times the information complexity of $f$. This is analogous to the well-known interpretation of Shannon entropy as the amortized bit-length required to transmit data from a given information source. Braverman and Rao's proof uses a technique known as "protocol compression", in which an information-efficient protocol is "compressed" into a communication-efficient protocol.

The techniques of information complexity enable the computation of the exact (up to first order) communication complexity of set disjointness to be $$1.4923\ldots n$$.

Information complexity techniques have also been used to analyze extended formulations, proving an essentially optimal lower bound on the complexity of algorithms based on linear programming which approximately solve the maximum clique problem.

Omri Weinstein's 2015 survey surveys the subject.

Quantum communication complexity
Quantum communication complexity tries to quantify the communication reduction possible by using quantum effects during a distributed computation.

At least three quantum generalizations of communication complexity have been proposed; for a survey see the suggested text by G. Brassard.

The first one is the qubit-communication model, where the parties can use quantum communication instead of classical communication, for example by exchanging photons through an optical fiber.

In a second model the communication is still performed with classical bits, but the parties are allowed to manipulate an unlimited supply of quantum entangled states as part of their protocols. By doing measurements on their entangled states, the parties can save on classical communication during a distributed computation.

The third model involves access to previously shared entanglement in addition to qubit communication, and is the least explored of the three quantum models.

Nondeterministic communication complexity
In nondeterministic communication complexity, Alice and Bob have access to an oracle. After receiving the oracle's word, the parties communicate to deduce $$f(x,y)$$. The nondeterministic communication complexity is then the maximum over all pairs $$(x,y)$$ over the sum of number of bits exchanged and the coding length of the oracle word.

Viewed differently, this amounts to covering all 1-entries of the 0/1-matrix by combinatorial 1-rectangles (i.e., non-contiguous, non-convex submatrices, whose entries are all one (see Kushilevitz and Nisan or Dietzfelbinger et al.)). The nondeterministic communication complexity is the binary logarithm of the rectangle covering number of the matrix: the minimum number of combinatorial 1-rectangles required to cover all 1-entries of the matrix, without covering any 0-entries.

Nondeterministic communication complexity occurs as a means to obtaining lower bounds for deterministic communication complexity (see Dietzfelbinger et al.), but also in the theory of nonnegative matrices, where it gives a lower bound on the nonnegative rank of a nonnegative matrix.

Unbounded-error communication complexity
In the unbounded-error setting, Alice and Bob have access to a private coin and their own inputs $$(x, y)$$. In this setting, Alice succeeds if she responds with the correct value of $$f(x, y)$$ with probability strictly greater than 1/2. In other words, if Alice's responses have any non-zero correlation to the true value of $$f(x, y)$$, then the protocol is considered valid.

Note that the requirement that the coin is private is essential. In particular, if the number of public bits shared between Alice and Bob are not counted against the communication complexity, it is easy to argue that computing any function has $$O(1)$$ communication complexity. On the other hand, both models are equivalent if the number of public bits used by Alice and Bob is counted against the protocol's total communication.

Though subtle, lower bounds on this model are extremely strong. More specifically, it is clear that any bound on problems of this class immediately imply equivalent bounds on problems in the deterministic model and the private and public coin models, but such bounds also hold immediately for nondeterministic communication models and quantum communication models.

Forster was the first to prove explicit lower bounds for this class, showing that computing the inner product $$\langle x, y \rangle$$ requires at least $$\Omega(n)$$ bits of communication, though an earlier result of Alon, Frankl, and Rödl proved that the communication complexity for almost all Boolean functions $$f: \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$$ is $$\Omega(n)$$.

Lifting
Lifting is a general technique in complexity theory in which a lower bound on a simple measure of complexity is "lifted" to a lower bound on a more difficult measure.

This technique was pioneered in the context of communication complexity by Raz and McKenzie, who proved the first query-to-communication lifting theorem, and used the result to separate the monotone NC hierarchy.

Given a function $$f\colon \{0,1\}^n \to \{0,1\}$$ and a gadget $$g\colon \{0,1\}^a \times \{0,1\}^b \to \{0,1\}$$, their composition $$f \circ g\colon \{0,1\}^{na} \times \{0,1\}^{nb} \to \{0,1\}$$ is defined as follows:

(f \circ g)(x,y) = f(g(x_{1,1} \cdots x_{1,a}, y_{1,1} \cdots y_{1,b}), \dots, g(x_{n,1} \cdots x_{n,a}, y_{n,1} \cdots y_{n,b})). $$

In words, $$x$$ is partitioned into $$n$$ blocks of length $$a$$, and $$y$$ is partitioned into $$n$$ blocks of length $$b$$. The gadget is applied $$n$$ times on the blocks, and the outputs are fed into $$f$$. Diagrammatically:

In this diagram, each of the inputs $$\mathbf{x}_1,\dots,\mathbf{x}_n$$ is $a$ bits long, and each of the inputs $$\mathbf{y}_1,\dots,\mathbf{y}_n$$ is $b$ bits long.

A decision tree of depth $$\Delta$$ for $$f$$ can be translated to a communication protocol whose cost is $$\Delta \cdot D(g)$$: each time the tree queries a bit, the corresponding value of $$g$$ is computed using an optimal protocol for $$g$$. Raz and McKenzie showed that this is optimal up to a constant factor when $$g$$ is the so-called "indexing gadget", in which $$x$$ has length $$c \log n$$ (for a large enough constant $c$), $$y$$ has length $$n^c$$, and $$g(x,y)$$ is the $$x$$-th bit of $$y$$.

The proof of the Raz–McKenzie lifting theorem uses the method of simulation, in which a protocol for the composed function $$f \circ g$$ is used to generate a decision tree for $$f$$. Göös, Pitassi and Watson gave an exposition of the original proof. Since then, several works have proved similar theorems with different gadgets, such as inner product. The smallest gadget which can be handled is the indexing gadget with $$c=1+\epsilon$$. Göös, Pitassi and Watson extended the Raz–McKenzie technique to randomized protocols.

A simple modification of the Raz–McKenzie lifting theorem gives a lower bound of $$\Delta \cdot D(g)$$ on the logarithm of the size of a protocol tree for computing $$f \circ g$$, where $$\Delta$$ is the depth of the optimal decision tree for $$f$$. Garg, Göös, Kamath and Sokolov extended this to the DAG-like setting, and used their result to obtain monotone circuit lower bounds. The same technique has also yielded applications to proof complexity.

A different type of lifting is exemplified by Sherstov's pattern matrix method, which gives a lower bound on the quantum communication complexity of $$f \circ g$$, where $g$ is a modified indexing gadget, in terms of the approximate degree of $f$. The approximate degree of a Boolean function is the minimal degree of a polynomial which approximates the function on all Boolean points up to an additive error of 1/3.

In contrast to the Raz–McKenzie proof which uses the method of simulation, Sherstov's proof takes a dual witness to the approximate degree of $f$ and gives a lower bound on the quantum query complexity of $$f \circ g$$ using the generalized discrepancy method. The dual witness for the approximate degree of $f$ is a lower bound witness for the approximate degree obtained via LP duality. This dual witness is massaged into other objects constituting data for the generalized discrepancy method.

Another example of this approach is the work of Pitassi and Robere, in which an algebraic gap is lifted to a lower bound on Razborov's rank measure. The result is a strongly exponential lower bound on the monotone circuit complexity of an explicit function, obtained via the Karchmer–Wigderson characterization of monotone circuit size in terms of communication complexity.

Open problems
Considering a 0 or 1 input matrix $$M_f=[f(x,y)]_{x,y\in \{0,1\}^n}$$, the minimum number of bits exchanged to compute $$f$$ deterministically in the worst case, $$D(f)$$, is known to be bounded from below by the logarithm of the rank of the matrix $$M_f$$. The log rank conjecture proposes that the communication complexity, $$D(f)$$, is bounded from above by a constant power of the logarithm of the rank of $$M_f$$. Since D(f) is bounded from above and below by polynomials of log rank$$(M_f)$$, we can say D(f) is polynomially related to log rank$$(M_f)$$. Since the rank of a matrix is polynomial time computable in the size of the matrix, such an upper bound would allow the matrix's communication complexity to be approximated in polynomial time. Note, however, that the size of the matrix itself is exponential in the size of the input.

For a randomized protocol, the number of bits exchanged in the worst case, R(f), was conjectured to be polynomially related to the following formula:

 * $$\log \min(\textrm{rank}(M'_f): M'_f\in \mathbb{R}^{2^n\times 2^n}, (M_f - M'_f)_\infty\leq 1/3).$$

Such log rank conjectures are valuable because they reduce the question of a matrix's communication complexity to a question of linearly independent rows (columns) of the matrix. This particular version, called the Log-Approximate-Rank Conjecture, was recently refuted by Chattopadhyay, Mande and Sherif (2019) using a surprisingly simple counter-example. This reveals that the essence of the communication complexity problem, for example in the EQ case above, is figuring out where in the matrix the inputs are, in order to find out if they're equivalent.

Applications
Lower bounds in communication complexity can be used to prove lower bounds in decision tree complexity, VLSI circuits, data structures, streaming algorithms, space–time tradeoffs for Turing machines and more.

Conitzer and Sandholm studied the communication complexity of some common voting rules, which are essential in political and non political organizations. Compilation complexity is a closely related notion, which can be seen as a single-round communication complexity.

title: Communication complexity


text:
Gerhard Armauer Hansen

Gerhard Henrik Armauer Hansen (29 July 1841 – 12 February 1912) was a Norwegian physician, remembered for his identification of the bacterium Mycobacterium leprae in 1873 as the causative agent of leprosy. His distinguished work was recognized at the International Leprosy Congress held at Bergen in 1909.

Life
Hansen was born in Bergen, Norway, and attended the Bergen Cathedral School. He worked at Rikshospitalet in Christiania (now Oslo) and as a doctor in Lofoten. In 1868 Hansen returned to Bergen to study leprosy while working at Lungegård Hospital (Lungegårdshospitalet) with Daniel Cornelius Danielssen, a noted expert.

Leprosy was regarded as largely hereditary or otherwise miasmic in origin. Hansen concluded on the basis of epidemiological studies that leprosy was a specific disease with a specific cause. In 1870–71 Hansen travelled to Bonn and Vienna to gain the training necessary for him to prove his hypothesis. In 1873, he announced the discovery of Mycobacterium leprae in the tissues of all people with the condition, although he did not identify them as bacteria, and received little support. The discovery was made with a "new and better" microscope.

In 1879 Hansen gave tissue samples to Albert Neisser, who then successfully stained the bacteria and announced his findings in 1880, claiming to have discovered the disease-causing organism. There was some dispute between Neisser and Hansen, Hansen as discoverer of the bacillus and Neisser as identifier of it as the etiological agent. Neisser tried to downplay the assistance of Hansen. Hansen's claim was weakened by his failure to produce a pure microbiological culture in an artificial medium, or to prove that the rod-shaped organisms were infectious. Further Hansen had attempted to infect at least one female patient without consent and although no damage was caused, that case ended in court and Hansen lost his post at the hospital.

Hansen remained medical officer for leprosy in Norway and it was through his efforts that the leprosy acts of 1877 and 1885 were passed, leading to a steady decline of the disease in Norway from 1,800 known cases in 1875 to just 575 cases in 1901.

Hansen had had syphilis since the 1860s but died of heart disease. He was an atheist.

Women's rights
He was a co-founder and a board member of the Bergen chapter of the Norwegian Association for Women's Rights, led by his sister, prominent women's rights advocate Amalie Hansen.

Honors

 * Leprosy Museum (Lepramuseet) at St. Jørgen Hospital in Bergen has been dedicated to Hansen.
 * Haukeland University Hospital has established Armauer Hansens hus as a research facility operated by the University of Bergen.
 * In Jerusalem, a 19th-century leprosarium has borne Hansen's name since 1950. It has been reconstructed into an art center while preserving the physician's surname in its title.
 * Armauer Hansen Research Institute (AHRI) in Addis Ababa, Ethiopia under the ministry of Health is named after Hansen. AHRI is a Biomedical research Institute in Ethiopia working in tuberculosis, HIV, malaria, leishmaniasis training, and research.https://ahri.gov.et/

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Gerhard Armauer Hansen


text:
Utrecht (province)

Utrecht, officially the Province of Utrecht (Provincie Utrecht), is a province of the Netherlands. It is located in the centre of the country, bordering the Eemmeer in the north-east, the province of Gelderland in the east and south-east, the province of South Holland in the west and south-west and the province of North Holland in the north-west and north. The province of Utrecht has a population of about 1,388,000 as of January 2023. With a land area of approximately 1484 km2, it is the second smallest province in the country. Apart from its eponymous capital, major cities and towns in the province are Amersfoort, Houten, IJsselstein, Nieuwegein, Veenendaal and Zeist. The busiest railway station in the Netherlands, Utrecht Centraal, is located in the province of Utrecht.

History
The Bishopric of Utrecht was established in 695 when Saint Willibrord was consecrated bishop of the Frisians at Rome by Pope Sergius I. With the consent of the Frankish ruler, Pippin of Herstal, he settled in an old Roman fort in Utrecht. After Willibrord's death the diocese suffered greatly from the incursions of the Vikings. Better times appeared during the reign of the Saxon emperors, who frequently summoned the Bishops of Utrecht to attend the imperial councils and diets. In 1024 the bishops were made Princes of the Holy Roman Empire and the new Prince-Bishopric of Utrecht was formed. In 1122, with the Concordat of Worms, the Emperor's right of investiture was annulled, and the cathedral chapter received the right to elect the bishop. It was, however, soon obligated to share this right with the four other collegiate chapters in the city. The Counts of Holland and Guelders, between whose territories the lands of the Bishops of Utrecht lay, also sought to acquire influence over the filling of the episcopal see. This often led to disputes and consequently the Holy See frequently interfered in the election. After the middle of the 14th century the popes repeatedly appointed the bishop directly without regard to the five chapters.

During the Hook and Cod Wars, Utrecht was fought over by forces of the Duke of Burgundy leading to the First Utrecht Civil War (1470–1474) and Second Utrecht Civil War (1481–1483).

In 1527, the Bishop sold his territories, and thus his secular authority, to Holy Roman Emperor Charles V and the principality became an integral part of the Habsburg dominions, which already included most other Dutch provinces. The chapters transferred their right of electing the bishop to Charles V and his government, a measure to which Pope Clement VII gave his consent, under political pressure after the Sack of Rome. However, the Habsburg rule did not last long, as Utrecht joined in the Dutch Revolt against Charles' successor Philip II in 1579, becoming a part of the Dutch Republic.

In World War II, Utrecht was held by German forces until the general capitulation of the Germans in the Netherlands on May 5, 1945. It was occupied by Canadian Allied forces on May 7, 1945. The towns of Oudewater, Woerden, Vianen and Leerdam were transferred from the province of South Holland to Utrecht in 1970, 1989, 2002 and 2019 respectively. In February 2011, Utrecht, together with the provinces of North Holland and Flevoland, showed a desire to investigate the feasibility of a merger between the three provinces. This has been positively received by the Dutch cabinet, for the desire to create one Randstad province has already been mentioned in the coalition agreement. The province of South Holland, part of the Randstad urban area, visioned to be part of the Randstad province, and very much supportive of the idea of a merger into one province, is not named. With or without South Holland, if created, the new province would be the largest in the Netherlands in both area and population.

Geography
In the east of Utrecht lies the Utrecht Hill Ridge (Dutch: Utrechtse Heuvelrug), a chain of hills left as lateral moraine by tongues of glacial ice after the Saline glaciation that preceded the last ice age. Because of the scarcity of nutrients in the fast-draining sandy soil, the greatest part of a landscape that was formerly heath has been planted with pine plantations. The south of the province is a river landscape. The west consists mostly of meadows. In the north are big lakes formed by the digging of peat from bogs formed after the last ice age.

Nature

One of the most attractive natural areas in the province is the Vechtstreek ("Vecht region"), situated on either side of the Vecht river.

An international nature conservation organisation that has settled the head office of its Netherlands branch in this province (at Zeist) is the WWF.

"Natuur en Milieu" ("Nature and Environment") is a national nature protection organisation whose head office is in this province (at Utrecht city).

Municipalities
The Province of Utrecht is divided into 26 municipalities.

 * Amersfoort
 * Baarn
 * Bunnik
 * Bunschoten
 * De Bilt
 * De Ronde Venen
 * Eemnes
 * Houten
 * IJsselstein
 * Leusden
 * Lopik
 * Montfoort
 * Nieuwegein
 * Oudewater
 * Renswoude
 * Rhenen
 * Soest
 * Stichtse Vecht
 * Utrecht
 * Utrechtse Heuvelrug
 * Veenendaal
 * Vianen
 * Vijfheerenlanden
 * Wijk bij Duurstede
 * Woerden
 * Woudenberg
 * Zeist

Religion
In 2015, 20.3% of the population belonged to the Protestant Church in the Netherlands, while 13.2% were Roman Catholic, 6.6% belonged to other churches or faiths, and 5.6% were Muslim. Over half of the population (54.3%) identified as non-religious.

Economy
The Gross domestic product (GDP) of the region was 71.5 billion € in 2018, accounting for 9.2% of the Netherlands economic output. GDP per capita adjusted for purchasing power was 47,900 € or 159% of the EU27 average in the same year.

Notable residents

 * Pope Adrian VI (1459–1523), the only Dutch pope.
 * C. H. D. Buys Ballot (1817–1890), Dutch chemist and meteorologist.
 * Mohamed Ihattaren (born 2002), Dutch professional footballer
 * Piet Mondrian (1872–1944), Dutch painter
 * Gerrit Rietveld (1888–1964), Dutch furniture designer and architect
 * Marco van Basten (born 1964), Dutch football manager
 * Theo van Doesburg (1883–1931), Dutch artist

title: Utrecht (province)


text:
Utrecht

Utrecht (, , Utrecht dialect: Ut(e)reg ) is the fourth-largest city of the Netherlands, as well as the capital and the most populous city of the province of Utrecht. The municipality of Utrecht is located in the eastern part of the Randstad conurbation, in the very centre of mainland Netherlands, and includes Haarzuilens, Vleuten and De Meern. It has a population of 361,699 as of.

Utrecht's ancient city centre features many buildings and structures, several dating as far back as the High Middle Ages. It has been the religious centre of the Netherlands since the 8th century. In 1579, the Union of Utrecht was signed in the city to lay the foundations for the Dutch Republic. Utrecht was the most important city in the Netherlands until the Dutch Golden Age, when it was surpassed by Amsterdam as the country's cultural centre and most populous city.

Utrecht is home to Utrecht University, the largest university in the Netherlands, as well as several other institutions of higher education. Due to its central position within the country, it is an important hub for both rail and road transport; it has the busiest train station in the Netherlands, Utrecht Centraal. It has the second-highest number of cultural events in the Netherlands, after Amsterdam. In 2012, Lonely Planet included Utrecht in the top 10 of the world's unsung places.

Origins (before 650 CE)
Although there is some evidence of earlier inhabitation in the region of Utrecht, dating back to the Stone Age (app. 2200 BCE) and settling in the Bronze Age (app. 1800–800 BCE), the founding date of the city is usually related to the construction of a Roman fortification (castellum), probably built in around 50 CE. A series of such fortresses were built after the Roman emperor Claudius decided the empire should not expand further north. To consolidate the border, the Limes Germanicus defense line was constructed along the main branch of the river Rhine, which at that time traversed a more northern route (now known as the Kromme Rijn) compared to today's Rhine flow. These fortresses were designed to house a cohort of about 500 Roman soldiers. Near the fort, settlements grew that housed artisans, traders and soldiers' wives and children.

In Roman times, the name of the Utrecht fortress was simply Traiectum, denoting its location at a possible Rhine crossing. Traiectum became Dutch Trecht; with the U from Old Dutch "uut" (downriver) added to distinguish U-trecht from Maas-tricht, on the river Meuse. In 11th-century official documents, it was Latinized as Ultra Traiectum. Around the year 200, the wooden walls of the fortification were replaced by sturdier tuff stone walls, remnants of which are still to be found below the buildings around Dom Square.

From the middle of the 3rd century, Germanic tribes regularly invaded the Roman territories. After around 275 the Romans could no longer maintain the northern border, and Utrecht was abandoned. Little is known about the period from 270 to 650. Utrecht is first spoken of again several centuries after the Romans left. Under the influence of the growing realms of the Franks, during Dagobert I's reign in the 7th century, a church was built within the walls of the Roman fortress. In ongoing border conflicts with the Frisians, this first church was destroyed.

Centre of Christianity in the Netherlands (650–1579)

By the mid-7th century, British, English and Irish missionaries set out to convert the Frisians. Pope Sergius I appointed their leader, Saint Willibrordus, as bishop of the Frisians. The tenure of Willibrordus is generally considered to be the beginning of the Bishopric of Utrecht. In 723, the Frankish leader Charles Martel bestowed the fortress in Utrecht and the surrounding lands as the base of the bishops. From then on Utrecht became one of the most influential seats of power for the Catholic Church in the Netherlands. The archbishops of Utrecht were based at the uneasy northern border of the Carolingian Empire. In addition, the city of Utrecht had competition from the nearby trading centre Dorestad. After the fall of Dorestad around 850, Utrecht became one of the most important cities in the Netherlands. The importance of Utrecht as a centre of Christianity is illustrated by the election of the Utrecht-born Adriaan Florenszoon Boeyens as pope in 1522 (the last non-Italian pope before John Paul II).

Prince-bishops
When the Frankish rulers established the system of feudalism, the Bishops of Utrecht came to exercise worldly power as prince-bishops. The territory of the bishopric not only included the modern province of Utrecht (Nedersticht, 'lower Sticht'), but also extended to the northeast. The feudal conflict of the Middle Ages heavily affected Utrecht. The prince-bishopric was involved in almost continuous conflicts with the Counts of Holland and the Dukes of Guelders. The Veluwe region was seized by Guelders, but large areas in the modern province of Overijssel remained as the Oversticht.

Religious buildings
Several churches and monasteries were built inside, or close to, the city of Utrecht. The most dominant of these was the Cathedral of Saint Martin, inside the old Roman fortress. The construction of the present Gothic building was begun in 1254 after an earlier romanesque construction had been badly damaged by fire. The choir and transept were finished from 1320 and were followed then by the ambitious Dom tower. The last part to be constructed was the central nave, from 1420. By that time, however, the age of the great cathedrals had come to an end and declining finances prevented the ambitious project from being finished, the construction of the central nave being suspended before the planned flying buttresses could be finished. Besides the cathedral there were four collegiate churches in Utrecht: St. Salvator's Church (demolished in the 16th century), on the Dom square, dating back to the early 8th century. Saint John (Janskerk), originating in 1040; Saint Peter, building started in 1039 and Saint Mary's church building started around 1090 (demolished in the early 19th century, cloister survives). Besides these churches, the city housed St. Paul's Abbey, the 15th-century beguinage of St. Nicholas, and a 14th-century chapter house of the Teutonic Knights.

Besides these buildings which belonged to the bishopric, an additional four parish churches were constructed in the city: the Jacobikerk (dedicated to Saint James), founded in the 11th century, with the current Gothic church dating back to the 14th century; the Buurkerk (Neighbourhood-church) of the 11th-century parish in the centre of the city; Nicolaichurch (dedicated to Saint Nicholas), from the 12th century, and the 13th-century Geertekerk (dedicated to Saint Gertrude of Nivelles).

City of Utrecht
Its location on the banks of the river Rhine allowed Utrecht to become an important trade centre in the Northern Netherlands. The growing town was granted city rights by Henry V at Utrecht on 2 June 1122. When the main flow of the Rhine moved south, the old bed which still flowed through the heart of the town became ever more canalized; and the wharf system was built as an inner city harbour system. On the wharfs, storage facilities (werfkelders) were built, on top of which the main street, including houses, was constructed. The wharfs and the cellars are accessible from a platform at water level with stairs descending from the street level to form a unique structure. The relations between the bishop, who controlled many lands outside of the city, and the citizens of Utrecht was not always easy. The bishop, for example dammed the Kromme Rijn at Wijk bij Duurstede to protect his estates from flooding. This threatened shipping for the city and led the city of Utrecht to commission a canal to ensure access to the town for shipping trade: the Vaartse Rijn, connecting Utrecht to the Hollandse IJssel at IJsselstein.

The end of independence
In 1528 the bishop lost secular power over both Neder- and Oversticht—which included the city of Utrecht—to Charles V, Holy Roman Emperor. Charles V combined the Seventeen Provinces (the current Benelux and the northern parts of France) as a personal union. This ended the prince-bishopric of Utrecht, as the secular rule was now the lordship of Utrecht, with the religious power remaining with the bishop, although Charles V had gained the right to appoint new bishops. In 1559 the bishopric of Utrecht was raised to archbishopric to make it the religious centre of the Northern ecclesiastical province in the Seventeen Provinces.

The transition from independence to a relatively minor part of a larger union was not easily accepted. To quell uprisings, Charles V struggled to exert his power over the city's citizens who had struggled to gain a certain level of independence from the bishops and were not willing to cede this to their new lord. The heavily fortified castle Vredenburg was built to house a large garrison whose main task was to maintain control over the city. The castle would last less than 50 years before it was demolished in an uprising in the early stages of the Dutch Revolt.

Republic of the Netherlands (1579–1806)

In 1579 the northern seven provinces signed the Union of Utrecht treaty (Dutch: Unie van Utrecht), in which they decided to join forces against Spanish rule. The Union of Utrecht is seen as the beginning of the Dutch Republic. In 1580, the new and predominantly Protestant state abolished the bishoprics, including the archbishopric of Utrecht. The stadtholders disapproved of the independent course of the Utrecht bourgeoisie and brought the city under much more direct control of the republic, shifting the power towards its dominant province Holland. This was the start of a long period of stagnation of trade and development in Utrecht. Utrecht remained an atypical city in the new republic being about 40% Catholic in the mid-17th century, and even more so among the elite groups, who included many rural nobility and gentry with town houses there.

The fortified city temporarily fell to the French invasion in 1672 (the Disaster Year, Dutch: Rampjaar). The French invasion was stopped just west of Utrecht at the Old Hollandic Waterline. In 1674, only two years after the French left, the centre of Utrecht was struck by a tornado. The halt to building before construction of flying buttresses in the 15th century now proved to be the undoing of the cathedral of St Martin church's central section which collapsed, creating the current Dom square between the tower and choir. In 1713, Utrecht hosted one of the first international peace negotiations when the Treaty of Utrecht settled the War of the Spanish Succession. Beginning in 1723, Utrecht became the centre of the non-Roman Old Catholic Churches in the world.

Modern history (1815–present)
In the early 19th century, the role of Utrecht as a fortified town had become obsolete. The fortifications of the Nieuwe Hollandse Waterlinie were moved east of Utrecht. The town walls could now be demolished to allow for expansion. The moats remained intact and formed an important feature of the Zocher plantsoen, an English style landscape park that remains largely intact today. Growth of the city increased when, in 1843, a railway connecting Utrecht to Amsterdam was opened. After that, Utrecht gradually became the main hub of the Dutch railway network. With the industrial revolution finally gathering speed in the Netherlands and the ramparts taken down, Utrecht began to grow far beyond its medieval centre. When the Dutch government allowed the bishopric of Utrecht to be reinstated by Rome in 1853, Utrecht became the centre of Dutch Catholicism once more. From the 1880s onward, neighbourhoods such as Oudwijk, Wittevrouwen, Vogelenbuurt to the East, and Lombok to the West were developed. New middle-class residential areas, such as Tuindorp and Oog in Al, were built in the 1920s and 1930s. During this period, several Jugendstil houses and office buildings were built, followed by Rietveld who built the Rietveld Schröder House (1924), and Dudok's construction of the city theatre (1941).

During World War II, Utrecht was held by German forces until the general German surrender of the Netherlands on 5 May 1945. British and Canadian troops that had surrounded the city entered it after that surrender, on 7 May 1945. Following the end of World War II, the city grew considerably when new neighbourhoods such as Overvecht, Kanaleneiland, and Lunetten were built. Around 2000, the Leidsche Rijn housing area was developed as an extension of the city to the west.

The area surrounding Utrecht Centraal railway station and the station itself were developed following modernist ideas of the 1960s, in a brutalist style. This development led to the construction of the shopping mall, the music centre Vredenburg (Hertzberger, 1979), and conversion of part of the ancient canal structure into a highway (Catherijnebaan). Protest against further modernisation of the city centre followed even before the last buildings were finalised. In the early 21st century, the whole area is undergoing change again. The redeveloped music centre TivoliVredenburg opened in 2014 with the original Vredenburg and Tivoli concert and rock and jazz halls brought together in a single building.

Climate
Utrecht experiences a temperate oceanic climate (Köppen: Cfb) similar to all of the Netherlands.

Demographics
Utrecht city had a population of 361,924 in 2022. It is a growing municipality and projections are that the population will surpass 392,000 by 2025. As of November 2019, the city of Utrecht has a population of 357,179.

Utrecht has a young population, with many inhabitants in the age category from 20 and 30 years, due to the presence of a large university. About 52% of the population is female, 48% is male. The majority of households (52.5%) in Utrecht are single-person households. About 29% of people living in Utrecht are either married, or have another legal partnership. About 3% of the population of Utrecht is divorced.

Inhabitants by origin
For 62.8% of the population of Utrecht both parents were born in the Netherlands. Approximately 12.4% of the population consists of people with a recent migration background from Western countries, while 24.8% of the population has at least one parent who is of 'non-Western origin' (8.8% from Morocco, 4% Turkey, 3% Surinam and Dutch Caribbean and 9.1% of other countries).

Religion
Utrecht has been the religious centre of the Netherlands since the 8th century. Currently it is the see of the Metropolitan Archbishop of Utrecht, the most senior Dutch Roman Catholic leader. His ecclesiastical province covers the whole kingdom.

Utrecht is also the see of the archbishop of the Old Catholic Church, titular head of the Union of Utrecht, and the location of the offices of the Protestant Church in the Netherlands, the main Dutch Protestant church.

As of 2013, the largest religion is Christianity with 28% of the population being Christian, followed by Islam with 9.9% in 2016 and Hinduism with 0.8%.

Population centres and agglomeration
The city of Utrecht is subdivided into 10 city quarters, all of which have their own neighbourhood council and service centre for civil affairs.

 * 1) Binnenstad
 * 2) Oost
 * 3) Leidsche Rijn
 * 4) West
 * 5) Overvecht
 * 6) Zuid
 * 7) Noordoost
 * 8) Zuidwest
 * 9) Noordwest
 * 10) Vleuten-De Meern

Utrecht is the centre of a densely populated area, a fact which makes concise definitions of its agglomeration difficult, and somewhat arbitrary. The smaller Utrecht agglomeration of continuously built-up areas counts some 420,000 inhabitants and includes Nieuwegein, IJsselstein and Maarssen. It is sometimes argued that the close by municipalities De Bilt, Zeist, Houten, Vianen, Driebergen-Rijsenburg (Utrechtse Heuvelrug), and Bunnik should also be counted towards the Utrecht agglomeration, bringing the total to 640,000 inhabitants. The larger region, including slightly more remote cities such as Woerden and Amersfoort, counts up to 820,000 inhabitants.

Cityscape
Utrecht's cityscape is dominated by the Dom Tower, the tallest belfry in the Netherlands and originally part of the Cathedral of Saint Martin. An ongoing debate is over whether any building in or near the centre of town should surpass the Dom Tower in height (112 m). Nevertheless, some tall buildings are now being constructed that will become part of the skyline of Utrecht. The second-tallest building of the city, the Rabobank-tower, was completed in 2010 and stands 105 m tall. Two antennas will increase that height to 120 m. Two other buildings were constructed around the Nieuw Galgenwaard stadium (2007). These buildings, the 'Kantoortoren Galghenwert' and 'Apollo Residence', stand 85.5 m and 64.5 m high, respectively. The former Utrecht Main Post Office, built in 1924, is still in the city centre at Neude square, but is now serving as library, see also Utrecht Post Office.

Another landmark is the old centre and the canal structure in the inner city. The Oudegracht is a curved canal, partly following the ancient main branch of the Rhine. It is lined with the unique wharf-basement structures that create a two-level street along the canals. The inner city has largely retained its medieval structure, and the moat ringing the old town is largely intact. In the 1970s part of the moat was converted into a motorway. It was then converted back into a waterway, the work being finished in 2020.

Because of the role of Utrecht as a fortified city, construction outside the medieval centre and its city walls was restricted until the 19th century. Surrounding the medieval core there is a ring of late-19th- and early-20th-century neighbourhoods, with newer neighbourhoods positioned farther out. The eastern part of Utrecht remains fairly open. The Dutch Water Line, moved east of the city in the early 19th century, required open lines of fire, thus prohibiting all permanent constructions until the middle of the 20th century on the east side of the city.

Due to the past importance of Utrecht as a religious centre, several monumental churches were erected, many of which have survived. Most prominent is the Dom Church. Other notable churches include the romanesque St Peter's and St John's churches; the gothic churches of St James and St Nicholas; and the Buurkerk, now converted into a museum for automatically playing musical instruments.

Public transport
Because of its central location, Utrecht is well connected to the rest of the Netherlands and has a well-developed public transport network.

Heavy rail
Utrecht Centraal is the main railway station of Utrecht and is the largest in the country. There are regular intercity services to all major Dutch cities, including direct services to Schiphol Airport. Utrecht Centraal is a station on the night service, providing an all-night service to (among others) Schiphol Airport, Amsterdam and Rotterdam, seven days a week. International InterCityExpress (ICE) services to Germany through Arnhem call at Utrecht Centraal. Regular local trains to all areas surrounding Utrecht also depart from Utrecht Centraal; and service several smaller stations: Utrecht Lunetten; Utrecht Vaartsche Rijn; Utrecht Overvecht; Utrecht Leidsche Rijn; Utrecht Terwijde; Utrecht Zuilen and Vleuten. A former station Utrecht Maliebaan closed in 1939 and has since been converted into the Dutch Railway Museum.

Utrecht is the location of the headquarters of Nederlandse Spoorwegen (English: Dutch Railways), the largest rail operator in the Netherlands, and ProRail, the state-owned company responsible for the construction and maintenance of the country's rail infrastructure.

Light rail
The Utrecht sneltram is a light rail scheme running southwards from Utrecht Centraal to the suburbs of IJsselstein, Kanaleneiland, Lombok and Nieuwegein. The sneltram began operations in 1983 and is currently operated by the private transport company Qbuzz. On 16 December 2019 the new tram line to the Uithof started operating, creating a direct mass transit connection from the central station to the main Utrecht university campus.

Bus transport
The main local and regional bus station of Utrecht is located adjacent to Utrecht Centraal railway station, at the East and West entrances. Due to large-scale renovation and construction works at the railway station, the station's bus stops are changing frequently. As a general rule, westbound buses depart from the bus station on the west entrance, other buses from the east side station. Local buses in Utrecht are operated by Qbuzz; its services include a high-frequency service to the Uithof university district. The local bus fleet is one of Europe's cleanest, using only buses compliant with the Euro-VI standard as well as electric buses for inner-city transport. Regional buses from the city are operated by Arriva and Connexxion.

The Utrecht Centraal railway station is also served by the pan-European services of Eurolines. Furthermore, it acts as departure and arrival place of many coach companies serving holiday resorts in Spain and France—and during winter in Austria and Switzerland.

Cycling
Like most Dutch cities, Utrecht has an extensive network of cycle paths, making cycling safe and popular. 33 % of journeys within the city are by bicycle, more than any other mode of transport. (Cars, for example, account for 30% of trips). Bicycles are used by young and old people, and by individuals and families. They are mostly traditional, upright, steel-framed bicycles, with few gears. There are also bucket bikes for carrying cargo such as groceries or small children. Thanks in part to the access provided by bicycles, 100% of the population lives in a 15-minute city and more than 90% can get to the major destination types within 10 minutes. In 2014, the city council decided to build the world's largest bicycle parking station, near the Central Railway Station. This three-floor construction will cost an estimated €48 million and will hold 12,500 bicycles. The bicycle parking station was finally opened on 19 August 2019.

Road transport
Utrecht is well-connected to the Dutch road network. Two of the most important major roads serve the city of Utrecht: the A12 and A2 motorways connect Amsterdam, Arnhem, The Hague and Maastricht, as well as Belgium and Germany. Other major motorways in the area are the Almere–Breda A27 and the Utrecht–Groningen A28. Due to the increasing traffic and the ancient city plan, traffic congestion is a common phenomenon in and around Utrecht, causing elevated levels of air pollutants. This has led to a passionate debate in the city about the best way to improve the city's air quality.

Shipping
Utrecht has an industrial port located on the Amsterdam-Rijnkanaal. The container terminal has a capacity of 80,000 containers a year. In 2003, the port facilitated the transport of four million tons of cargo; mostly sand, gravel, fertiliser and fodder. Additionally, some tourist boat trips are organised from various places on the Oudegracht; and the city is connected to touristic shipping routes through sluices.

Economy

Production industry constitutes a small part of the economy of Utrecht. The economy of Utrecht depends for a large part on the several large institutions located in the city. It is the centre of the Dutch railway network and the location of the head office of Nederlandse Spoorwegen. ProRail is headquartered in  (The Inkwell), the largest brick building in the Netherlands (the "UFO" featured on its façade stems from an art program in 2000). Rabobank, a large bank, has its headquarters in Utrecht.

Utrecht is also informally considered the "capital" of the Dutch games industry. It was named by Business Finland in 2023 as one of several capitals for the European games industry as a whole. Utrecht's influence in this field was caused by video game development courses at its universities, which were the first such courses in Europe when launched in 2002. Since 2008 Utrecht has also been home to the studio incubator program Dutch Game Garden, which has launched a number of studios in the area. By 2014 the program had created 200 jobs. Utrecht is also home to Nixxes Software (a PlayStation Studios subsidiary) as well as Sokpop Collective.

Education

Utrecht hosts several large institutions of higher education. The most prominent of these is Utrecht University (est. 1636), the largest university of the Netherlands with 30,449 students. The university is partially based in the inner city as well as in the Uithof campus area, on the east side of the city. According to Shanghai Jiaotong University's university ranking in 2014, it is the 57th-best university in the world. Utrecht also houses the much smaller University of Humanistic Studies, which houses about 400 students.

Utrecht is home of one of the locations of TIAS School for Business and Society, focused on post-experience management education and the largest management school of its kind in the Netherlands. In 2008, its executive MBA program was rated the 24th best program in the world by the Financial Times.

Utrecht is also home to two other large institutions of higher education: the vocational university Hogeschool Utrecht (37,000 students), with locations in the city and the Uithof campus; and the HKU Utrecht School of the Arts (3,000 students).

There are many schools for primary and secondary education, allowing parents to select from different philosophies and religions in the school as is inherent in the Dutch school system.

Culture

Utrecht city has an active cultural life, and in the Netherlands is second only to Amsterdam. There are several theatres and theatre companies. The 1941 main city theatre was built by Dudok. In addition to theatres, there is a large number of cinemas including three arthouse cinemas. Utrecht is host to the international Early Music Festival (Festival Oude Muziek, for music before 1800) and the Netherlands Film Festival. The city has an important classical music hall Vredenburg (1979 by Herman Hertzberger). Its acoustics are considered among the best of the 20th-century original music halls. The original Vredenburg music hall has been redeveloped as part of the larger station area redevelopment plan and in 2014 gained additional halls that allowed its merger with the rock club Tivoli and the SJU jazzpodium. There are several other venues for music throughout the city. Young musicians are educated in the conservatory, a department of the Utrecht School of the Arts. There is a specialised museum of automatically playing musical instruments.

There are many art galleries in Utrecht. There are also several foundations to support art and artists. Training of artists is done at the Utrecht School of the Arts. The Centraal Museum has many exhibitions on the arts, including a permanent exhibition on the works of Utrecht resident illustrator Dick Bruna, who is best known for creating Miffy ("Nijntje", in Dutch). BAK, [Dutch: "Basis voor Actuele Kunst," Basis for Contemporary Art] offers contemporary art exhibitions and public events, as well as a Fellowship program for practitioners involved in contemporary arts, theory and activisms. Although street art is illegal in Utrecht, the Utrechtse Kabouter, a picture of a gnome with a red hat, became a common sight in 2004. Utrecht also houses one of the landmarks of modern architecture, the 1924 Rietveld Schröder House, which is listed on UNESCO's World Heritage Sites.

Every Saturday, a paviour adds another letter to The Letters of Utrecht, an endless poem in the cobblestones of the Oude Gracht in Utrecht. With the Letters, Utrecht has a social sculpture as a growing monument created for the benefit of future people.

To promote culture, Utrecht city organizes cultural Sundays. During a thematic Sunday, several organisations create a program which is open to everyone without, or with a substantially reduced, admission fee. There are also initiatives for amateur artists. The city subsidises an organisation for amateur education in arts aimed at all inhabitants (Utrechts Centrum voor de Kunsten), as does the university for its staff and students. Additionally there are also several private initiatives. The city council provides coupons for discounts to inhabitants who receive welfare to be used with many of the initiatives.

In 2017, Utrecht was named as a UNESCO City of Literature. In 2025 the national literature museum will move from the Hague to Utrecht.

Sports
Utrecht is home to the premier league (professional) football club FC Utrecht, which plays in Stadium Nieuw Galgenwaard. It is also the home of Kampong, the largest (amateur) sportsclub in the Netherlands (4,500 members), SV Kampong. Kampong features field hockey, association football, cricket, tennis, squash and boules. Kampong's men and women top hockey squads play in the highest Dutch hockey league, the Rabohoofdklasse. Utrecht is also home to baseball and softball club UVV, which plays in the highest Dutch baseball league: de Hoofdklasse. Utrecht's waterways are used by several rowing clubs. Viking is a large club open to the general public, and the student clubs Orca and Triton compete in the Varsity each year.

In July 2013, Utrecht hosted the European Youth Olympic Festival, in which more than 2,000 young athletes competed in nine different Olympic sports. In July 2015, Utrecht hosted the Grand Départ and first stage of the Tour de France.

Museums
Utrecht has several smaller and larger museums. Many of those are located in the southern part of the old town, the Museumkwartier.
 * , located at the Oudegracht and closed since 15 June 2017, this museum had a small exhibit of Australian Aboriginal Art
 * BAK, basis voor actuele kunst, an international platform for theoretically-informed, politically driven art and experimental research
 * Centraal Museum, located in the MuseumQuarter, this municipal museum has a large collection of art, design, and historical artifacts;
 * , art of Centraal Museum on this separate location is dedicated to Miffy creator Dick Bruna.
 * Duitse Huis has a collection of historical items including many charters with seals dating from as far back as the early 13th century and a collection of medieval coins.
 * Museum Catharijneconvent, Museum of the Catholic Church shows the history of Christian culture and arts in the Netherlands;
 * Museum Speelklok National Museum in the centre of the city, displays several centuries of mechanical musical instruments;
 * Railway Museum (Nederlands Spoorwegmuseum) Railway sponsored museum on the history of the Dutch railways;
 * Utrecht Archives, are located at Hamburgerstraat 28 in Utrecht;
 * Utrecht University museum includes the ancient botanical garden;
 * Sonnenborgh Observatory observatory and museum that regularly hosts lectures on astronomy, located at Zonnenburg 2 in Utrecht;
 * museum for the grocer's shop where people can buy old-fashioned food and non-food items, located at Hoogt 6 in Utrecht.
 * museum for the grocer's shop where people can buy old-fashioned food and non-food items, located at Hoogt 6 in Utrecht.

Music and events
The city has several music venues such as TivoliVredenburg, Tivoli De Helling, ACU, Moira, EKKO, dB's and RASA. Utrecht hosts the yearly Utrecht Early Music Festival (Festival Oude Muziek). Several Editions of the Thunderdome, a large gabber music event, have been held in Jaarbeurs Utrecht. The city also hosts Trance Energy there. Every summer there used to be the Summer Darkness festival, which celebrated goth culture and music. In November the Le Guess Who? festival, focused on indie rock, art rock and experimental rock, takes place in many of the city's venues.

Theatre
There are two main theatres in the city, the and the. De Parade, a travelling theatre festival, performs in Utrecht in summer. The city also hosts the yearly Festival aan de Werf which offers a selection of contemporary international theatre, together with visual arts, public art and music.

Notable people from Utrecht

 * See also the category People from Utrecht

Over the ages famous people have been born and/or raised in Utrecht. Among the most famous Utrechters are:
 * Pope Adrian VI (1459–1523), head of the Catholic Church
 * Louis Andriessen (1939–2021), composer
 * Marco van Basten (born 1964), football player
 * Dick Bruna (1927–2017), writer and illustrator (Miffy)
 * C.H.D. Buys Ballot (1817–1890), meteorologist (Buys-Ballot's law)
 * Theo van Doesburg (1883–1931), painter and artist (De Stijl movement)
 * Karel Doorman (1889–1942), Rear Admiral (Battle of the Java Sea)
 * Paul Fentener van Vlissingen (1941–2006), businessman and philanthropist
 * Anton Geesink (1934–2010), judoka, first non-Japanese worldchampion Judo
 * Rijk de Gooyer (1925–2011), actor, writer, comedian and singer
 * Sylvia Kristel (1952–2012), actress (Emmanuelle)
 * Gerrit Rietveld (1888–1964), designer and architect (De Stijl movement)
 * Dafne Schippers (born 1992), sprinter/heptathlon Olympian
 * Herman van Veen (born 1945), actor, musician, singer-songwriter and author of Alfred J. Kwak
 * Wil Velders-Vlasblom (1930–2019), first female alderman in Utrecht
 * Jason Wilnis (born 1990), mixed martial artist and former kickboxing Glory middleweight champion
 * Jurriën Timber (born 2001), football player for Premier League side Arsenal, with 15 international caps for The Dutch National Team

Twin towns
Utrecht is twinned with:
 * León, Nicaragua
 * 🇨🇿 Brno, Czech Republic
 * Pekanbaru, Indonesia
 * previously 🇩🇪 Hannover, Germany, between 1970 and 1976

Other relations

 * 🇺🇸 Portland, Oregon, United States as a friendship city

title: Utrecht


text:
John Polkinghorne

John Charlton Polkinghorne (16 October 1930 – 9 March 2021) was an English theoretical physicist, theologian, and Anglican priest. A prominent and leading voice explaining the relationship between science and religion, he was professor of mathematical physics at the University of Cambridge from 1968 to 1979, when he resigned his chair to study for the priesthood, becoming an ordained Anglican priest in 1982. He served as the president of Queens' College, Cambridge, from 1988 until 1996.

Polkinghorne was the author of five books on physics and twenty-six on the relationship between science and religion; his publications include The Quantum World (1989), Quantum Physics and Theology: An Unexpected Kinship (2005), Exploring Reality: The Intertwining of Science and Religion (2007), and Questions of Truth (2009). The Polkinghorne Reader (edited by Thomas Jay Oord) provides key excerpts from Polkinghorne's most influential books. He was knighted in 1997 and in 2002 received the £1-million Templeton Prize, awarded for exceptional contributions to affirming life's spiritual dimension.

Early life and education
Polkinghorne was born in Weston-super-Mare in Somerset on 16 October 1930 to Dorothy Charlton, the daughter of a groom and George Polkinghorne, who worked for the post office. John was the couple's third child. He had a brother, Peter, and a sister, Ann, who died when she was six, one month before John's birth. Peter died in 1942 while flying for the Royal Air Force during the Second World War.

He was educated at the local primary school in Street, Somerset, then was taught by a friend of the family at home, and later at a Quaker school. When he was 11 he went to Elmhurst Grammar School in Street, and when his father was promoted to head postmaster in Ely in 1945, Polkinghorne was transferred to The Perse School, Cambridge. Following National Service in the Royal Army Educational Corps from 1948 to 1949, he read mathematics at Trinity College, Cambridge, graduating in 1952 as Senior Wrangler, then earned his PhD in physics in 1955, supervised by the Nobel laureate Abdus Salam in the group led by Paul Dirac.

Physics
Polkinghorne joined the Christian Union of UCCF while at Cambridge and met his future wife, Ruth Martin, another member of the union and also a mathematics student. They married on 26 March 1955, and at the end of that year sailed from Liverpool to New York. Polkinghorne accepted a postdoctoral Harkness Fellowship with the California Institute of Technology, where he worked with Murray Gell-Mann. Toward the end of the fellowship he was offered a position as lecturer at the University of Edinburgh, which he took up in 1956.

After two years in Scotland, he returned to teach at Cambridge in 1958. He was promoted to reader in 1965, and in 1968 was offered a professorship in mathematical physics, a position he held until 1979, his students including Brian Josephson and Martin Rees. For 25 years, he worked on theories about elementary particles, played a role in the discovery of the quark, and researched the analytic and high-energy properties of Feynman integrals and the foundations of S-matrix theory. While employed by Cambridge, he also spent time at Princeton, Berkeley, Stanford, and at CERN in Geneva. He was elected a Fellow of the Royal Society in 1974.

Priesthood and Queens' College
Polkinghorne decided to train for the priesthood in 1977. He said in an interview that he felt he had done his bit for science after 25 years, and that his best mathematical work was probably behind him; Christianity had always been central to his life, so ordination offered an attractive second career. He resigned his chair in 1979 to study at Westcott House, Cambridge, an Anglican theological college, becoming an ordained priest on 6 June 1982 (Trinity Sunday). The ceremony was held at Trinity College, Cambridge, and presided over by Bishop John A. T. Robinson. He worked for five years as a curate in south Bristol, then as vicar in Blean, Kent, before returning to Cambridge in 1986 as dean of chapel at Trinity Hall. He became the president of Queens' College that year, a position he held until his retirement in 1996. He served as canon theologian of Liverpool Cathedral from 1994 to 2005. Polkinghorne died on 9 March 2021 at the age of 90.

Awards
In 1997 Polkinghorne was made a Knight Commander of the Order of the British Empire (KBE), although as an ordained priest in the Church of England, he was not styled as "Sir John Polkinghorne". He was an honorary fellow of St Chad's College, Durham, and was awarded an honorary doctorate by the University of Durham in 1998; and in 2002 was awarded the Templeton Prize for his contributions to research at the interface between science and religion. He spoke on "The Universe as Creation" at the Trotter Prize ceremony in 2003.

He has been a member of the BMA Medical Ethics Committee, the General Synod of the Church of England, the Doctrine Commission, and the Human Genetics Commission. He served as chairman of the governors of The Perse School from 1972 to 1981. He was a fellow of Queens' College, Cambridge, and was for 10 years a canon theologian of Liverpool Cathedral. He was a founding member of the Society of Ordained Scientists and also of the International Society for Science and Religion, of which he was the first president. He was selected to give the prestigious Gifford Lectures in 1993–1994, which he later published as The Faith of a Physicist.

In 2006 he was awarded an honorary doctorate by the Hong Kong Baptist University as part of their 50-year celebrations. This included giving a public lecture on "The Dialogue between Science and Religion and Its Significance for the Academy" and an "East–West Dialogue" with Yang Chen-Ning, a Nobel laureate in physics. He was a member of staff of the Psychology and Religion Research Group at Cambridge University. He was an honorary fellow of St Edmund's College, Cambridge.

Ideas
Polkinghorne said in an interview that he believes his move from science to religion has given him binocular vision, though he understands that it has aroused the kind of suspicion "that might follow the claim to be a vegetarian butcher." He describes his position as critical realism and believes that science and religion address aspects of the same reality. It is a consistent theme of his work that when he "turned his collar around" he did not stop seeking truth. He argues there are five points of comparison between the ways in which science and theology pursue truth: moments of enforced radical revision, a period of unresolved confusion, new synthesis and understanding, continued wrestling with unresolved problems, deeper implications.

He suggests that the mechanistic explanations of the world that have continued from Laplace to Richard Dawkins should be replaced by an understanding that most of nature is cloud-like rather than clock-like. He regards the mind, soul and body as different aspects of the same underlying reality — "dual aspect monism" — writing that "there is only one stuff in the world (not two — the material and the mental), but it can occur in two contrasting states (material and mental phases, a physicist might say) which explain our perception of the difference between mind and matter." He believes that standard physical causation cannot adequately describe the manifold ways in which things and people interact, and uses the phrase "active information" to describe how, when several outcomes are possible, there may be higher levels of causation that choose which one occurs.

Sometimes Christianity seems to him to be just too good to be true, but when this sort of doubt arises he says to himself, "All right then, deny it", and writes that he knows this is something he could never do.

On the existence of God
Polkinghorne considers that "the question of the existence of God is the single most important question we face about the nature of reality" and quotes, with approval, Sir Anthony Kenny: "After all, if there is no God, then God is incalculably the greatest single creation of the human imagination." He addresses the questions of "Does the concept of God make sense? If so, do we have reason for believing in such a thing?" He is "cautious about our powers to assess coherence", pointing out that in 1900 a "competent… undergraduate could have demonstrated the 'incoherence'" of quantum ideas. He suggests that "the nearest analogy in the physical world [to God] would be… the Quantum Vacuum."

He suggests that God is the ultimate answer to Leibniz's great question "why is there something rather than nothing?" The atheist's "plain assertion of the world's existence" is a "grossly impoverished view of reality… [arguing that] theism explains more than a reductionist atheism can ever address.".

He is very doubtful of St Anselm's Ontological Argument. Referring to Gödel's incompleteness theorem, he said: "If we cannot prove the consistency of arithmetic it seems a bit much to hope that God's existence is easier to deal with," concluding that God is "ontologically necessary, but not logically necessary." He "does not assert that God's existence can be demonstrated in a logically coercive way (any more than God's non-existence can) but that theism makes more sense of the world, and of human experience, than does atheism." He cites in particular:

 * The intelligibility of the universe: One would anticipate that evolutionary selection would produce hominid minds apt for coping with everyday experience, but that these minds should also be able to understand the subatomic world and general relativity goes far beyond anything of relevance to survival fitness. The mystery deepens when one recognises the proven fruitfulness of mathematical beauty as a guide to successful theory choice.
 * The anthropic fine tuning of the universe: He quotes with approval Freeman Dyson, who said "the more I examine the universe and the details of its architecture, the more evidence I find that the universe in some sense must have known we were coming" and suggests there is a wide consensus amongst physicists that either there are a very large number of other universes in the Multiverse or that "there is just one universe which is the way it is in its anthropic fruitfulness because it is the expression of the purposive design of a Creator, who has endowed it with the finely tuned potentialty for life."
 * A wider humane reality: He considers that theism offers a more persuasive account of ethical and aesthetic perceptions. He argues that it is difficult to accommodate the idea that "we have real moral knowledge" and that statements such as 'torturing children is wrong' are more than "simply social conventions of the societies within which they are uttered" within an atheistic or naturalistic world view. He also believes such a world view finds it hard to explain how "Something of lasting significance is glimpsed in the beauty of the natural world and the beauty of the fruits of human creativity."

On free will
Polkinghorne believes that "The well-known free will defence in relation to moral evil asserts that a world with a possibility of sinful people is better than one with perfectly programmed machines. The tale of human evil is such that one cannot make that assertion without a quiver, but I believe that it is true nevertheless. I have added to it the free-process defence, that a world allowed to make itself is better than a puppet theatre with a Cosmic Tyrant. I think that these two defences are opposite sides of the same coin, that our nature is inextricably linked with that of the physical world which has given us birth."

On creationism
Following the resignation of Michael Reiss, the director of education at the Royal Society—who had controversially argued that school pupils who believed in creationism should be used by science teachers to start discussions, rather than be rejected per se — Polkinghorne argued in The Times that "As a Christian believer I am, of course, a creationist in the proper sense of the term, for I believe that the mind and the purpose of a divine Creator lie behind the fruitful history and remarkable order of the universe which science explores. But I am certainly not a creationist in that curious North American sense, which implies interpreting Genesis 1 in a flat-footed literal way and supposing that evolution is wrong."

Critical reception
Nancy Frankenberry, Professor of Religion at Dartmouth College, has described Polkinghorne as the finest British theologian/scientist of our time, citing his work on the possible relationship between chaos theory and natural theology. Owen Gingerich, an astronomer and former Harvard professor, has called him a leading voice on the relationship between science and religion.

The British philosopher Simon Blackburn has criticized Polkinghorne for using primitive thinking and rhetorical devices instead of engaging in philosophy. When Polkinghorne argues that the minute adjustments of cosmological constants for life points towards an explanation beyond the scientific realm, Blackburn argues that this relies on a natural preference for explanation in terms of agency. Blackburn writes that he finished Polkinghorne's books in "despair at humanity's capacity for self-deception." Against this, Freeman Dyson called Polkinghorne's arguments on theology and natural science "polished and logically coherent." The novelist Simon Ings, writing in the New Scientist, said Polkinghorne's argument for the proposition that God is real is cogent and his evidence elegant.

Richard Dawkins, formerly Professor for Public Understanding of Science at Oxford, writes that the same three names of British scientists who are also sincerely religious crop up with the "likable familiarity of senior partners in a firm of Dickensian lawyers": Arthur Peacocke, Russell Stannard, and John Polkinghorne, all of whom have either won the Templeton Prize or are on its board of trustees. Dawkins writes that he is not so much bewildered by their belief in a cosmic lawgiver, but by their beliefs in the minutiae of Christianity, such as the resurrection and forgiveness of sins, and that such scientists, in Britain and in the US, are the subject of bemused bafflement among their peers. Polkinghorne responded that "debating with Dawkins is hopeless, because there's no give and take. He doesn't give you an inch. He just says no when you say yes." Nicholas Beale writes in Questions of Truth, which he co-authored with Polkinghorne, that he hopes Dawkins will be a bit less baffled once he reads it.

A. C. Grayling criticized the Royal Society for allowing its premises to be used in connection with the launch of Questions of Truth, describing it as a scandal, and suggesting that Polkinghorne had exploited his fellowship there to publicize a "weak, casuistical and tendentious pamphlet." After implying that the book's publisher, Westminster John Knox, was a self-publisher, Grayling went on to write that Polkinghorne and others were eager to see the credibility accorded to scientific research extended to religious perspectives through association.

In contrast to Grayling, science historian Edward B. Davis praises Questions of Truth, saying the book provides "the kind of technical information… that scientifically trained readers will appreciate—yet they can be read profitably by anyone interested in science and Christianity." Davis concludes, "It hasn't been easy to steer a middle course between fundamentalism and modernism, particularly on issues involving science. Polkinghorne has done that very successfully for a generation, and for this he ought to be both appreciated and emulated."

Published works
Polkinghorne wrote 34 books, translated into 18 languages; 26 concern science and religion, often for a popular audience.

 * Science and religion
 * The Polkinghorne Reader : Science, Faith, and the Search for Meaning (Edited by Thomas Jay Oord) (SPCK and Templeton Foundation Press, 2010) ISBN 1-59947-315-1 and ISBN 978-0-281-06053-5
 * The Way the World Is: The Christian Perspective of a Scientist (1984 – revised 1992) ISBN 0-281-04597-6
 * One World (SPCK/Princeton University Press 1987; Templeton Foundation Press, 2007) ISBN 978-1-59947-111-2
 * Science and Creation (SPCK/New Science Library, 1989; Templeton Foundation Press, 2006) ISBN 978-1-59947-100-6
 * Science and Providence (SPCK/New Science Library, 1989; Templeton Foundation Press, 2006) ISBN 978-1-932031-92-8
 * Reason and Reality: Relationship Between Science and Theology  (SPCK/Trinity Press International 1991) ISBN 978-0-281-04487-0
 * Quarks, Chaos and Christianity (1994; Second edition SPCK/Crossroad 2005) ISBN 0-281-04779-0
 * The Faith of a Physicist – published in the UK as Science and Christian Belief (1994) ISBN 0-691-03620-9
 * Serious Talk: Science and Religion in Dialogue (Trinity Press International/SCM Press, 1996) ISBN 978-1-56338-109-6
 * Scientists as Theologians (1996) ISBN 0-281-04945-9
 * Beyond Science: The wider human context (CUP 1996) ISBN 978-0-521-57212-5
 * Searching for Truth (Bible Reading Fellowship/Crossroad, 1996)
 * Belief in God in an Age of Science (Yale University Press, 1998) ISBN 0-300-08003-4
 * Science and Theology (SPCK/Fortress 1998) ISBN 0-8006-3153-6
 * The End of the World and the Ends of God (Trinity Press International, 2000) with Michael Welker
 * Traffic in Truth: Exchanges Between Sciences and Theology (Canterbury Press/Fortress, 2000) ISBN 978-0-8006-3579-4
 * Faith, Science and Understanding (2000) SPCK/Yale University Press ISBN 0-300-08372-6
 * The Work of Love: Creation as Kenosis editor, with contributors including Ian Barbour, Sarah Coakley, George Ellis, Jurgen Moltmann and Keith Ward (SPCK/Eerdmans 2001) ISBN 0-281-05372-3 / ISBN 0-8028-4885-0
 * The God of Hope and the End of the World (Yale University Press, 2002) ISBN 0-300-09211-3
 * The Archbishop's School of Christianity and Science (York Courses, 2003) ISBN 0954054385
 * 'Science and Christian Faith' (Conversation on CD with Canon John Young. York Courses)
 * Living with Hope (SPCK/Westminster John Knox Press, 2003)
 * Science and the Trinity: The Christian Encounter With Reality (2004) ISBN 0-300-10445-6 (a particularly accessible summary of his thought)
 * Exploring Reality: The Intertwining of Science & Religion (SPCK 2005) ISBN 0-300-11014-6
 * Quantum Physics & Theology: An Unexpected Kinship (SPCK 2007) ISBN 978-0-281-05767-2
 * From Physicist to Priest, an Autobiography SPCK 2007 ISBN 978-0-281-05915-7
 * Theology in the Context of Science SPCK 2008 ISBN 978-0-281-05916-4
 * Questions of Truth: Fiftyone Responses to Questions about God, Science and Belief, with Nicholas Beale; foreword by Antony Hewish (Westminster John Knox 2009) ISBN 978-0-664-23351-8
 * Reason and Reality: The Relationship Between Science and Theology (2011) SPCK ISBN 978-0-281-06400-7
 * Science and Religion in Quest of Truth (2011) SPCK ISBN 978-0-281-06412-0
 * 'Hawking, Dawkins and GOD' (2012) (Conversation on CD with Canon John Young. York Courses)
 * What Can We Hope For? (Sam&Sam, 2019) with Patrick Miles ISBN 978-1-9999676-1-1

 * Science
 * The Analytic S-Matrix (CUP 1966, jointly with RJ Eden, PV Landshoff and DI Olive)
 * The Particle Play (W.H. Freeman, 1979)
 * Models of High Energy Processes (CUP 1980)
 * The Quantum World (Longmans/Princeton University Press, 1985; Penguin 1986; Templeton Foundation Press 2007) ISBN 978-0-691-02388-5
 * Rochester Roundabout: The Story of High Energy Physics (New York, Longman, 1989) ISBN 978-0-582-05011-2
 * Quantum Theory: A Very Short Introduction (2002) OUP ISBN 0-19-280252-6
 * Meaning in Mathematics (2011) OUP (edited, with contributions from Timothy Gowers, Roger Penrose, Marcus du Sautoy and others) ISBN 978-0-19-960505-7

 * Chapters
 * "The Trinity and Scientific Theology" in The Blackwell Companion to Science and Christianity, J.B. Stump and Alan G. Padgett (eds.), (Wiley-Blackwell, 2012)
 * On Space and Time (CUP 2008) along with Andrew Taylor, Shahn Majid, Roger Penrose, Alain Connes and Michael Heller ISBN 978-0-521-88926-1
 * Spiritual Information: 100 Perspectives on Science and Religion (Templeton Foundation Press, 2005) ed Charles Harper ISBN 1-932031-73-1
 * Creation, Law and Probability (Fortress Press 2008) ed Fraser Watts with Peter Harrison, George Ellis, Philip Clayton, Michael Ruse, Nancey Murphy, John Bowker & others ISBN 978-0-8006-6278-3
 * "Physical Processes, Quantum Events, and Divine Agency," in Quantum Mechanics: Scientific Perspectives on Divine Action, Russell, R.J., Clayton, P., Wegter-McNelly, K., Polkinghorne, J. (eds.), (VATICAN: Vatican Observatory, 2001)

title: John Polkinghorne