# Pseudorandom Finite Models

Jan Dreier  TU Wien<EMAIL_ADDRESS>Jamie Tucker-Foltz  Harvard
University<EMAIL_ADDRESS>
###### Abstract

We study pseudorandomness and pseudorandom generators from the perspective of
logical definability. Building on results from ordinary derandomization and
finite model theory, we show that it is possible to deterministically
construct, in polynomial time, graphs and relational structures that are
statistically indistinguishable from random structures by any sentence of
first order or least fixed point logics. This raises the question of whether
such constructions can be implemented via logical transductions from simpler
structures with less entropy. In other words, can logical formulas be
pseudorandom generators? We provide a complete classification of when this is
possible for first order logic, fixed point logic, and fixed point logic with
parity, and provide partial results and conjectures for first order logic with
parity.

##  1 Introduction

The worst-case tractability of decision problems has found an elegant analog
in the realm of finite model theory, where hardness is measured not in terms
of the computational resources required to solve a given problem, but the
logical constructs needed to define it. From the pioneering work of Fagin [13]
to the recent “quest to capture polynomial time” [16], a wide variety of
complexity classes for decision problems have been described in terms of
logics [20]. Recent work has begun to extend descriptive complexity into the
realm of approximation as well [3, 28]. However, very little has been said
about _average case_ computational problems from a logical perspective.

A foundational conjecture of cryptography is the existence of
cryptographically secure pseudorandom generators (PRGs): Deterministic
polynomial-time algorithms that map random inputs to longer pseudorandom
outputs in such a way that no polynomial-time algorithm can distinguish the
output from real randomness. This may be thought of as a game between a
_generator_ who builds the pseudorandom output and an _adversary_ who with
probability $\frac{1}{2}$ either sees the generator’s output or a truly random
string and has to distinguish the two with probability significantly better
than chance. The existence of PRGs is equivalent to the existence of one-way
functions, which is a standard and widely-believed conjecture in cryptography
(see Section 2.4). In this paper, we study the ability of logical formulas to
act as generator or adversary. The logics we consider are first order (FO)
logic and its well-studied extensions with operators for computing least fixed
points (LFP) and parities ($\textup{FO}[\oplus]$ and $\textup{LFP}[\oplus]$).

Instead of considering random strings, we measure randomness via random graphs
and relational structures. This allows us to build off existing results about
these logics and study intriguing questions specific to _unordered_
structures, meaning those without a binary relation symbol that is always
interpreted as a total order. For varying relational signatures, we consider
structures where each tuple appears in a relation independently with
probability $\frac{1}{2}$. For a single symmetric binary relation, this
yields, for example, the classic Erdös-Renyi random graph $G(n,1/2)$. The
expressive power of logics on such structures is well understood: the _zero-
one laws_ for FO [14] and LFP [5] state that, for any sentence $\varphi$, as
the size of the universe $n$ grows, the probability of satisfying the sentence
converges exponentially fast to either _zero_ or _one_ , depending on
$\varphi$. A variant of this phenomenon holds for $\textup{FO}[\oplus]$ as
well (by [22], reviewed in detail in Section 5), where on random graphs the
probability of being satisfied converges to two limits (one for even $n$ and
one for odd $n$). On the other hand, $\textup{LFP}[\oplus]$ can canonize
random structures with high probability [17], implying (via the Immerman-Vardi
theorem [19, 29]) that $\textup{LFP}[\oplus]$ is as powerful as polynomial
time computation when it comes to random inputs, so obviously no zero-one law
can possibly hold.

In this paper, we study structures that are not random, but _pseudorandom_.
Our formal definition of this concept, presented in Section 2, closely mirrors
the standard definition from private-key cryptography.111To the best of our
knowledge, this paper is the first to investigate cryptographic notions in the
setting of logical definability. There is a literature on “pseudorandom
graphs” but this typically refers to graphs satisfying useful statistical
properties of graphs such as subgraph densities and spectral gap. These graphs
are not generally pseudorandom in our context. See Krivelevich and Sudakov
[23] for a survey. The zero-one law suggests that FO and LFP should admit
polynomial-time PRGs: To generate pseudorandomness that fools an adversary
based on a formula $\varphi$, it suffices to construct a structure that
accepts $\varphi$ if and only if the limiting probability is one rather than
zero—and nearly all structures satisfy this property. However, complexity
theory is littered with examples of similar tasks (known as “finding hay in a
haystack” [2, Chapter 21]) that turn out to be quite difficult.

###  1.1 Deterministic construction of existentially-closed graphs

Our first main result, presented in Section 3, is a deterministic, polynomial-
time construction of graphs and other structures that FO and LFP cannot
distinguish from truly-random structures (Theorem 12). We do so by building
patterns described by the so-called _extension axioms_ (defined in Section 3).
These patterns can be found with high probability in random structures and are
responsible for forcing the zero-one convergence of FO and LFP sentences.

Over graphs, this can be understood as a finite analogue of an infinite
construction: The _Rado graph_ is the unique (up to isomorphism) infinite
graph satisfying all extension axioms. Sampling from the infinite Erdös-Renyi
graph $G(\infty,1/2)$ yields with probability one the Rado graph. There are
several existing explicit constructions222For example, use the vertex set
$\mathbb{\mathbb{Z}}_{\geq 1}$ and connect $x$ and $y$ if $x<y$ and the
$x^{\text{th}}$ bit of the binary representation of $y$ is one [1, 27]. and
their finite prefixes can be computed in polynomial time. However, these
prefixes do _not_ satisfy the extension axioms, and hence do not provide
pseudorandom structures even against FO adversaries.

It turns out to be a much more challenging task to deterministically construct
_finite_ analogues of the Rado graph, which are also commonly referred to as
_existentially-closed_ graphs. Explicit graphs satisfying the extension axioms
have been discovered, but they are delicate constructions based on special
properties of mathematical structures, such as Paley graphs [4], binary
matrices [6], and affine designs [9]; see Bonato [7] for an overview of these
constructions. None of them have obvious generalizations to more complicated
finite models with multiple non-symmetric relations of arbitrary
arities.333There is one exception that we are aware of: Even-Zohar, Farber,
and Mead [12] extend the Paley graph construction to work for hypergraphs
using a clever application of Vandermonde determinants. However, it is still
unclear how to extend this idea further to work for arbitrary relational
signatures. To this end, we develop a more robust, versatile framework using
tools from the literature on derandomization—specifically _perfect hash
functions_ and _universal sets_. Our approach is quite different from its
predecessors and easily handles graphs as well as arbitrary relational
structures.

###  1.2 Logic vs. logic

Just as we restrict the adversary to being definable in a given logic, we may
“level the playing field” by also restricting the generator to a logic. To
define what it means to generate an output from an input via logic, we
consider the notion of _transductions_ [10] (formally defined in Section 2.2).
For the purpose of this paper, transductions are tuples of logical formulas
that map all structures with a certain signature $\sigma$ to structures with
the same universe but different signature $\tau$. For example, consider an
input signature $\sigma$ with a single binary relation and an output signature
$\tau$ with a single ternary relation $T$. Then a transduction $\Theta$ from
$\sigma$ to $\tau$ consists of a single $\sigma$-formula $\theta(x,y,z)$ that
associates with every input $\sigma$-structure $\mathbb{A}$ the
$\tau$-structure $\Theta(\mathbb{A})$ where $T(x,y,z)$ holds if and only if
$\theta(x,y,z)$ holds in $\mathbb{A}$. We say that $\Theta$ is a _pseudorandom
generator from $\sigma$ to $\tau$_ if applying $\Theta$ to a random
$\sigma$-structure yields a pseudorandom $\tau$-structure. Thus, in our
example, $\Theta$ gets a binary $\sigma$-structure with $n^{2}$ bits of
entropy and has to generate a pseudorandom output (that the adversary cannot
distinguish from a ternary $\tau$-structure) with $n^{3}$ bits of entropy. We
consider this to be an appropriate model-theoretic analogue of PRGs.

Our second main result, proved in Section 4, is a complete classification of
when such PRGs exist, depending on the logics we require the generator and
adversary to be in, from all possible pairs among
$\\{\text{FO},\text{LFP},\text{$\textup{LFP}[\oplus]$}\\}$, as well as the
input and output signatures. Table 1 lists the results for the special case
where $\sigma$ has just one binary relation and $\tau$ has just one ternary
relation.

$\Theta$ $\varphi$ | FO | LFP | $\textup{LFP}[\oplus]$
---|---|---|---
FO | ✗ | ✗ | ✗
LFP | ✗ | ✗ | ✗
$\textup{LFP}[\oplus]$ | ✓ | ✓ |  $\iff$OWFs exist
Table 1: Existence/nonexistence of PRGs from a relational signature with one
binary relation to a relational signature with one ternary relation, depending
on the logics that the transduction $\Theta$ and adversary $\varphi$ are
allowed to be defined in. For the bottom-right entry, existence is equivalent
to the standard conjecture in private-key cryptography that one-way functions
exist (also equivalent to Conjecture 3). A general classification for all
possible pairs of signatures is given in Table 2.

Note that, in this model-theoretic setting, entropy comes in different
“shapes.” Consider PRGs from structures with a single ternary relation to
structures with three binary relations. Ordinarily, it is trivial to reshape
and truncate an input containing $n^{3}$ independent random bits into an
output with $3n^{2}$ bits, but it is not immediately clear whether logics can
accomplish this task as well. We come up with a measure of “entropy” that
completely determines between which signatures pseudorandom generators exist.
Surprisingly, this notion depends on the pairs of logics under consideration,
and does not always define a total order on the signatures.

###  1.3 First order with parity

It is notable that none of the logics we considered so far admit a PRG that is
unconditionally secure against adversaries from the same logic: FO and LFP are
too weak while $\textup{LFP}[\oplus]$ is too strong. To find an interesting
middle ground, we turn to $\textup{FO}[\oplus]$, which does not come close to
capturing polynomial time yet can still express interesting properties like
“there are an odd number of triangles” which hold in random graphs with
limiting probability $\frac{1}{2}$. We consider the
$\textup{FO}[\oplus]$-transduction that creates a $t$-hypergraph from a normal
graph by adding each hyperedge $\\{v_{1},\dots,v_{t}\\}$ if and only if there
are an odd number of vertices that are adjacent to each of
$v_{1},\dots,v_{t}$. We show in Section 5 that this transduction is a
pseudorandom generator that is secure against FO and LFP. This is done by
proving that the transduced hypergraph satisfies with high probability the
corresponding hypergraph-extension axioms. Hence, our transduction takes a
random graph with ${n\choose 2}$ bits of entropy and yields a hypergraph that
an FO or LFP adversary cannot distinguish from a real $t$-hypergraph with
${n\choose t}$ bits of entropy. We conjecture that this specific transduction
is also secure against $\textup{FO}[\oplus]$, and that therefore
$\textup{FO}[\oplus]$ admits a PRG that is secure against itself.

##  2 Preliminaries

For any nonnegative integer $n$, let $[n]:=\\{1,2,3,\dots,n\\}$. By $\log(n)$
we mean the logarithm with base 2. We say a function $f(n)$ is _negligible_
if, for any polynomial function $p$, for all sufficiently large $n$,
$|f(n)|\leq 1/p(n)$. We write $f(n)=\textnormal{negl}(n)$ to indicate this.
For any finite set $S$, we denote sampling an element $s$ uniformly from $S$
by $s\sim S$, and sampling according to a distribution $\mathcal{D}$ over $S$
by $s\sim\mathcal{D}$. For any nonnegative integer $k$, ${S\choose k}$ is the
set of all $k$-element subsets of $S$.

###  2.1 Models and logics

In this paper we study two kinds of random structures. First, _relational
structures_ , which we define with respect to a _relational signature_
$\sigma=\langle{R}_{1},{R}_{2},\dots,{R}_{t}\rangle$, where each relation
symbol $R_{i}$ has an associated _arity_ $a_{i}$. A _$\sigma$ -structure_
$\mathbb{A}$ is a finite universe $A$ together with a sequence of relations
$\langle
R_{1}^{\mathbb{A}},R_{2}^{\mathbb{A}},\dots,R_{t}^{\mathbb{A}}\rangle$, where
each $R_{i}^{\mathbb{A}}$ is an $a_{i}$-ary relation over $A$, that is, a
subset of $A^{a_{i}}$. We identify $\mathbb{A}$ with its universe $A$ and thus
write, for example, $a\in\mathbb{A}$ instead of $a\in A$. We denote the set of
all $\sigma$-structures by $\textup{Str}[{\sigma}]$ and the set of all
$n$-element $\sigma$-structures by $\textup{Str}[{\sigma,n}]$. Uniformly
sampling from $\textup{Str}[{\sigma,n}]$ yields a _random $\sigma$-structure_,
where every ordered $a_{i}$-tuple of (possibly non-distinct) elements of the
universe is in relation $R_{i}$ independently with probability $\frac{1}{2}$.

Second, _$t$ -hypergraphs_ are relational structures consisting of a single
symmetric, $t$-ary hyperedge relation where every $t$-tuple consists of $t$
distinct elements. A $2$-hypergraph is simply a _graph_. The Erdös-Renyi
random graph $G(n,1/2)$ is defined as the uniform distribution over all
$n$-vertex graphs, that is, the distribution where each edge appears
independently with probability $1/2$. Similarly, $G_{t}(n,1/2)$ denotes the
uniform distribution over all $n$-element $t$-hypergraphs, where each set of
$t$ distinct vertices forms a hyperedge independently with probability $1/2$.

For any class of graphs or relational structures $\mathcal{P}$ and logic $L$,
we say that $\mathcal{P}$ is _definable_ in $L$ if there is some sentence
$\varphi$ in $L$ such that $\mathcal{P}$ consists precisely of all
graphs/structures that model $\varphi$. We assume the reader is familiar with
first order logic (FO). We denote the extension of FO with a least fixed-point
operator as LFP. It is not necessary for us to go into detail about LFP except
to note the following property it has. The _Immerman-Vardi theorem_ states
that, in the presence of a relation symbol that is interpreted as a total
order over the universe, the expressive power of LFP is equivalent to
polynomial time computation:

######  Theorem 1 (Immerman [19], Vardi [29]).

Let $\sigma$ be a signature containing a binary relation symbol $\leq$, and
let $\mathcal{P}$ be a property of $\sigma$-structures such that, for any
$\sigma$-structure $\mathbb{A}$ with property $\mathcal{P}$,
$\leq^{\mathbb{A}}$ is a total order over the universe. Then $\mathcal{P}$ is
decidable in polynomial time if and only if it is definable in LFP.

It is often easier to think of operations on finite structures as algorithms,
with the implicit understanding that properties computed by the algorithm can
be expressed in a given logic. In this paper, we frequently do not go into
detail about how such a translation works. The Immerman-Vardi Theorem assures
us that, as long as we have defined a total order over the universe somehow,
we can superimpose this order onto the structure and apply Theorem 1 to this
“implicit” structure. This lets us successfully translate any steps of the
algorithm that are polynomial-time into LFP.

###  2.2 Transductions

A _transduction_ is a way of defining one model from another, possibly of a
different signature. In the context of relational structures, we define a
transduction as follows. Let $\sigma$ and $\tau$ be signatures, where
$\tau=\langle{R}_{1},{R}_{2},\dots,{R}_{t}\rangle$, and $R_{i}$ has arity
$a_{i}$. Then a _transduction from $\sigma$ to $\tau$_ (also known as an
_interpretation of $\tau$ in $\sigma$_) is a sequence of $\sigma$-formulas
$\Theta=({\theta}_{1},{\theta}_{2},\dots,{\theta}_{t})$, where each
$\theta_{i}$ has $a_{i}$ free variables ${x}_{1},{x}_{2},\dots,{x}_{a_{i}}$.
Overloading notation, we think of
$\Theta:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ as a function mapping
$\sigma$-structures to $\tau$-structures, where, given any $\sigma$-structure
$\mathbb{A}$, we define $\Theta(\mathbb{A})$ to be the $\tau$-structure over
the same universe as that of $\mathbb{A}$, where relation
$R_{i}^{\Theta(\mathbb{A})}$ holds on a tuple
$({x}_{1},{x}_{2},\dots,{x}_{a_{i}})$ if and only if
$\mathbb{A}\models\theta_{i}({x}_{1},{x}_{2},\dots,{x}_{a_{i}})$. In the
contexts of graphs and hypergraphs, we denote by $\theta(G)$ the transduction
where a single relation based on formula $\theta$ is created.

###  2.3 The parity operator

We may augment any logic $L$ with a _parity_ operator to form the new logic
$L[\oplus]$. The expression $\oplus y~{}\varphi$ asks whether there is an odd
number of elements $y$ in the universe satisfying the subformula $\varphi$.

This operator adds considerable power to LFP on random structures. In
particular, it makes it possible to define a total order over the universe
with probability $1-\textnormal{negl}(n)$ [17]. In Appendix B, we prove the
following variant of this result, which says that we can almost always use a
relation of arity $k\geq 2$ to simultaneously order the universe and extract
$\Omega(n^{k})$ independent random bits. The Immerman-Vardi theorem lets us
then apply polynomial-time computations to these bits.

######  Lemma 2.

Let $\sigma$ be a relational signature containing a relation symbol $R$ of
arity $k\geq 2$, and let $\tau$ be a relational signature containing symbols
“$\leq$” of arity 2 and $Q$ of arity $k$. There is an $\textup{LFP}[\oplus]$
transduction $\Gamma:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ such that,
with probability $1-\textnormal{negl}(n)$ over a random $\sigma$-structure
$\mathbb{A}$,

  1. (i)

$\leq^{\Gamma(\mathbb{A})}$ defines a total order over the universe, and

  2. (ii)

$\left|{Q^{\Gamma(\mathbb{A})}}\right|=\Omega(n^{k})$.

Furthermore, it is always the case that, for $k$-tuples
$({x}_{1},{x}_{2},\dots,{x}_{k})\in Q^{\Gamma(\mathbb{A})}$, even after
conditioning on any realization of $\leq^{\Gamma(\mathbb{A})}$ and
$Q^{\Gamma(\mathbb{A})}$, the probabilities that
$({x}_{1},{x}_{2},\dots,{x}_{k})\in R^{\mathbb{A}}$ are all $\frac{1}{2}$ and
pairwise independent across $({x}_{1},{x}_{2},\dots,{x}_{k})\in
Q^{\Gamma(\mathbb{A})}$.

###  2.4 Ordinary pseudorandomness and cryptography

We refer the reader to the textbook by Boneh and Shoup [8] for a comprehensive
discussion of the cryptographic notions used in this paper. Here we only
provide a brief overview.

A _pseudorandom generator_ is a collection of functions
$f_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{\ell(n)}$ such that, for any collection of
polynomial-sized circuits $A_{n}:\\{0,1\\}^{\ell(n)}\to\\{0,1\\}$,

$\left|{\Pr_{s\sim\\{0,1\\}^{n}}[A_{n}(f_{n}(s))=1]-\Pr_{t\sim\\{0,1\\}^{\ell(n)}}[A_{n}(t)=1]}\right|=\textnormal{negl}(n).$

We may alternatively think of the collection of functions $A_{n}$ as a single
Turing machine with access to “advice” bits (storing for each $n$ a circuit)
that runs in polynomial time (to simulate the circuit). The advice bits may
depend on $n$ in an arbitrary (not necessarily computable) way.

It is believed that there exist pseudorandom generators that extend $n$ random
bits to $\ell(n)>n$ pseudorandom bits.

######  Conjecture 3.

There exists a polynomial-time pseudorandom generator
$f_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$.

This is known to be equivalent to a list of other conjectures in cryptography,
including:

  * •

The existence of one-way functions (OWFs), which are functions that are easy
to compute but hard to invert given the output of a random input.

  * •

The existence of a computationally secure private-key encryption scheme
between two parties with a short pre-distributed key.

  * •

Even stronger security guarantees against chosen-plaintext or chosen-
ciphertext attacks, in which we assume the adversary has query access to
encrypt/decrypt other messages.

The hardest part of the equivalence is due to the celebrated result of Håstad,
Impagliazzo, Levin, and Luby [18], which shows how to construct a PRG from an
arbitrary OWF. Since OWFs are more fundamental, simple objects, Conjecture 3
is often referred to as the _OWF Conjecture_. The conjecture implies P $\neq$
NP.

Note that, in the definitions of each of these cryptographic objects, we must
always allow the adversary to be nonuniform, otherwise some of the reductions
do not go through properly. For example, one classic reduction, known as the
_length-extension theorem_ ,444See Boneh and Shoup [8, Theorem 3.3]. takes a
PRG $f_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ and iterates it a polynomial
$p(n)$ number of times to produce a PRG
$g_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{p(n)}$. After each iteration we output a
single bit and feed the remaining $n$ bits back into $f_{n}$ for the next
iteration, until we have output $p(n)$ bits. The proof of security uses the
_hybrid argument_ , which considers distributions
$H_{0},H_{1},H_{2},\dots,H_{p(n)}$ over $p(n)$-bit strings where, in $H_{i}$,
the first $i$ bits are chosen uniformly at random, while the remaining bits
are generated from iterating $f_{n}$ as in the definition of $g_{n}$. It
suffices to prove that, for each $i$, no adversary can distinguish strings
drawn from $H_{i}$ from those drawn from $H_{i+1}$ with non-negligible
advantage; from this it follows that no adversary can distinguish $H_{0}$ from
$H_{p(n)}$, which means $g_{n}$ is secure. This is true because an adversary
that distinguishes $H_{i}$ from $H_{i+1}$ can be transformed into an adversary
that breaks the security of $f_{n}$. However, this algorithm requires
randomness, and the only known way to derandomize it is to encode a good draw
of the random bits as nonuniform advice.

In the proof of one of the cases of Theorem 17, we require a novel adaptation
of the length-extension construction that can be implemented as an
$\textup{LFP}[\oplus]$-transduction.

###  2.5 Model-theoretic pseudorandomness

Consider a collection of probability distributions
$(\mathcal{D}_{n})_{n\in\mathbb{\mathbb{Z}}_{\geq 1}}$, where
$\mathcal{D}_{n}$ ranges over structures $\textup{Str}[{\tau,n}]$. Now, we may
say that this distribution is uniformly pseudorandom for a logic $L$ if, for
every $\tau$-sentence $\varphi\in L$,

$\left|{\Pr_{\mathbb{A}\sim\mathcal{D}_{n}}[\mathbb{A}\models\varphi]-\Pr_{\mathbb{A}\sim\textup{Str}[{\tau,n}]}[\mathbb{A}\models\varphi]}\right|=\textnormal{negl}(n).$

While in the ordinary notion of PRGs, the adversary has access to a polynomial
number of non-uniform advice bits, this model-theoretic definition is
completely uniform and makes no mention of advice. It may be seen as a
strength of this model that almost all of our results hold without the
presence of advice (specifically, all results except for Theorem 17 part (i)).
However, to link our results to the foundational conjectures of cryptography,
we will also give our logical adversary access to advice. This is done via
disjoint polynomial-size advice structures
$(\mathbb{X}_{n})_{n\in\mathbb{\mathbb{Z}}_{\geq 1}}$ that may depend non-
uniformly on $n$.

For a $\tau$-structure $\mathbb{A}$ and $\rho$-structure $\mathbb{X}_{n}$, we
denote by $(\mathbb{A},\mathbb{X}_{n})$ the $(\tau\cup\rho)$-structure
obtained by the disjoint union555The universe of $(\mathbb{A},\mathbb{X}_{n})$
is the disjoint union of the universes of $\mathbb{A}$ and $\mathbb{X}_{n}$,
and each relation from $\tau\cup\rho$ is interpreted as the disjoint union of
the relations of the two structures, where missing relations are considered
empty. of the two structures. A distribution
$(\mathcal{D}_{n})_{n\in\mathbb{\mathbb{Z}}_{\geq 1}}$ is _pseudorandom for a
logic $L$_ if, for every advice-signature $\rho$, every sequence of
$\rho$-structures $(\mathbb{X}_{n})_{n\in\mathbb{\mathbb{Z}}_{\geq 1}}$, where
$\mathbb{X}_{n}$ has a universe of size $n$, and every
$(\tau\cup\rho)$-sentence $\varphi\in L$,

$\left|{\Pr_{\mathbb{A}\sim\mathcal{D}_{n}}[(\mathbb{A},\mathbb{X}_{n})\models\varphi]-\Pr_{\mathbb{A}\sim\textup{Str}[{\tau,n}]}[(\mathbb{A},\mathbb{X}_{n})\models\varphi]}\right|=\textnormal{negl}(n).$

Finally, for any pair of logics $L_{1}$ and $L_{2}$, an _$(L_{1},L_{2})$
-pseudorandom generator from $\sigma$ to $\tau$_ is an $L_{1}$ transduction
$\Theta:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ such that the family of
distributions obtained by sampling
$\mathbb{C}_{n}\sim\textup{Str}[{\sigma,n}]$ and outputting
$\Theta(\mathbb{C}_{n})$ is pseudorandom for $L_{2}$.

##  3 Pseudorandom Structures for LFP
and Extension Axioms

A central property for creating pseudorandom structures with respect to FO or
LFP adversary are the so-called _extension axioms_. For now, we define them
for graphs and give the more involved definition for relational structures
later.

######  Definition 4.

A graph $G$ satisfies the _$k$ -extension axioms $\textnormal{EA}_{k}$_ if,
for all sets $S\subseteq V(G)$ of size $k$ and all $T\subseteq S$, there
exists $v\not\in S$ (called an extension vertex of $(S,T)$) that is adjacent
to every vertex in $T$ and non-adjacent to every vertex in $S\setminus T$.

Informally speaking, the $k$-extension axioms state that any set of $k$
pebbles in the Ehrenfeucht–Fraïssé game for (finitary or infinitary) first
order logic can be extended in all possible ways by an additional
pebble.666While not necessary for comprehending this paper, we refer the
reader to Libkin [24] for more background on pebbling games. Thus, if two
structures satisfy the $k$-extension axioms, then Duplicator always has a way
to respond regardless of where the pebbles are. In other words, for any given
LFP sentence $\varphi$, there exists $k$ such that, for any pair of graphs
$G_{1},G_{2}$ both satisfying the $k$-extension axioms $\textnormal{EA}_{k}$,
we have that $G_{1}\models\varphi\Leftrightarrow G_{2}\models\varphi$. While
this is a standard argument, for completeness, we prove this statement (even
in the presence of our additional advice structure) later in Lemma 11.

An important observation is that a random graph satisfies the extension axioms
with high probability. As we show in Lemma 10, for every positive integer $k$,

$\Pr_{G\sim
G(n,1/2)}\bigl{[}G\not\models\textnormal{EA}_{k}\bigr{]}=\textnormal{negl}(n).$

The zero-one laws for FO [14] and LFP [5] then follow immediately: any given
sentence with quantifier rank $k$ either holds in all or no graphs satisfying
the $k$-extension axioms, and thus on almost all or almost no graphs. In
particular, the infinite random graph $G(\infty,1/2)$, also called the Rado
graph, satisfies the $k$-extension axioms for all
$k\in\mathbb{\mathbb{Z}}_{\geq 1}$ with probability 1.

In this section, we provide a polynomial-time deterministic construction of
$n$-element graphs and relational structures satisfying the $k$-extension
axioms for $k=\log(\log(\Theta(n)))$, implying that FO and LFP adversaries
cannot distinguish them from truly-random graphs and structures.

#### Universal sets and perfect hash functions

The following definitions provide a natural way to “extend” sets of size $k$
from a linear sized set using only a logarithmic number of elements.

######  Definition 5.

Let $\mathcal{F}$ be a family of functions from $[n]$ to $[k]$. We say
$\mathcal{F}$ is an _$(n,k)$ -family of perfect hash functions_ if for every
set $S\subseteq[n]$ of size $k$, there exists $f\in\mathcal{F}$ such that
$\\{f(s)\mid s\in S\\}=[k]$. A family $\cal U$ of subsets of $[n]$ is an
_$(n,k)$ -universal set_ if for every subset $S\subseteq[n]$ of size $k$, the
family $\\{S\cap U\colon U\in\cal U\\}$ contains all $2^{k}$ subsets of $S$.

Perfect hash functions and universal sets of small size exist and can be
constructed efficiently. We use the following classic result.

######  Theorem 6 (Naor, Shulman, and Srinivasan [26]).

There exists a constant $c$ such that, for $n,k\geq 1$, one can construct an
$(n,k)$-family of perfect hash functions and an $(n,k)$-universal set of size
$2^{ck}\log(n)$ in time $2^{ck}n\log(n)$.

#### Tournaments

A _tournament_ is an edge orientation of a complete undirected graph. This
means it is a directed graph that contains for every pair of vertices $a,b$
either the directed edge from $a$ to $b$ or from $b$ to $a$ but not both. By
brute-force, we find a tournament graph of size $\log(\Theta(n))$ that
reserves for each set of size $k$ a vertex that points towards all elements of
the set, and use it to assign the extension vertices, as shown in Figure 1.

######  Lemma 7.

Let $k$ be a nonnegative integer. There exists a tournament $F$ of size
$2^{3k}$ such that, for every $S\subseteq V(F)$ of size $k$, there is a vertex
that has a directed edge towards every vertex in $S$.

###### Proof.

Let us consider a random tournament $F$ on $2^{3k}$ vertices where the
orientation of every edge is chosen independently uniformly at random. We use
the probabilistic method, proving the statement by showing that there is a
non-zero probability that $F$ has the stated properties. Let us fix a set
$S\subseteq V(F)$ of size $k$. The probability that a fixed vertex has edges
directed towards every vertex in $S$ is precisely $2^{-k}$. The probability
that there is no vertex with edges directed towards every vertex in $S$ is
(using 24 in Appendix A) at most

$(1-2^{-k})^{2^{3k}-k}\leq e^{-(2^{3k}-k)/2^{k}}.$

By the union bound, the probability that, for some set $S$ of vertices of size
$k$, there is no vertex with edges directed towards every vertex in $S$ is at
most

${2^{3k}\choose k}\cdot e^{-(2^{3k}-k)/2^{k}}.$

Basic calculus yields that this term is smaller than $1$ for all $k$. This
means there is a non-zero probability that $F$ has the stated properties. ∎

###  3.1 Graphs

We present our construction for graphs first, and afterwards for relational
structures.

######  Theorem 8.

There exists a constant $c$ such that, for every $n$, one can construct in
time $O(n^{3})$ an $n$-vertex graph satisfying the extension axioms
$\textnormal{EA}_{k}$ for all $k\leq\lfloor\log(\log(n))/c\rfloor$.

Since the extension axioms hold with high probability and determine the truth
of LFP sentences, it immediately follows that LFP cannot distinguish between a
truly random graph $G(n,1/2)$ and the pseudorandom output of Theorem 8. We
formalize this later in Theorem 12.

###### Proof of Theorem 8.

We prove the following claim that implies the theorem: There exists a constant
$c$ such that, for every $n,k\in\mathbb{\mathbb{Z}}_{\geq 1}$ with
$2^{k^{c}}\leq n$, one can construct in time $O(2^{2^{ck}}n^{2})$ an
$n$-vertex graph satisfying $\textnormal{EA}_{k}$.

Figure 1:  Our finite Rado graph construction. To find an extension vertex to
sets $S$ and $T$, first choose a tournament node with directed edges (large
gray arrows) towards all tournament nodes that contain parts of $S$. Within
this tournament node, choose a set $U$ from an $(n,k)$-universal set with
$U\cap S=T$. There exists an extension vertex $v$ with $N(v)\cap S=~{}T$.

There are at most $2^{2^{3k\cdot 2}}$ tournaments with $2^{3k}$ vertices. By
enumerating them all, we find according to Lemma 7 a tournament $F$ with the
vertex set $[2^{3k}]$ such that, for every $S\subseteq[2^{3k}]$ of size $k$,
there is a vertex $j\in[2^{3k}]$ that has a directed edge towards every vertex
in $S$.

We will construct a graph $G$ with vertex set $[n]$ satisfying the extension
axioms $\textnormal{EA}_{k}$. We start by using Theorem 6 to construct an
$(n,k)$-universal set $\mathcal{U}$. Next, we need to partition the vertex set
$[n]$ into $2^{3k}$ many parts $P_{1},\dots,P_{2^{3k}}$ of size at least
$|\mathcal{U}|$ (these will correspond to vertices in a tournament). Let us
argue that one can choose the parameter $c$ such that this is possible for all
$n\geq 2^{k^{c}}$. Let $c^{\prime}$ be the constant from Theorem 6, such that
we can bound the size of our $(n,k)$-universal set by
$2^{c^{\prime}k}\log(n)$. We may choose $c$ such, that for every
$k\in\mathbb{\mathbb{Z}}_{\geq 1}$,

$2^{3k}\cdot 2^{c^{\prime}k}\cdot 2\leq 2^{k^{c}}/k^{c}.$

Hence, for every $n\in\mathbb{\mathbb{Z}}_{\geq 1}$ with $2^{k^{c}}\leq n$
holds $2^{k^{c}}/k^{c}\leq n/\log(n)$ and thus

$2^{3k}\cdot 2^{c^{\prime}k}\log(n)\cdot 2\leq n.$

This means we can partition the vertices into parts $P_{1},\dots,P_{2^{3k}}$,
each of size at least

$\lfloor 2^{c^{\prime}k}\log(n)\cdot 2\rfloor\geq|\mathcal{U}|.$

Next, we want to choose a function $\textsc{pattern}:[n]\to\mathcal{U}$. Since
we have $|P_{j}|\geq|\mathcal{U}|$, we can guarantee that

$\\{\textsc{pattern}(v)\mid v\in P_{j}\\}=\mathcal{U}$

for all $j\in[2^{3k}]$. We further denote by $\textnormal{index}(v)$ the index
$j$ such that $v\in P_{j}$. To construct our graph $G$, we now do the
following for all pairs $\\{u,v\\}\in{[n]\choose 2}$:

> Up to renaming, we may assume that the arc in our tournament $F$ goes from
> $\textnormal{index}(v)$ to $\textnormal{index}(u)$. Add the edge $\\{u,v\\}$
> to $G$ if and only if $u\in\textsc{pattern}(v)$.

#### Correctness

Let $S\subseteq[n]$ and let $T\subseteq S$. We constructed our tournament $F$
using Lemma 7 such that we can choose $j\in[2^{3k}]$ with a directed edge to
all vertices in $\\{\textnormal{index}(s)\mid s\in S\\}$. Since $\mathcal{U}$
is an $(n,k)$-universal set, there exists $U\in\mathcal{U}$ such that $S\cap
U=T$. Since pattern, restricted to $P_{j}$, was chosen to be surjective, we
can pick $v\in P_{j}$ with $\textsc{pattern}(v)=U$. Since $F$ has no self
loops, $v\not\in S$. We selected $v$ such that $\textnormal{index}(v)$ has in
$F$ a directed edge to $\textnormal{index}(u)$ for all $u\in S$. Thus, $v$ is
adjacent to $u\in S$ if and only if $u\in\textsc{pattern}(v)=T$.

#### Run time

The construction of $F$ takes time at most $2^{2^{3k\cdot 2}}\cdot k^{2}$. By
Theorem 6, we can construct the $(n,k)$-universal set in time
$2^{c^{\prime}k}n\log(n)$. The remaining part of the construction takes time
$O(|\mathcal{U}|\cdot n^{2})$. By possibly rescaling $c$, we get a run time of
$O(2^{2^{ck}}n^{2})$. ∎

###  3.2 Relational structures

The definition of $k$-extension axioms $\textnormal{EA}^{\sigma}_{k}$ for
general signatures $\sigma$ becomes more involved, and thus our finite Rado-
construction becomes more opaque, even though we ultimately use the same
arguments as for graphs. Given a set $S$, we find a tournament node oriented
to the tournament nodes containing $S$. Instead of using universal sets, we
now select a function $f$ from a family of $(n,k)$-perfect hash functions that
is bijective on $S$. Our construction adds an extension element that is valid
for all sets $S$ on which $f$ is bijective. The definition of $k$-extension
axioms $\textnormal{EA}^{\sigma}_{k}$ (Definition 25) and the proof of Theorem
9 can be found in Appendix C.

######  Theorem 9.

Let $\sigma$ be a relational signature. There exists a constant $c$ such that,
for every $n$, one can construct in time $O(n^{c})$ an $n$-element
$\sigma$-structure satisfying the extension axioms
$\textnormal{EA}^{\sigma}_{k}$ for all $k\leq\lfloor\log(\log(n))/c\rfloor$.

Even though we do not prove this, Theorem 9 can be easily modified to also
generate pseudorandom hypergraphs. As we see in the next section, just like
for graphs, the extension axioms determine the truth of FO and LFP formulas
and hold with high probability.

###  3.3 Pseudorandom graphs and structures

Let us now discuss why the constructions of Theorem 8 and Theorem 9 give
pseudorandom structures for FO and LFP. First, observe that random graphs,
hypergraphs, and relational structures readily satisfy the respective
extension axioms.

######  Lemma 10.

For every signature $\sigma$ and every $k,t$,

$\displaystyle\Pr_{G\sim
G(1/2,n)}\bigl{[}G\not\models\textnormal{EA}_{k}\bigr{]}={}$
$\displaystyle\textnormal{negl}(n),$ $\displaystyle\Pr_{G\sim
G_{t}(1/2,n)}\bigl{[}G\not\models\textnormal{EA}^{t}_{k}\bigr{]}={}$
$\displaystyle\textnormal{negl}(n),$
$\displaystyle\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}\bigl{[}\mathbb{A}\not\models\textnormal{EA}^{\sigma}_{k}\bigr{]}={}$
$\displaystyle\textnormal{negl}(n).$

This is a well-known result [11, Sections 4.1 and 4.2], but we include a proof
in Appendix D for completeness.

Next, we argue via pebbling games (see for example [25, Lemma 12.7]) that the
extension axioms determine the truth of FO or LFP sentences. This proof is
also straightforward and included in Appendix E.

######  Lemma 11.

Consider a pair of graphs/hypergraphs/structures
$\mathbb{A}_{1},\mathbb{A}_{2}$ of the same signature that both satisfy the
corresponding $k$-extension axioms. Then, for every advice structure
$\mathbb{X}$, and every LFP sentence $\varphi$ of quantifier rank at most $k$
and matching signature, we have
$(\mathbb{A}_{1},\mathbb{X})\models\varphi\Leftrightarrow(\mathbb{A}_{2},\mathbb{X})\models\varphi$.

Now, Lemma 10 and Lemma 11 together with Theorem 8 (for graphs) and Theorem 9
(for structures) immediately imply the main theorem of this section.

######  Theorem 12.

There are deterministic polynomial-time algorithms to construct graphs or
relational structures that are pseudorandom for FO and LFP.

##  4 Pseudorandom Transductions

We now turn to the question of whether transductions can act as pseudorandom
generators. Specifically, we ask for which logics $L_{1}$ and $L_{2}$ and for
which relational signatures $\sigma$ and $\tau$ there exists an
$(L_{1},L_{2})$-pseudorandom transduction from $\sigma$ to $\tau$, that is, an
$L_{1}$-transduction that is secure against $L_{2}$. In this section, we
provide a complete classification for all pairs
$L_{1},L_{2}\in\\{\text{FO},\text{LFP},\text{$\textup{LFP}[\oplus]$}\\}$ and
all relational signatures.

Clearly, the existence of such transductions depends on the number and arities
of the relations in $\sigma$ and $\tau$. For instance, if the multiset of
arities of $\tau$ is a subset of that of $\sigma$, we may simply match up the
relation symbols with formulas of the form

$\theta_{i}({x}_{1},{x}_{2},\dots,{x}_{a_{i}})=R_{j}({x}_{1},{x}_{2},\dots,{x}_{a_{i}})$

and ignore the extra relation symbols from $\sigma$. This transduction is
definable in any logic and will yield a uniformly random $\tau$-structure, so
will be pseudorandom for any logic as well. A more interesting case is when
the target $\tau$-structures inherently have more “entropy” than the input
$\sigma$-structures, for example, going from a single binary relation to a
single ternary relation. Our results for this case were summarized in Table 1.

In other cases it is not immediately clear how to measure entropy. For
example, does there exist a pseudorandom transduction from a signature with
one ternary relation to a signature with ten binary relations? Curiously, we
find that the “right” way of measuring entropy depends on the tranduction
logic $L_{1}$; in this particular case the answer for FO and LFP is No, while
the answer for $\textup{LFP}[\oplus]$ is Yes.

Let $\sigma=\langle{R}_{1},{R}_{2},\dots,{R}_{t}\rangle$ and $\tau=\langle
R^{\prime}_{1},R^{\prime}_{2},\dots,R^{\prime}_{t^{\prime}}\rangle$ be
signatures, where $R_{i}$ has arity $a_{i}$ and $R^{\prime}_{i}$ has arity
$a^{\prime}_{i}$. We will show that the right measure of entropy for
$\textup{LFP}[\oplus]$ is the following “lexicographic” order $\succeq_{L}$.
We say $\sigma\succeq_{L}\tau$ if and only if the arity-tuple
$({a}_{1},{a}_{2},\dots,{a}_{t})$ of $\sigma$ is (weakly) lexicographically
larger than the corresponding tuple
$(a^{\prime}_{1},a^{\prime}_{2},\dots,a^{\prime}_{t^{\prime}})$ of $\tau$
after sorting both tuples in descending order. Equivalently,

$\sigma\succeq_{L}\tau\iff\sum_{i=1}^{t}(t+t^{\prime})^{a_{i}}\geq\sum_{i=1}^{t^{\prime}}(t+t^{\prime})^{a^{\prime}_{i}}.$

As one may expect, $\succeq_{L}$ is a total order and matches our intuitive
understanding of entropy in random structures, where one assigns an $a$-ary
relation an entropy of $n^{a}$, which is asymptotically larger than any
combination of $b$-ary relations with $b<a$.

The story becomes more complex when the transduction logic $L_{1}$ is FO or
LFP. Here, the correct entropy measure will be the order $\succeq_{S}$ defined
by

$\sigma\succeq_{S}\tau\iff\text{for all $k\in\mathbb{Z}_{\geq 1}$,
}\sum_{i=1}^{t}T(a_{i},k)\geq\sum_{i=1}^{t^{\prime}}T(a^{\prime}_{i},k),$

where

$T(a,k):=\sum_{j=0}^{k}(-1)^{k-j}j^{a}{k\choose j}$

counts the number of surjections from a set of size $a$ to a set of size $k$
[15, (6.19)]. Note that $\succeq_{S}$ is a refinement of $\succeq_{L}$, and is
not a total order. That is, having more entropy in the sense of $\succeq_{L}$
is a necessary, but not sufficient condition for the existence of pseudorandom
generators. Intuitively speaking, this is because FO and LFP are not powerful
enough to convert certain “shapes” of the input entropy into the required
output shape.

We summarize how the existence of pseudorandom transductions depends on both
the logics and the entropies of the signatures in Table 2, from which Table 1
can be derived as a special case.

$\Theta$ $\varphi$ | FO | LFP | $\textup{LFP}[\oplus]$
---|---|---|---
FO | $\sigma\succeq_{S}\tau$ | $\sigma\succeq_{S}\tau$ | $\sigma\succeq_{S}\tau$
LFP | $\sigma\succeq_{S}\tau$ | $\sigma\succeq_{S}\tau$ | $\sigma\succeq_{S}\tau$
$\textup{LFP}[\oplus]$ |  $\sigma\succeq_{L}\tau$ or $\sigma$ not all-unary |  $\sigma\succeq_{L}\tau$ or $\sigma$ not all-unary |  $\sigma\succeq_{L}\tau$ or ($\sigma$ not all-unary and OWFs exist)
Table 2: Conditions on the signatures $\sigma$ and $\tau$ for the existence of
an $(L_{1},L_{2})$-pseudorandom generator from $\sigma$ to $\tau$. The rows
range over generator logics $L_{1}$ and the columns range over adversary
logics $L_{2}$. This generalizes Table 1.

###  4.1 Impossibility for LFP

We now state and outline the proof of the following result, filling in the top
two-thirds of Table 2.

######  Theorem 13.

Let $\sigma=\langle{R}_{1},{R}_{2},\dots,{R}_{t}\rangle$ and $\tau=\langle
R^{\prime}_{1},R^{\prime}_{2},\dots,R^{\prime}_{t^{\prime}}\rangle$ be
relational signatures, where $R_{i}$ has arity $a_{i}$ and $R^{\prime}_{i}$
has arity $a^{\prime}_{i}$. The following statements are equivalent:

  1. (i)

There exists an $(\textnormal{LFP},\textnormal{FO})$-pseudorandom generator
from $\sigma$ to $\tau$.

  2. (ii)

There exists a quantifier-free FO transduction
$\Theta:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ such that, for all $n$,
the distribution on $\textup{Str}[{\tau,n}]$ obtained by applying $\Theta$ to
$\mathbb{A}\sim\textup{Str}[{\sigma,n}]$ is statistically identical to the
distribution $\mathbb{B}\sim\textup{Str}[{\tau,n}]$.

  3. (iii)

$\sigma\succeq_{S}\tau$.

To see why this fills in the FO and LFP rows of Table 2, first suppose
$\sigma\succeq_{S}\tau$. Then by (ii), there is a FO-transduction (and thus an
LFP-transduction) $\Theta$ generating $\tau$-structures statistically
identical to random $\tau$-structures. Thus, not even a computationally
unbounded adversary could distinguish the two cases, so $\Theta$ is secure
against any adversary logic, filling in the top two rows in the affirmative.
On the other hand, if we do not have $\sigma\succeq_{S}\tau$, then by (i),
even a generator defined in LFP cannot fool every adversary in FO, and the
same holds for weaker generators and stronger adversaries, filling in the top
two rows in the negative.

This theorem can be thought of as an impossibility theorem for LFP. The
equivalence of (i) and (ii) means that there are no “novel”
$(\textnormal{LFP},\textnormal{FO})$-pseudorandom generators, in the sense
that any LFP-definable transduction that is secure even against the weak logic
FO can be replaced by an extremely simple alternative transduction in which
all formulas are FO and do not contain quantifiers. And this simple
transduction is “as secure as it gets,” in the sense that the output
distribution is not merely computationally indistinguishable from the truly-
random distribution, but _is_ the truly-random distribution. Thus, all the
additional power of LFP is irrelevant for generating pseudorandom structures
in this context.

As we previously remarked, the notion of entropy $\succeq_{S}$ for
characterizing pseudorandom generators in these logics is only a partial
order. For instance, if $\sigma$ consists of one binary relation and $\tau$
consists of two unary relations, Theorem 13 implies that there are no
pseudorandom generators either from $\sigma$ to $\tau$ or from $\tau$ to
$\sigma$, since

$\sum_{i=1}^{t}T(a_{i},2)=2>0=\sum_{i=1}^{t^{\prime}}T(a^{\prime}_{i},2)$

but

$\sum_{i=1}^{t}T(a_{i},1)=1<2=\sum_{i=1}^{t^{\prime}}T(a^{\prime}_{i},1).$

The full proof is long and technical, and thus deferred to Appendix F. Here we
sketch the argument for all 3 cases.

(ii)$\implies$(i): This is immediate, since a transduction $\Theta$ with the
properties in (ii) is an $(L_{1},L_{2})$-pseudorandom generator for any
$L_{1}$ and $L_{2}$ such that $L_{1}$ extends quantifier-free FO.

(iii)$\implies$(ii): Consider the following example. Suppose we want to build
a transduction from an input signature $\sigma$ consisting of three relations
of arities $a_{1}=3$, $a_{2}=1$, $a_{3}=1$, to an output signature $\tau$ with
also three relations, but of arities
$a^{\prime}_{1}=a^{\prime}_{2}=a^{\prime}_{3}=2$. If $\sigma$ had a binary
relation, we could use it to directly fill one of the three relations in
$\tau$; but since we do not, we must use specializations of the ternary
relation of the form $R_{1}(x,x,y)$, $R_{1}(x,y,x)$, and $R_{1}(y,x,x)$. For
$x\neq y$, these tuples will each be in the relation $R_{1}$ independently of
one another, so can each be used to fill one of the 3 binary relations in
$\tau$. However, this accounting only takes care of “binary parts” of the
relations, where there are two distinct variables involved. To determine which
relations $R^{\prime}_{i}(x,x)$ hold, we may only use $R_{1}(x,x,x)$ once, so
have to use the unary relations $R_{2}(x)$ and $R_{3}(x)$ for the other two.
Thus, by treating the binary and unary parts separately, we arrive at a
quantifier-free FO transduction $\Theta=(\theta_{1},\theta_{2},\theta_{3})$
that produces uniformly random $\tau$-structures from uniformly random
$\sigma$-structures:

$\displaystyle\theta_{1}(x_{1},x_{2}):=\ $ $\displaystyle
R_{1}(x_{1},x_{1},x_{2})$ $\displaystyle\theta_{2}(x_{1},x_{2}):=\ $
$\displaystyle\bigl{(}(x_{1}\neq x_{2})\wedge
R_{1}(x_{1},x_{2},x_{1})\bigr{)}\vee\bigl{(}(x_{1}=x_{2})\wedge
R_{2}(x_{1})\bigr{)}$ $\displaystyle\theta_{3}(x_{1},x_{2}):=\ $
$\displaystyle\bigl{(}(x_{1}\neq x_{2})\wedge
R_{1}(x_{1},x_{2},x_{2})\bigr{)}\vee\bigl{(}(x_{1}=x_{2})\wedge
R_{3}(x_{1})\bigr{)}.$

More generally, the condition that $\sigma\succeq_{S}\tau$ amounts to checking
that there are enough $k$-ary parts of relations in $\sigma$ to cover the
$k$-ary parts of the relations in $\tau$, for each possible number of distinct
variables $k$.

$\neg$(iii)$\implies$$\neg$(i): This is the most difficult part of the
argument, where we must use the zero-one law to argue that, no matter what the
LFP transduction
$\Theta=({\theta}_{1},{\theta}_{2},\dots,{\theta}_{t^{\prime}})$ does, we can
construct an FO sentence $\varphi$ that distinguishes its outputs from truly
random $\tau$-structures. In order to do this, we must manipulate each formula
$\theta_{i}$ to put it into a form where the zero-one law applies. For
example, suppose one of the formulas is

$\theta_{i}(x_{1},x_{2},x_{3})=\forall x_{4}\ R_{1}(x_{3},x_{4}).$

By distinguishing whether or not $x_{4}\in\\{x_{1},x_{2},x_{3}\\}$, we first
equivalently rewrite this sentence as

$\theta_{i}(x_{1},x_{2},x_{3})=R_{1}(x_{3},x_{1})\wedge
R_{1}(x_{3},x_{2})\wedge R_{1}(x_{3},x_{3})\wedge\forall
x_{4}\notin\\{x_{1},x_{2},x_{3}\\}\ R_{1}(x_{3},x_{4}).$

We then observe that $R_{1}(x_{3},\cdot)$ can be thought of as a random unary
relation on the structure obtained by removing $x_{1}$, $x_{2}$, and $x_{3}$,
so by the zero-one law applied to this structure, we know that the final part
of this sentence,

$\forall x_{4}\notin\\{x_{1},x_{2},x_{3}\\}\ R_{1}(x_{3},x_{4}),$

can be replaced by either TRUE or FALSE (in this case FALSE) and the resulting
formula will be equivalent with probability $1-\textnormal{negl}(n)$. In this
manner, we may remove all quantifiers from the formula. Taking a union bound
over the polynomially-many negligible error terms, we conclude that the
resulting quantifier-free formula $\overline{\theta}_{i}$ will be equivalent
with probability $1-\textnormal{negl}(n)$.

Finally, we let $k$ be a positive integer violating the condition that
$\sigma\succeq_{S}\tau$ and choose a large (but constant) positive integer
$c$. We write a sentence $\varphi$ that checks the following condition: “For
every way that a $c$-tuple $({y}_{1},{y}_{2},\dots,{y}_{c})$ of $c$ distinct
elements of the universe _could_ behave with respect to relations using at
most $k$ distinct variables exclusively from
$\\{{y}_{1},{y}_{2},\dots,{y}_{c}\\}$, there is in fact a $c$-tuple that
_does_ behave in that way.” Clearly, a truly random $\tau$-structure will
satisfy $\varphi$ with probability $1-\textnormal{negl}(n)$. On the other
hand, we show that, for large enough $c$,
$\overline{\Theta}=({\overline{\theta}}_{1},{\overline{\theta}}_{2},\dots,{\overline{\theta}}_{t^{\prime}})$
produces structures satisfying $\varphi$ with probability 0. This step is
formally accomplished by the following Lemma, which is proved in Appendix G
and is also used later to show impossibilities for $\textup{LFP}[\oplus]$ when
$\sigma$ has only unary relations.

######  Definition 14.

Given integers $1\leq k\leq c$, a relational signature
$\sigma=\langle{R}_{1},{R}_{2},\dots,{R}_{t}\rangle$ with arities
${a}_{1},{a}_{2},\dots,{a}_{t}$, a $\sigma$-structure $\mathbb{A}$ and
distinct elements ${y}_{1},{y}_{2},\dots,{y}_{c}\in\mathbb{A}$, the _$(c,k)$
-type of $({y}_{1},{y}_{2},\dots,{y}_{c})$ in $\mathbb{A}$_ is the subset

$T\subseteq\bigcup_{i=1}^{t}\bigcup_{\begin{subarray}{c}S\subseteq[c]\\\
\left|{S}\right|\leq k\end{subarray}}\\{(i,S,g)\ |\ g:[a_{i}]\to S\text{ is
surjective}\\}$

such that $T$ describes (by indexing $({y}_{1},{y}_{2},\dots,{y}_{c})$)
exactly which relations in $\mathbb{A}$ hold on tuples containing at most $k$
distinct elements from $({y}_{1},{y}_{2},\dots,{y}_{c})$. In other words,
$(i,S,g)\in T$ means $(y_{g(1)},y_{g(2)},\dots,y_{g(a_{i})})\in
R_{i}^{\mathbb{A}}$.

######  Lemma 15.

Suppose $\sigma$ and $\tau$ are relational signatures for which some positive
integer $k$ violates the condition that ${\sigma\succeq_{S}\tau}$. Let
$f:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ be a function such that, for
any positive integer $c\geq k$ and any $\sigma$-structure $\mathbb{A}$, if the
$(c,k)$-types of any pair of $c$-tuples
$({y}_{1},{y}_{2},\dots,{y}_{c}),(y^{\prime}_{1},y^{\prime}_{2},\dots,y^{\prime}_{c})\in\mathbb{A}^{c}$
are the same in $\mathbb{A}$ then their $(c,k)$-types are the same in
$f(\mathbb{A})$. Then the distribution obtained by applying $f$ to a uniformly
random $\sigma$-structure is not pseudorandom for FO.

We may apply this lemma to $f:=\overline{\Theta}$ since it is quantifier-free,
which yields that $\overline{\Theta}$ is not a pseudorandom generator. Since
the original transduction $\Theta$ differs from $\overline{\Theta}$ only
negligibly, it follows that $\Theta$ is not a pseudorandom generator either.

###  4.2 Possibility for $\textup{LFP}[\oplus]$

Adding in a parity operator allows us to circumvent the zero-one law so that
pseudorandom transductions are plausible. In the presence of at least one non-
unary relation, we can canonize an input structure and thus define a
pseudorandom output structure for FO and LFP using the polynomial-time
construction from Theorem 12.

######  Corollary 16.

For $L_{2}\in\\{\textnormal{FO},\textnormal{LFP}\\}$, there exists an
$(\textnormal{$\textup{LFP}[\oplus]$},L_{2})$-pseudorandom generator from
$\sigma$ to $\tau$ if and only if $\sigma$ has at least one non-unary relation
or $\sigma$ and $\tau$ both have only unary relations, with $\sigma$
containing at least as many as $\tau$.

###### Proof.

If $\sigma$ has at least one non-unary relation, it is possible to canonize
(meaning define a total order on) the entire input structure with probability
$1-\textnormal{negl}(n)$ by Lemma 2. Assuming this happens, by the Immerman-
Vardi Theorem (Theorem 1) we have the full power of polynomial-time
computation, so may apply the deterministic algorithm of Theorem 12.

If $\sigma$ and $\tau$ both have only unary relations and $\sigma$ has at
least as many as $\tau$, a pseudorandom transduction obviously exists by
simply matching them up and ignoring any extras.

If neither of these conditions hold, it means that $\sigma\succeq_{S}\tau$ is
violated for $k=1$. Let $\Theta:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$
be an arbitrary $\textup{LFP}[\oplus]$ transduction. For any integer $c$, if
two $c$-tuples have the $(c,1)$-types in a $\sigma$-structure $\mathbb{A}$, it
means that the same unary relations hold on the $i^{\text{th}}$ element of
each tuple for each $1\leq i\leq c$. Since $\sigma$ has only unary relations,
it follows that there is an automorphism of $\mathbb{A}$ taking one tuple to
the other. Since $\Theta$ is a transduction, it means that there is a similar
automorphism in $\Theta(\mathbb{A})$, implying that the two tuples have the
same $(c,1)$-type in $\Theta(\mathbb{A})$. Hence Lemma 15 applies, so $\Theta$
is not a pseudorandom transduction for FO or LFP. ∎

In light of this theorem, the only remaining box in Table 2 we have not
discussed is the bottom-right cell, when both logics are
$\textup{LFP}[\oplus]$. The following result completely characterizes when
$(\textnormal{$\textup{LFP}[\oplus]$},\textnormal{$\textup{LFP}[\oplus]$})$-pseudorandom
generators exist, depending on the comparative entropies of $\sigma$ and
$\tau$ (this time measured using $\succeq_{L}$, rather than $\succeq_{S}$).

######  Theorem 17.

Let $\sigma$ and $\tau$ be relational signatures.

  1. (i)

If $\sigma\prec_{L}\tau$ and $\sigma$ contains at least one non-unary
relation, then
$(\textnormal{$\textup{LFP}[\oplus]$},\textnormal{$\textup{LFP}[\oplus]$})$-pseudorandom
generators from $\sigma$ to $\tau$ exist if and only if length-increasing
ordinary pseudorandom generators exist (i.e., Conjecture 3 holds).

  2. (ii)

If $\sigma\succeq_{L}\tau$, then there exists an
$(\textnormal{$\textup{LFP}[\oplus]$},\textnormal{$\textup{LFP}[\oplus]$})$-pseudorandom
generator from $\sigma$ to $\tau$.

  3. (iii)

Otherwise, there does not exist an
$(\textnormal{$\textup{LFP}[\oplus]$},\textnormal{$\textup{LFP}[\oplus]$})$-pseudorandom
generator from $\sigma$ to $\tau$.

The most difficult and interesting statement is (i), and the proof involves
converting back and forth between strings and relational structures in a way
that is definable in $\textup{LFP}[\oplus]$. It turns out that the backward
direction of the proof, which involves building a pseudorandom transduction
from an ordinary pseudorandom generator, is relatively straightforward.
However, the forward direction presents multiple challenges. To build an
ordinary pseudorandom generator out of a pseudorandom transduction $\Theta$,
the basic idea is to use the random input bits to construct a structure
$\mathbb{A}$, simulate applying $\Theta$ to it, then read out the relations to
generate more random bits than we started with. To prove security, we must
argue that an ordinary adversary distinguishing random from pseudorandom
strings can be turned into a logical adversary distinguishing random from
pseudorandom structures. To define such a logical adversary, it is necessary
for the post-processing step of reading out the random bits from the relations
to be definable in $\textup{LFP}[\oplus]$ in an order-invariant way, i.e.,
_without_ referring to the original arbitrary order of the elements of the
universe. When $\tau$ contains an extra $k$-ary relation for $k\geq 2$ we may
achieve this by using Lemma 2 to do the post-processing step. Thus, the only
remaining case is when $\tau$ contains the same number of $k$-ary relations as
$\sigma$ for all $k\geq 2$ but has more unary relations. This problem is by
far the most challenging, and we tackle it by employing a novel adaptation of
the length-extension theorem from cryptography (reviewed in Section 2.4) to
our domain. This involves writing an $\textup{LFP}[\oplus]$ formula to iterate
$\Theta$ a polynomial number of times, extracting a single random parity bit
from the extra unary relation in $\tau$ on each iteration, as illustrated in
Figure 3.

The only place where we use the parity operator is in applying Lemma 2
(multiple times). The proof goes through exactly the same if we were to
replace $\textup{LFP}[\oplus]$ with the extensively-studied _fixed point logic
with counting_ (FPC).

###### Proof of Theorem 17.

(i): We define

$\displaystyle p(n)$ $\displaystyle:=\sum_{i=1}^{t}n^{a_{i}},$ $\displaystyle
p^{\prime}(n)$ $\displaystyle:=\sum_{i=1}^{t^{\prime}}n^{a^{\prime}_{i}}.$

For the backward direction, suppose ordinary pseudorandom generators exist.
Let $R$ be a relation in $\sigma$ of arity at least 2 and let
$f:\\{0,1\\}^{n}\to\\{0,1\\}^{p^{\prime}(n)}$ be a pseudorandom generator.
Consider the $\textup{LFP}[\oplus]$ transduction $\Theta$ described by the
following algorithm. On input $\mathbb{A}$, we first apply the transduction
from Lemma 2 using $R$ to obtain (with probability $1-\textnormal{negl}(n)$) a
total order over the universe $\leq$ and at least $\Omega(n^{2})$ bits of
independent randomness from $R$ at locations described by relation $Q$. We
then simulate $f$ (via Theorem 1) on the first $n$ bits of randomness
according to $\leq$ to obtain $p^{\prime}(n)$ bits of pseudorandomness, which
we then use to fill all the relations in $\tau$, again according to the order
$\leq$. It is clear that this can all be accomplished as an
$\textup{LFP}[\oplus]$ transduction.

Suppose toward a contradiction that some $\textup{LFP}[\oplus]$ adversary
$\varphi$ could break the security of $\Theta$. Then consider the algorithm
$A$ that, on input $t\in\\{0,1\\}^{p^{\prime}(n)}$, generates a
$\tau$-structure $\mathbb{B}$ using $t$ to determine each relation, then
evaluates $\varphi$ and outputs 1 if and only if $\mathbb{B}\models\varphi$.
Clearly, when $t$ is a uniformly random string, $A$ outputs 1 with the same
probability that $\mathbb{B}\models\varphi$ for a random
$\mathbb{B}\sim\textup{Str}[{\tau,n}]$. On the other hand, feeding in $t=f(s)$
for a uniformly random $s\sim\\{0,1\\}^{n}$ is equivalent to attempting to
apply Lemma 2 over and over until it succeeds in ordering the structure and
producing $n$ ordered bits of independent randomness, then applying $f$ to the
result, as depicted in Figure 2. On a random structure $\mathbb{A}$ that can
be successfully ordered, $A$ will then output 1 if and only if
$\Theta(\mathbb{A})\models\varphi$. Thus, the probability $A$ outputs 1 in the
case where $t=f(s)$ is precisely the probability that
$\Theta(\mathbb{A})\models\varphi$ for a random
$\mathbb{A}\sim\textup{Str}[{\sigma,n}]$, but conditioned on the event that
$\mathbb{A}$ was successfully ordered, which we denote as sampling
$\mathbb{A}\sim\textup{Str}_{\leq}[{\sigma,n}]$. By Lemma 2, this is only
different from the unconditional
$\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}[\Theta(\mathbb{A})\models\varphi]$
by a negligible amount. By the triangle inequality, we have that

$\displaystyle\left|{\Pr_{t\sim\\{0,1\\}^{p^{\prime}(n)}}[A(t)=1]-\Pr_{s\sim\\{0,1\\}^{n}}[A(f(s))=1]}\right|$
$\displaystyle=\left|{\Pr_{\mathbb{B}\sim\textup{Str}[{\tau,n}]}[\mathbb{B}\models\varphi]-\Pr_{\mathbb{A}\sim\textup{Str}_{\leq}[{\sigma,n}]}[\Theta(\mathbb{A})\models\varphi]}\right|$
$\displaystyle\geq\left|{\Pr_{\mathbb{B}\sim\textup{Str}[{\tau,n}]}[\mathbb{B}\models\varphi]-\Pr_{\mathbb{A}\sim\textup{Str}_{\leq}[{\sigma,n}]}[\Theta(\mathbb{A})\models\varphi]}\right|$
$\displaystyle\ \ \
-\left|{\Pr_{\mathbb{A}\sim\textup{Str}_{\leq}[{\sigma,n}]}[\Theta(\mathbb{A})\models\varphi]-\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}[\Theta(\mathbb{A})\models\varphi]}\right|,$

which is non-negligible, since the first term is non-negligible and the second
term is negligible. Thus, $A$ breaks the security of $f$, which is a
contradiction.

Figure 2: Illustration accompanying the backward direction of the proof of
Theorem 17 (i), where $\cong$ denotes the fact that the two distributions over
outputs in $\\{0,1\\}$ are only negligibly different, as Lemma 2 fails with
negligible probability.

For the forward direction, suppose
$\Theta:\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$ is an
$(\textnormal{$\textup{LFP}[\oplus]$},\textnormal{$\textup{LFP}[\oplus]$})$-pseudorandom
generator. To define an ordinary pseudorandom generator, there are two cases
to consider. Let $k$ be the largest arity such that $\sigma$ and $\tau$ have a
different number of relations of arity $k$, and first consider the case where
$k\geq 2$. Let $g(n)=\Omega(n^{k})$ be the function from Lemma 2, and let

$h(n):=\sum_{k^{\prime}=k}^{\infty}\left|{\\{i\ |\
a_{i}=k^{\prime}\\}}\right|\cdot n^{k^{\prime}}.$

From the way $k$ was defined and the fact that $\sigma\prec_{L}\tau$, we know
that, for all $k^{\prime}\geq k$, the coefficient of $n^{k^{\prime}}$ is the
same in $h(n)$ and $p^{\prime}(n)$, while the $n^{k}$ coefficient is strictly
larger in $h(n)$. Hence, for large enough $n$, $p^{\prime}(n)\leq
h(n)-n^{k}+g(n)$, as $g(n)=\Omega(n^{k})$ dominates any remaining degree $<k$
terms coming from relations in $\tau$ of arity $<k$. It thus suffices to
define a pseudorandom generator
$f:\\{0,1\\}^{p(n)}\to\\{0,1\\}^{h(n)-n^{k}+g(n)}$. On input
$s\in\\{0,1\\}^{p(n)}$, we use all of the random bits to generate a random
$\sigma$-structure $\mathbb{A}$. We then run $\Theta$ to obtain a
$\tau$-structure $\mathbb{B}=\Theta(\mathbb{A})$, on which we apply Lemma 2
using an arbitrary $k$-ary relation $R$ of $\tau$. With probability
$1-\textnormal{negl}(n)$, we obtain a total order over the universe and can
extract and output $g(n)$ ordered bits of randomness from $R$ and a further
$h(n)-n^{k}$ ordered bits of randomness from the other relations of arity at
least $k$. (If the ordering step fails, we just output some arbitrary string.)

Suppose toward a contradiction that some adversary $A$ could break the
security of $f$. Then we describe an $\textup{LFP}[\oplus]$ adversary
$\varphi$ to break $\Theta$ via the following algorithm. Given a
$\tau$-structure $\mathbb{B}$, we order the structure and extract
$h(n)-n^{k}+g(n)$ bits of randomness as in the last step of $f$, and then
return true if and only if $A$ outputs 1 on the resulting string. Clearly,
this can be implemented in $\textup{LFP}[\oplus]$ (by Theorem 1). If
$\mathbb{B}$ was sampled randomly from $\textup{Str}[{\tau,n}]$, then, with
probability $1-\textnormal{negl}(n)$, the input fed to $A$ is a uniformly
random $p(n)$-bit string. On the other hand, testing whether
$\mathbb{B}=\Theta(\mathbb{A})\models\varphi$ for
$\mathbb{A}\sim\textup{Str}[{\sigma,n}]$ is equivalent to generating a random
$p(n)$-bit string, using it to fill relations in $\mathbb{A}$, applying
$\Theta$, applying Lemma 2 to extract $h(n)-n^{k}+g(n)$ bits of randomness,
and finally feeding the resulting string into $A$. Executing these steps is
precisely equivalent to running $f$ on a uniformly random $p(n)$ bit string
and then feeding the result to $A$. Thus, since $A$ breaks the security of
$f$, it follows from a similar argument as in the forward direction that
$\varphi$ breaks the security of $\Theta$, contradicting our assumption.

Finally, consider the case where $k=1$. In other words, $\sigma$ and $\tau$
have the same numbers of relations of every arity greater than 1, but $\tau$
has strictly more unary relations than $\sigma$. Without loss of generality,
assume $\sigma$ and $\tau$ have the same relation symbols, except that $\tau$
has exactly one more unary relation symbol, $U$ (if there are more than one
extra unary relations, we ignore them). Let
$f:\\{0,1\\}^{p(n)}\to\\{0,1\\}^{p(n)+1}$ be defined as follows. We use the
input bits to generate a random $\sigma$-structure $\mathbb{B}_{0}$, then
apply $\Theta$ repeatedly, $p(n)+1$ times, ignoring the $U$ relation. Let
$\mathbb{B}_{i}$ be the intermediate $\tau$-structure obtained after $i$
iterations. We then output a string $t$ where the $i^{\text{th}}$ bit of $t$
is equal to $\left|{U^{\mathbb{B}_{i}}}\right|\bmod 2$, i.e., the parity of
the number of elements on which $U$ held on the output of the $i^{\text{th}}$
iteration (see Figure 3).

Figure 3: Illustration of the length-extension construction of an ordinary
pseudorandom generator $f:\\{0,1\\}^{p(n)}\to\\{0,1\\}^{p(n)+1}$ using a
pseudorandom transduction $\Theta$.

To prove $f$ is secure, we use the hybrid argument. For each
$i\in\\{0,1,2,3,\dots,p(n)+1\\}$, let $H_{i}$ be the distribution over
($p(n)+1$)-bit strings where the first $i$ bits are chosen uniformly at
random, while the remaining bits are determined by iterating $\Theta$ as in
the definition of $f$, starting from a random $\sigma$-structure. Suppose
toward a contradiction that some adversary $A$ could break the security of
$f$. That is,

$\left|{\Pr_{s\sim\\{0,1\\}^{p(n)}}[A(f(s))=1]-\Pr_{t\sim\\{0,1\\}^{p(n)+1}}[A(t)=1]}\right|$

is non-negligible. Since $H_{0}$ is equivalent to the former distribution and
$H_{p(n)+1}$ is equivalent to the latter distribution, it follows from the
triangle inequality that, for some $i^{*}\in\\{0,1,2,3,\dots,p(n)\\}$,

$\left|{\Pr_{y\sim H_{i^{*}}}[A(y)=1]-\Pr_{y\sim H_{i^{*}+1}}[A(y)=1]}\right|$

is non-negligible (as the sum of any $p(n)$ negligible functions is
negligible). We will use this to define an $\textup{LFP}[\oplus]$ adversary
$\varphi$ to break $\Theta$. First consider the following randomized algorithm
$A^{\prime}$. Given a $\tau$-structure $\mathbb{B}$, we uniformly sample
$r\sim\\{0,1\\}^{i^{*}}$, then iterate $\Theta$, $p(n)-i^{*}$ times, starting
from $\mathbb{B}$, to extract $p(n)+1-i^{*}$ parity bits from the $U$
relation, just as in the definition of $f$ (we include the initial parity of
$U^{\mathbb{B}}$ as well), appending the result to $r$. We then run $A$ on the
resulting $p(n)+1$ bit string and output whatever it does. Observe that, when
the input $\mathbb{B}$ is a random $\tau$-structure, the distribution over the
input fed to $A$ is precisely $H_{i^{*}+1}$, and when
$\mathbb{B}=\Theta(\mathbb{A})$ for $\mathbb{A}\sim\textup{Str}[{\sigma,n}]$,
the distribution over the input fed to $A$ is precisely $H_{i^{*}}$. Thus, we
have that

$\left|{\Pr_{\begin{subarray}{c}\mathbb{A}\sim\textup{Str}[{\sigma,n}]\\\
r\sim\\{0,1\\}^{i^{*}}\end{subarray}}[A^{\prime}(\Theta(\mathbb{A}))=1]-\Pr_{\begin{subarray}{c}\mathbb{B}\sim\textup{Str}[{\tau,n}]\\\
r\sim\\{0,1\\}^{i^{*}}\end{subarray}}[A^{\prime}(\mathbb{B})=1]}\right|$

is non-negligible. All that remains is to convert $A^{\prime}$ into an
$\textup{LFP}[\oplus]$ sentence $\varphi$, which will then contradict our
assumption that $\Theta$ is secure. The main difficulty is that $A^{\prime}$
is a randomized algorithm. While an $\textup{LFP}[\oplus]$-transduction cannot
draw random bits for $r$ we can instead encode a good realization $r^{*}$ into
the advice structure and use that. By this, we mean a sample
$r\in\\{0,1\\}^{i^{*}}$ such that

$\displaystyle\left|{\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}[A^{\prime}(\Theta(\mathbb{A}),r^{*})=1]-\Pr_{\mathbb{B}\sim\textup{Str}[{\tau,n}]}[A^{\prime}(\mathbb{B},r^{*})=1]}\right|$
$\displaystyle\geq\left|{\Pr_{\begin{subarray}{c}\mathbb{A}\sim\textup{Str}[{\sigma,n}]\\\
r\sim\\{0,1\\}^{i^{*}}\end{subarray}}[A^{\prime}(\Theta(\mathbb{A}))=1]-\Pr_{\begin{subarray}{c}\mathbb{B}\sim\textup{Str}[{\tau,n}]\\\
r\sim\\{0,1\\}^{i^{*}}\end{subarray}}[A^{\prime}(\mathbb{B})=1]}\right|,$

which must exist by the averaging principle. We also encode a total order into
the advice structure to allow us to store the outputs of each iteration of
$\Theta$ using an inductively defined relation. Thus, we can turn $A^{\prime}$
into an $\textup{LFP}[\oplus]$ sentence $\varphi$, concluding the proof of
case (i).

(ii): If $(a^{\prime}_{1},a^{\prime}_{2},\dots,a^{\prime}_{t^{\prime}})$ is a
permutation of $({a}_{1},{a}_{2},\dots,{a}_{t})$, then clearly an
$(\text{$\textup{LFP}[\oplus]$},\text{$\textup{LFP}[\oplus]$})$-pseudorandom
generator exists by mapping relations to each other according to that
permutation. Otherwise, let $k$ be the largest arity such that $\sigma$ and
$\tau$ have a different number of relations of arity $k$. If $k=1$, then it is
again easy to construct a pseudorandom generator from $\sigma$ to $\tau$: Just
match up relations by arity and ignore the extra unary relation(s) in
$\sigma$. If $k\geq 2$, then matching up the lower arity parts may not be
possible (that is, when $\sigma\succeq_{L}\tau$ but
$\sigma\not\succeq_{S}\tau$). Instead, we appeal to Lemma 2 again, using a
$k$-ary relation to (with probability $1-\textnormal{negl}(n)$) order the
universe and then fill the lower arity relations with the $\Omega(n^{k})$ bits
of randomness defined by $Q$, in order. Since this yields a uniformly random
$\tau$-structure with probability $1-\textnormal{negl}(n)$, the resulting
distribution is clearly pseudorandom for any logic.

(iii): In this case $\sigma$ contains only unary relations and
$\sigma\prec_{L}\tau$, which implies $\sigma\not\succeq_{S}\tau$ as
$\succeq_{S}$ is a refinement of $\succeq_{L}$. By Corollary 16, there does
not even exist an $(\text{$\textup{LFP}[\oplus]$},\text{FO})$-pseudorandom
generator from $\sigma$ to $\tau$, so clearly there cannot be an
$(\text{$\textup{LFP}[\oplus]$},\text{$\textup{LFP}[\oplus]$})$-pseudorandom
generator either. ∎

##  5 First Order Logic with Parity

The transduction $\theta^{t}(x_{1},\dots,x_{t}):=\oplus
y~{}\bigwedge_{i=1}^{t}E(y,x_{i})$ asks whether there are an odd number of
vertices $y$ that are adjacent to all vertices from $x_{1},\dots,x_{t}$. It
creates a $t$-hypergraph from an ordinary graph. We argue that FO and LFP
cannot distinguish $\theta^{t}(G(n,1/2))$ from a real random $t$-hypergraph
$G_{t}(n,1/2)$ by showing that both satisfy the following extension axioms
with high probability.

######  Definition 18.

A $t$-hypergraph satisfies the extension axioms $\textnormal{EA}^{t}_{k}$ if
for all sets $S$ of size $k$ and all $T\subseteq{S\choose t-1}$ there exists
$v\not\in S$ such that for every $\\{s_{1},\dots,s_{t-1}\\}\in{S\choose t-1}$
we have a hyperedge $\\{s_{1},\dots,s_{t-1},v\\}$ if and only if
$\\{s_{1},\dots,s_{t-1}\\}\in T$.

Lemma 11 states that, also for hypergraphs, the corresponding extension axioms
determine the truth of LFP sentences, even in the presence of an advice
structure, and it follows from Lemma 10 that a random hypergraph satisfies the
extension axioms with high probability: For every $k$ and $t$,

$\Pr_{G\sim
G_{t}(1/2,n)}\bigl{[}G\not\models\textnormal{EA}^{t}_{k}\bigr{]}=\textnormal{negl}(n).$

As the main result of this section, a probabilistic analysis of parities of
certain sets in $G(n,1/2)$ will reveal that the same also holds in the
transduced graph $\theta^{t}(G(n,1/2))$.

######  Lemma 19.

For every $k$ and $t$,

$\Pr_{G\sim
G(n,1/2)}\bigl{[}\theta^{t}(G)\not\models\textnormal{EA}^{t}_{k}\bigr{]}=\textnormal{negl}(n).$

We prove this lemma in the next subsection. Then the following theorem
immediately follows from Lemmas 10, 11, and 19.

######  Theorem 20.

For every $t$, $\theta^{t}$ is an
$(\textnormal{$\textup{FO}[\oplus]$},\textnormal{{LFP}})$-pseudorandom
generator from graphs to $t$-hypergraphs.

It would be interesting to find a logic that admits pseudorandom generators
that are secure against adversaries in the same logic. We believe
$\textup{FO}[\oplus]$ to be a candidate for this. The current proof only shows
security against FO or LFP adversaries, since the extension axioms are not
enough to determine the truth value of $\textup{FO}[\oplus]$ sentences.
However, Kolaitis and Kopparty [22] give a powerful result for
$\textup{FO}[\oplus]$ in a similar spirit: To determine the truth value of any
$\textup{FO}[\oplus]$ sentence, it is sufficient to know certain “subgraph
frequencies”, that is, the parities of the number of occurrences of certain
subgraphs up to some size. If this statement can be lifted to hypergraphs,
then, to fool $\textup{FO}[\oplus]$, it is sufficient to transduce a
$t$-hypergraph that mimics these subgraph frequencies. Thus, [22] can be
understood as evidence for the following conjecture.

######  Conjecture 21.

For every $t$, $\theta^{t}$ is an
$(\textnormal{$\textup{FO}[\oplus]$},\textnormal{$\textup{FO}[\oplus]$})$-pseudorandom
generator from graphs to $t$-hypergraphs.

###  5.1 Parity Probabilities in Random Graphs

It remains to show that $\theta^{t}(G(n,1/2))$ satisfies the extension axioms
with high probability. Roughly speaking, the sets $\\{v\\}\cup C$ in the
following lemma with $|C|=t-1$ will correspond to the input variables of
$\theta^{t}$, that is, the parity of the “number of vertices that are adjacent
to every vertex in $\\{v\\}\cup C$” will determine whether $\\{v\\}\cup C$
forms a hyperedge.

######  Lemma 22.

Let $k\in\mathbb{\mathbb{Z}}_{\geq 1}$. In $G(n,1/2)$, with probability
$1-\textnormal{negl}(n)$, for every vertex set $S\subseteq[n]$ of size $k$ and
every $\mathcal{C}\subseteq\\{C\mid\emptyset\neq C\subseteq S\\}$ there exists
$v\not\in S$ such that for all $\emptyset\neq C\subseteq S$ we have
$C\in\mathcal{C}$ if and only if the number of vertices that are adjacent to
every vertex in $\\{v\\}\cup C$ is odd.

We derive Lemma 22 via a careful basis construction over a suitable vector
space from the following similar statement, which we prove first.

######  Lemma 23.

Let $k\in\mathbb{\mathbb{Z}}_{\geq 1}$. In $G(n,1/2)$, with probability
$1-\textnormal{negl}(n)$, for every vertex set $S\subseteq[n]$ of size $k$ and
every $\mathcal{B}\subseteq\\{B\mid\emptyset\neq B\subseteq S\\}$, there
exists $v\not\in S$ such that for all $\emptyset\neq B\subseteq S$ we have
$B\in\mathcal{B}$ if and only if the number of vertices that are adjacent to
every vertex in $\\{v\\}\cup B$ and non-adjacent to every vertex in
$S\setminus B$ is odd.

###### Proof.

The distribution of $G(n,1/2)$ is identical to a random process where all
adjacencies between tuples $\\{u,v\\}\in{[n]\choose 2}$ are revealed one by
one in an arbitrary order, and each tuple is revealed to be either adjacent or
non-adjacent with probability $1/2$, each.

Let $S$ be a set of $k$ vertices and
$\mathcal{B}\subseteq\\{B\mid\emptyset\neq B\subseteq S\\}$. We start by
revealing all adjacencies incident to $S$. The revealed edges partition the
vertices of the graph into $2^{k}$ sets via their connection to $S$. For
$B\subseteq S$, we denote by $V_{B}\subseteq[n]$ the vertices whose
neighborhood in $S$ is exactly $B$.

Let $B\subseteq S$. Since all edges appear independently with probability
$1/2$, the probability that a vertex outside $S$ is contained in $V_{B}$ is
$2^{-k}$. Since we only need to specify the asymptotic behavior of the error
probability, we can assume at all times $n$ to be sufficiently large in
comparison to $k$. We may assume $k\leq n/2$, which implies $n-k\geq n/2$, and
thus the expected number of vertices in this set is

$E\bigl{[}|V_{B}\setminus S|\bigr{]}=(n-k)\cdot 2^{-k}\geq n/2^{k+1}.$

The events that a vertex outside $S$ is contained in $V_{B}$ are all
independent. The Chernoff bound states that a sum of independent binary random
variables significantly differs from its expected value only with
exponentially small probability. We apply the Chernoff bound and obtain

$\displaystyle\Pr\Bigl{[}|V_{B}\setminus S|\leq n/2^{k+2}\Bigr{]}$
$\displaystyle\leq\Pr\Bigl{[}|V_{B}\setminus S|\leq E[|V_{B}\setminus
S|]/2\Bigr{]}$ $\displaystyle\leq e^{-E[|V_{B}\setminus S|]/12}$
$\displaystyle\leq e^{-n/2^{k+5}}.$

By the union bound, the probability that $E\bigl{[}|V_{B}\setminus
S|\bigr{]}\leq n/2^{k+3}$ for any $B\subseteq A$ is at most

$2^{k}\cdot e^{-n/2^{k+5}}.$ (1)

Thus, let us assume (for now) that we revealed the edges incident to $S$ in
such a way that $|V_{B}\setminus S|\geq n/2^{k+2}$ for all $B\subseteq S$. For
sufficiently large $n$ as a function of $k$, this implies $V_{B}\setminus S$
to be non-empty. This lets us pick for every $\emptyset\neq B\subseteq S$ a
“toggle” vertex $v_{B}\in V_{B}\setminus S$.

Consider a vertex $v\in V_{\emptyset}\setminus S$. We have already revealed
the edges between $v$ and $S$. Let us next reveal the remaining edges between
$v$ and $V\setminus\bigl{(}V_{\emptyset}\cup\\{v_{B}\mid B\subseteq
S\\}\bigr{)}$. We define a “parity pattern”
$\mathcal{B}(v)\subseteq\\{B\mid\emptyset\neq B\subseteq S\\}$, where
$B\in\mathcal{B}(v)$ if and only if $v$ is adjacent to an odd number of
vertices from $V_{B}$. The parity pattern $\mathcal{B}(v)$ will change over
time, as we reveal one by one the edges between $v$ and the vertices $v_{B}$
with $\emptyset\neq B\subseteq S$. When the edge to $v_{B}$ is revealed, the
fact whether $B\in\mathcal{B}(v)$ is inverted with probability $1/2$, while
all other values of the parity pattern stay as they are. Since all edges are
independent, this guarantees that, afterwards, the events whether
$B\in\mathcal{B}(v)$ for $B\neq\emptyset$ are all independent and appear with
probability $1/2$. Since all edges between $v$ and $V\setminus V_{\emptyset}$
were revealed, $\mathcal{B}(v)$ will not change anymore when further edges are
revealed.

The event that $\mathcal{B}(v)=\mathcal{B}$ appears with probability exactly
$2^{-2^{k}-1}$ and is equivalent to our goal that for all $\emptyset\neq
B\subseteq S$ holds $B\in\mathcal{B}$ if and only if the number of vertices
adjacent to every vertex in $\\{v\\}\cup B$ and non-adjacent to every vertex
in $S\setminus B$ is odd. We proceed revealing edges and analyzing the parity
pattern $\mathcal{B}(v)$ in the same way for all other $v\in
V_{\emptyset}\setminus S$. The $|V_{\emptyset}\setminus S|$ many events that
$\mathcal{B}(v)=\mathcal{B}$ are all independent. Thus, the probability that
no vertex $v\in V_{\emptyset}$ realizes the parity pattern
$\mathcal{B}(v)=\mathcal{B}$ equals (using 24 for the first inequality and
$|V_{\emptyset}\setminus S|\geq n/2^{k+2}$ for the second inequality)

$\left(1-2^{-2^{k}+1}\right)^{|V_{\emptyset}\setminus S|}\leq
e^{-|V_{\emptyset}\setminus S|/2^{2^{k}-1}}\leq e^{-n/\bigl{(}2^{k+2}\cdot
2^{2^{k}-1}\bigr{)}}=e^{n/2^{2^{k}+k+1}}.$ (2)

If there exists a vertex realizing the parity pattern for any choice of $S$
and $\mathcal{B}$, the claimed statement is satisfied. There are at most
$n^{k}\cdot 2^{2^{k}}$ choices for $S$ and $\mathcal{B}$, and for each, the
error probability is bounded by the sum of (1) and (2). Thus, by the union
bound, the total error probability is at most

$\left(n^{k}\cdot 2^{2^{k}}\right)\cdot\left(2^{k}\cdot
e^{-n/2^{k+5}}+e^{-n/2^{2^{k}+k+1}}\right).$

As $k$ is fixed, this is a negligible function in $n$. ∎

We now return to proving Lemmas 22 and 19, which concludes the proof of
Theorem 20.

###### Proof of Lemma 22.

Let us fix $S\subseteq[n]$. For every $v\in[n]$, let $\mathcal{B}(v)$ be the
subset of $\\{B\mid\emptyset\neq B\subseteq S\\}$ such that for all
$\emptyset\neq B\subseteq S$ we have $B\in\mathcal{B}(v)$ if and only if the
number of vertices that are adjacent to every vertex in $\\{v\\}\cup B$ and
non-adjacent to every vertex in $S\setminus B$ is odd. Let similarly
$\mathcal{C}(v)$ be the subset of $\\{C\mid\emptyset\neq C\subseteq S\\}$ such
that for all $\emptyset\neq C\subseteq S$ we have $C\in\mathcal{C}(v)$ if and
only if the number of vertices that are adjacent to every vertex in
$\\{v\\}\cup C$ is odd.

For some vertex $v$ and set $C$, let $X$ be the vertices that adjacent to
every vertex in $\\{v\\}\cup C$. We may partition the vertices in $X$ by their
adjacencies to $S\setminus C$. Now $X$ has odd size if and only if we
partitioned $X$ into an odd number of parts of odd size. In other words,

$C\in\mathcal{C}(v)\iff\bigl{\\{}B\mid C\subseteq B\subseteq
S,B\in\mathcal{B}(v)\bigr{\\}}\textnormal{ has odd size}.$ (3)

One can also show for vertices $v$ and sets $B$ that

$\mathcal{B}(v)=\\{B\\}\quad\Longrightarrow\quad\mathcal{C}(v)=\\{C\mid
B\subseteq C\subseteq S\\}.$ (4)

In the following, we consider the vector space $2^{\\{B\mid\emptyset\neq
B\subseteq S\\}}$ with the symmetric difference operator $\oplus$. For
example, for vectors $\\{B_{1},B_{2}\\}$ and $\\{B_{2},B_{3}\\}$ of this
vector space (with $\emptyset\neq B_{1},B_{2},B_{3}\subseteq S$), we have
$\\{B_{1},B_{2}\\}\oplus\\{B_{2},B_{3}\\}=\\{B_{1},B_{3}\\}$. We claim that
the sets

$\bigl{\\{}\\{B\mid C\subseteq B\subseteq S\\}\mid\emptyset\neq C\subseteq
S\bigr{\\}}$

form a basis of this vector space. To prove this, we iteratively construct for
decreasing $i$ all unit vectors $\\{I\\}$ with $\emptyset\subseteq I\subseteq
S,|I|=i$ as linear combinations of our proclaimed basis. For $i>|S|$ there is
nothing to show. To generate a unit vector $\\{I\\}$ with $|I|=i-1$, we start
with the vector $\\{B\mid I\subseteq B\subseteq S\\}$ and eliminate all
excessive entries $I\subsetneq B\subseteq S$ of size at least $i$ using the
$\oplus$ operator and the already constructed vectors $\\{B\\}$.

Next, we will argue that for all $v,v_{1},v_{2}\in[n]$,

$\mathcal{B}(v)=\mathcal{B}(v_{1})\oplus\mathcal{B}(v_{2})\quad\Longrightarrow\quad\mathcal{C}(v)=\mathcal{C}(v_{1})\oplus\mathcal{C}(v_{2}).$
(5)

Assume $\mathcal{B}(v)=\mathcal{B}(v_{1})\oplus\mathcal{B}(v_{2})$. For a set
$C$, we observe

$\displaystyle C\in C(v)$ $\displaystyle\iff\\{B\mid C\subseteq B\subseteq
A,B\in(\mathcal{B}(v_{1})\oplus\mathcal{B}(v_{2}))\\}\text{ has odd size}\ \ \
\ \ \text{(from (\ref{eq:oddSize}))}$ $\displaystyle\iff\\{B\mid C\subseteq
B\subseteq A,B\in\mathcal{B}(v_{1})\\}\text{ and }\\{B\mid C\subseteq
B\subseteq A,B\in\mathcal{B}(v_{2})\\}$ have sizes of different parity
$\displaystyle\iff(C\in C(v_{1})\text{ and }C\not\in C(v_{2}))\text{ or
}(C\not\in C(v_{1})\text{ and }C\in C(v_{2})).$

This proves (5).

By Lemma 23, we can assume with negligible error probability that, for every

$\mathcal{B}\subseteq\\{B\mid\emptyset\neq B\subseteq S\\},$

there exists $v\in[n]$ with $\mathcal{B}(v)=\mathcal{B}$. In particular, for
every $\emptyset\neq B\subseteq S$ there exists $v\in[n]$ with
$\mathcal{B}(v)=\\{B\\}$, which, by (4), implies $\mathcal{C}(v)=\\{C\mid
B\subseteq C\subseteq S\\}$. Hence, by the claim above, $\\{\mathcal{C}(v)\mid
v\in[n]\\}$ is a basis of our vector space. To finally prove the claim of this
lemma, pick an arbitrary $\mathcal{C}\subseteq\\{C\mid\emptyset\neq C\subseteq
S\\}$. Since $\\{\mathcal{C}(v)\mid v\in[n]\\}$ is a basis of our vector
space, we can express $\mathcal{C}$ as
$\mathcal{C}=\mathcal{C}(v_{1})\oplus{}\dots\oplus\mathcal{C}(v_{t})$ for some
vertices $v_{1},\dots,v_{t}\in[n]$. The invocation of Lemma 23 at the
beginning of the paragraph implies the existence of a vertex $v$ with
$\mathcal{B}(v)=\mathcal{B}(v_{1})\oplus{}\dots\oplus X(v_{t})$. Repeated
application of (5) then implies
$\mathcal{C}(v)=\mathcal{C}(v_{1})\oplus{}\dots\oplus C(v_{t})$. Thus,
$\mathcal{C}(v)=\mathcal{C}$. ∎

###### Proof of Lemma 19.

By Lemma 22, with negligible error probability in $n$, for every vertex set
$S\subseteq[n]$ of size $k$ and every
$\mathcal{C}\subseteq\\{C\mid\emptyset\neq C\subseteq S\\}$ there exists
$v\not\in S$ such that for all $\emptyset\neq C\subseteq S$ we have
$C\in\mathcal{C}$ if and only if the number of vertices that are adjacent to
every vertex in $\\{v\\}\cup C$ is odd. Thus, in particular, for every
$T\subseteq{S\choose t-1}$ there exists $v\not\in S$ such that for every
$\\{s_{1},\dots,s_{t-1}\\}\in{S\choose t-1}$, $\\{s_{1},\dots,s_{t-1}\\}\in T$
if and only if the number of vertices that are adjacent to every vertex in
$\\{s_{1},\dots,s_{t-1},v\\}$ is odd. The latter is equivalent to
$\\{s_{1},\dots,s_{t-1},v\\}$ being an edge in $\theta^{t}(G)$. Hence, with
negligible error probability, $G\models\textnormal{EA}^{t}_{k}$. ∎

##  6 Conclusion

In this paper, we define model-theoretic analogues of pseudorandom generators.
We give an exhaustive classification between which generator and adversary
logics from FO, LFP, $\textup{LFP}[\oplus]$ pseudorandom generators exist, and
we deterministically construct structures that fool FO and LFP adversaries,
even in the realm of arbitrary relational signatures. Finally, we give a
potential candidate for an $\textup{FO}[\oplus]$-transduction that acts as a
pseudorandom generator that is secure against $\textup{FO}[\oplus]$ itself. On
a conceptual level, this work contributes a novel perspective on
pseudorandomness and opens up new avenues for descriptive complexity in the
realm of cryptography, where average-case analysis is paramount.

## Acknowledgments

We are very grateful to Boaz Barak for helpful pointers and feedback on an
earlier draft.

This material is based upon work supported in part by the National Science
Foundation Graduate Research Fellowship Program under Grant No. DGE1745303.
Any opinions, findings, and conclusions or recommendations expressed in this
material are those of the authors and do not necessarily reflect the views of
the National Science Foundation.

## References

  * [1] Wilhelm Ackermann.  Die widerspruchsfreiheit der allgemeinen mengenlehre.  Mathematische Annalen, 114(1):305–315, 1937.
  * [2] Sanjeev Arora and Boaz Barak.  Computational Complexity - A Modern Approach.  Cambridge University Press, 2009.
  * [3] Albert Atserias and Anuj Dawar.  Definable inapproximability: new challenges for duplicator.  J. Log. Comput., 29(8):1185–1210, 2019.
  * [4] Andreas Blass, Geoffrey Exoo, and Frank Harary.  Paley graphs satisfy all first-order adjacency axioms.  Journal of Graph Theory, 5(4):435–439, 1981.
  * [5] Andreas Blass, Yuri Gurevich, and Dexter Kozen.  A zero-one law for logic with a fixed-point operator.  Inf. Control., 67(1-3):70–90, 1985.
  * [6] Andreas Blass and Benjamin Rossman.  Explicit graphs with extension properties.  Bull. EATCS, 86:166–175, 2005.
  * [7] Anthony Bonato.  The search for n-e.c. graphs.  Contributions to Discrete Mathematics, 4(1), 2009.
  * [8] Dan Boneh and Victor Shoup.  A Graduate Course in Applied Cryptography.  2015\.
  * [9] Peter J. Cameron and Dudley Stark.  A prolific construction of strongly regular graphs with the n-e.c. property.  Electron. J. Comb., 9(1), 2002.
  * [10] Bruno Courcelle and Joost Engelfriet.  Graph structure and monadic second-order logic: a language-theoretic approach, volume 138.  Cambridge University Press, 2012.
  * [11] Heinz-Dieter Ebbinghaus and Jörg Flum.  Finite Model Theory.  Springer Berlin, Heidelberg, 1995.
  * [12] Chaim Even-Zohar, Michael Farber, and Lewis Mead.  Ample simplicial complexes.  European Journal of Mathematics, 8(1):1–32, 2022.
  * [13] Ronald Fagin.  Generalized first-order spectra and polynomial-time recognizable sets.  Complexity of computation, 7:43–73, 1974.
  * [14] Ronald Fagin.  Probabilities on finite models.  J. Symb. Log., 41(1):50–58, 1976.
  * [15] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik.  Concrete mathematics - a foundation for computer science.  Addison-Wesley, 1989.
  * [16] Martin Grohe.  The quest for a logic capturing PTIME.  In Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008, 24-27 June 2008, Pittsburgh, PA, USA, pages 267–271. IEEE Computer Society, 2008.
  * [17] Lauri Hella, Phokion G. Kolaitis, and Kerkko Luosto.  Almost everywhere equivalence of logics in finite model theory.  Bull. Symb. Log., 2(4):422–443, 1996.
  * [18] Johan HÅstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby.  A pseudorandom generator from any one-way function.  SIAM Journal on Computing, 28(4):1364–1396, 1999.
  * [19] Neil Immerman.  Relational queries computable in polynomial time.  Inf. Control., 68(1-3):86–104, 1986.
  * [20] Neil Immerman.  Descriptive complexity.  Graduate texts in computer science. Springer, 1999.
  * [21] Richard M. Karp.  Probabilistic analysis of a canonical numbering algorithm for graphs.  In Relations between combinatorics and other parts of mathematics (Proc. Sympos. Pure Math., Ohio State Univ., Columbus, Ohio, 1978), Proc. Sympos. Pure Math., XXXIV, pages 365–378. Amer. Math. Soc., Providence, R.I., 1979.
  * [22] Phokion G. Kolaitis and Swastik Kopparty.  Random graphs and the parity quantifier.  J. ACM, 60(5), oct 2013.
  * [23] Michael Krivelevich and Benny Sudakov.  Pseudo-random graphs.  In More sets, graphs and numbers, pages 199–262. Springer, 2006\.
  * [24] Leonid Libkin.  Elements of Finite Model Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004\.
  * [25] Leonid Libkin.  Elements of Finite Model Theory.  Springer, 2004.
  * [26] Moni Naor, Leonard J Schulman, and Aravind Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191. IEEE, 1995.
  * [27] R. Rado.  Universal graphs and universal functions.  Acta Arithmetica, 9(4):331–340, 1964.
  * [28] Jamie Tucker-Foltz.  Inapproximability of unique games in fixed-point logic with counting.  In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1–13. IEEE, 2021.
  * [29] Moshe Y. Vardi.  The complexity of relational query languages (extended abstract).  In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 137–146, 1982\.

##  Appendix A Error Probabilities

For completeness, we review a simple fact that is useful for bounding error
probabilities.

######  Observation 24.

Since $1-x\leq e^{x}$ for all $x$, we can conclude for all $a,b$ that

$\Bigl{(}1-\frac{1}{a}\Bigr{)}^{b}\leq e^{-b/a}.$

For $a=2^{k}$ and $b=n$, we may bound, for example, the probability of failing
to obtain $k$ times heads in $k$ coin flips, when being allowed to repeat the
experiment $n$ times, by

$(1-2^{-k})^{n}\leq e^{-n/2^{k}},$

which becomes increasingly small if $n$ is sufficiently large compared to $k$.

##  Appendix B Proof of Lemma 2

See 2

###### Proof.

Consider the following algorithm. Let $S$ be the set of elements $x$ of the
universe over which $R(x,x,\dots,x)$ holds, and let $\overline{S}$ be its
complement. By the Chernoff bound, with probability $1-\textnormal{negl}(n)$,
$S$ and $\overline{S}$ will each contain at least $\frac{n}{3}$ elements
total. We define graphs $G$ on $S$ and $\overline{G}$ on $\overline{S}$ where
there is an edge between two distinct vertices $x$ and $y$ in the respective
vertex sets if and only if exactly one of $R(x,y,y,\dots,y)$ and
$R(y,x,x,\dots,x)$ holds. Note that these will both always be uniformly random
graphs. We then apply an algorithm of Karp [21] to both $G$ and $\overline{G}$
to compute canonical total orders on the vertex sets $S$ and $\overline{S}$.
Since $S$ is definable, we can string the orders together with all elements in
$S$ occurring before all elements in $\overline{S}$. Hella, Kolaitis, and
Luosto [17] showed that Karp’s algorithm can be implemented as an
$\textup{LFP}[\oplus]$ formula, and all the other steps are clearly doable in
FO. This gives as an $\textup{LFP}[\oplus]$ definition of $\leq$. We then
define the relation $Q$ to hold on all tuples
$(x,{y}_{1},{y}_{2},\dots,{y}_{k-1})$ where $x\in S$ and each
$y_{i}\in\overline{S}$.

When run on a random graph, the probability that Karp’s algorithm fails to
find a canonical order is a negligible function of the number of vertices.
Thus, assuming each vertex set is of size at least $\frac{n}{3}$, the
probability that at least one of the two graphs is not successfully ordered is
at most
$\textnormal{negl}(\frac{n}{3})+\textnormal{negl}(\frac{n}{3})=\textnormal{negl}(n)$.
Also, again assuming each vertex set is of size at least $\frac{n}{3}$, $Q$
will contain at least

$\left(\frac{n}{3}\right)\cdot\left(\frac{n}{3}\right)^{k-1}=\frac{1}{3^{k}}\cdot
n^{k}=\Omega(n^{k})$

$k$-tuples. Finally, the independence condition follows from the fact that the
canonization algorithm only considers the graphs $G$ and $\overline{G}$ and
thus does not ever check whether any of the tuples in $Q$ are in $R$. ∎

##  Appendix C Relational Rado Structures

We extend the definition of extension axioms and our deterministic
construction of finite Rado graphs to relational structures.

######  Definition 25.

Fix a signature $\sigma$. We say a _$k$ -atomic type_ is a set of tuples
$(R,(i_{1},\dots,i_{a}))$, where $R\in\sigma$ is a relation symbol of arity
$a$ and $i_{1},\dots,i_{a}\in\\{0,\dots,k\\}$ are indices with
$0\in\\{i_{1},\dots,i_{a}\\}$. We denote by $\textnormal{types}(\sigma,k)$ the
set of all possible $k$-atomic types. If the relations in $\sigma$ have
arities $a_{1},\dots,a_{t}$, then $|\textnormal{types}(\sigma,k)|\leq
2^{\sum_{i=1}^{t}(k+1)^{a_{i}}}$.

In a $\sigma$-structure $\mathbb{A}$, we say a vertex $v\in\mathbb{A}$
_satisfies_ a given $k$-atomic type on a tuple
$(v_{1},\dots,v_{k})\in\mathbb{A}^{k}$ if for all tuples
$(R,(i_{1},\dots,i_{a}))$ as above, we have $(v_{i_{1}},\dots,v_{i_{a}})\in
R^{\mathbb{A}}$ if and only if $R(i_{1},\dots,i_{a})$ is contained in the
atomic type.

We say $\mathbb{A}$ satisfies the extension axioms
$\textnormal{EA}^{\sigma}_{s}$ if for all pairwise distinct
$v_{1},\dots,v_{k}\in\mathbb{A}$ and all $k$-atomic types there exists
$v_{0}\neq v_{1},\dots,v_{k}$ satisfying the given type on
$(v_{1},\dots,v_{k})$.

The construction of finite Rado structures follows along the same lines as
Theorem 8, but the additional number of possible atomic types makes the
construction more opaque. Together with Lemma 10 and Lemma 11, the following
theorem implies (see Theorem 12) that LFP cannot distinguish between random
$\sigma$-structures and the output of the following theorem.

See 9

###### Proof.

We instead prove the claim: There exists a constant $c$ such that, for every
$n,k\in\mathbb{\mathbb{Z}}_{\geq 1}$ with $2^{k^{c}}\leq n$, one can construct
in time $O(2^{2^{ck}}n^{c})$ an $n$-element $\sigma$-structure satisfying the
extension axioms $\textnormal{EA}^{\sigma}_{k}$. This claim then implies the
statement of the theorem.

We again use Lemma 7 and brute-force enumeration to find a tournament $F$ with
vertex set $[2^{3k}]$ such that, for every $S\subseteq[2^{3k}]$ of size $k$,
there is a vertex $j\in[2^{3k}]$ that has a directed edge towards every vertex
in $S$.

We will construct a structure $\mathbb{A}$ with universe $[n]$ satisfying the
extension axioms $\textnormal{EA}^{\sigma}_{k}$. Let us start by using Theorem
6 to construct an $(n,k)$-family of perfect hash functions $\mathcal{F}$.
Next, we need to partition the universe $[n]$ into $2^{3k}$ many parts
$P_{1},\dots,P_{2^{3k}}$ of size at least $|\mathcal{F}|\cdot
k!\cdot|\textnormal{types}(\sigma,k)|$. Let us argue that one can choose the
parameter $c$ such that this is possible for all $n\geq 2^{k^{c}}$. Let
$c^{\prime}$ be the constant from Theorem 6, such that we can bound the size
of our $(n,k)$-family of perfect hash functions by $2^{c^{\prime}k}\log(n)$.
Let the relations of the arities in $\sigma$ be $a_{1},\dots,a_{t}$. Then the
number of $k$-atomic types is at most $|\textnormal{types}(\sigma,k)|\leq
2^{\sum_{i=1}^{t}(k+1)^{a_{i}}}$. We may choose $c$ such that, for every
$k\in\mathbb{\mathbb{Z}}_{\geq 1}$,

$2^{3k}\cdot k!\cdot 2^{c^{\prime}k}\cdot|\textnormal{types}(\sigma,k)|\cdot
2\leq 2^{k^{c}}/k^{c}.$

Hence, for every $n\in\mathbb{\mathbb{Z}}_{\geq 1}$ with $2^{k^{c}}\leq n$
holds $2^{k^{c}}/k^{c}\leq n/\log(n)$ and thus

$2^{3k}\cdot k!\cdot
2^{c^{\prime}k}\log(n)\cdot|\textnormal{types}(\sigma,k)|\cdot 2\leq n.$

This means, we can partition the universe into parts $P_{1},\dots,P_{2^{3k}}$,
each of size at least

$\lfloor 2^{c^{\prime}k}k!\cdot\log(n)\cdot|\textnormal{types}(\sigma,k)|\cdot
2\rfloor\geq k!\cdot|\mathcal{F}|\cdot|\textnormal{types}(\sigma,k)|.$

For convenience, we define an extended set of functions $\mathcal{F}^{*}$
which contains for every function $f\in\mathcal{F}$ and every permutation
$\pi:[k]\to[k]$ the function $\pi\circ f$. Note that
$|\mathcal{F}^{*}|\leq|\mathcal{F}|\cdot k!$ and additionally, for all
distinct elements $v_{1},\dots,v_{k}$, there exists $f\in\mathcal{F}^{*}$ with
$f(v_{l})=l$ for all $l\in[k]$. We made the parts $P_{1},\dots,P_{2^{3k}}$,
large enough so that we can choose a function
$\textsc{pattern}:[n]\to\mathcal{F}^{*}\times\textnormal{types}(\sigma,k)$
such that, for each $j\in[2^{3k}]$, the function pattern, when restricted to
$P_{j}$, is surjective. We further denote by $\textnormal{index}(v)$ the index
$j$ such that $v\in P_{j}$. To construct our structure $\mathbb{A}$, we now do
the following for every $R\in\sigma$ or arity $a$ and sequence
$u_{1},\dots,u_{a}\in\mathbb{A}$ of (not necessarily distinct) elements:

> Let $v_{0}\in\\{u_{1},\dots,u_{a}\\}$ be the unique element such that in our
> tournament $F$ there are directed edges from $\textnormal{index}(v_{0})$ to
> all vertices in
> $\\{\textnormal{index}(u_{1}),\dots,\textnormal{index}(u_{a})\\}\setminus\\{\textnormal{index}(v_{0})\\}$,
> and let $\textsc{pattern}(v_{0})=(f,\tau)$. Add the tuple
> $(u_{1},\dots,u_{a})$ to $R^{\mathbb{A}}$ if and only if there exists
> $(R,(i_{1},\dots,i_{a}))\in\tau$ with
>
> $\begin{cases}u_{l}=v_{0}&\textnormal{for all $l$ with $i_{l}=0$},\\\
> f(u_{l})=i_{l}&\textnormal{for all $l$ with $i_{l}\neq 0$}.\end{cases}$

#### Correctness

Let $v_{1},\dots,v_{k}\in\mathbb{A}$ be pairwise distinct and let $\tau$ be a
$k$-atomic type. We constructed our tournament $F$ using Lemma 7 such that we
can choose $j\in[2^{3k}]$ with a directed edge to all vertices in
$\textnormal{index}(v_{1}),\dots,\textnormal{index}(v_{k})$. The set
$\mathcal{F}^{*}$ was constructed such that there is $f\in\mathcal{F}^{*}$
with $f(v_{l})=l$ for all $l$. Since pattern, restricted to $P_{j}$, was
chosen to be surjective, we can also pick $v_{0}\in P_{j}$ with
$\textsc{pattern}(v_{0})=(f,\tau)$. Since $F$ has no self-loops, $v_{0}\neq
v_{1},\dots,v_{k}$.

Consider now a tuple $(R,(i_{1},\dots,i_{a}))$, where $R\in\sigma$ is a
relation symbol of arity $a$ and $i_{1},\dots,i_{a}\in\\{0,\dots,k\\}$ are
indices with $0\in\\{i_{1},\dots,i_{a}\\}$. To prove that $\mathbb{A}$
satisfies the extension axioms $\textnormal{EA}^{\sigma}_{k}$, we have to show
that $(v_{i_{1}},\dots,v_{i_{a}})\in R^{\mathbb{A}}$ if and only if
$R(i_{1},\dots,i_{a})\in\tau$. Note that
$v_{0}\in\\{v_{i_{1}},\dots,v_{i_{a}}\\}$ is the unique vertex such that in
$F$ there is a directed edge from $\textnormal{index}(v_{0})$ to all vertices
in
$\\{\textnormal{index}(u_{1}),\dots,\textnormal{index}(u_{a})\\}\setminus\\{\textnormal{index}(v_{0})\\}$.
Also, $\textsc{pattern}(v_{0})=(f,\tau)$. Additionally, note that $f$ was
chosen such that

$\begin{cases}v_{i_{l}}=v_{0}&\textnormal{for all $l$ with $i_{l}=0$},\\\
f(v_{i_{l}})=i_{l}&\textnormal{for all $l$ with $i_{l}\neq 0$}.\end{cases}$

Hence, by our construction, $(v_{i_{1}},\dots,v_{i_{a}})\in R^{\mathbb{A}}$ if
and only if $(R,(i_{1},\dots,i_{a}))\in\tau$, satisfying the extension axiom.

#### Run time

The construction of $F$ takes time at most $2^{2^{3k\cdot 2}}\cdot k^{2}$. By
Theorem 6, we can construct the $(n,k)$-universal family in time
$2^{c^{\prime}k}n\log(n)$. The remaining part of the construction takes time
$O(|\textnormal{types}(\sigma,k)|\cdot n^{a})$, where $a$ is the largest arity
among relations in $\sigma$. By possibly rescaling $c$ such that $c\geq a$, we
get a run time of $O(2^{2^{ck}}n^{c})$. ∎

##  Appendix D Proof of Lemma 10

See 10

###### Proof.

We prove the statement for relational structures only, as the proof for graphs
and hypergraphs is analogous and simpler. Fix a signature $\sigma=\langle
R_{1},\dots,R_{t}\rangle$ with relations of arity $a_{1},\dots,a_{t}$. Then
atomic $k$-types over $\sigma$ specify the presence of at most
$\sum_{i=1}^{t}(k+1)^{a_{i}}$ connections. Fix a tuple
$v_{1},\dots,v_{k}\in\mathbb{A}^{k}$ and an atomic $k$-type. A vertex
$v\not\in S$ satisfies each of the $\sum_{i=1}^{t}(k+1)^{a_{i}}$ connections
specified by the $k$-type with probability $1/2$, each. There are $n-k$
choices for $v$. Using 24, the probability that no vertex satisfies the
requirements is

$\left(1-2^{-{\sum_{i=1}^{t}(k+1)^{a_{i}}}}\right)^{n-k}\leq
e^{(n-k)/{\sum_{i=1}^{t}(k+1)^{a_{i}}}}.$

There are $n^{k}$ choices for $v_{1},\dots,v_{k}$ and at most
$2^{\sum_{i=1}^{t}(k+1)^{a_{i}}}$ atomic $k$-types. The union bound thus
bounds the failure probability over all these options by at most

$n^{k}\cdot 2^{\sum_{i=1}^{t}(k+1)^{a_{i}}}\cdot
e^{(n-k)/{\sum_{i=1}^{t}(k+1)^{a_{i}}}}.$

Since $\sigma$ and $k$ are fixed, this function is negligible in $n$. ∎

##  Appendix E Proof of Lemma 11

See 11

###### Proof.

We show that two structures satisfy the same LFP sentences up to quantifier
rank $k$ by showing that Duplicator wins the infinitary pebble game with $k$
pebbles [25, Definition 11.4] on $(\mathbb{A}_{1},\mathbb{X})$ and
$(\mathbb{A}_{2},\mathbb{X})$. Assuming we have pebbles $p_{1},\dots,p_{k}$ to
be placed on structure $(\mathbb{A}_{1},\mathbb{X})$ and pebbles
$q_{1},\dots,q_{k}$ to be placed on $(\mathbb{A}_{2},\mathbb{X})$, we need to
present a winning strategy for Duplicator that always maintains that the two
(ordered) $k$-tuples of pebbles $p_{1},\dots,p_{k}$ and $q_{1},\dots,q_{k}$
describe a partial isomorphism between $(\mathbb{A}_{1},\mathbb{X})$ and
$(\mathbb{A}_{2},\mathbb{X})$. If, Spoiler places a pebble $p_{i}$ on an
$\mathbb{X}$-element of $(\mathbb{A}_{1},\mathbb{X})$ then Duplicator places
$q_{i}$ on the exact same element of $(\mathbb{A}_{2},\mathbb{X})$. If Spoiler
places $p_{i}$ on an $\mathbb{A}_{1}$-element of
$(\mathbb{A}_{1},\mathbb{X})$, then Duplicator observes (in the case of
relational structures) the $\leq k$-atomic type that $p_{i}$ satisfies in
$\mathbb{A}_{1}$ on the subset of pebbles of $p_{1},\dots,p_{k}$ that lie on
$\mathbb{A}_{1}$, and uses the $k$-extension axioms to place $q_{i}$ onto an
element of $\mathbb{A}_{2}$ satisfying the same $\leq k$-atomic type on the
placed pebbles in $\mathbb{A}_{2}$. The partial isomorphism of the structures
follows from the $k$-atomic types being the same. Thus, Duplicator can follow
this strategy ad infinitum and will not lose. The cases of graphs and
hypergraphs are completely analogous. ∎

##  Appendix F Proof of Theorem 13

We will need the following lemma, which extends the zero-one law for LFP to
formulas with free variables.

######  Lemma 26 (Zero-One Law with free variables).

For every LFP $\sigma$-formula $\varphi(\bar{x})$ there exists a quantifier
free FO $\sigma$-formula $\overline{\varphi}(\bar{x})$ such that, as $n$ tends
to infinity,

$\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}\Bigl{[}\mathbb{A}\models\varphi(\bar{u})\text{
iff }\mathbb{A}\models\overline{\varphi}(\bar{u})\text{ for every
$|\bar{x}|$-tuple $\bar{u}$ over $[n]$}\Bigr{]}\geq 1-\textnormal{negl}(n).$

###### Proof.

Let $\varphi$ be an LFP formula with free variables
${x}_{1},{x}_{2},\dots,{x}_{\ell}$, of the form $\varphi=\exists x_{\ell+1}\
\varphi^{*}$ where $x_{\ell+1}$ is a new variable and $\varphi^{*}$ is the
remainder of the formula. Let $\varphi^{*}[x_{i}/x_{\ell+1}]$ denote the
formula obtained from $\varphi^{*}$ by replacing all occurrences of the
variable $x_{\ell+1}$ with $x_{i}$. Then we may rewrite $\varphi$ equivalently
as

$\varphi=\left(\bigvee_{i\in[\ell]}\varphi^{*}[x_{i}/x_{\ell+1}]\right)\vee\exists
x_{\ell+1}\ \left(\left(\bigwedge_{i\in[\ell]}x_{\ell+1}\neq
x_{i}\right)\wedge\varphi^{*}\right).$ (6)

Atoms of the form $x_{i}=x_{l+1}$ and $x_{i}\neq x_{l+1}$ in $\varphi^{*}$ can
be replaced with FALSE and TRUE, respectively. Repeating this for for every
quantifier, we rewrite $\varphi$ such that every quantifier ranges only over
variables distinct from ${x}_{1},{x}_{2},\dots,{x}_{\ell}$ and there are no
(other) comparisons between free and quantified variables.

Next, we separate free and quantified variables occuring toegether in
relations. Let $\sigma^{\prime}$ be the extended signature, where we add for
every $a$-ary relation $R_{p}$, every $a^{\prime}\leq a$ and every
$a^{\prime}$-tuple $\bar{y}$ over the variables from $\bar{x}$ a new
$(a-a^{\prime})$-ary relation symbol $R^{\bar{y}}_{i}$. We obtain a new
formula $\varphi^{\prime}$ from $\varphi$ by replacing every atom
$R_{i}(\bar{y}\bar{z})$, where the variables of the atom are partitioned such
that $\bar{y}$ and $\bar{z}$ contain free and bound variables of $\varphi$,
respectively, with $R^{\bar{y}}_{i}(\bar{z})$. Since both in
$\textup{Str}[{\sigma,n}]$ and $\textup{Str}[{\sigma^{\prime},n}]$, all
relations are distributed independently with probability one half, for every
tuple $\bar{u}$

$\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}[\mathbb{A}\models\varphi(\bar{u})]~{}~{}=~{}~{}\Pr_{\mathbb{A^{\prime}}\sim\textup{Str}[{\sigma^{\prime},n}]}[\mathbb{A^{\prime}}\models\varphi^{\prime}(\bar{u})].$

Note that in $\varphi^{\prime}$ variables from $\bar{x}$ occur in no
relational atom. We next rewrite and partition $\varphi^{\prime}$ in
disjunctive normal form

$\varphi(\bar{x})=\bigvee_{i=1}^{s}\xi_{i}(\bar{x})\land\psi_{i}(\bar{x}),$

such that each formula $\xi_{i}(\bar{x})$ is quantifier free and each formula
$\psi_{i}(\bar{x})$ quantifies only over variables distinct from $\bar{x}$ and
contains no relations depending on variables from $\bar{x}$. We may therefore
see $\psi_{i}$ as sentences within a $\sigma^{\prime}$ stucture where the
elements $\bar{x}$ have been removed. In other words, for an $|\bar{x}|$-tuple
$\bar{u}$

$\Pr_{\mathbb{A}\sim\textup{Str}[{\sigma,n}]}[\mathbb{A}\models\varphi(\bar{u})]~{}~{}=~{}~{}\Pr_{\mathbb{A^{\prime}}\sim\textup{Str}[{\sigma^{\prime},n}]}~{}\Pr_{\mathbb{A^{\prime\prime}}\sim\textup{Str}[{\sigma^{\prime\prime},n-|\bar{x}|}]}\left[\bigvee_{i=1}^{s}\mathbb{A^{\prime}}\models\xi_{i}(\bar{u})\land\mathbb{A^{\prime\prime}}\models\psi_{i}\right].$

By treating each $\psi_{i}$ as a sentence, the LFP zero-one law of Blass,
Gurevich, and Kozen [5] (or the combination of Lemma 10 and Lemma 11) implies
that $\psi_{i}$ is either satisfied with probability $\textnormal{negl}(n)$ or
$1-\textnormal{negl}(n)$. Let $\overline{\psi}_{i}$ be either TRUE or FALSE,
accordingly. Then for a fixed $\bar{u}$ and $i$, $\overline{\psi}_{i}$ and
$\psi_{i}(\bar{u})$ differ with probability $\textnormal{negl}(n)$. We have to
bound the probability that for _some_ tuple $\bar{u}$ and _some_ $i$,
$\overline{\psi}_{i}$ and $\psi_{i}(\bar{u})$ differ. There are only a
polynomial number of tuples $\bar{u}$ and only a constant number of $i$, and
thus by the union bound and the fact that the sum of a polynomial number of
negligible functions is still negligible, the statement holds. ∎

We are now ready to prove our impossibility result for LFP.

See 13

###### Proof.

(ii)$\implies$(i): Obvious.

(iii)$\implies$(ii): For positive integers $a$ and $k$, let
$\text{eq}\left(a,k\right)$ denote the set of equivalence relations on $[a]$
with exactly $k$ equivalence classes, and let

$\displaystyle\mathcal{S}_{k}:=\\{(i,\text{eq}\left([a_{i}],k\right))\mid
i\in[t]\\},$
$\displaystyle\mathcal{S}^{\prime}_{k}:=\\{(i^{\prime},\text{eq}\left([a^{\prime}_{i^{\prime}}],k\right))\mid
i^{\prime}\in[t^{\prime}]\\}.$

Note that, for any $a$ and $k$,
$T(a,k)=\left|{\text{eq}\left(a,k\right)}\right|\cdot k!$, since choosing a
surjective function from a set $S$ to a set of size $k$ can be thought of as
first choosing an equivalence relation determining which elements of $S$ will
get mapped to the same element, and then choosing a bijection from the
equivalence classes (of which there must be exactly $k$) to the target set of
size $k$. Therefore, assuming $\sigma\succeq_{S}\tau$, we know that, for each
positive integer $k$,

$\left|{\mathcal{S}_{k}}\right|=\sum_{i=1}^{t}\frac{T(a_{i},k)}{k!}\geq\sum_{i=1}^{t^{\prime}}\frac{T(a^{\prime}_{i},k)}{k!}=\left|{\mathcal{S}^{\prime}_{k}}\right|.$

Hence, there exists injections
$f_{k}\colon\mathcal{S}^{\prime}_{k}\to\mathcal{S}_{k}$.

We describe a transduction
$\Theta=({\theta}_{1},{\theta}_{2},\dots,{\theta}_{t^{\prime}}):\textup{Str}[{\sigma}]\to\textup{Str}[{\tau}]$
via the following algorithm. Suppose we wish to determine the truth of
$\theta_{i^{\prime}}({x}_{1},{x}_{2},\dots,{x}_{a^{\prime}_{i^{\prime}}})$ for
some index $1\leq i^{\prime}\leq t^{\prime}$. We first check equality between
the $x$ variables to yield an equivalence relation $\sim^{\prime}$ on the
index set $[a^{\prime}_{i^{\prime}}]$. It will have some number $k$ of
equivalence classes. Then let $(i,\sim):=f_{k}(i^{\prime},\sim^{\prime})$.
Finally, return the truth value of $R_{i}({y}_{1},{y}_{2},\dots,{y}_{a_{i}})$,
where $y_{j}$ refers to the variable $x_{j^{\prime}}$ such that the
equivalence relation determined by testing equality among
$({y}_{1},{y}_{2},\dots,{y}_{j})$ is $\sim$ and $y_{j}$ belongs to the
$\ell^{\text{th}}$ equivalence class of $\sim$ where $\ell$ is such that
$x_{j^{\prime}}$ belongs to the $\ell^{\text{th}}$ equivalence class of
$\sim^{\prime}$. Note that all the “computation” here is determining how to
route variables to a relation in $\sigma$ solely based on equality
comparisons, and can be accomplished purely syntactically by a large (but
finite) quantifier-free FO sentence.

The point of this construction is that, for every $i$ and every
${x}_{1},{x}_{2},\dots,{x}_{a_{i^{\prime}}}$, the truth of
$\theta_{i}({x}_{1},{x}_{2},\dots,{x}_{a_{i}})$ depends on an independent
evaluation of a relation from the input $\sigma$-structure $\mathbb{A}$. This
can be verified by checking that no two tuples
$({x}_{1},{x}_{2},\dots,{x}_{a_{i^{\prime}}})$ and
$({x}_{1},{x}_{2},\dots,{x}_{a_{j^{\prime}}})$ are mapped to the same
evaluation of relations in $\mathbb{A}$. To see this, observe that, since all
variables are used, if
$\\{{x}_{1},{x}_{2},\dots,{x}_{a_{i^{\prime}}}\\}\neq\\{{x}_{1},{x}_{2},\dots,{x}_{a_{j^{\prime}}}\\}$
then the tuples are mapped to different evaluations in $\mathbb{A}$.
Otherwise, if they both contain the same set of $k$ distinct elements but have
different equivalence relation types, they are mapped to evaluations of either
different relations in $\sigma$ or different equivalence relation types, as
$f_{k}$ is an injection. And if they have the same equivalence relation types,
then they are mapped to the same evaluation if and only if the first
occurrences are in the same order, i.e., the tuples are literally identical.
Thus, by independence $\Theta$ produces uniformly random $\tau$ structures
from uniformly random $\sigma$-structures.

$\neg$(iii)$\implies$$\neg$(i): Let
$\Theta=({\theta}_{1},{\theta}_{2},\dots,{\theta}_{t^{\prime}})$ be given,
where each $\theta_{i}$ is a $\sigma$-formula with $a^{\prime}_{i}$ free
variables. By applying Lemma 26 to each formula of $\Theta$, we obtain a
quantifier free first order transduction
$\overline{\Theta}:=({\overline{\theta}}_{1},{\overline{\theta}}_{2},\dots,{\overline{\theta}}_{t^{\prime}})$
such that, for $\mathbb{A}\sim\textup{Str}[{\sigma,n}]$, the structure
$\Theta(\mathbb{A})$ is equivalent to $\overline{\Theta}(\mathbb{A})$ with
probability $1-\textnormal{negl}(n)$.

Since $\overline{\Theta}$ is quantifier-free, it satisfies the hypothesis of
Lemma 15 for any $k$. Hence, as we are assuming $\sigma\not\succeq_{S}\tau$,
Lemma 15 tells us that$\overline{\Theta}$ is not a pseudorandom generator,
meaning that there is some sentence $\varphi$ that can distinguish its outputs
from uniformly random $\tau$ structures with non-negligible advantage. It
follows that $\Theta$ cannot be a pseudorandom generator either, as the
triangle inequality and the fact that a non-negligible function plus a
negligible function is a non-negligible function imply $\varphi$ breaks the
security of $\Theta$ as well. ∎

##  Appendix G Proof of Lemma 15

See 15

###### Proof.

Let $k$ be a positive integer such that

$\sum_{i=1}^{t}T(a_{i},k)<\sum_{i=1}^{t^{\prime}}T(a^{\prime}_{i},k).$ (7)

Let $\mathcal{T}_{c}$ be the set of $(c,k)$-types. For any $c$ and any
$T\in\mathcal{T}_{c}$, let $\varphi_{T}({y}_{1},{y}_{2},\dots,{y}_{c})$ be the
FO formula checking that $({y}_{1},{y}_{2},\dots,{y}_{c})$ are all distinct
and have $(c,k)$-type $T$. We claim that there exists a $c$ such that, for all
sufficiently large $n$, the sentence FO sentence

$\varphi_{c}:=\bigwedge_{T\in\mathcal{T}_{c}}\exists{y}_{1},{y}_{2},\dots,{y}_{c}\varphi_{T}({y}_{1},{y}_{2},\dots,{y}_{c})$

discriminates between $\mathbb{B}\sim\textup{Str}[{\tau}]$ and $f(\mathbb{A})$
for $\mathbb{A}\sim\textup{Str}[{\sigma,n}]$.

Clearly, when $\mathbb{B}\sim\textup{Str}[{\tau}]$, the probability that
$\mathbb{B}\models\varphi_{c}$ is $1-\textnormal{negl}(n)$; this is a basic
consequence of 24. On the other hand, we will show that, for large enough $c$,
there is no $\mathbb{A}\in\textup{Str}[{\sigma,n}]$ such that
$f(\mathbb{A})\models\varphi_{c}$.

We proceed by counting the numbers $N_{\sigma}$ and $N_{\tau}$ of possible
$(c,k)$-types that a given $c$-tuple could have in any $\sigma$-structure or
$\tau$-structure, respectively. Letting $\mathcal{P}(R)$ denote the power set
of $R$, starting from the expression in Definition 14, we have

$\displaystyle N_{\sigma}$
$\displaystyle=\left|{\mathcal{P}\left(\bigcup_{i=1}^{t}\bigcup_{\begin{subarray}{c}S\subseteq[c]\\\
\left|{S}\right|\leq k\end{subarray}}\\{(i,S,g):\ |\ g:[a_{i}]\to S\text{ is
surjective}\\}\right)}\right|$
$\displaystyle=\left|{\mathcal{P}\left(\bigcup_{k^{\prime}=1}^{k}\bigcup_{i=1}^{t}\bigcup_{\begin{subarray}{c}S\subseteq[c]\\\
\left|{S}\right|=k^{\prime}\end{subarray}}\\{(i,S,g):\ |\ g:[a_{i}]\to S\text{
is surjective}\\}\right)}\right|$
$\displaystyle=2^{\sum_{k^{\prime}=1}^{k}\sum_{i=1}^{t}T(a_{i},k^{\prime}){c\choose
k^{\prime}}}.$

By the assumption on $f$, for any fixed structure $\mathbb{A}$, any given
$c$-tuple can only have one of $N_{\sigma}$ possible $(c,k)$-types in
$f(\mathbb{A})$. However, there are

$N_{\tau}=2^{\sum_{k^{\prime}=1}^{k}\sum_{i=1}^{t}T(a^{\prime}_{i},k^{\prime}){c\choose
k^{\prime}}}$

$(c,k)$-types total. For large enough $c$, the ${c\choose k^{\prime}}$-terms
dominate in the sums over $k^{\prime}$; for $N_{\sigma}$ the coefficient of
this term is

$\sum_{i=1}^{t}T(a_{i},k),$

and for $N_{\tau}$ the coefficient is

$\sum_{i=1}^{t}T(a^{\prime}_{i},k).$

It thus follows from Equation (7) that $N_{\sigma}<N_{\tau}$. Hence, no matter
what $\mathbb{A}$ is, there must be some $k$-type that isn’t held by any
$c$-tuple in $f(\mathbb{A})$, so $f(\mathbb{A})\not\models\varphi_{c}$. ∎