text:
\section{Introduction}
\label{sec:intro}
\input{intro}

\section{Preliminaries}
\label{sec:prelim}
\input{prelim}

\section{Symmetry and Support}
\label{sec:support}
\input{support}

\section{Translating Symmetric Circuits to Formulas}
\label{sec:sym-def}
\input{sym-def}

\section{Consequences}
\label{sec:conseq}
\input{conseq}

\section{Coherent and Locally Polynomial Circuits}
\label{sec:coherence}
\input{coherence}

\section{Future Directions}
\label{sec:conc}
\input{conc}

\paragraph{Acknowledgments.} The authors thank Dieter van Melkebeek for looking at an early draft of this paper.  This research was supported by EPSRC grant EP/H026835.

\bibliographystyle{plain}

\subsection{Vocabularies, Structures, and Logics}

A \emph{relational vocabulary} (always denoted by $\tau$) is a finite
sequence of relation symbols $(R_1^{r_1},\ldots,R_k^{r_k})$ where for
each $i \in [k]$ the relation symbol $R_i$ has an associated arity
$r_i \in \ensuremath{\mathbb{N}}\xspace$.  A \emph{$\tau$-structure} $\str{A}$ is a tuple
$\tup{A,R_1^{\str{A}},\ldots,R_k^{\str{A}}}$ consisting of (i) a
non-empty set $A$ called the \emph{universe} of $\str{A}$, and (ii)
relations $R_i^{\str{A}} \subseteq A^{r_i}$ for $i \in [k]$.  Members of
the universe $A$ are called \emph{elements} of $\str{A}$.  A
\emph{multi-sorted} structure is one whose universe is given as a
disjoint union of several distinct \emph{sorts}.  Define the
\emph{size} of a structure $|\str{A}|$ to be the cardinality of its
universe.  All structures considered in this paper are \emph{finite},
i.e., their universes have finite cardinality.  Let $\ensuremath{\mathrm{fin}}[\tau]$
denote the set of all finite $\tau$-structures.

\paragraph{First-Order and Fixed-Point Logics.}
Let $\ensuremath{\mathrm{FO}}\xspace(\tau)$ denote \emph{first-order logic} with respect to the
vocabulary $\tau$.  The logic $\ensuremath{\mathrm{FO}}\xspace(\tau)$ is the set of formulas whose
atoms are formed using the relation symbols in $\tau$, an equality
symbol $=$, an infinite sequence of variables $(x,y,z\ldots)$, and
that are closed under the Boolean connectives ($\wedge$ and $\vee$),
negation ($\neg$), and universal and existential quantification
($\forall$ and $\exists$).  Let \emph{fixed-point logic} $\ensuremath{\mathrm{FP}}\xspace(\tau)$
denote the extension of $\ensuremath{\mathrm{FO}}\xspace(\tau)$ to include an inflationary fixed-point
operator $\ensuremath{\mathrm{ifp}}$.  Assume standard syntax and semantics for \ensuremath{\mathrm{FO}}\xspace and \ensuremath{\mathrm{FP}}\xspace
(see the textbook \cite{EF06} for more background).  For a formula
$\phi$ write $\phi(x)$ to indicate that $x$ is the tuple of the free
variables of $\phi$.  For a logic $\mathcal{L}$, a formula $\phi(x) \in
\mathcal{L}(\tau)$ with $k$ free variables, $\str{A} \in \ensuremath{\mathrm{fin}}[\tau]$, and tuple
$a \in A^k$ write $\str{A} \models_{\mathcal{L}} \phi[a]$ to express that the
tuple $a$ makes the formula $\phi$ true in the structure $\str{A}$
with respect to the logic $\mathcal{L}$.  We usually drop the subscript $\mathcal{L}$
and write  $\str{A} \models \phi[a]$ when no confusion would arise.

\paragraph{Logics with Disjoint Advice.}
Let $\ensuremath{\tau_{\mathrm{arb}}}\xspace$ be a relational vocabulary without a binary relation
symbol $\le$.  Let $\Upsilon : \ensuremath{\mathbb{N}}\xspace \rightarrow \ensuremath{\mathrm{fin}}[\ensuremath{\tau_{\mathrm{arb}}}\xspace \uplus
  \set{\le^2}]$ be an \emph{advice function}, where for $n \in \ensuremath{\mathbb{N}}\xspace$,
$\Upsilon(n)$ has universe $\set{0,1,\ldots,n}$ naturally ordered by
$\le$.  For a logic $\mathcal{L}$, typically $\ensuremath{\mathrm{FO}}\xspace$ or $\ensuremath{\mathrm{FP}}\xspace$, let $(\ensuremath{\Lo+\mathrm{\Upsilon}}\xspace)(\tau)$
denote the set of formulas of $\mathcal{L}(\tau')$ where $\tau' := \tau \uplus
\ensuremath{\tau_{\mathrm{arb}}}\xspace \uplus \set{\le^2}$ and $\tau$ is a vocabulary disjoint from
$\ensuremath{\tau_{\mathrm{arb}}}\xspace \uplus \set{\le^2}$.  For a structure $\str{A} \in \ensuremath{\mathrm{fin}}[\tau]$
define the semantics of $\phi \in (\ensuremath{\Lo+\mathrm{\Upsilon}}\xspace)(\tau)$ to be $\str{A}
\models_{(\ensuremath{\Lo+\mathrm{\Upsilon}}\xspace)} \phi \text{ iff } \str{A}^\Upsilon \models_{\mathcal{L}} \phi,$
where $\str{A}^\Upsilon := \str{A} \oplus \Upsilon(|\str{A}|)$ is the
multi-sorted $\tau'$-structure formed by taking the disjoint union of
$\str{A}$ with a structure coding a linear order of corresponding
cardinality endowed with interpretations of the relations in $\ensuremath{\tau_{\mathrm{arb}}}\xspace$.
The universe of the multi-sorted structure $\str{A}^\Upsilon$ is written
as $A \uplus \set{0,1,\ldots,|A|}$; refer to $A$ as the \emph{point
  sort} of $\str{A}^\Upsilon$

  and to
$\set{0,1,\ldots,|A|}$ as the \emph{number sort} of $\str{A}^\Upsilon$.
We are primarily interested in the
special case when $\ensuremath{\tau_{\mathrm{arb}}}\xspace$ is empty and hence $\Upsilon(|\str{A}|) =
\tup{\set{0,1,\ldots,|A|},\le}$ is simply a linear order.  Denote
formulas of this logic by $(\ensuremath{\Lo+\mathrm{\le}}\xspace)(\tau)$ and extended structures by
$\str{A}^{\le}$ to emphasise the disjoint linear order.

Let $\ensuremath{\mathrm{FPC}}\xspace(\tau)$ denote the extension of $(\ensuremath{\mathrm{FP}+\mathrm{\le}}\xspace)(\tau)$ with a
counting operator $\#_x$ where $x$ is a point or number variable.  For a
structure $\str{A} \in \ensuremath{\mathrm{fin}}[\tau]$ and a formula $\phi(x) \in
\ensuremath{\mathrm{FPC}}\xspace(\tau)$, $\#_x \phi(x)$ is a term denoting the element in the number
sort corresponding to $|\condset{a \in \str{A}}{\str{A} \models
  \phi[a]}|$.  See \cite[Section 8.4.2]{EF06} for more details.
Finally, we consider the extension of fixed-point logic with both
advice functions and counting quantifiers $(\ensuremath{\mathrm{FPC}+\Upsilon}\xspace)(\tau)$.

Using $k$-tuples of number variables, it is possible in $\ensuremath{\mathrm{FP}+\mathrm{\le}}\xspace$ and
$\ensuremath{\mathrm{FPC}}\xspace$ to represent numbers up to $n^k$ and perform arithmetic
operations on them.  We omit details but use such constructions
freely.

\subsection{Symmetric and Uniform Circuits}
\label{sec:boolean}

A \emph{Boolean basis} (always denoted by $\mathbb{B}$) is a finite set of
Boolean functions from $\set{0,1}^*$ to $\set{0,1}$.  We consider only
bases containing symmetric functions, i.e., for all $f \in \mathbb{B}$, $f(x)
= f(y)$ for all $n \in \ensuremath{\mathbb{N}}\xspace$ and $x,y \in \set{0,1}^n$ with the same
number of ones.  The \emph{standard Boolean basis} $\B_{\mathrm{std}}$ consists of
unbounded fan-in AND, OR, and unary NOT operators.  The \emph{majority
  basis} $\B_{\mathrm{maj}}$ extends the standard basis with an operator MAJ which
is one iff the number of ones in the input is at least the number of
zeroes.

\begin{definition}[Circuits on Structures]
A \emph{Boolean $(\mathbb{B},\tau)$-circuit $C$ with universe $U$ computing a
  $q$-ary query $Q$} is a structure
$\tup{G,W,\Omega,\Sigma,\Lambda}$.
\begin{itemize}
\item $G$ is a set called the \emph{gates} of $C$.  The \emph{size} of $C$ is $|C| := |G|$.
\item $W \subseteq G \times G$ is a binary relation called the
  \emph{wires} of the circuit.  We require that $(G,W)$ forms a \emph{directed
    acyclic graph}.  Call the gates with no incoming wires
  \emph{input gates}, and all other gates \emph{internal gates}.
  Gates $h$ with $(h,g) \in W$ are called the \emph{children} of
  $g$.
\item $\Omega$ is an injective function from $U^q$ to $G$.  The gates
  in the image of $\Omega$ are called the \emph{output gates}.  When $q
  = 0$, $\Omega$ is a constant function mapping to a single output
  gate.
\item $\Sigma$ is a function from $G$ to $\mathbb{B} \uplus \tau \uplus
  \set{0,1}$ which maps input gates into $\tau \uplus \set{0,1}$ with
  $|\Sigma^{-1}(0)|,|\Sigma^{-1}(1)| \le 1$ and internal gates into
  $\mathbb{B}$.  Call the input gates marked with a relation from $\tau$
  \emph{relational gates} and the input gates marked with 0 or 1
  \emph{constant gates}.
\item $\Lambda$ is a sequence of injective functions $(\Lambda_R)_{R \in
    \tau}$ where for each $R \in \tau$, $\Lambda_R$ maps each relational
  gate $g$ with $R = \Sigma(g)$ to $\Lambda_R(g) \in U^r$
  where $r$ is the arity of $R$.  Where no ambiguity arises, we write
  $\Lambda(g)$ for $\Lambda_R(g)$.
\end{itemize}
\end{definition}

Let $C$ be a Boolean $(\mathbb{B},\tau)$-circuit with universe $U$, $\str{A}
\in \ensuremath{\mathrm{fin}}[\tau]$ with $|\str{A}| = |U|$, and $\gamma : A \rightarrow U$
be a bijection.  Let $\gamma \str{A}$ denote the $\tau$-structure over
the universe $U$ obtained by relabelling the universe of $\str{A}$
according to $\gamma$.  Recursively evaluate $C$ on $\gamma\str{A}$ by
determining a value $C[\gamma\str{A}](g)$ for each gate $g$: (i) a
constant gate evaluates to the bit given by $\Sigma(g)$, (ii) a
relational gate evaluates to 1 iff $\gamma\str{A} \models
\Sigma(g)(\Lambda(g))$, and (iii) an internal gate evaluates to the
result of applying the Boolean operation $\Sigma(g)$ to the values for
$g$'s children.
$C$ defines the $q$-ary query $Q \subseteq \str{A}^q$ where $a \in Q$ iff $C[\gamma
  \str{A}](\Omega(\gamma a)) = 1$.

\begin{definition}[Invariant Circuit]
 Let $C$ be a $(\mathbb{B},\tau)$-circuit with universe $U$ computing a
 $q$-ary query.  The circuit $C$ is \emph{invariant} if for every
 $\str{A} \in \ensuremath{\mathrm{fin}}[\tau]$ with $|\str{A}| = |U|$, $a \in \str{A}^q$,
 and bijections $\gamma_1,\gamma_2$ from $A$ to $U$,
 $C[\gamma_1\str{A}](\Omega(\gamma_1a)) =
 C[\gamma_2\str{A}](\Omega(\gamma_2a)).$
\end{definition}

Invariance indicates that $C$ computes a property of $\tau$-structures
which is invariant to presentations of the structure.  Moreover, for
an invariant circuit $C$ only the size of $U$ matters and we often
write $C = C_n$ to emphasise that $C_n$ has a universe of size $n$.
A \emph{family} $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ of invariant
$(\mathbb{B},\tau)$-circuits naturally computes a $q$-ary query on
$\tau$-structures.  When $q = 0$ the family computes a Boolean
property of structures.  We now discuss a structural property of
circuits called \emph{symmetry} that implies invariance.

\paragraph{Symmetric Circuits.}
Permuting a circuit's universe may induce automorphisms of the
circuit.

\begin{definition}[Induced Automorphism]
  Let $C = \tup{G,W,\Omega,\Sigma,\Lambda}$ be a $(\mathbb{B},\tau)$-circuit
  with universe $U$ computing a
 $q$-ary query.  Let $\sigma \in \Sym{U}$.  If there is a
  bijection $\pi$ from $G$ to $G$ such that
  \begin{itemize}
    \item for all gates $g,h \in G$, $W(g,h)$ iff $W(\pi(g),\pi(h))$,
    \item for all output tuples $x \in U^q$, $\pi\Omega(x) = \Omega(\sigma(x))$,
    \item for all gates $g \in G$, $\Sigma(g) = \Sigma(\pi(g))$, and
    \item for each relational gate $g \in G$, $\sigma\Lambda(g) =
      \Lambda(\pi(g))$,
  \end{itemize}
  we say $\sigma$ \emph{induces the automorphism $\pi$} of $C$.
\end{definition}

The principle goal of this paper is to understand the computational
power of circuit classes with the following type of structural
symmetry.

\begin{definition}[Symmetric]\label{def:symmetric}
  A circuit $C$ with universe $U$ is called \emph{symmetric}
  if for every permutation $\sigma \in \Sym{U}$, $\sigma$ induces an
  automorphism of $C$.
\end{definition}
It is not difficult to see that, for a symmetric circuit $C$, there is
a homomorphism $h: \Sym{U} \rightarrow \Aut{C}$ (where $\Aut{C}$ denotes the
automorphism group of $C$) such that $h(\sigma)$ is an automorphism
induced by $\sigma$.
As long as some element of $U$ appears in the label of some
input gate of $C$, $h$ is an injective homomorphism.  Henceforth we
assume that this is always the case as otherwise $C$ has no relational inputs and computes a constant function.  Circuits where the homomorphism is not also surjective introduce artifacts into our arguments.  To avoid this we require the circuits we consider to be \emph{rigid}.

\begin{definition}[Rigid]
  \label{def:rigid}
  Let $C = \tup{G,W,\Omega,\Sigma,\Lambda}$ be a $(\mathbb{B},\tau)$-circuit
  with universe $U$.  Call $C$ \emph{rigid} if there do not exist
  distinct gates $g,g' \in G$ with $\Sigma(g) = \Sigma(g')$,
  $\Lambda(g) = \Lambda(g')$, $\Omega^{-1}(g) = \Omega^{-1}(g')$, and
  for every $g'' \in G$, $W(g'',g)$ iff $W(g'',g')$.
\end{definition}

To show that for rigid symmetric circuits $C$, any injective
homomorphism from $\Sym{U}$ to $\Aut{C}$ is surjective, it suffices to
show that each $\sigma \in \Sym{U}$ induces a unique automorphism in
$\Aut{C}$.

\begin{prop}
  \label{prop:rigid}
  Let $C$ be a rigid circuit with universe $U$, and $\sigma \in
  \Sym{U}$.  If $\sigma$ induces an automorphism of $C$, that
  automorphism is unique.
\end{prop}

We defer the proof of this proposition to Section~\ref{subsec:rigid} were we also show that symmetric circuits can be transformed into equivalent rigid symmetric circuits in polynomial time, and hence show that rigidity can be assumed of circuits without loss of generality in our setting.
For a rigid symmetric circuit $C$, the group of automorphisms of
$C$ is exactly $\Sym{U}$ acting faithfully.  We shall therefore abuse
notation and use these interchangeably.  In particular, we shall write
$\sigma g$ to denote the image of a gate $g$ in $C$ under the action
of the automorphism induced by a permutation $\sigma$ in $\Sym{U}$.

An examination of the definitions suffices to show that symmetry
implies invariance.  In symmetric circuits it is useful to consider
those permutations which induce automorphisms that fix gates.  Let
$\mathcal{P}}%partial$ be a partition of a set $U$.  Let the \emph{pointwise stabiliser}
of $\mathcal{P}}%partial$ be $\stabu{\mathcal{P}}%partial} := \condset { \sigma \in \Sym{U}}{\forall P
  \in \mathcal{P}}%partial, \sigma P = P},$ and similarly define the \emph{setwise
  stabiliser} $\sstabu{\mathcal{P}}%partial} := \condset{ \sigma \in \Sym{U}}{\forall P
  \in \mathcal{P}}%partial, \sigma P \in \mathcal{P}}%partial}$.  For a gate $g$ in a rigid symmetric circuit $C$ with
universe $U$, let the \emph{stabiliser} of $g$ be $\stabu{g} :=
\condset{ \sigma \in \Sym{U}}{ \induce{\sigma}(g) = g}$, and let the \emph{orbit} of $g$
under the automorphism group $\Aut{C}$ of $C$ be $\mathrm{Orb}(g) :=
\condset{\pi g}{\pi \in \Aut{C}}$.
  In each case, when $U=[n]$, we
write $\mathrm{Stab}_n$ instead of $\mathrm{Stab}_{[n]}$.

\paragraph{Uniform Circuits.}
One natural class of circuits are those with
polynomial-size descriptions that can be generated by a deterministic
polynomial-time machine.

\begin{definition}[\ensuremath{\mathrm{P}}\xspace and \ensuremath{\PT/\poly}\xspace-Uniform]
  A $(\mathbb{B},\tau)$-circuit family $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ computing a
  $q$-ary query is \emph{\ensuremath{\PT/\poly}\xspace-uniform} if there exists an integer $t
  \ge q$ and function $\Upsilon : \ensuremath{\mathbb{N}}\xspace \rightarrow \set{0,1}^*$ which
  takes an integer $n$ to a binary string $\Upsilon(n)$ such that
  $|\Upsilon(n)| = \ensuremath{\mathrm{poly}}\xspace(n)$, and $\Upsilon(n)$
  describes\footnote{Formally one must define a particular way of
    encoding circuits via binary strings.  However, since the details
    of the representation are largely irrelevant for our purposes we omit them.}
  the circuit $C_n$ whose gates are indexed by $t$-tuples of
  $\set{0,1,\ldots,n}$, inputs are labelled by $t$-tuples of $[n]$,
  and outputs are labelled by $q$-tuples of $[n]$.  Moreover, if there
  exists a deterministic Turing machine $M$ that for each integer $n$
  computes $\Upsilon(n)$ from $1^n$ in time $\ensuremath{\mathrm{poly}}\xspace(n)$ call $\ensuremath{\mathcal{C}}\xspace$
  \emph{\ensuremath{\mathrm{P}}\xspace-uniform}.
\end{definition}

Note that such uniform families implicitly have polynomial size.
It follows from the Immerman-Vardi Theorem \cite{V82,I86} that any
$\ensuremath{\mathrm{P}}\xspace$-uniform family $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ of circuits is definable
by an $\ensuremath{\mathrm{FP}}\xspace$ interpretation in the sense that there is a sequence of
formulas $(\phi_G, \phi_W,
  \phi_\Omega,(\phi_s)_{s \in \mathbb{B} \uplus \tau \uplus \set{0,1}},
  (\phi_{\Lambda_R})_{R\in \tau})$ which, interpreted in the structure $\tup{[n],\le}$,
  describes the circuit $C_n =  \tup{G,W,\Omega,\Sigma,\Lambda}$, with

  \begin{itemize}
  \item $G \subseteq [n]^t$ such that $g \in G$ iff
    $ \tup{[n],\le}\models \phi_G[g]$.
  \item For all $g,g' \in G$ and
    $W(g,g')$ iff $\tup{[n],\le} \models \phi_W[g,g']$.
  \item For all $g \in G$ and $a \in [n]^q$, $\Omega(a)
    = g$ iff $\tup{[n],\le} \models \phi_\Omega[a,g]$.
  \item For all $g \in G$ and $s \in \mathbb{B} \uplus \tau \uplus \set{0,1}$,
    $\Sigma(g) = s$ iff $\tup{[n],\le}\models \phi_s[g]$.
  \item For all relational gates $g \in G$ and $a \in
    [n]^r$,
    $\Lambda_R(g) = a$ iff $\tup{[n],\le} \models
    \phi_\Lambda[g,a]$, where $r$ is the arity of $R = \Sigma(g)$.
  \end{itemize}

\noindent More generally, if  $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ is a \emph{\ensuremath{\PT/\poly}\xspace-uniform}
family of circuits, there is an $(\ensuremath{\mathrm{FP}+\Upsilon}\xspace)$-definable interpretation of
$C_n$ in $\str{A}^\Upsilon$ for a suitable advice function $\Upsilon$.

Over ordered structures
neither $\ensuremath{\mathrm{P}}\xspace$-uniform nor $\ensuremath{\PT/\poly}\xspace$-uniform circuits need compute
invariant queries as their computation may
implicitly depend on the order associated with $[n]$.  To obtain
invariance for such circuits we assert symmetry.  The next section
proves a natural property of symmetric circuits that ultimately
implies that \emph{symmetric} \ensuremath{\mathrm{P}}\xspace-uniform circuits coincide with
$\ensuremath{\mathrm{FP}}\xspace$ definitions on the standard and majority bases.

\subsection{Supporting Partitions}\label{subsec:partitions}

The notion of a supporting partition generalises the notion of a
support of a gate by replacing the set with a partition and
the stabiliser group of the gate with an arbitrary permutation group.

\begin{definition}[Supporting Partition]
Let $G \subseteq \Sym{U}$ be a group and $\mathcal{P}}%partial$ a partition of $U$.  We say
that $\mathcal{P}}%partial$ is a \emph{supporting partition} of $G$ if $\stabu{\mathcal{P}}%partial} \subseteq
G$.
\end{definition}

For intuition consider two extremes.  When $G$ has supporting
partition $\mathcal{P}}%partial = \set{U}$, it indicates $G =\Sym{U}$.  Saying that $G$
has supporting partition $\mathcal{P}}%partial =
\set{\set{u_1},\set{u_2},\ldots,\set{u_{|U|}}}$ indicates only that
$G$ contains the identity permutation, which is always true.

A natural partial order on partitions is the coarseness relation,
i.e., $\mathcal{P}}%partial'$ is as coarse as $\mathcal{P}}%partial$, denoted $\mathcal{P}}%partial' \supseteq \mathcal{P}}%partial$, if every part in $\mathcal{P}}%partial$ is
contained in some part of $\mathcal{P}}%partial'$.  For two partitions $\mathcal{P}}%partial$ and $\mathcal{P}}%partial'$,
there is a most refined partition that is as coarse as either partition:
\begin{definition}
  \label{def:E}
  Let $\mathcal{P}}%partial,\mathcal{P}}%partial'$ be partitions of $U$.  Define a binary relation
  $\sim$ on $U$: $u_1 \sim u_2$ iff there exists $P \in \mathcal{P}}%partial \cup \mathcal{P}}%partial'$
  such that $u_1,u_2 \in P$.  Let $\ensuremath{\mathcal{E}}(\mathcal{P}}%partial,\mathcal{P}}%partial')$ denote the
  partition of $U$ corresponding to the equivalence classes of $U$
  under the transitive closure of $\sim$.
\end{definition}
Now it is easy to show that $\ensuremath{\mathcal{E}}$ preserves supporting partitions (the proof
is similar to that of (*) on page 379 of \cite{O97}).
\begin{prop}
  \label{prop:intersect_gen}
Let $G \subseteq \Sym{U}$ be a group and $\mathcal{P}}%partial,\mathcal{P}}%partial'$ be supporting partitions
of $G$.  Then  $\ensuremath{\mathcal{E}}(\mathcal{P}}%partial,\mathcal{P}}%partial')$ is also a supporting partition of $G$.
\end{prop}
\begin{proof}
  Let $\ensuremath{\mathcal{E}} := \ensuremath{\mathcal{E}}(\mathcal{P}}%partial,\mathcal{P}}%partial') = \set{E_1,\ldots,E_m}$.  Suppose $\sigma \in
  \stab{\ensuremath{\mathcal{E}}}$ and we now show that $\sigma \in G$.   Because the parts $E_i$ are
  disjoint write $\sigma$ as $\sigma_1\cdots \sigma_m$ where $\sigma_i
  \in \Sym{E_i}$ (i.e., it permutes only the elements of $E_i$).
  Indeed each $\sigma_i$ may be written as a sequence of
  transpositions of elements in $E_i$.  Thus it suffices to show that
  each transposition $(u u')$ with $u,u' \in E_i$ can be written as a
  sequence of permutations in $\stab{\mathcal{P}}%partial} \cup \stab{\mathcal{P}}%partial'} \subseteq
  G$.  Since $u,u' \in E_i$ there is a sequence of elements of $u_1,
  \ldots, u_\ell$ with $u_1 = u$, $u_\ell = u'$ and $u_j \sim u_{j+1}$
  for $j \in [\ell-1]$ witnessing the path from $u$ to $u'$.  By the
  definition of $\sim$, for each $j \in [\ell-1]$ there is $P \in \mathcal{P}}%partial
  \cup \mathcal{P}}%partial'$ such that $u_j, u_{j+1} \in P$ and therefore
  $(u_ju_{j+1})$ is a transposition in $\stab{\mathcal{P}}%partial} \cup \stab{\mathcal{P}}%partial'}$.
  Conclude that the transposition $(uu') = (u_1u_\ell) =
  (u_1u_2)(u_2u_3)\cdots
  (u_{\ell-2}u_{\ell-1})(u_{\ell-1}u_\ell)(u_{\ell-2}u_{\ell-1})\cdots
  (u_1u_2)$ is a sequence of transpositions from $\stab{\mathcal{P}}%partial} \cup
  \stab{\mathcal{P}}%partial'}$ and the proof is complete.
\end{proof}
This implies that each permutation group has a unique coarsest
partition that supports it.
\begin{lemma} \label{lem:supp-gen}
Each permutation group $G\subseteq \Sym{U}$ has a unique coarsest supporting partition.
\end{lemma}
\begin{proof}
  Suppose $G$ has two distinct coarsest
  partitions $\mathcal{P}}%partial,\mathcal{P}}%partial'$ of the universe $U$ that support it, then
  Proposition~\ref{prop:intersect_gen} implies that the coarser
  partition $\ensuremath{\mathcal{E}}(\mathcal{P}}%partial,\mathcal{P}}%partial')$ also supports $G$.  This is a contradiction.
\end{proof}

We write $\mathsf{SP}(G)$ for \emph{the unique coarsest partition supporting} $G$.
For a partition $\mathcal{P}}%partial$ of $U$ and a permutation $\sigma \in \Sym{U}$,
we write $\sigma\mathcal{P}}%partial$ for the partition $\condset{\sigma P}{P \in \mathcal{P}}%partial}$.
Note that this commutes with the operation $\ensuremath{\mathcal{E}}$, so $\sigma\ensuremath{\mathcal{E}}(\mathcal{P}}%partial,\mathcal{P}}%partial')
= \ensuremath{\mathcal{E}}(\sigma\mathcal{P}}%partial,\sigma\mathcal{P}}%partial')$.
The next lemma shows how supporting partitions are affected by the
conjugacy action of $\Sym{U}$.
\begin{lemma}\label{lem:supp-conjug1}
If $\mathcal{P}}%partial$ is a partition supporting a group $G$, then for any $\sigma
\in \Sym{U}$, $\sigma\mathcal{P}}%partial$ supports the group $\sigma G \sigma^{-1}$.
\end{lemma}

\begin{proof}
Let $\pi \in \stabu{\sigma \mathcal{P}}%partial}$
and let $P$ be a part in $\mathcal{P}}%partial$, then:
$$ (\sigma^{-1}\pi\sigma)P = (\sigma^{-1}\pi)(\sigma P) =
\sigma^{-1}\sigma P = P,$$
where the second equality follows from the fact that $\pi$ fixes
$\sigma P$.  Thus, $\sigma^{-1}\pi\sigma$ fixes $\mathcal{P}}%partial$ pointwise,
therefore $\sigma^{-1}\pi\sigma \in G$ and hence $\pi \in \sigma G
\sigma^{-1}$.
\end{proof}
This indicates how the unique coarsest supporting partition of a group translates under conjugation.
\begin{lemma}\label{lem:supp-conjug}
For any $G \subseteq \Sym{U}$ and any $\sigma \in \Sym{U}$, $\sigma \mathsf{SP}(G) = \mathsf{SP}(\sigma G \sigma^{-1})$.
\end{lemma}
\begin{proof}
Immediate from Lemma~\ref{lem:supp-conjug1} and the fact that the
action of $\ensuremath{\mathcal{E}}$ commutes with $\sigma$.
\end{proof}
We conclude that any group $G$ is sandwiched between the pointwise and setwise
stabilisers of $\mathsf{SP}(G)$.
\begin{lemma}\label{lem:supp-group}
For any group $G \subseteq \Sym{U}$, we have $\stabu{\mathsf{SP}(G)} \subseteq G \subseteq
\sstabu{\mathsf{SP}(G)}$.
\end{lemma}
\begin{proof}
The first inclusion is by definition of supporting partitions.  For
the second, note that if $\sigma \in G$, then $\sigma G \sigma^{-1} =
G$.  Then, by Lemma~\ref{lem:supp-conjug}, $\sigma\mathsf{SP}(G) = \mathsf{SP}(G)$.
\end{proof}
Note that these bounds need not be tight.
For example, if $G$ is the alternating group on $U$
(or, indeed, any transitive, primitive subgroup of $\Sym{U}$),
then $\mathsf{SP}(G)$ is the partition of $U$ into singletons.  In this case,
$\stabu{\mathsf{SP}(G)}$ is the trivial group while $\sstabu{\mathsf{SP}(G)}$ is all
of $\Sym{U}$.

We now use the bounds given by Lemma~\ref{lem:supp-group},
in conjunction with bounds on $G$ to obtain size bounds on $\mathsf{SP}(G)$.
Recall that the index of $G$ in $\Sym{U}$, denoted
$\ind{\Sym{U}}{G}$ is the number of cosets of $G$ in $\Sym{U}$ or,
equivalently, $\frac{|\Sym{U}|}{|G|}$.
The next lemma says that if $\mathcal{P}}%partial$ is a partition of $[n]$ where the
index of $\sstabn{\mathcal{P}}%partial}$ in $\Sym{n}$ is sufficiently small then the
number of parts in $\mathcal{P}}%partial$ is either very small or very big.
\begin{lemma}\label{lem:small-large}
For any $\epsilon$ and $n$ such that $0\leq \epsilon < 1$ and $\log n \geq
\frac{4}{\epsilon}$, if $\mathcal{P}}%partial$ is a partition of $[n]$ with $k$ parts,
$s := \ind{\Sym{n}}{\sstabn{\mathcal{P}}%partial}}$ and $n \leq s \leq
2^{n^{1-\epsilon}}$, then $\min\set{k,n-k} \le \frac{8}{\epsilon}
\frac{\log s}{\log n}$.
\end{lemma}
\begin{proof}
 Let $p_1 \le p_2 \le \ldots \le p_k$ be the
  respective sizes of the parts in $\mathcal{P}}%partial$.  Thus,
  \begin{equation}
    \label{eq:weak-k:1}
    \hfill s =
    \frac{n!}{|\sstabn{\mathcal{P}}%partial}|} \ge \frac{1}{k!}\frac{n!}{p_1! p_2!
      \cdots p_k!}.\hfill
  \end{equation}
Observe that,  if $p_i > 1$, then $p_1! p_2! \cdots p_k! \leq p_1! p_2!
\cdots (p_i -1)! \cdots (p_k+1)!$.  By repeatedly applying this, we
see that in the lower bound on $s$ given by
Equation~\eqref{eq:weak-k:1}, we can replace $p_1! p_2! \cdots p_k!$
by $(n - (k-1))!$.

Let $k' :=
  \min\set{k,n-k}$ and we have
  $$s \ge \frac{n!}{k
  (n-(k-1))!} = \frac{1}{n+1}\binom{n+1}{k} \ge
  \frac{1}{n+1}\binom{n}{k} \ge \frac{1}{n+1}\binom{n}{k'} \ge
  \frac{1}{n+1}\left(\frac{n}{k'}\right)^{k'}$$ where the second
  inequality follows because $\binom{n}{k} = \binom{n}{n-k} =
  \binom{n}{k'}$, and the third inequality follows from a simple
  combinatorial bound.  Take the logarithm of both sides of the above
  equation to get $\log s \ge k' (\log n - \log k') - \log (n+1)$.
  Using the fact that $s \ge n \ge 2$ ($\log n \ge \frac{4}{\epsilon}
  \ge 4$) then implies that
  \begin{equation}
    \hfill 4\log s \ge k' (\log n - \log k'), \label{eq:weak-k:2}\hfill
  \end{equation}
  The definition of $k'$ implies that $k' \le \frac{n}{2}$ and $\log n
  - \log k' \ge 1$.  Plugging this into Equation~\eqref{eq:weak-k:2}
  gives that $4\log s \ge k'.$ Take the logarithm of this inequality
  and apply the upper bound on $s$ to determine that $(1-\epsilon)\log
  n + 2 \ge \log k'.$ Inserting this inequality back into
  Equation~\eqref{eq:weak-k:2} gives $4 \log s \ge k' (\epsilon \log n
  - 2).$ Since $\frac{\epsilon}{2}\log n \ge 2$, conclude that $k' \le
  \frac{8}{\epsilon}\frac{\log s}{\log n}$.
\end{proof}

We use a similar argument to establish that, under the assumptions of
the previous lemma, when the number of parts in $\mathcal{P}}%partial$ is small, then
the largest part is very big.

\begin{lemma}\label{lem:largepart}
For any $\epsilon$ and $n$ such that $0\leq \epsilon < 1$ and $\log n
\geq \frac{8}{\epsilon^2}$, if $\mathcal{P}}%partial$ is a partition of $[n]$ with
$\npart{\mathcal{P}}%partial} \leq \frac{n}{2}$, $s := \ind{\Sym{n}}{\sstabn{\mathcal{P}}%partial}}$
and $n \leq s \leq 2^{n^{1-\epsilon}}$, then $\mathcal{P}}%partial$ contains a part $P$
with at least $n - \frac{33}{\epsilon} \cdot \frac{\log s}{\log n}$
elements.
\end{lemma}
\begin{proof}
  The initial setup is the same as in the proof of
  Lemma~\ref{lem:small-large}.   Let $p_1 \le p_2
  \le \ldots \le p_k$ be the respective sizes of the parts in $\mathcal{P}}%partial$ and
  let $S := \sum_{i = 1}^{k-1}p_i$.  Our aim is to show that $S \leq
  \frac{33}{\epsilon} \cdot \frac{\log s}{\log n}$.
  Denote the size of the second largest part by $p := p_{k-1}$.  We
  have
  \begin{equation}
    \label{eq:rk:1}
    \hfill s = \frac{n!}{|\sstabn{\mathcal{P}}%partial}|} \ge \frac{1}{k!}\frac{n!}{p_1!p_2!
      \cdots p_k!}.\hfill
  \end{equation}
  Let $\ell \in \ensuremath{\mathbb{N}}\xspace$ be such that
  \begin{equation}
    \label{eq:rk:2}
    \hfill \ell \le k-1, \text{ and } k-1 + \ell (p-1) \le \sum_{i =
      1}^{k-1}p_i = S. \hfill
  \end{equation}
   Provided $\mathcal{P}}%partial$ contains more than one part both $\ell \in \set{0,1}$
  satisfy Equation~\eqref{eq:rk:2}.   We may assume that $p > 1$
  otherwise $S \le \npart{\mathcal{P}}%partial}$ and we are done by
  Lemma~\ref{lem:small-large}.
 For any $\ell \ge 1$ satisfying
  Equation~\eqref{eq:rk:2}, redistributing weight from a $p_i$ to $p_j$
  with $i < j$ in a way similar to the proof of
  Lemma~\ref{lem:small-large} gives the following,
  \begin{align}

    s &\ge \frac{1}{k!}\frac{n!}{ \underbrace{1!\cdots1!}_{k-1-\ell
        \text{~times}} \underbrace{p!\cdots p!}_{\ell
        \text{~times}}(n-(k-1-\ell + \ell p))!} \ge \frac{n!}{
      (p!)^\ell (n-\ell(p-1) + 1)!} \notag \\

    &\ge \frac{(\frac{n}{e})^n}{(e \sqrt{p}(\frac{p}{e})^p)^\ell (e
      \sqrt{n}
      (\frac{n}{e})^{n-\ell(p-1)+1})}=\frac{n^{\ell(p-1)-3/2}}{p^{\ell(p+1/2)}}
    \underbrace{\frac{e^{\ell p} e^{n-\ell(p-1)+1}}{e^{\ell+1}
        e^n}}_{=1} \notag

  \end{align}
  where the third inequality follows from Stirling's Formula, i.e.,
  that for any $x \ge 2$, $(\frac{x}{e})^x \le x! \le \sqrt{2\pi
    x}(\frac{x}{e})^x e^{\frac{1}{12x}} \le e \sqrt{x}
  (\frac{x}{e})^x$.  Take the logarithm of the above equation to
  determine that
  \begin{align}
    %
    \label{eq:rk:3}
    \log s &\ge \left[\ell(p-1)-\frac{3}{2}\right] \log n - \ell \left(p
    +\frac{1}{2}\right) \log p \\ &= \ell \left(p + \frac{1}{2}\right) (\log n
    - \log p) - \frac{3}{2}(\ell-1)\log n, \notag \\
    %
    \label{eq:rk:4}
    \frac{5}{2} \log s &\ge \ell p (\log n - \log p) -
    \frac{3}{2}\ell \log n \ge p (\log n - \log p) -
    \frac{3}{2}\log n, \\
   %
    \label{eq:rk:5}
    4\log s &\ge  p (\log n - \log p) \ge p,
  \end{align}
  where Equation~\eqref{eq:rk:4} follows from Equation~\eqref{eq:rk:3}
  since $s \ge n$ and $\ell \ge 1$, and Equation~\eqref{eq:rk:5}
  follows from Equation~\eqref{eq:rk:4} because $p$ is the size of the
  second largest part of $\mathcal{P}}%partial$ and hence $p \le \frac{n}{2}$ and $(\log
  n - \log p) \ge 1$.  Take the logarithm of Equation~\ref{eq:rk:5}
  and use the bound on $s$ to determine that $\log p \le \log \log s +
  2 \le (1-\epsilon) \log n + 2$.  Plug this bound into
  Equation~\eqref{eq:rk:4} to get that $\frac{5}{2} \log s \ge
  \ell p (\epsilon \log n - 2) - \frac{3}{2} \ell \log n$.  Using
  $\frac{\epsilon}{2} \log n \ge 2$ and dividing by $\log n$,
  $\frac{5}{2}\frac{\log s}{\log n} \ge \ell (\frac{p\epsilon}{2} -
  \frac{3}{2})$.

    If $\frac{p \epsilon}{4} \ge \frac{3}{2}$, then $\frac{10}{\epsilon}
  \frac{\log s}{\log n} \ge \ell p$.  For the largest value of $\ell$,
  $k-1 + (\ell+1)(p-1) \ge S$, and hence $k-1 + 2\ell p
  \ge S$.  Thus  Lemma~\ref{lem:small-large} implies that
  $S \le \frac{8 + 20}{\epsilon}\frac{\log s}{\log n}$.
  Otherwise $p < \frac{6}{\epsilon}$ and hence $\log p \le 3 - \log
  \epsilon$.  Plugging this into Equation~\eqref{eq:rk:4} and using
  $\log n \ge \frac{8}{\epsilon^2} \ge 2(3 - \log \epsilon) \ge 2\log
  p$ gives $\frac{5}{2} \log s \ge \ell \frac{p-3}{2} \log n.$ If $p
  \ge 5$, then recover $\frac{25}{2\epsilon}\frac{\log s}{\log n} \ge
  \ell p$ and conclude $S \le \frac{8 +
    25}{\epsilon}\frac{\log s}{\log n}$ analogously to before.  Otherwise
  $p \le 4$, and $S \le p (k-1) \le 4 \cdot
  \frac{8}{\epsilon}\frac{\log s}{\log n}$ by
   Lemma~\ref{lem:small-large}.  Since each case concluded that
  $S \le \frac{33}{\epsilon}\frac{\log s}{\log n}$ the
  proof is complete.
\end{proof}

\subsection{Support Theorem}\label{subsec:suppthm}

Here we leverage the two combinatorial lemmas of the last subsection
to show that in symmetric circuits of polynomial size, each gate has a
small supporting partition, and hence has a small support.

Let $g$ be a gate in a symmetric circuit $C$ over universe $U$, from
now on, we abuse notation and write $\mathsf{SP}(g)$ for $\mathsf{SP}(\stabu{g})$.
Note that, if $P$ is any part in $\mathsf{SP}(g)$, then $U\setminus P$ is a
support of $g$ in the sense of Definition~\ref{def:support}.  We write
$\spart{\mathsf{SP}(g)}$ to denote the smallest value of $|U\setminus P|$ over
all parts $P$ in $\mathsf{SP}(g)$.  Also, let $\mathsf{SP}(C)$ denote the maximum of
$\spart{\mathsf{SP}(g)}$ over all gates $g$ in $C$.

By the orbit-stabiliser theorem, $|\mathrm{Orb}(g)| =
\ind{\Sym{U}}{\stabu{g}}$.  By Lemma~\ref{lem:supp-group}, we have
that $\stabu{g} \subseteq \sstabu{\mathsf{SP}(g)}$ and thus, if $s$ is an upper
bound on $|\mathrm{Orb}(g)|$, $s \ge \ind{\Sym{U}}{\stabu{g}} \ge
\ind{\Sym{U}}{\sstabu{\mathsf{SP}(g)}}$.  Then, by Lemma~\ref{lem:largepart},
$g$ has a support of small size provided that (i) $s$ is
sub-exponential, and (ii) $\mathsf{SP}(g)$ has fewer than $n/2$ parts.  Thus,
to prove our main technical theorem, which formalises
Theorem~\ref{thm:intro-support} from the introduction, it suffices to
show that if $s$ is sufficiently sub-exponential, (ii) holds.

\begin{theorem}[Support Theorem]
  \label{thm:support}
  For any $\epsilon$ and $n$ with $\frac{2}{3} \le \epsilon \le 1$ and
  $n > 2^{\frac{56}{\epsilon^2}}$, if $C$ is a rigid symmetric circuit over
  universe $U$ with $|U| = n$ and $s := \max_{g \in C} |\mathrm{Orb}(g)| \le
  2^{n^{1-\epsilon}}$, then, $\mathsf{SP}(C) \le \frac{33}{\epsilon}
  \frac{\log s}{\log n}.$
\end{theorem}
\begin{proof}
  Suppose $1 \le s < n$.  $C$ cannot have relational inputs, because
  each relational gate must have an orbit of size at least $n$, so
  each gate of $C$ computes a constant Boolean function.  The support
  of every gate $g$ in $C$ must be $\set{U}$, and hence $0 =
  \spart{\mathsf{SP}(g)} = \mathsf{SP}(C)$.  Therefore assume $s \ge n$.

  To conclude the theorem from Lemma~\ref{lem:largepart} it
  suffices to argue that for all gates $g$, $\npart{\mathsf{SP}(g)} \le
  \frac{n}{2}$.  Suppose $g$ is a constant gate, then, because $g$ is
  the only gate with its label, it is fixed under all permutations and
  hence $\npart{\mathsf{SP}(g)} = \npart{\set{U}} = 1 <
  \frac{n}{2}$.  If $g$ is a relational gate, then it is fixed by any
  permutation that fixes all elements appearing in $\Lambda(g)$ and moved by
  all others.  Thus, $\mathsf{SP}(g)$ must contain singleton parts for each
  element of $U$ in
  $\Lambda(g)$ and a part containing everything else.  Thus, if
  $\npart{\mathsf{SP}(g)} > \frac{n}{2}$, $\mathsf{SP}(g)$ contains at least
  $\frac{n}{2}$ singleton parts, there is a contradiction using the
  bounds on $s, n,$ and $\epsilon$, $s \ge |\mathrm{Orb}(g)| \ge
  \spart{\mathsf{SP}(g)}! \cdot \binom{n}{\spart{\mathsf{SP}(g)}} \ge
  \left\lfloor\frac{n}{2}\right\rfloor!  \ge
  2^{\lfloor\frac{n}{4}\rfloor} > 2^{n^{1-\epsilon}}.$

  It remains to consider internal gates. For the sake of contradiction
  let $g$ be a topologically first internal gate such that $\mathsf{SP}(g)$ has more
  than $\frac{n}{2}$ parts.  Lemma~\ref{lem:small-large} implies,
  along with the assumptions on $s, n,$ and $\epsilon$, that
  $n-\npart{\mathsf{SP}(g)} \le k' := \left\lceil\frac{8}{\epsilon}\frac{\log
    s}{\log n}\right\rceil \le \frac{1}{4} n^{1 - \epsilon} <
  \frac{n}{2}.$

  Let $H$ denote the children of $g$.  Because $g$ is a topologically
  first gate with $\npart{\mathsf{SP}(g)} > \frac{n}{2}$, for all $h \in H$,
  $\mathsf{SP}(h)$ has at most $\frac{n}{2}$ parts.  As before, we
  argue a contradiction with the upper bound on $s$.  This done by
  demonstrating that there is a set of gate-automorphism pairs $S =
  \condset{(h,\sigma)}{h \in H, \sigma \in \Sym{U}}$ that are: (i) \emph{useful} -- the automorphism
  moves the gate out of the set of $g$'s children, i.e., $\sigma h
  \not\in H$, and (ii) \emph{independent} -- each child and its image
  under the automorphism are fixed points of the other automorphisms
  in the set, i.e., for all $(h,\sigma), (h', \sigma') \in S$, $\sigma' h =
  h$ and $\sigma' \sigma h = \sigma h$.  Note that sets which are useful and
  independent contain tuples whose gate and automorphism parts are all
  distinct.  The set $S$ describes elements in the orbit of $H$ with
  respect to $\Sym{U}$.

  \begin{claim}
    \label{claim:p}
    Let $S$ be useful and independent, then $|\Orb{}{H}| \ge
    2^{|S|}$.
  \end{claim}
  \begin{proof}
    Let $R$ be any subset of $S$.  Derive an automorphism from $R$:
    $\sigma_R := \prod_{(h,\sigma) \in R} \sigma$ (since automorphisms
    need not commute fix an arbitrary ordering of $S$).

    Let $R$ and $Q$ be distinct subsets of $S$ where without loss of
    generality $|R| \ge |Q|$.  Pick any $(h,\sigma) \in R \ensuremath{\backslash} Q \neq
    \emptyset$.  Because $S$ is independent $\sigma_R h = \sigma h$ and $\sigma_Q\sigma
    h = \sigma h$.  Since $S$ is useful, $\sigma h \not\in H$.  Thus $\sigma h
    \in \sigma_R H$, but $\sigma h \not\in \sigma_Q H$.  Hence $\sigma_R H \neq
    \sigma_Q H$.  Therefore each subset of $S$ can be identified with a distinct element
    in $\mathrm{Orb}(H)$ and hence $|\mathrm{Orb}(H)| \ge 2^{|S|}$.
  \end{proof}

  Thus to reach a contradiction it suffices to construct a
  sufficiently large set $S$ of gate-automorphism pairs.  To this end, divide $U$
  into $\lfloor\frac{|U|}{k'+2}\rfloor$ disjoint sets $S_i$ of size
  $k'+2$ and ignore the elements left over.  Observe that for each $i$
  there is a permutation $\sigma_i$ which fixes $U \ensuremath{\backslash} S_i$ but
  $\sigma_i$ moves $g$, because otherwise the supporting partition of $g$
  could be smaller ($n - (k'+2)+1$).  Since $g$ is moved by each
  $\sigma_i$ and $C$ is rigid, there must be an associated child $h_i \in H$
  with $\sigma_i h_i \not\in H$.  Thus let
  $(h_i,\sigma_i)$ be the gate-automorphism pair for $S_i$,
  these pairs are \emph{useful}.  Let $Q_i$ be the union of all but
  the largest part of $\mathsf{SP}(h_i)$.  Observe that for any $\sigma$ which
  fixes $Q_i$ pointwise $\sigma$ also fixes both $h_i$ and
  $\sigma_i h_i$, simply by the definition of support.

  Define a directed graph $K$ on the sets $S_i$ as follows.  Include
  an edge from $S_i$ to $S_j$, with $i \neq j$, if $Q_i \cap S_j \neq
  \emptyset$.  An edge in $K$ indicates a potential lack of independence
  between $(h_i,\sigma_i)$ and $(h_j,\sigma_j)$, and on the other hand if
  there are no edges between $S_i$ and $S_j$, the associated pairs are
  independent.  Thus it remains to argue that $K$ has a large
  independent set.  This is possible because the out-degree of $S_i$
  in $K$ is bounded by $|Q_i| = \spart{\mathsf{SP}(h_i)} \le
  \frac{33}{\epsilon}\frac{\log s}{\log n}$ as the sets $S_i$
  are disjoint and Lemma~\ref{lem:largepart} can be
  applied to $h_i$.  Thus the average total degree (in-degree +
  out-degree) of $K$ is at most $9k'$.  Greedily select a maximal
  independent set in $K$ by repeatedly selecting the $S_i$ with the
  lowest total degree and eliminating it and its neighbours.  This
  action does not effect the bound on the average total degree of $K$
  and hence determines an independent set $I$ in $K$ of size at least
  $$\frac{\lfloor\frac{|U|}{k'+2}\rfloor}{9 k'+1} \ge
  \frac{n-(k'+2)}{(9k'+1)(k'+2)} \ge \frac{\frac{n}{2}-1}{9k'^2+10k'+2}
  \ge \frac{\frac{7}{16}n}{9k'^2+10k'+2} \ge \frac{n}{(7 k')^2}$$ where
  the first inequality follows by expanding the floored expression,
  the second follows because $k' < \frac{n}{2}$, the third follows
  from the lower bound on $n$, and the last follows because $k' \ge 1$
  as it is the ceiling of a positive non-zero quantity by definition.

  Take $S := \condset{(h_i,\sigma_i)}{S_i \in I}$.  By the argument
  above $S$ is useful and independent.  By Claim~\ref{claim:p},
  conclude that $s \ge |\mathrm{Orb}(g)| \ge |\mathrm{Orb}(H)| \ge 2^{|S|} \ge
  2^{\frac{n}{(7k')^2}}.$ For $\epsilon \ge \frac{2}{3}$, $s \le
  2^{n^{1-\epsilon}}$, and $\frac{\epsilon}{56} \log n > 1$ the
  following is a contradiction

  $\log s \ge n \cdot (\frac{56}{\epsilon}\frac{\log s}{\log
        n})^{-2} > n \cdot (n^{1-\epsilon})^{-2} =
  n^{2\epsilon-1} \ge n^{1-\epsilon}.$
  Thus $\npart{\mathsf{SP}(g)}
  \le \frac{n}{2}$ for all $g \in C$ and the proof is complete by
  Lemma~\ref{lem:largepart}.
\end{proof}

Observe that when $s$ is polynomial in $n$ the support of a rigid symmetric
circuit family is asymptotically constant.  This is the case for
polynomial-size families.

\begin{corollary}
  \label{cor:support}
  Let $\ensuremath{\mathcal{C}}\xspace$ be a polynomial-size rigid symmetric circuit family, then
  $\mathsf{SP}(\mathcal{C}) = O(1)$.
\end{corollary}

\subsection{Rigid Circuits}\label{subsec:rigid}

We first argue that rigid circuits uniquely induce automorphisms.

\begin{proof}[Proof of Proposition~\ref{prop:rigid}]
  Let $\sigma \in \Sym{U}$ induce the automorphisms $\pi, \pi'$ of
  $C$.  We show $\pi g = \pi' g$ for all gates $g$ in $C$, and hence
  $\pi = \pi'$.

  Observe that if $g$ is an output gate, the image of $g$ under any
  automorphism induced by $\sigma$ must be
  $\Omega(\sigma\Omega^{-1}(g))$, because $\Omega$ is a function, and
  hence $\pi g = \pi' g$ is unique and completely determined by $\sigma$.
  Therefore assume that $g$ is not an output gate.  We proceed by
  induction on the height of $g$ to show that $\pi g = \pi' g$.

  In the base case $g$ is an input gate.  If $g$ is a constant gate,
  $g$ is the only constant gate of its type and hence all
  automorphisms of $C$ must fix it.  If $g$ is a relational gate, $g$
  is the only relational gate with its type $\Sigma(g)$ and label
  $\Lambda(g)$ and it must map to the similarly unique gate with type
  $\Sigma(g)$ and tuple $\sigma \Lambda(g)$ and hence $\pi g = \pi
  g'$.

  In the induction step $g$ is an internal gate.  By rigidity of $C$,
  $g$ is unique for its children and type.  Moreover, by induction the
  children of $g$ map in the same way under $\pi$ and $\pi'$, and
  hence the image of $g$ must be the same in both automorphisms.  Thus
  $\pi g = \pi' g$ for all gates of $C$.
\end{proof}

To see that any symmetric circuit can be transformed in polynomial
time into an equivalent rigid symmetric circuit, observe that we can proceed
inductively from the input gates, identifying gates whenever they
have the same label and the same set of children.  This allows us to
establish the following lemma.
\begin{lemma}
  \label{lem:alg-rigid}
  Let $C = \tup{G,W,\Omega,\Sigma,\Lambda}$ be a $(\mathbb{B},\tau)$-circuit
  with universe $U$.  There is a
  deterministic algorithm which runs in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$ and outputs
  a rigid $(\mathbb{B},\tau)$-circuit $C'$ with gates $G' = G$ such that for
  any $g \in G$, any input $\tau$-structure $\str{A}$ and any
  bijection $\gamma$ from $A$ to $U$, $C[\gamma\str{A}](g) =
  C'[\gamma\str{A}](g)$.
Moreover, $C'$ is symmetric if $C$ is.
\end{lemma}
  \begin{proof}
  Partition the gates $G$ into equivalence classes where gates in the
  same class have the same labels, output markings, and children.  If
  $C$ is rigid every class has size one, otherwise there is at least
  one class containing two gates.

  Let $E$ be a minimum height equivalence class containing at least two gates.
  Order the gates in $E$: $g_1,g_2,\ldots,g_{|E|}$.   For each gate $f \in G \ensuremath{\backslash} E$, let $c_f$ denote the number of wires from $E$ to $f$, and note that $c_f \le |E|$.   For all gates in $E$ remove all outgoing wires.   For all gates $E \ensuremath{\backslash} \set{g_1}$: (i) remove all input wires, and (ii) set their operation to AND.  For each $i$, $1 \le i \le |E|-1$, add a wire from $g_i$ to $g_{i+1}$.  For each $f \in G \ensuremath{\backslash} E$ and $i \in [|E|]$, add a wire from $g_i$ to $f$ if $c_f \le i$.  This completes the transformation of the gates in $E$.

  We now argue that this does not effect the result computed at any
  gate $g$.
  First observe that no output gates appear in $E$,  because
  $\Omega$ is injective and hence each output gate must be the sole
  member of its equivalence class.  All gates in $E$ originally had
  identical sets of children and labels and hence they must have evaluated to the
  same value.  The modifications made do not change this property as
  $g_1$ computes the value it originally would have, then passes this
  value to the other gates in $E$, along a chain of single input AND
  gates.  The modifications to the outgoing wires of $E$ insure that
  each gate that originally took input from $E$ has the same number of
  inputs from $E$ (each with the same value) in the modified circuit.
  Taken together this means that the result computed at any gate in
  the modified circuit is the same as that computed at that gate in $C$.

  We next argue that the local modification of $E$ makes strict progress towards producing a rigid circuit $C'$.  The local modification of $E$ can only change equivalence classes above $E$ because
the changes to the output wires of $E$ are the only thing that can possibly effect other equivalence classes. After the modification all gates in $E$ must be in singleton equivalence classes because each gate in $E$ is designed to have a unique set of children.

  Greedily applying the above local modification simultaneously to all topologically minimal non-singleton equivalence classes of $C$, until none remain, produces a rigid circuit $C'$ that computes the same query as $C$, because, as we have just argued, equivalence classes cannot grow as a result of this local modification.  Moreover, this must happen after at most $|C|$ many local modifications, because the number of equivalence classes is at most $|C|$.

  We now show that this transformation preserves symmetry.   Suppose $C$ is symmetric.
  Fix any permutation $\sigma \in \Sym{U}$.   Let $\pi$ be an automorphism induced by $\sigma$ on $C$.  Observe that any induced automorphism on $C$ must map equivalence classes
  to equivalence classes because labels and children are preserved.
  It is easy to translate $\pi$ into an induced automorphism of $C'$.
  Let $E$ and $E'$ be two equivaluence classes such that $\pi E = E'$
  where $g_1,\ldots,g_{|E|}$ and $g_1',\ldots,g_{|E'|}'$ are the
  ordering of the gates in $E$ and $E'$ in $C'$.  It can be argued by
  induction that mapping $g_i$ to $g_i'$ for all $1 \le i \le
  |E|=|E'|$ preserves all labels and wires and hence is an induced
  automorphism of $\sigma$ in $C'$.  Since $\sigma$ is arbitrary, we
  conclude that the resulting circuit is symmetric.

  The construction of equivalence classes and, indeed, the overall
  construction of $C'$ can be easily implemented in time polynomial in
  $|C|$ when given the circuit in a reasonable binary encoding.  Finally, as gates are only being rewired and relabelled, $G = G'$.
\end{proof}

\subsection{Computing Supports}\label{subsec:supports}

By Lemma~\ref{lem:alg-rigid}, we know that there is a polynomial-time
algorithm that converts a circuit into an equivalent rigid circuit
while preserving symmetry.  In this subsection we show how to, in
polynomial time, check whether the resulting circuit is symmetric, and
if it is, compute the support of each gate.  To this end we first describe an algorithm for determining induced automorphisms of a rigid circuit.

\begin{lemma} \label{lem:alg-action}
  Let $C$ be a rigid $(\mathbb{B},\tau)$-circuit with universe $U$ and $\sigma
  \in \Sym{U}$.  There is a deterministic algorithm which runs in time
  $\ensuremath{\mathrm{poly}}\xspace(|C|)$ and outputs for each gate $g \in G$ its image under the
  automorphism $\pi$ induced by $\sigma$, if it exists.
\end{lemma}

\begin{proof}
  Process the gates of $C$ recursively building up a mapping $\pi$.
  Compute the mapping for the children of a gate $g$ before
  determining the mapping for $g$.  If at any point an image for $g$
  cannot be located, halt and output that there is no induced
  automorphism.

  Let $g$ be a constant gate, then $g$ is fixed under every
  automorphism.  Let $g$ be a relational gate, then there is at most
  one gate $g'$ in $C$ with $\Sigma(g) = \Sigma(g')$, $\sigma
  \Lambda(g) = \Lambda(g')$, and $\sigma \Omega^{-1}(g) =
  \Omega^{-1}(g')$.  If $g'$ exists, set $\pi g$ to $g'$, otherwise
  halt with failure.  Similarly, when $g$ is an internal gate use
  $\Lambda$, $\Omega$, and the action of $\pi$ on the children of $G$
  (via $W$) to determine a unique image of $g$, if it exists.

  By Proposition~\ref{prop:rigid} if $\sigma$ induces an automorphism
  of $C$, it is unique and will be discovered by the above algorithm.
  This algorithm clearly runs in time polynomial in $|C|$.
\end{proof}

Using the preceding lemma we can determine whether a given rigid
circuit is symmetric by computing the set of automorphisms induced by
transpositions of the universe.  If an induced automorphism fails to
exist the circuit cannot be symmetric.  Otherwise, it must be
symmetric because such transpositions generate the symmetric
group.  If the circuit is symmetric, the coarsest supporting
partitions and orbits of each gate can be determined by examining the
transitive closure of the action of the automorphisms induced by
transpositions on the universe and the gates, respectively.

\begin{lemma}
  \label{lem:alg-sym}
  Let $C$ be a rigid $(\mathbb{B},\tau)$-circuit with universe $U$.  There is a
  deterministic algorithm which runs in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$ and decides
  whether $C$ is symmetric.  If $C$ is symmetric the algorithm also
  outputs the orbits and coarsest supporting partitions of every gate.
\end{lemma}

\begin{proof}
  For all transpositions $(uv) \in \Sym{U}$ run the algorithm of
  Lemma~\ref{lem:alg-action} to determine the unique automorphism
  $\pi_{(uv)}$ of $C$ induced by $(uv)$, if it exists.  Output that
  $C$ is symmetric iff every induced automorphism $\pi_{(uv)}$ exists.
  This is correct because the set of transpositions generates all of
  $\Sym{U}$, and therefore the automorphisms $\pi_{(uv)}$ generate all induced automorphisms of $C$.

  If $C$ is symmetric, these induced automorphisms also indicate the
  supporting partitions and orbits of each gate $g$.  Let $\mathcal{P}}%partial_{(uv)} :=
  \set{\set{u,v}} \cup_{w \in U \ensuremath{\backslash} \set{u,v}} \set{\set{w}}$ be a
  partition of $U$.  Note that $\pi_{(uv)}$ fixes $g$ iff $\mathcal{P}}%partial_{(uv)}$
  supports $g$.  Let $\mathcal{P}}%partial$ be the partition determined by combining the
  partitions $\mathcal{P}}%partial_{(uv)}$ which support $g$ using $\mathcal{E}$.
  Proposition~\ref{prop:intersect_gen} implies that $\mathcal{P}}%partial$ supports $g$.
  Suppose $\mathcal{P}}%partial$ is not the coarsest partition supporting $g$.  Then,
  there exists $u,v \in U$ which are not in the same part of $\mathcal{P}}%partial$ but
  in the same part of some partition supporting $g$.  But by
  the definition of $\mathcal{P}}%partial$, $\pi_{(uv)}$ cannot fix $g$---a contradiction.  Therefore $\mathcal{P}}%partial$ is the coarsest partition
  supporting $g$.

  To compute the orbit of a gate $g$: Start with $S_0 := \set{g}$,
  and for $i \ge 0$, compute $S_{i+1} := S_i \cup_{(uv) \in \Sym{U}}
  \pi_{(uv)} S_i$.  Let $S$ be the least fixed point of this process.  We argue that $S = \mathrm{Orb}(g)$.  $S \subseteq \mathrm{Orb}(g)$, because it consists
  of gates reachable from $g$ via a sequence of induced automorphisms
  of $C$.  $S \supseteq \mathrm{Orb}(g)$, because the set of automorphisms induced
  by transpositions generate the the group of all induced
  automorphisms.

  Since there are only $\binom{|U|}{2}$ transpositions, and we can
  determine whether there is an induced automorphism for each
  transposition in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$ and hence determine whether $C$
  is symmetric in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$.  If $C$ is symmetric the
  computation of the supports and orbits of all gates also is computed
  in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$ because each output is completely determined by
  the equivalence classes induced by the relations defined by the
  induced automorphisms $\pi_{(uv)}$.  Therefore the overall algorithm
  runs in time $\ensuremath{\mathrm{poly}}\xspace(|C|)$.
\end{proof}

\subsection{Succinctly Evaluating Symmetric Circuits
\label{subsec:evaluate}

Let $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ be a family of polynomial-size rigid symmetric
circuits computing a $q$-ary query.  Let $n_0$ be a constant sufficient to apply the
Support Theorem to $C_n$ for $n \ge n_0$ and fix such an $n$.  By
Theorem~\ref{thm:support}, there is a constant bound $k$ so that for
each gate $g$ in $C_n$ the union of all but the largest part of the
coarsest partition supporting $g$, $\mathsf{SP}(g)$, has at most $k$ elements.
Moreover, this union is a
\emph{support} of $g$ in the sense of Definition~\ref{def:support}.
We call it the \emph{canonical support} of $g$ and denote it by
$\spt{g}$.  In this subsection we show that how a gate $g$ evaluates in
$C_n$ with respect to a structure $\str{A}$ depends only on how the universe $U$ of
the structure is mapped to the canonical support of $g$.  This allows
us to succinctly encode the bijections which make a gate true (first
as injective partial functions and then as tuples).  This ultimately
lets us build a fixed-point formula for evaluating $C_n$---indeed, all
symmetric circuits---in the next subsection.

For any set $X \subseteq [n]$, let $U^X$ denote the set of \emph{injective}
functions from $X$ to $U$.  Let $X, Y \subseteq [n]$ and $\alpha \in
U^X, \beta \in U^Y$, we say $\alpha$ and $\beta$
are \emph{consistent}, denoted $\alpha \sim \beta$, if for all $z \in
X \cap Y, \alpha(z) = \beta(z)$, and for all $x \in X \ensuremath{\backslash} Y$ and
$y \in Y \ensuremath{\backslash} X$, $\alpha(x) \neq \beta(y)$.  Recall that any bijection
$\gamma: U \rightarrow [n]$ determines an evaluation of the circuit $C_n$ on
the input structure $\str{A}$ which assigns to each gate $g$ the
Boolean value $C_n[\gamma\str{A}](g)$.  (Note that $\gamma^{-1} \in
U^{[n]}$.)  Let $g$ be a gate and let
$\Gamma(g) := \condset{\gamma}{C_n[\gamma\str{A}](g) = 1}$ denote the
set of those bijections which make $g$ evaluate to $1$.  The following
claim proves that the membership of $\gamma$ in $\Gamma(g)$ (moreover,
the number of 1s input to $g$) depends only on what $\gamma$ maps to
$\spt{g}$.

\begin{claim}\label{claim.gamma}
Let $g$ be a gate in
$C_n$ with children $H$.  Let $\alpha \in U^\spt{g}$, then for all
$\gamma_1, \gamma_2 : U \rightarrow [n]$ with
$\gamma_1^{-1} \sim \alpha$ and $\gamma_2^{-1} \sim \alpha$,
\begin{enumerate}
\item $\gamma_1 \in \Gamma(g)$ iff $\gamma_2 \in \Gamma(g)$. \label{claim.gamma.i}
\item $|\condset{ h \in H }{\gamma_1 \in \Gamma(h)}| = |\condset{ h \in H
}{\gamma_2 \in \Gamma(h)}|.$ \label{claim.gamma.ii}
\end{enumerate}
\end{claim}

\begin{proof}
There is a unique permutation $\pi \in \Sym{n}$ such that $\gamma_1
= \pi\gamma_2$.  Moreover, $\pi$ fixes $\spt{g}$ pointwise, since
$\gamma_1^{-1}$ and $\gamma_2^{-1}$ are consistent with $\alpha$.  Since
$C_n$ is rigid and symmetric, $\pi$ is an automorphism of $C_n$, and
we have that $C_n[\gamma_1\str{A}](g) = C_n[(\pi\gamma_1)\str{A}](\pi
g)$.  Since $\pi$ fixes $\spt{g}$ pointwise, we have $\pi g = g$ and
therefore $C_n[\gamma_1\str{A}](g) = C_n[(\pi\gamma_1)\str{A}](g) =
C_n[\gamma_2\str{A}](g)$, proving part~\ref{claim.gamma.i}.
Similarly, for any child $h \in H$ we have that
$C_n[\gamma_1\str{A}](h) = C_n[(\pi\gamma_1)\str{A}](\pi h) =
C_n[\gamma_2\str{A}](\pi h)$.  Since $\pi$ fixes $g$, $\pi$
fixes $H$ setwise.  As this establishes a bijection between the children
$H$ that evaluate to 1 for $\gamma_1$ and $\gamma_2$, we conclude
part~\ref{claim.gamma.ii}.
\end{proof}

We associate with each gate $g$ a set of injective functions
$\EV{g} \subseteq U^{\spt{g}}$ defined by $\EV{g} := \condset{\alpha \in
U^\spt{g}}{\exists \gamma \in \Gamma(g) \wedge \alpha \sim \gamma^{-1}}$
and note that, by Claim~\ref{claim.gamma}, this completely determines
$\Gamma(g)$.  We can use the following claim to recursively construct
$\EV{g}$ for all gates in $C$.

\begin{claim}\label{claim.ev}
Let $g$ be a gate in
$C$ with children $H$.  Let $\alpha \in U^\spt{g}$, then for all
$\gamma : U \rightarrow [n]$ with $\gamma^{-1} \sim \alpha$,
\begin{equation}
\hfill
|\condset{ h \in H }{\gamma \in \Gamma(h)}| = \sum_{h \in
H} \frac{|A_h \cap \EV{h}|}{|A_h|}, \label{eqn.ev} \hfill
\end{equation}
where for $h \in H$, $A_h := \condset{\beta \in
U^{\spt{h}}}{\alpha \sim \beta}$.
\end{claim}

\begin{proof}
We have,
\begin{equation}
\begin{aligned}
|\condset{ h \in H }{\gamma \in \Gamma(h)}| &\cdot |\condset{\delta \in
 U^{[n]}}{\delta \sim \alpha}| \\
&= \sum_{\condset{\delta \in
 U^{[n]}}{ \delta \sim \alpha}} |\condset{h \in
 H}{\delta^{-1} \in \Gamma(h)}|\\
&= \sum_{h \in H} \sum_{\condset{\delta \in
U^{[n]}}{ \delta \sim \alpha}} |\set{\delta^{-1} \in \Gamma(h)}| \\
&= \sum_{h \in H} \sum_{\beta \in A_h} \sum_{\condset{\delta \in
U^{[n]}}{ \delta \sim \alpha \wedge \delta \sim \beta}}
|\set{\delta^{-1} \in \Gamma(h)}| \\
&= \sum_{h \in H} \sum_{\beta \in A_h} |\set{\beta \in \EV{h}}| \cdot
|\condset{\delta \in
U^{[n]}}{ \delta \sim \alpha \wedge \delta \sim \beta}| \\
\end{aligned}
\end{equation}
where the first equality follows from Claim~\ref{claim.gamma}
Part~\ref{claim.gamma.ii}, the second by linearity of addition (note
that $|\set{\delta^{-1} \in \Gamma(h)}| \in \set{0,1}$), the third by
the definitions of $\sim$ and $A_h$, and the fourth by the definition of
$\EV{h}$.  Observing that $|\condset{\delta \in
U^{[n]}}{ \delta \sim \alpha \wedge \delta \sim \beta}| /
|\condset{\delta \in U^{[n]}}{ \delta \sim \alpha}| = \frac{1}{|A_h|}$,
we conclude that
$$|\condset{ h \in H }{\gamma \in \Gamma(h)}| = \sum_{h \in
H} \sum_{\condset{\beta \in
U^\spt{h}}{\beta \sim \alpha}} \frac{|\set{\beta \in \EV{h}}|}{|A_h|}
= \sum_{h\in H} \frac{|A_h \cap \EV{h}|}{|A_h|}.$$
\end{proof}
Note that implicit in the claim is that the r.h.s.\ side of \eqref{eqn.ev}
is integral.

Since $[n]$ is linearly ordered, $X \subseteq [n]$ inherits this order and
we write $\vec{X}$ for the ordered $|X|$-tuple consisting of the elements of
$X$ in the inherited order.  For $\alpha \in U^X$ we write
$\vec{\alpha} \in U^{\vec{X}}$ to indicate the tuple
$\alpha(\vec{X})$.  Observe that this transformation is invertible.
This allows us to succinctly encode such injective functions as tuples
over $U$ and, further, to write relational analogs of the sets of
injective functions we considered before, e.g.,
$\oEV{g} := \condset{\vec{\alpha}}{\alpha \in \EV{g}}.$ Using
Claim~\ref{claim.ev} is it easy to recursively define $\oEV{g}$ over
$C_n$.

\begin{itemize}
\item
Let $g$ be a constant input gate, then $\spt{g}$ is empty.  If
$\Sigma(g) = 0$, then $\Gamma(g) = \emptyset$ and $\oEV{g}
= \emptyset$.  Otherwise $\Sigma(g) = 1$, then $\Gamma(g)$ is all
bijections and $\oEV{g} = \set{\tup{}}$, i.e., the set containing
the empty tuple.
\item
Let $g$ be a relational gate with $\Sigma(g) = R \in \tau$, then
$\spt{g}$ is the set of elements in the tuple $\Lambda_R(g)$.  By
definition we have $\oEV{g} = \condset{\vec{\alpha} \in
U^{\ospt{g}}}{\alpha (\Lambda_R(g)) \in R^\ensuremath{\mathcal{A}}\xspace}$.
\item
Let $\Sigma(g) = \text{AND}$ and consider $\vec{\alpha} \in
 U^\ospt{g}$.  By Claim~\ref{claim.ev},
 $\vec{\alpha} \in \oEV{g}$ iff $\vec{A_h} = \oEV{h}$
 for \emph{every} child $h$ of $g$, i.e., for \emph{every} child $h$
 and \emph{every} $\beta \in U^\spt{h}$ with $\alpha \sim \beta$, we
 have $\vec{\beta} \in \oEV{h}$.
\item
Let $\Sigma(g) = \text{OR}$ and consider $\vec{\alpha} \in
U^\ospt{g}$.  By Claim~\ref{claim.ev}, $\vec{\alpha} \in \oEV{g}$
iff there is a child $h$ of $g$ where $\vec{A_h} \cap \oEV{h}$ is
non-empty, i.e., for \emph{some} child $h$ of $g$ and \emph{some}
$\beta \in U^\spt{h}$ with $\alpha \sim \beta$, we have
$\vec{\beta} \in \oEV{h}$.
\item
Let $\Sigma(g) = \text{NOT}$ and consider $\vec{\alpha} \in
U^\ospt{g}$.  The gate $g$ has exactly one child $h$.
Claim~\ref{claim.ev} implies that $\vec{\alpha} \in \oEV{g}$ iff
$\vec{A_h} \neq \oEV{h}$, i.e., for \emph{some} $\beta \in
U^\spt{h}$ with $\alpha \sim \beta$, we have
$\vec{\beta} \not\in \oEV{h}$.
\item
Let $\Sigma(g) = \text{MAJ}$ and consider $\vec{\alpha} \in
U^\ospt{g}$.  Let $H$ be the set of children of $g$ and let
$A_h := \condset{ \beta \in U^{\spt{h}}}{\beta\sim\alpha}$.  Then
Claim~\ref{claim.ev} implies that $\vec{\alpha} \in \oEV{g}$ if,
and only if,
\begin{equation}\label{eqn:maj-gate}
\hfill
\sum_{h \in H}
\frac{| \vec{A_h} \cap \oEV{h} |}{|\vec{A_h}|} \ge \frac{|H|}{2}.
\hfill
\end{equation}
\end{itemize}
From $\oEV{}$ we can recover the $q$-ary query $Q$ computed by
$C_n$ on the input structure $\str{A}$ because the support of an output gate $g$ is exactly
the set of elements in the marking of $g$ by
$\Lambda_\Omega$.  In particular:
 $$Q = \condset{\bar a \in U^q}{\exists g \in
G, \vec\alpha \in \oEV{g}\text{ such that
} \Lambda_\Omega(\alpha^{-1}(\bar a)) = g}.$$ For Boolean properties $q
= 0$, and $Q = \set{\tup{}}$ indicates that $\str{A}$ has the property and
$Q = \emptyset$ indicates that it does not.

\subsection{Translating to Formulas of $\ensuremath{\mathrm{FP}}\xspace$}\label{subsec:formulas}

Let $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ be a $\ensuremath{\mathrm{P}}\xspace$-uniform family of symmetric
$(\mathbb{B},\tau)$ circuits, where $\mathbb{B}$ is either $\B_{\mathrm{std}}$ or $\B_{\mathrm{maj}}$.  Our aim is
to show that there is a formula $Q$ of $\ensuremath{\mathrm{FP}}\xspace$, or $\ensuremath{\mathrm{FPC}}\xspace$ in the
case of $\B_{\mathrm{maj}}$, in the vocabulary $\tau\uplus \set{\le}$ such that for
any $n$ and $\tau$-structure $\str{A}$ over a universe $U$ with
$|U|=n$, the $q$-ary query defined by $C_n$ on input $\str{A}$ is
defined by the formula $Q$ when interpreted in the structure
$\str{A}^\le := \str{A} \uplus \tup{[n],\le}$.

Since $\ensuremath{\mathcal{C}}\xspace$ is $\ensuremath{\mathrm{P}}\xspace$-uniform, by the Immerman-Vardi theorem and Lemma~\ref{lem:alg-rigid}, we have an
$\ensuremath{\mathrm{FP}}\xspace$ interpretation defining a rigid symmetric circuit equivalent to $C_n$---that we also call $C_n$---over the number sort of
$\str{A}^\le$, i.e., a sequence $\Phi :=
(\phi_G, \phi_W, \phi_\Omega,(\phi_s)_{s \in \mathbb{B} \uplus \tau \uplus \set{0,1}},
(\phi_{\Lambda_R})_{R\in \tau})$
of formulas of $\ensuremath{\mathrm{FP}}\xspace(\le)$ that define the circuit when interpreted in
$\tup{[n],\le}$.  Note that $C_n$ is defined over the universe
$[n]$.  Let $t$ be the arity of the interpretation, i.e., $\phi_G$
defines a $t$-ary relation $G \subseteq [n]^t$.  If $n$ is less than
$n_0$, the length threshold for applying the support theorem, $C_n$
can be trivially be evaluated by a $\ensuremath{\mathrm{FP}}\xspace$ formula which quantifies over
all (constantly-many) bijections from the point sort of $\str{A}^\le$
to the number sort of $\str{A}^\le$ and then directly evaluates the
circuit with respect to the bijection.  Thus we only need to consider
the case when $n \ge n_0$, and are able to use the recursive
construction of $\oEV{}$ from the last subsection along with a
constant bound $k$ on the size of the gate supports in $C_n$.

A small technical difficulty arises from the fact that we want to
define the relation $\oEV{g}$ inductively, but these are actually
relations of varying arities, depending on the size of $\spt{g}$.  For
the sake of a uniform definition, we extend $\oEV{g}$ to a $k$-ary
relation for all $g$ by padding it with all possible values to obtain
tuples of length $k$.  If $|\spt{g}| = \ell$, define $\tEV{g} =
\condset{(a_1\cdots a_k)}{(a_1\cdots a_\ell) \in \oEV{g} \mbox{ and } a_i
  \neq a_j \mbox{ for } i \neq j}$.

Define the relation $V \subseteq [n]^t \times U^k$ by $V(g,\bar a)$ if, and
only if, $\bar a \in \tEV{g}$.  Our aim is to show that the relation $V$ is
definable by a formula of $\ensuremath{\mathrm{FP}}\xspace$.  Throughout this subsection we use $\mu$ and $\nu$ to indicate $t$-tuples of number variables which denote gate indexes in $[n]^t$, and use the $k$-tuples of point variables $\bar x = (x_1,\ldots,x_k)$ and $\bar y = (y_1,\ldots, y_k)$ to denote injective functions that have been turned into tuples and then padded.

By Lemma~\ref{lem:alg-sym} and invoking the Immerman-Vardi theorem again,
we have a formula $\textsc{supp}$ such that $\tup{[n],\le} \models \textsc{supp}[g,u]$ if,
and only if, $\tup{[n],\le} \models \phi_G[g]$ (i.e., $g$ is a gate of $C_n$
as defined by the interpretation $\Phi$) and $u$ is in $\spt{g}$.
We use $\textsc{supp}$ to define some additional auxiliary formulas.
First we define, for each $i$ with $1 \leq i \leq k$ a
formula $\textsc{supp}_i$ such that  $\tup{[n],\le} \models \textsc{supp}_i[g,u]$ if, and
only if, $u$ is the $i^{th}$ element of $\ospt{g}$.
These formulas can be defined inductively as follows, where $\eta$ is a number variable
$$
\begin{array}{rcl}
\textsc{supp}_1(\mu,\eta) & := & \textsc{supp}(\mu,\eta) \land \forall \chi (\chi < \eta) \rightarrow \neg\textsc{supp}(\mu,\chi) \\
\textsc{supp}_{i+1}(\mu,\eta) & := &  \textsc{supp}(\mu,\eta) \land \exists \chi_1
(\chi_1 < \eta \land \textsc{supp}_i(\mu,\chi_1) \\
& &~~~~~~~~~~~~~~~~~~~~~~~\land \forall \chi_2 [(\chi_1
< \chi_2 < \eta) \rightarrow \neg\textsc{supp}(\mu,\chi_2)]) .
\end{array}
$$

We now define a formula $\textsc{agree}(\mu,\nu,\bar{x},\bar{y})$
so that for a structure $\str{A}$,
$\str{A}^{\leq} \models \textsc{agree}[g,h,\bar{a},\bar{b}]$ if, and only if,
$\alpha \sim \beta$ for $\vec\alpha \in U^\ospt{g}$, $\vec\beta \in U^\ospt{h}$ that
are the restrictions of the
$k$-tuples $\bar{a}$ and $\bar{b}$ to the length of $\ospt{g}$ and
$\ospt{h}$ respectively.
$$
\begin{array}{rcl@{}l}
\textsc{agree}(\mu,\nu,\bar{x},\bar{y}) & := &
\displaystyle \bigwedge_{1\leq i,j, \leq k} & (\forall \eta
(\textsc{supp}_i(\mu,\eta) \land \textsc{supp}_j(\nu,\eta)) \rightarrow x_i = y_j) \land \\
& & & (\forall \eta_1 \eta_2 (\textsc{supp}_i(\mu,\eta_1) \land \textsc{supp}_j(\nu,\eta_2) \land
x_i = y_j) \rightarrow \eta_1 = \eta_2)
\end{array}
$$

With these, we now define a series of formulas
$(\theta_s)_{s \in \mathbb{B} \uplus \tau \uplus \set{0,1}}(\mu,x)$
corresponding to the various cases of the construction of the relation
$\oEV{g}$ from Section~\ref{subsec:evaluate}.  In these, $V$ is a relational variable for the relation
being inductively defined.
$$
\begin{array}{rcl@{}l}
\theta_0(\mu,\bar{x}) & := & \text{false} \\
\theta_1(\mu,\bar{x}) & := & \displaystyle \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \\
\theta_R(\mu,\bar{x}) & := & \displaystyle  \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \land  \exists z_1\cdots z_r \exists \eta_1\cdots \eta_r
R(z_1,\ldots,z_r) \land \phi_{\Lambda_R}(\mu,\eta) \land \\
& & \hspace{23ex} \displaystyle \bigwedge_{1\leq i \leq r
} \bigwedge_{1\leq j \leq k } (\textsc{supp}_j(\mu,\eta_i) \rightarrow z_i = x_j) \\
\theta_{\text{OR}}(\mu,\bar{x}) & := & \displaystyle  \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \land \exists \nu \exists \bar{y}
(W(\nu,\mu) \land \textsc{agree}(\mu,\nu,\bar{x},\bar{y})) \land V(\nu,\bar{y})) \\
\theta_{\text{AND}}(\mu,\bar{x}) & := & \displaystyle  \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \land \forall \nu \forall \bar{y}
(W(\nu,\mu) \land \textsc{agree}(\mu,\nu,\bar{x},\bar{y})) \rightarrow V(\nu,\bar{y})) \\
\theta_{\text{NOT}}(\mu,\bar{x}) & := & \displaystyle  \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \land \forall \nu \forall \bar{y}
(W(\nu,\mu) \land \textsc{agree}(\mu,\nu,\bar{x},\bar{y})) \rightarrow \neg V(\nu,\bar{y}))
\end{array}
$$

To define $\theta_{\text{MAJ}}$ we start with some observations.  We
wish to formalise Equation~\ref{eqn:maj-gate}, but there are a few
complications.  The relation $k$-ary $\tEV{h}$ we are defining
inductively is the result of padding $\oEV{h}$ with all tuples of
$k-|\spt{h}|$ distinct elements.  Thus the number of elements in
$\tEV{h}$ is $|\oEV{h}|\cdot\frac{(n-|\spt{h}|)!}{(n-k)!}$.  Similarly,
for any fixed $g$, $h$ and $\bar a$, if we write $\bar{A}_h$ for the set of
tuples $\bar b$ satisfying $\textsc{agree}(g,h,\bar a,\bar b)$, then $|\bar{A}_h| =
|\vec A_h|\cdot\frac{(n-|\spt{h}|)!}{(n-k)!}$.  Finally, the tuples in
$\bar{A}_h \cap \tEV{h}$ are exactly those obtained by padding tuples
in $\vec A_h \cap \oEV{h}$ to length $k$ and there are therefore
$|\vec A_h \cap \oEV{h}|\cdot\frac{(n-|\spt{h}|)!}{(n-k)!}$ many of these.
Thus,
$\frac{|\vec A_h \cap \oEV{h}|}{|\vec A_h|} = \frac{| \bar{A}_h \cap \tEV{h}|}{|\bar{A}_h|}$ and it suffices to compute the latter.
Observe that $|\vec A_h|$ and $|\bar{A}_h|$ are completely determined by $|\spt{g}|$, $|\spt{h}|$ and
$|\spt{g} \cap \spt{h}|$.
We avoid dealing explicitly with fractions by noting that for any gate
$h$, the sum $\sum_{h' \in \mathrm{Orb}(h)}
\frac{| \vec{A}_{h'} \cap \oEV{h'} |}{|\vec{A}_{h'}|}$ is an integer
(by an argument analogous to Claim~\ref{claim.ev}).  Since
$|\bar{A}_{h'}|$ is the same for all $h' \in \mathrm{Orb}(h)$, it suffices to
compute the sum of $| \bar{A}_{h'} \cap \tEV{h'} |$ for all $h'$ with a fixed
size of  $|\bar{A}_h|$ and then divide the sum by  $|\bar{A}_h|$.
This is what we use to compute the sum on the l.h.s.\ of
Equation~\ref{eqn:maj-gate}.

For any fixed $i$ and $j$ with $0 \leq i \leq  j \leq k$, define the
formula $\textsc{overlap}_{ij}(\mu,\nu)$
so that
$\str{A}^{\leq} \models \textsc{overlap}_{ij}[g,h]$ iff $|\spt{h}| = j$ and
$|\spt{g}\cap\spt{h}| = i$.  This formula can be defined in $\ensuremath{\mathrm{FO}}\xspace$.

Using $k$-tuples of number variables in $\ensuremath{\mathrm{FPC}}\xspace$ we can represent
natural numbers less than $n^k$.  We assume, without giving detailed construction
of the formulas involved, that we can define arithmetic operations on
these numbers.  In particular, we assume we have for each $i,j$ as
above a formula
$\textsc{asize}_{ij}(\mu,\xi)$, with $\xi$ a
$k$-tuple of number variables, such that
$\str{A}^{\leq} \models \textsc{asize}_{ij}[g,e]$ iff $e = |\bar{A}_h|$ for
any gate $h$ with  $|\spt{h}| = j$ and $|\spt{g}\cap\spt{h}| = i$.

Using this, we define the formula $\textsc{num}_{ij}(\mu,\bar{x},\xi)$, with $\xi$ a $k$-tuple of
number variables,
so that
$\str{A}^{\leq} \models \textsc{num}_{ij}[g,\bar a,e]$ iff $e$ is the
number of gates $h$ with $\str{A}^{\leq} \models \textsc{overlap}_{ij}[g,h]$ which
are made true by some bijection
that assigns the tuple $\bar a$ to
$\spt{g}$.  This formula is given by
$$
\begin{array}{rcll}
\textsc{num}_{ij}(\mu,\bar{x},\xi) & := &
\exists \xi_1 \xi_2 & \textsc{asize}_{ij}(\mu,\xi_1) \land \\
& & & \xi_2 = \#_{\nu \bar y}(W(\nu,\mu) \land \textsc{overlap}_{ij}(\mu,\nu) \land
V(\nu,\bar{y}) \land \textsc{agree}(\mu,\nu,\bar{x},\bar{y}) ) \land \\
& & & \xi \cdot \xi_1 = \xi_2.
\end{array}
$$
Now we can define the required formula $\theta_{\text{MAJ}}$ by
$$
\theta_{\text{MAJ}}(\mu,\bar{x}) := \displaystyle  \bigwedge_{1\leq i<j \leq k}
x_i \neq x_j \land \exists \xi (2\cdot \xi \geq
\#_{\nu} W(\nu,\mu)) \land \xi = \sum_{0\leq
i \leq j \leq k} \condset{\xi'}{\textsc{num}_{ij}(\mu,\bar{x},\xi')},
$$
where the sum inside the formula is to be understood as shorthand
for taking the sum over the bounded number of possible values of $i$
and $j$.

Now, we can define the relation $V \subseteq [n]^t \times U^k$ given by
$V(g,\bar a)$ if, and only if, $\bar a \in \tEV{g}$ by the following formula
$$
\theta(\mu,\bar x) := [\ensuremath{\mathrm{ifp}}_{V,\nu \bar y} \displaystyle \bigvee_{s \in  \mathbb{B} \uplus \tau \uplus \set{0,1}}
(\phi_s(\mu) \land \theta_s(\nu,\bar y))](\mu,\bar x).
$$
The overall $q$-ary output query computed by the circuit is
given by the following formula derived from final the construction in the
last subsection
\begin{equation}
\begin{aligned}
Q(z_1,\ldots,z_q) &:= \exists \mu\bar x \nu_1 \cdots \nu_q \eta_1 \cdots \eta_k
[ \theta(\mu, \bar x) \wedge \phi_\Omega(\nu_1,\ldots,\nu_q, \mu) \wedge \\
& \hspace{23ex} \bigwedge_{1 \le i \le
k} (\textsc{supp}_i(\mu,\eta_i) \vee \forall \eta [\neg \textsc{supp}_i(\mu,\eta)]) \wedge \\
& \hspace{23ex} \bigwedge_{1 \le i \le k} \bigwedge_{1 \le j \le q}
([\textsc{supp}_i(\mu,\eta_i) \wedge x_i = z_j] \rightarrow \nu_j
= \eta_i) \wedge \\
& \hspace{23ex}\bigwedge_{1 \le j \le q} \bigvee_{1 \le i \le k} (x_i =
z_j \wedge \textsc{supp}_i(\mu,\eta_i))]
\end{aligned}
\end{equation}
where the purpose of the last three lines is to invert the injective
function encoded in $\bar x$ and then apply it to $z_i$ to produce
$\nu_i$; in particular: the second line puts the ordered support of
$\mu$ into $\eta_1,\ldots,\eta_k$, the third line defines the map from
$z_i$ to $\nu_i$, and the fourth line insures that this map covered all
coordinates of $z_i$.

Note that this is a formula of $\ensuremath{\mathrm{FP}+\mathrm{\le}}\xspace$ if $\mathbb{B}$ is the standard basis
and a formula of $\ensuremath{\mathrm{FPC}}\xspace$ if $\mathbb{B}$ is the majority basis.
Moreover, if the family $\ensuremath{\mathcal{C}}\xspace = (C_n)_{n \in \ensuremath{\mathbb{N}}\xspace}$ of symmetric circuits
is not $\ensuremath{\mathrm{P}}\xspace$-uniform, but given by an advice function $\Upsilon$, the
construction gives us an equivalent formula of $\ensuremath{\mathrm{FP}+\Upsilon}\xspace$ (for the
standard basis) or $\ensuremath{\mathrm{FPC}+\Upsilon}\xspace$ (for the majority basis).  This may be
formalised as follows.
\begin{lemma}\label{lem:main}~
\begin{enumerate}
\item
Any relational query defined by a $\ensuremath{\mathrm{P}}\xspace$-uniform family
of circuits over the standard basis is definable in $\ensuremath{\mathrm{FP}+\mathrm{\le}}\xspace$.
\item
Any relational query defined by a $\ensuremath{\mathrm{P}}\xspace$-uniform family
of circuits over the majority basis is definable in $\ensuremath{\mathrm{FPC}}\xspace$.
\item
Any relational query defined by a $\ensuremath{\PT/\poly}\xspace$-uniform family
of circuits over the standard basis is definable in $\ensuremath{\mathrm{FP}+\Upsilon}\xspace$, for some advice function $\Upsilon$.
\end{enumerate}
\end{lemma}

redpajama_set_name: RedPajamaArXiv


text:
TVS Motor records highest-ever revenue, profit, 2W exports in Q1 FY2023
Revenue of Rs 6,009 crore is up 53%, net profit up 500% to Rs 321 crore; TVS also recorded its best-ever two-wheeler exports of 295,690 units in the April-June quarter.
By Ajit Dalvi 28 Jul 2022 6542 Views Share -
TVS Motor Company is on a roll. The Chennai-based two- and three-wheeler manufacturer has reported operating revenue of Rs 6,009 crore for the April-June 2022 quarter, which constitutes 53% year-on-year growth (Q1 FY2022: Rs 3,934 crore). EBITDA of Rs 599 crore in Q1 FY2023 is a 118% increase (Q1 FY2022: Rs 274 crore), while profit after tax has zoomed 500% to Rs 321 crore versus Rs 53 crore in Q1 FY2022.
The first three months of the current fiscal saw TVS clock total sales of 907,000 units (including exports), up 38% (Q1 FY2022: 658,000). Motorcycle sales comprised 434,000 units, up 7% Q1 FY2022: 405,000), while scooter sales catapulted 121% to 306,000 units (Q1 FY2022:138,000).
TVS recorded its best-ever two-wheeler exports in this quarter – 296,000 units. Three-wheeler sales were up 18% to 46,000 units. The TVS iQube electric scooter sold 8,724 units, up 822% YoY on a low year-ago base of 946 units but also reflecting the growing demand for electric scooters.
The first quarter saw TVS launch three new variants of the iQube EV with an increased range of 140km on a single charge (pictured below). The refreshed iQube, which is presently available in 33 cities, is slated to reach 52 more cities within India.
Another scooter variant launch was the NTorq XT with a hybrid TFT console and over 60 hi-tech features.
Tags: TVS Motor Co

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: TypeError: __init__() got an unexpected keyword argument 'average' When running the following code, I receive the error TypeError: __init__() got an unexpected keyword argument 'average'
What am I doing wrong?
from sklearn.model_selection import GridSearchCV

X_train, X_holdout, y_train, y_holdout = train_test_split(X, y, test_size=0.3, random_state=17)

tree = DecisionTreeClassifier(random_state=17)

tree_params = {'max_depth': range(1,5), 'max_features': range(3,6), 'criterion': ['gini','entropy']}

tree_grid = GridSearchCV(tree, tree_params, cv=scoring='recall',average='macro')

tree_grid.fit(X_train, y_train)

A: The GridSearchCV class does not have a average parameter - you use it in average='macro'.
Have a look at the documentation of the class please:
class sklearn.model_selection.GridSearchCV(estimator, param_grid, *, scoring=None, n_jobs=None, iid='deprecated', refit=True, cv=None, verbose=0, pre_dispatch='2*n_jobs', error_score=nan, return_train_score=False)

redpajama_set_name: RedPajamaStackExchange


Manage food from farm to fork by running core business processes along the entire agribusiness value chain more efficiently with SAP solutions.
of the potential market for drones in the near term is expected to be in agriculture.
Digital agribusiness is real and it's here to stay. Digitisation in the agribusiness sector significantly increases the ability to feed the rapidly growing world population in a sustainable way.
billion is the expected value of the market for agricultural robots by 2020.
per-year growth in the precision agriculture market, reaching US$3.7 billion by 2018.
Build a sustainable and fully traceable agriculture supply chain. Designed for agribusiness companies, this supply chain management software connects smallholder farmers to the agricultural value chain – and offers full transparency into the source of your raw materials.
Take advantage of flexible, comprehensive contract support for your agricultural commodities. Control and track all expenses related to individual deals, consolidate complex settlements, and take advantage of automated processing with configurable business rules.
Discover how Cargill was able to develop a digitalized supply chain that supports its commitment to helping the world thrive.
Find out how Royal Swaziland Sugar Corporation responsibly reduces operational costs so it can better contribute to its community.
See how Kalangala Palm Oil Growers Trust uses the Intelligent Enterprise to improve processes and keep local farmers and buyers connected.
Find out how digitisation is the next big thing for agribusiness companies. It will increase farming efficiency and create a transparent and sustainable food supply chain.
See how technology can make farming processes more efficient and precise to meet the growing demand for food as global populations rise.
Learn why public-private partnerships are key to deploying the IoT in agriculture, transportation, housing services, and retail across rural and urban markets.
Learn about the three key areas that agrichemical manufacturers can utilise dynamic digital tools and mitigate risks.
Stay up to date on the latest trends, innovations, and solutions by joining other consumer products stakeholders to learn and share insights through blogs, discussions, and networking. Find out how SAP can help your consumer products business embrace the digital transformation.


text:
Pterulon je organsko jedinjenje, koje sadrži 13 atoma ugljenika i ima molekulsku masu od 234,678 -{Da}-.

Osobine

Reference

Literatura

Spoljašnje veze

Ароматични кетони
Органохлориди

redpajama_set_name: RedPajamaWikipedia


j-labs sp.z o.o. | CyberForum e.V.
We are software specialists who build specific software in JAVA and .NET based on your idea.
We follow the values and principles expressed in the Agile Manifesto.
We offer dedicated development teams which could support your software development needs in agile nearshoring model. We provide services based on flexibility&simplicity like also full transparency.
ABB, Akamai, HSBC, Oracle, Sabre, Samsung, Statoil – CircleK.
We are active member of development community.


text:
Professor Dame Jessica Rawson DBE FBA
Honorary Fellow, Warden 1994–2010
Professor Dame Jessica Rawson was Merton's first female Warden, serving for 16 years from 1994 to 2010. She was also Pro Vice-Chancellor of the University of Oxford from 2006 to 2011 and was appointed Professor of Chinese Art and Archaeology at Oxford in 2000.
Jessica read History at the University of Cambridge and then went on to the University of London, where she completed a further degree in Chinese Language and Literature. She began her career in the Civil Service as Assistant Principal at the Ministry of Health, before going on to the British Museum to serve over the years 1968-1994 as Assistant Keeper, Deputy Keeper, and finally, Keeper of the Department of Oriental Antiquities. During her time there, Professor Rawson was an integral part of the Museum, organising several inter-departmental exhibitions, including Chinese Ornament: The Lotus and the Dragon and Mysteries of Ancient China. She headed the renovation of the Sir Joseph Hotung Gallery of Oriental Antiquities, opened by Her Majesty The Queen in November 1992. Since moving to Oxford, she has remained involved in the life of the British Museum, taking part in a second renovation of the Hotung Gallery, which was re-opened by the Queen in 2017.
Professor Rawson's primary academic interests are in early China's history and material culture. She is today best known for her research on the interaction of the peoples of central China with those along the borders with northern Eurasia, which resulted in major innovations, such as the introduction of metallurgy to China. She has organised visits with Chinese colleagues to Mongolia, Siberia and Central Asia to explore these important developments. Jessica has presented her recent research as a Global Fellow at Peking University in 2017 and as an Academic Fellow at the China Academy of Art, Hangzhou from 2017 to 2019. From 2011 to 2016, she held a Leverhulme Trust grant for the project 'China and Inner Asia, 1000-200 BC: Interactions that Changed China'. Over the years, Jessica has worked extensively in academia and continues to do so, supervising graduate students at Oxford. She has also taught at the Universities of Cambridge, London and East Anglia, and has held visiting professorships at the universities of Heidelberg and Chicago. For the academic year 2013-2014, she held the position of Slade Professor of Fine Art at Cambridge.
Jessica has been a member of a number of academic committees in Britain and around the world, especially in China. She has received many honours, including her appointment as a Fellow of the British Academy in 1990, her election as a member of the American Academy of Arts and Sciences in 2012, and her receipt in 2017 of the Charles Lang Freer Medal from the Freer Gallery, Smithsonian Institution. She was made an Honorary Fellow of Merton following the end of her Wardenship in 2010 and an Honorary Professor at Peking University in 2019. She has been recognised multiple times in the Queen's Honours lists. Professor Rawson received a CBE in 1994 and was awarded the title of Dame in 2002 for services to oriental studies.
Her time at Merton
Professor Rawson's Wardenship at Merton was very active. She strongly supported the College's academic achievements, nurturing the Tutorial System and raising funds for new teaching and research Fellowships. She oversaw several key refurbishments throughout the College, as well as the construction of new buildings, not least the Finlay Building and the much-celebrated TS Eliot Lecture Theatre. She also made sure that the cultural and spiritual life of the College continued to thrive with, for example, the creation of the Choral Foundation in 2008 and the publication of a study of the Chapel Glass. In 2007, toward the end of her Wardenship, Jessica launched the 750th Anniversary Campaign, which raised a staggering £30 million by 2014, ensuring that the excellence she sustained and expanded during her time as Warden continues. "All Merton's Wardens are part of its history but Jessica, I suspect, will be part of its legend," commented Professor Richard McCabe, Sub-Warden at the time, in a speech given at Professor Rawson's farewell dinner in Hall in July 2010. He went on to say: "she will be remembered not as the first female Warden but much more properly and appropriately as one of the great Wardens." It is hard to argue with that.
Read Professor Rawson's farewell feature in Postmaster & The Merton Record 2010
Thinking of the first day you walked through the Merton Lodge arch, what was your first impression?
Quiet.
The recitation of the College grace on the first evening in Hall, marking the beginning of every academic year.
I think of myself as an outsider.
What tips would you give your younger self to prepare for the career you've achieved?
Persistence despite opposition.
Beautiful and hidden.
A lecture by Professor Dame Jessica Rawson
Professor Rawson gave an online talk, part of our 40 Years Series of lectures, on Thursday 12 November 2020. Her subject was, 'What does China's past tell us about China today?'.


text:
Adnoc is world's fastest-growing major oil and gas brand
Abu Dhabi National Oil Company preserved its position as the top brand in the UAE for the fourth year in a…
Sheikh Khalifa issues new family business ownership governance law
UAE's President Sheikh Khalifa has approved a new family business ownership governance law, bolstering the sector's contribution to the economy and…
Qatar can't help Europe much if Russian gas is interrupted
According to three people familiar with the issue, Qatar would be unable to considerably increase natural gas supply to Europe if…
Abu Dhabi's Chimera Capital concludes second close of VC fund at $10bn
Chimera Capital, an Abu Dhabi asset management firm and part of Chimera Investments has completed the second closing of its Alpha…
Kuwait draft 2022-2023 budget sees deficit down 74%
Kuwait's finance ministry said on Monday that it has filed a draft budget for 2022-2023 with a projected deficit of 3.1…
Ford launches high-performance Bronco Raptor
Ford Motor Company (F.N) unveiled a Raptor variation of its Bronco SUV on Monday, adding a new high-priced vehicle to the…
Investcorp's real estate deal volume in US hit $4bn in 2021
Investcorp, the alternative asset manager with Mubadala Investment Company as its largest shareholder, completed $4 billion in real estate transactions in…
Philips expects summer recovery from supply chain woes
Philips (PHG.AS), a Dutch health technology firm, said on Monday that it expects sales to rebound quickly in the second half…
Dubai Duty Free expects $1.4bn in sales in 2022 as passenger traffic rebounds
Dubai Duty Free expects yearly revenues to rise 40% to Dh5.1 billion ($1.4 billion) in 2022, and it aims to rehire…
Gulf economies to grow faster in 2022, oil price fall biggest threat
According to a Reuters survey of analysts, the economies of the six-member Gulf Cooperation Council will expand at their quickest rates…
Since record high in November 2021, Bitcoin plummets to almost half its value
Bitcoin seems to have lost almost half of its value since its record high in November last year, while numerous economies…
Boulben withdraws from race for Orange CEO post -Figaro
According to Le Figaro, Verizon Chief Revenue Officer Frank Boulben has written to Orange's board of directors to withdraw from the…
PREV 1 2 3 4 … 161 NEXT


While visiting Pcbprototype.site, we may ask you to register and/or provide information that personally identifies you ("Personal Information") for the purpose of interacting with our website, including, as an example, when you place an order, request for quotation, or download material. Pcbprototype.site is dedicated to respecting your privacy and granting you with appropriate protection and management of any personally identifiable information you share with us.
Pcbprototype.site collects personal information which you provide to us. Personal Information means any information which may be used to identify an individual, including, but not limited to, a first and last name, a home or other physical address and an e-mail address or other contact information, whether at work or at home. If you do decide to give us this information, you are telling us that this information is both true and accurate. Also, you're telling us that you have the authorization to provide us with that information.
This information is utilized to guarantee a quick, efficient flow of products and services to you. We may also collect certain non-PII information (such as destination or site usage behavior) according to your use of Pcbprototype.site. We may use this information to display information that you find interesting and suppress information that you might find boring or annoying. For instance, we might show you search suggestions or part suggestions.
To help us debug problems with our software (rare as they are), we may collect some technical info from your web browser software (like Mozilla Firefox or I. E.), screen resolution and the site that referred you to us.
We are always striving to ensure your information remains safe. Once we receive your information, we use various security measures and procedures, taking into account industry standards, to try to protect the private information that you provide and to prevent unauthorized entry to that information.
We will do our utmost to protect your personal data. There are a number of general things we would also recommend that you do. Please help keep your account safe by using a strong password that includes characters instead of just letters. We will also encourage you not to use the same password across all or many of your online accounts. As emails, instant messaging, and similar means of communication are not encrypted, additionally, we would recommend not communicating any sensitive information through these means.


text:
FT.COM: Crisis panel delays report amid rancour
Posted on November 22, 2010 by Neil Garfield
http://www.ft.com/cms/s/0/92bbba26-f2a7-11df-8020-00144feab49a.html#ixzz15q6EE2wV
By Tom Braithwaite in Washington
Published: November 18 2010 00:17 | Last updated: November 18 2010 00:17
The Financial Crisis Inquiry Commission has delayed its report into the causes of the crisis amid rancour between members of the panel.
Set up by Congress as a version of the widely praised Pecora commission, which in the 1930s studied the causes of the Great Depression, the FCIC has told the White House it wants to delay publication of the report from December.
In depth: FCIC hearings – Jun-02
Bernanke regrets reticence on Lehman – Sep-02
FCIC blog: Bernanke faces crisis panel – Sep-02
Fuld criticises Fed for letting Lehman fail – Sep-02
Probe chief to issue Wall St data – Sep-01
Gillian Tett: Cautionary tale from Japan – Sep-02
"This is very basic – we believe that to ensure that the commission's investigation is properly completed and documented we need to deliver the report in January," Phil Angelides, FCIC chairman, told the Financial Times.
The FCIC has hauled before it financial figures ranging from Lloyd Blankfein, chief executive of Goldman Sachs, to Ben Bernanke, Federal Reserve chairman, producing some memorable moments and unearthing millions of pages of documents.
But the effectiveness of the investigation and whether all members of the FCIC will sign off on the final report when it is delivered in January is still in doubt.
In particular, Republican members have wanted more of a focus on the government's role in the crisis and are concerned that Mr Angelides, a Democratic appointee, is focusing too much on Wall Street's role, according to people familiar with the committee.
Some members argued that the FCIC did not have the power to extend its deadline without approval by Congress.
Some have argued that the panel is yet to get into substantive discussion on the causes of the crisis and say they do not believe that will happen.
"What's important is that the report be truthful and factual," said Mr Angelides. "It should be no surprise that 10 people with very different places in life will have disagreements."
He said the task was monumental. "It could go on for years because of the extent and nature of devastation that came to our financial system. The Wall Street firms have spent more on lawyers by leaps and bounds than our full budget but we have a lean and committed staff that's been working literally 15 hours a day."
In the last Washington hearing in September, Mr Bernanke said he should have been "more straightforward" with Congress when he avoided saying the central bank had no means to save Lehman Brothers. Dick Fuld, former chief executive of Lehman, said the Fed could and should have saved the bank.
Filed under: bubble, CDO, CORRUPTION, currency, Eviction, foreclosure, GTC | Honor, Investor, Mortgage, securities fraud |
« Rasmussen: Homeowners Still Show Little Confidence In Short-Term Housing Market Wall Street Pit: Gasparino on FCIC Delaying Report to Investigate Foreclosure Fraud »
Neva, on November 22, 2010 at 8:44 am said:
As usual, the money is talking, and the mega banks and Wall Street are getting away with it. Why have a commission to study anything if one can't get to the truth. I have another question: if you are an attorney representing Wall Street or a mega bank, don't you have a duty as an officer of the court, to represent the truth. If your client is lying under oath, don't you have a responsibility to remedy that? I know that under the Constitution everyone has a right to a defense, but if that defense is about lying, what then? http://www.challengingforeclosure.com Sirak@challengingforeclosure.com


No matter what electronic component you use, there is a way to mount it on your WorkBench.
If you are stuck for a graceful solution, please contact us. We will challenge our team of Makers/Engineers/Designers to develop a solution. Contact: Info@PhaseDock.com or post your challenge to the Phase Dock Forum.
We want you to succeed and your project to perform and look great!
Step 1: Assemble the Slide you need to the Click.
Step 2: Use M2.5 x 6mm machine screws to fasten electronics to the mounting bosses on the Arduino UNO, Raspberry Pi 2/3, or Feather/Particle Click/Slide assembly.
See Click-Slide Configurations Available Today if you are not sure which Slide to use.
Use the white tubular standoffs and self-tapping screws provided in the Hardware Packet.
Attach electronics directly to an appropriately sized Click by threading screws through the mounting hole in the electronics, through the tubular standoff and into the Click Platform. Screws may protrude slightly on the underside of the Click but this will not interfere with the functionality of the Click.
A power screwdriver makes assembly easier.
CAUTION: AVOID placing screws directly into the two spring corners of the Click (red X) as this may interfere with the spring action.
Use the breadboard mounting tape to stick directly to a 2x3 Click.
Use M2.5 male-female nylon or brass standoffs to layer electronics.
Another option to attach items that lack mounting holes, is to use zipties. Once the item is attached to a Click, you can easily mount it or reposition it on your project.
This is an easy way to secure your batteries to your project and charge them when needed — without having to move your entire project.
No need to chain your project to a wall outlet when you can easily attach a battery.
Neatly manage cables or wires.
Use the 8-32 x 7/16 machine screw and Nyloc nut to attach a cable-tie saddle mount (shown in white) using one of the smaller holes in the Base.
Attach to the top or the underside of the Base. Finish it off with a small ziptie or hook-and-loop tie.


text:
<?xml version="1.0" encoding="utf-8"?>
<resources>
    <dimen name="snacky_icon_padding">16dp</dimen>
</resources>

redpajama_set_name: RedPajamaGithub


text:
Marriott's Grande Vista is a Marriott Vacation Club resort, on International Drive in Orlando, Florida. The timeshare resort is the largest in the Marriott Vacation Club portfolio, with 1616 guest studios, and one-, two- and three-bedroom villas in 24 Mission-style buildings.

Resort Property
Situated on , Marriott's Grande Vista opened in March 1997. The resort opened along with the "Faldo Golf Institute," a nine-hole golf course and training center, located on property. Construction of the resort's remaining unbuilt villas, dubbed the "West Village," continued on through the 2000s and are currently complete (with the last buildings completed in 2006). The "West Village" also includes a new pool area and bar and grill restaurant called the Copa Loca Bar and Grill (opened in 2004).

The property is home to 24 buildings, four pool areas, several restaurants and bars, a convenience store dubbed "The Marketplace," a lake, fitness center and a spa built in the summer of 2009.

The Marriott Vacation Club's Headquarters is located on Westwood Boulevard about one mile away from the property. In 2009, the resort was awarded Green Lodging certification by the Florida Department of Environmental Protection. It has won Southeast/Caribbean Resort of the Year multiple times and was also named Marriott Vacation Club's Resort of the Year in 2003 and 2010.

References

External links

Resorts in Florida
Marriott hotels
Hotels in Orlando, Florida
Hotels established in 1997
Hotel buildings completed in 1997
1997 establishments in Florida