text:
\section{Introduction}
\vskip-13cm{\sl An extended abstract of this paper appears
in \emph{7th Algorithmic Number Theory Symposium (ANTS
VII)}, F.~Hess, S.~Pauli, and M.~Pohst, editors, LNCS 4076,
pp. 582--598, 2006. This is the full and corrected
version.}\vskip12cm One of the most important assumptions
in modern cryptography is the hardness of the discrete
logarithm problem (DLP). The scope of this paper is
restricted to groups of prime order $p$, where the DLP is
the problem of computing $x$ given $(g,g^x)$ for $x$ chosen
uniformly at random from $\mathbb{Z}_p$ (see the next section for
notation). In some groups the DLP is believed to have
average complexity of $\mathrm{\Theta}(\sqrt{p})$ group
operations. The \emph{constrained DLP} is defined as the
problem of computing $x$ given $(g,g^x)$ where $x$ is
chosen uniformly at random from a publicly known set
$S\subseteq\mathbb{Z}_p$.

For the standard DLP there is a well-understood dichotomy
between generic algorithms, which are oblivious to the
underlying group, and group-specific algorithms. By
analogy, we distinguish between generic and group-specific
algorithms for the constrained DLP. In this paper we
concentrate on the former kind, i.e., generic algorithms.
Our main tool for analysis of generic algorithms is the
Shoup-Nechaev generic group
model~\cite{shoup97-generic,Nechaev94}.

The main motivation of our work is the fundamental nature
of the problem and the tantalizing gap that exists between
lower and upper bounds on the constrained DLP. A trivial
generalization of Shoup's proof shows that the DLP
constrained to any set $S\subseteq \mathbb{Z}_p$ has generic
complexity $\mathrm{\Omega}(\sqrt{|S|})$ group operations. On the
other hand, Schnorr demonstrates that the DLP constrained
to a \emph{random} $S$ of size $\sqrt{p}$ has complexity
$\tilde \mathrm{\Theta}(\sqrt{p})=\tilde \mathrm{\Theta}(|S|)$ with
high probability~\cite{Schnorr01-hardcore}. \emph{Explicit}
(de-randomized) constructions or even succinct
representation of small sets with high complexity, or any
complexity better than the square root lower bound were
conspicuously absent.

The importance of improving the square root lower bound for
concrete subsets of $\mathbb{Z}_p$ is implicit
in~\cite{Yacobi98,HS03-sparse,SJ04-hash}, which suggest
exponentiation algorithms that are faster than average for
exponents sampled from certain subsets. These algorithms
either rely on heuristic assumptions of security of the DLP
constrained to their respective sets or use the square root
lower bound to the detriment of their efficiency. For
example, Yacobi proposes to use ``compressible'' exponents
whose binary representation contains repetitive
patterns~\cite{Yacobi98}, which can be exploited by some
algorithms for fast exponentiation. However, without
optimistic assumptions about the complexity of the DLP
constrained to this set the method offers no advantage over
the sliding window exponentiation. Another method of
speeding up exponentiation is to generate an exponent
together with a short addition chain for
it~\cite[Ch.~4.6.3]{knuth-vol2}. Absent reliable methods of
sampling addition chains with uniformly distributed last
elements, this approach depends on the hardness of the DLP
on a non-uniform distribution.

The main technical contribution of our work is the proof
that the DLP constrained to a set $S$, which is chosen from
an easily sampleable family of sets of cardinality
$p^{1/12-\varepsilon}$, has complexity $\mathrm{\Omega}(|S|^{3/5})$ with
probability $1-6p^{-12\varepsilon}$. At a higher level of
abstraction we develop combinatorial techniques to bound
the complexity of the constrained DLP, which is a global
property, using the set's local properties. We view our
work as a step towards better understanding the constrained
DLP and possibly designing fast exponentiation algorithms
tuned to work on exponents from ``secure" subsets.

The structure of the paper is as follows. In
Section~\ref{s:generic} we present a number of results
which are known but otherwise scattered in the literature.
In Sections~\ref{s:more} and~\ref{s:beyond} we give new
constructions of sets with provable lower bounds on various
families of algorithms for solving the constrained DLP.

\subsection{Notation}
We use the standard notation for asymptotic growth of
functions, where
\begin{align*}
O(g)&=\{f\colon \mathbb{N}\to\mathbb{R}^+\mid\exists
c,n_0>0\textrm{ s. t. } 0\leq f(n)\leq cg(n)\textrm{ for
all }n>n_0\};\\
\mathrm{\mathrm{\Omega}}(g)&=\{f\colon
\mathbb{N}\to\mathbb{R}^+\mid\exists c,n_0>0\textrm{ s. t.
} cg(n)\leq f(n)\textrm{ for all
}n>n_0\};\\
\mathrm{\Theta}(g)&=\{f\colon f=O(g) \textrm{ and }g=O(f)\};\\
\tilde O, \tilde\mathrm{\Omega}, \tilde \mathrm{\Theta}&\textrm{ ---
same as }O,\mathrm{\Omega},\mathrm{\Theta}\textrm{ with logarithmic factors ignored;}\\
\mathbb{Z}_p&\textrm{ --- the field of residues modulo prime
$p$;}\\
x\in_R S&\textrm{ --- $x$ chosen uniformly at random from
$S$.}
\end{align*}

\subsection{Previous work}

Algorithms for solving number-theoretic problems can be
grouped into two main classes: generic attacks, applicable
in any group, and specific attacks designed for particular
groups. The generic attacks on discrete logarithm include
the baby-step giant-step attack~\cite{Shanks71}, Pollard's
rho and lambda algorithms~\cite{Pollard78} as well as their
parallelized versions~\cite{OW99-dlog,Pollard00-kangaroos},
surveyed in~\cite{Teske01-survey}. The specific attacks
have sprouted into a field in their own right, surveyed
in~\cite{SWD96,Odlyzko00}.

A combinatorial view on generic attacks on the DLP was
first introduced by Schnorr~\cite{Schnorr01-hardcore}. He
suggested the concept of the generic DL-complexity of a
subset $S\subseteq \mathbb{Z}_p$ defined as the minimal number of
generic operations required to solve the DLP for any
element of $\{g^x\mid x\in S\}$. He showed that the generic
DL-complexity of random sets of size $m<\sqrt{p}$ is
$m/2+o(1)$. In part our work is an extension of Schnorr's
paper. The combinatorial approach to the DLP was further
advanced by~\cite{CLS03} which gave a characterization of
generic attacks on the entire group of prime order.

Systematically the constrained DLP has been studied for two
special cases: Exponents restricted to an interval and
exponents with low Hamming weight. Pollard's kangaroo
method has complexity proportional to the square root of
the size of the interval~\cite{Pollard00-kangaroos}. The
running time of a simple Las Vegas baby-step giant-step
attack on low-weight exponents is $O(\sqrt t{n/2\choose
t/2})$, where $n$ is the length and $t$ is the weight of
the exponent~\cite{heiman92} (for a deterministic version
see~\cite{Stinson02-bsgs}, which credits it to
Coppersmith). See~\cite{CLP05-bsgs} for cryptanalysis of a
similar scheme in a group of unknown order.

Erd\"os and D.~Newman studied the BSGS-1 complexity (in our
notation) and asked for constructions of sets with a high
(better than a random subset's) BSGS-1
complexity~\cite{EN77-bases}.

\subsection{Generic algorithms}

The generic group model introduced by Shoup and Nechaev
\cite{shoup97-generic,Nechaev94} provides access to a group
$G$ via a random injective mapping $\sigma:G\to\Sigma$,
which \emph{encodes} group elements. The group operation is
implemented as an oracle that on input $\langle \sigma(g),
\sigma(h),\alpha,\beta\rangle $ outputs $\sigma(g^\alpha
h^\beta)$ (for the sake of notation brevity we roll three
group operations, group multiplication, group inversion,
and group exponentiation, in one). Wlog, we restrict the
arguments of the queries issued by algorithms operating in
this model to encodings previously output by the oracle.

The discrete logarithm problem for groups of prime order has a
trivial formalization in the generic group model:
\begin{quote}
Given $p,\sigma(g),\sigma(g^x)$ where $g$ has order $p$ and
$x\in_R\mathbb{Z}_p$, find $x$.
\end{quote}

The proof sketch of the theorem below, which is essentially
the original one due to Shoup, is reproduced here because
it lays the ground for a systematic study of complexity of
algorithms in the generic group model.

\begin{theorem}[\cite{shoup97-generic}]\label{th:shoup}Let
$\mathcal{A}$ be a probabilistic algorithm and $m$ be the number of
queries made by $\mathcal{A}$. $\mathcal{A}$ solves the discrete logarithm
problem in a group of prime order $p$ with probability
$$
\Pr[\mathcal{A}(p,\sigma(g),\sigma(g^x))=x]<\frac{(m+2)^2}{2p}+\frac1p.
$$
The probability space is $x$, $\mathcal{A}$'s coin tosses, and the
random function $\sigma$.
\end{theorem}
\begin{proof}[sketch] Instead of letting $\mathcal{A}$ interact with a real
oracle, consider the following game played by a simulator.
The simulator keeps track of two lists of equal length
$L_1$ and $L_2$: the list of encodings
$\sigma_1$,\dots,$\sigma_t\in \Sigma$ and the list of
linear polynomials $a_1x+b_1$,\dots,$a_tx+b_t\in \mathbb{Z}_p[x]$.
Initially $L_1$ consists of two elements $\sigma_1$ and
$\sigma_2$, which are the two inputs of $\mathcal{A}$, and $L_2$
consists of $1$ and $x$. When $\mathcal{A}$ issues a query $\langle
\sigma_i,\sigma_j,\alpha,\beta\rangle$, the simulator
fetches the polynomials $a_ix+b_i$ and $a_jx+b_j$ from
$L_2$, computes $a=\alpha a_i+\beta a_j$ and $b=\alpha
b_i+\beta b_j$ and looks up $ax+b$ in $L_2$. If
$ax+b=a_kx+b_k$ for some $k$, the simulator returns
$\sigma_k$ as the answer to the query. Otherwise, the
simulator generates a new element
$\sigma_{t+1}\in_R\Sigma\setminus L_1$, appends
$\sigma_{t+1}$ to $L_1$ and $ax+b$ to $L_2$, and returns
$\sigma_{t+1}$.

$\mathcal{A}$ terminates by outputting some $y\in \mathbb{Z}_p$. The game
completes as follows:
\begin{enumerate}\setlength{\topsep}{0in}\setlength{\itemsep}{0ex}\setlength{\parskip}{0in}
\item The simulator randomly selects $x^*\in_R\mathbb{Z}_p$.

\item Compute $a_ix^*+b_i$ for all $i\leq m+2$. If
$a_ix^*+b_i=a_jx^*+b_j$ for some $i\neq j$, the simulator
fails.

\item $\mathcal{A}$ succeeds if and only if $x^*=y$.
\end{enumerate}
Observe that the game played by the simulator is
indistinguishable from the transcript of $\mathcal{A}$'s interaction
with the actual oracle unless the simulator fails in step
2. Since for any two distinct polynomials $a_ix+b_i$ and
$a_jx+b_j$ the probability that $a_ix^*+b_i=a_jx^*+b_j$ is
at most $1/p$, the probability that step 2 fails is at most
$(m+2)^2/{2p}$. Finally, we observe that the probability
that $\mathcal{A}$ wins the game in step 3 is exactly $1/p$, which
completes the proof.\hfill $\!\square$
\end{proof}

It follows from the proof that the probability of success
of any probabilistic adaptive algorithm for solving the
discrete logarithm in $\mathbb{Z}_p$ in the generic group model can
be computed given the list of the linear polynomials
induced by its queries. This observation leads us to the
concept of generic complexity defined in the next section.

\section{Generic Complexity}\label{s:generic}

\begin{definition}[Intersection set] For a set of pairs $L\subseteq \mathbb{Z}_p^2$, we define its \emph{intersection
set}
$$I(L)=\{x\in
\mathbb{Z}_p\mid \exists (a,b),(a',b')\in L\textrm{\ s.t.\ }
ax+b=a'x+b'\textrm{\ and\ }(a,b)\neq(a',b')\}.$$
\end{definition}

The set of pairs from the above definition corresponds to
the set of queries asked by the generic algorithm. Its
intersection set is the set of inputs on which the
simulator from the proof of Theorem~\ref{th:shoup} fails.

\begin{definition}[$L$ recognizes an $\alpha$-fraction of $S$] For $L\subseteq \mathbb{Z}_p^2$,
$S\subseteq \mathbb{Z}_p$, and $0<\alpha\leq 1$ we say that $L$
\emph{recognizes an $\alpha$-fraction of} the set $S$ if
$$|S\cap I(L)|\geq\alpha |S|.$$
\end{definition}

\begin{definition}[Generic complexity] The set $S\subseteq \mathbb{Z}_p$
is said to have \emph{generic $\alpha$-complexity} $m$
denoted as $\C{\alpha}(S)$ if $m$ is the smallest
cardinality of a set $L$ recognizing an $\alpha$-fraction
of $S$.
\end{definition}

Our definition of generic complexity is slightly different
from a similar concept of the generic DL-complexity put
forth by Schnorr. We only require that the intersection set
$I(L)$ covers a constant fraction of $S$ rather than the
entire set~\cite{Schnorr01-hardcore}. Our definition better
matches the standard practice of cryptanalysis, when an
attack is considered successful if it succeeds on a
nontrivial fraction of the inputs. Moreover, our bounds
exhibit different scaling behavior as a function of
$\alpha$, and by parametrizing the definition with $\alpha$
we make the dependency explicit.

\begin{proposition}[\cite{Schnorr01-hardcore}]\label{prop:twoineq}For any $S\subseteq \mathbb{Z}_p$ the generic $\alpha$-complexity of
the set $S$ is bounded as
$$
\sqrt{2\alpha|S|}< \C{\alpha}(S)\leq \alpha|S|/2+3.
$$
\end{proposition}
\begin{proof} The lower bound follows from the fact that for any
$L\subseteq \mathbb{Z}_p^2$ the cardinality of the intersection set
is bounded as $|I(L)|<|L|^2/2$. Therefore, in order to
cover at least an $\alpha$-fraction of the set, $|L|^2/2$
must be more than $\alpha|S|$.

The upper bound is attained by the following construction.
If $2m\geq \alpha|S|$ and $\{x_1,\dots,x_{2m}\}\subseteq
S$, then an $\alpha$-fraction of $S$ is recognized by $L$
of size $m+2$ defined as
$$
L=\left\{(0,0),(0,1),(\frac1{x_2-x_1},\frac{x_1}{x_1-x_2}),\dots,(\frac1{x_{2m}-x_{2m-1}},\frac{x_{2m-1}}{x_{2m-1}-x_{2m}})\right\},
$$
since $x_i$ and $x_{i-1}$ are the $x$-coordinates of the
points of intersection of the line
$(\frac1{x_i-x_{i-1}},\frac{x_{i-1}}{x_{i-1}-x_i})$ with
lines $y=0$ and $y=1$ respectively.\hfill $\!\square$
\end{proof}

\begin{proposition}\label{prop:C(Z_p)}$\sqrt {2\alpha p}<\C{\alpha}(\mathbb{Z}_p)\leq
2\lceil\sqrt{\alpha p}\rceil$.
\end{proposition}
\begin{proof}The lower bound on $\C{\alpha}(\mathbb{Z}_p)$ is by Proposition~\ref{prop:twoineq}.
The upper bound is given by the set $L=\{(0,i), (1,-\lambda
i)\mid 0\leq i< \lambda\}$, where $\lambda=\lceil
\sqrt{\alpha p}\rceil$. Indeed,
$$
I(L)=\bigcup_{0\leq i,j<\lambda} I(\{(0,i),(1,-\lambda
j)\}=\bigcup_{0\leq i,j<\lambda} \{\lambda j+i\},
$$
which covers $[0,\alpha p)$. \hfill $\!\square$
\end{proof}

A tighter (up to a constant factor) bound in the general
case and exact values for $\C{1}(\mathbb{Z}_p)$ for small primes
$p<100$ appear in~\cite{CLS03}.

Since the generic complexity is a monotone property, it
follows that for any set $S\subseteq \mathbb{Z}_p$
$$
\C{\alpha}(S)\leq \min({\alpha}|S|/2+3, 2\lceil\sqrt{\alpha
p}\rceil).
$$

Now we are ready to establish the connection between the generic
complexity of a set and the discrete logarithm problem.

\begin{theorem}Let $S\subseteq \mathbb{Z}_p$, $\mathcal{A}_S$ be a generic algorithm that makes $m<\C{\alpha}(S)$ queries
and outputs a number from $\mathbb{Z}_p$. Then its probability of
success is bounded as\footnote{This statement is stronger
than the one in the proceedings version.}
$$\Pr[\mathcal{A}_S(\sigma(g),\sigma(g^x))=x]<\alpha+\frac1{|S|},$$
where the probability is taken over $\mathcal{A}$'s random tape, the
oracle answers, and $x\in_R S$. The above bound is tight,
i.e., for any set $S$ there is a generic algorithm whose
query complexity is $\C{\alpha}(S)$ and probability of
success is at least $\alpha+1/|S|$.
\end{theorem}
\begin{proof}[sketch] The proof essentially follows that of
Theorem~\ref{th:shoup}. Let $L$ be a set of pairs
$(a_i,b_i)$ constructed by the simulator and $x^\ast\in_R
S$ be its choice for $x$. The adversary succeeds in two
cases: either $x^\ast$ belongs to the intersection set of
$L$ or $x^\ast$ is the output of $\mathcal{A}_S$. The first
probability is at most $|I(L)\cap S|/|S|< \alpha$ as long
as $m<\C{\alpha}(S)$, the second probability is exactly
$1/|S|$.

The tightness property follows from the definition of
generic complexity. Let $L$ be the set of pairs of size
$\C{\alpha}(S)$ so that $|S\cap I(L)|\geq \alpha|S|$. Query
the oracle $\langle \sigma(g^x),\sigma(g),a,b\rangle$ for
all pairs $(a,b)\in L$. With probability $|I(L)\cap S|/|S|$
there is a collision that gives away $x$, otherwise make a
guess that succeeds with probability $1/|S\setminus
I(L)|$.\hfill $\!\square$
\end{proof}

Notice that the theorem above is unconditional and the
adversary is computationally unbounded. In particular, the
adversary is given full access to $S$ and can design an
$S$-specific algorithm. As long as the algorithm has only
oracle access to the group, $\C{\alpha}(S)$ is a lower
bound on the number $m$ of oracle queries needed by the
algorithm to succeed with probability at least
${\alpha}+1/|S|$.

We know that $\C{\alpha}(S)$ can be negligible compared to
$|S|$ (for instance, according to
Proposition~\ref{prop:C(Z_p)}, when $S=\mathbb{Z}_p$, $|S|=p$ but
its generic complexity is $O(\sqrt p)$). Since the generic
complexity is intimately related to the query complexity of
any discrete logarithm-solving algorithm, we would like to
build sets with higher generic complexity. The next theorem
demonstrates that for a fixed $p$ a random set of size less
than $\sqrt p$ has a near-linear generic complexity.

\begin{theorem}\label{th:random}For a random subset $S\subseteq_R \mathbb{Z}_p$ of size
$p^\varepsilon$ for some constant $\varepsilon\leq 1/2$ its generic
${\alpha}$-complexity is at least
$$
\C{\alpha}(S)>\frac{\alpha |S|}{\ln p}
$$
with probability $1-1/p$ for large enough $p$.
\end{theorem}
\begin{proof} The proof is by a counting argument.
We shall bound the number of the sets $S$ of size $k=p^\varepsilon$
whose $\alpha$-fraction can be recognized by a set $L$ of
size $\delta k$, when $\varepsilon\leq 1/2$ and $\delta=\alpha/\ln
p$. Suppose $|L|=\delta k$ and $|I(L)\cap S|\geq \alpha k$,
where $S$ is to be constructed. There are ${p^2\choose
\delta k}$ subsets $L\subseteq \mathbb{Z}^2_p$ of size $\delta k$.
The intersection set $I(L)$ has size at most $(\delta k)^2$
and contains at least $\alpha k$ elements which belong to
$S$. There are thus at most $\binom{p^2}{\delta
k}\binom{(\delta k)^2}{\alpha k}$ distinct possibilities
for these $\alpha k$ elements. The $(1-\alpha)$-fraction of
$S$ can be chosen arbitrarily from $\mathbb{Z}_p$, in ${p\choose
(1-\alpha)k}$ many ways. In total the number of subsets $S$
of generic complexity $\delta k$ and cardinality $k$ is
bounded by ${p^2\choose \delta k}{(\delta k)^2\choose
{\alpha k}}{p\choose (1-\alpha)k}$. Using ${n\choose
k}<\left(ne/k\right)^k$ for any $0<k\leq n$ and
$x^{-x}<1.5$ for any $x>0$ we bound the product as
\begin{multline*}p^{2\delta k+(1-\alpha)k}\delta^{-\delta k+2\alpha
k}k^{-\delta k+2\alpha k-k}\alpha^{-\alpha
k}(1-\alpha)^{-(1-\alpha)k}e^{\delta k+k}<\\
\left[4p^{2\delta+(1-\alpha)}\delta^{2\alpha
}k^{-\delta+2\alpha-1}e^{\delta+1}\right]^k<\left[12p^{2\delta+(1-\alpha)}\delta^{2\alpha
}k^{-\delta+2\alpha-1}\right]^k.
\end{multline*}
We want this number to be less than a $1/p$-fraction of the
number of subsets of $\mathbb{Z}_p$ of size $k$, which is
$1/p{p\choose k}>1/p(p/k)^k$. By taking the $k$th root of
both numbers and substituting $k=p^\varepsilon$, we arrive at the
following inequality:
$$
12\delta^{2\alpha}p^{2\delta+(1-\alpha)+\varepsilon(-\delta+2\alpha-1)+p^{-\varepsilon}}<p^{1-\varepsilon}.
$$
Notice that the inequality holds for $\delta <
\alpha(1-2\varepsilon)$ if $\varepsilon<1/2$ and for $\delta<\alpha/\ln p$ if
$\varepsilon=1/2$. When $\varepsilon$ is constant and $p$ is large enough,
$\delta=\alpha/\ln p<\alpha(1-2\varepsilon)$.\hfill $\!\square$
\end{proof}

The bottom line of the theorem we just proved is that hard
sets (where the discrete logarithm is hard to compute using
a generic algorithm) are easy to come by. In fact, almost
any set has high generic complexity (also previously
observed in~\cite{Schnorr01-hardcore}).

In what follows we sharply lower the amount of randomness
that is required to provide any non-trivial guarantee of
generic complexity.

\section{More complexities and lower bounds}\label{s:more}

Many sets of group elements with special properties may be
attacked using a baby-step giant-step method. In this
method the attacker first computes
$g^{c_1}$,\dots,$g^{c_m}$ (giant steps) and then compares
them against $g^{a_1x+b_1}$,\dots,$g^{a_mx+b_m}$ (baby
steps). Any collision between a baby step and a giant step
gives away $x$. We define the complexity of this method
along the lines of the generic complexity from the previous
section.

\begin{definition}[Intersection set-2] For a set of pairs $L\subseteq \mathbb{Z}_p^2$
and a set of points $C\subseteq\mathbb{Z}_p$, we define their
\emph{intersection set} as
$$
I(L,C)=\{x\in \mathbb{Z}_p\mid \exists (a,b)\in L, c\in C\textrm{\
s.t.\ }a\neq 0\textrm{\ and\ }ax+b=c\}.
$$
\end{definition}

\begin{definition}[Baby-step giant-step complexity.] The set $S\subseteq \mathbb{Z}_p$
is said to have the \emph{baby-step giant-step
$\alpha$-complexity} (BSGS complexity for short) $m$
denoted as $\Cbsgs{\alpha}(S)$ if $m$ is the smallest
integer such that there exist $L\subseteq \mathbb{Z}_p^2$ and
$C\subseteq\mathbb{Z}_p$, with $|L|=|C|=m$ and $|I(L,C)\cap
S|\geq\alpha |S|$.
\end{definition}

An important particular case of the baby-step giant-step method is
when all lines defined by $L$ are parallel (i.e., all $a_i=1$).

\begin{definition}[BSGS-1 complexity] The set $S\subseteq \mathbb{Z}_p$
has \emph{BSGS-1 $\alpha$-complexity} $m$ denoted as
$\Cbsgsone\alpha(S)$ if $m$ is the smallest integer such
that there exist $L\subseteq \{1\}\times \mathbb{Z}_p$ and
$C\subseteq\mathbb{Z}_p$, with $|L|=|C|=m$ and $|I(L,C)\cap
S|\geq\alpha|S|$.
\end{definition}

Equivalently, $\Cbsgsone\alpha(S)$ is the smallest integer
$n$ such that there exist $X,Y\subseteq \mathbb{Z}_p$, with
$n=|X|=|Y|$ and $|S\cap (X-Y)|\geq\alpha|S|$, where $X-Y$
is the set of pairwise differences between $X$ and $Y$. The
intersection sets from the three definitions of
complexities appear in Fig.~\ref{fig:intersectionsets}.
\begin{figure}[htb]
\begin{center}
\psfrag{BSGS}{\scriptsize$I(\{(a_1,b_1),(a_2,b_2),(a_3,b_3)\},\{c_1,c_2,c_3\})$}
\psfrag{BSGS1}{\scriptsize$I(\{(1,b_1),(1,b_2),(1,b_3)\},\{c_1,c_2,c_3\})$}
\psfrag{generic complexity}{\scriptsize$I(\{(a_1,b_1),(a_2,b_2),(a_3,b_3),(a_4,b_4),(a_5,b_5)\})$}
\psfrag{x}{$x$}
\psfrag{c1}{$c_1$}
\psfrag{c2}{$c_2$}
\psfrag{c3}{$c_3$}
\psfrag{x+b1}{$x+b_1$}
\psfrag{x+b2}{$x+b_2$}
\psfrag{x+b3}{$x+b_3$}
\psfrag{a1x+b1}{$a_1x+b_1$}
\psfrag{a2x+b2}{$a_2x+b_2$}
\psfrag{a3x+b3}{$a_3x+b_3$}
\psfrag{a4x+b4}{$a_4x+b_4$}
\psfrag{a5x+b5}{$a_5x+b_5$}
\includegraphics[scale=0.9]{intersectionsets.md}
\caption{\small Intersection sets for BSGS-1, BSGS, and
generic complexities.}\label{fig:intersectionsets}
\end{center}
\end{figure}

The problem of computing $\Cbsgsone\alpha(S)$ is
superficially similar to a number of problems in additive
number theory concerned with studying properties of $X-Y$.
However, our goal is fundamentally different since we
require that $X-Y$ cover a large fraction of $S$ rather
than be its exact equal. To the best of our knowledge, the
only paper in the literature directly applicable to
bounding $\Cbsgsone1(S)$ is a 1977 paper by Erd\"os and
Newman~\cite{EN77-bases}. They proved analogues of our
Theorems~\ref{th:random} and~\ref{th:bsgs1} and bounded the
BSGS-1 complexity (in our notation) of the set of small
squares $\{x^2\mid x<\sqrt{p}\}$ to be $\Omega(p^{1/3 -
c/\log\log p})$. They leave open the problem of
constructing sets with a strictly linear BSGS-1 complexity
(without the $1/\log p$ factor).

The BSGS and BSGS-1 complexities provide useful upper
bounds for the generic complexity.

\begin{proposition}\label{prop:bounds}$\frac12\C{\alpha}(S)\leq \Cbsgs{\alpha}(S)\leq \Cbsgsone\alpha(S)$.
\end{proposition}
\begin{proof} Let $C'=\{0\}\times C=\{(0,c)\mid c\in
C\}$. Then $I(L,C)\subseteq I(L\cup C')$, which implies the
first inequality. The second inequality follows from the
fact that any BSGS-1 attack is also a BSGS attack.\hfill $\!\square$
\end{proof}

Consider, for example, the baby-step giant-step attacks on
exponents with low Hamming
weight~\cite{heiman92,Stinson02-bsgs}. Define
$S_\lambda=\{x \in \mathbb{Z}_p\mid \nu(x)=\lambda |x|\}$, where
$\nu(x)$ is the number of ones in the binary representation
of $x$. Stinson~\cite{Stinson02-bsgs} estimates the
complexity of the randomized algorithm due to Coppersmith
to yield
$$
\Cbsgsone{1/2}(S_\lambda)=\tilde
O(p^{1/2\log_2(\lambda^{-\lambda}(1-\lambda)^{\lambda-1})}).
$$
For instance, if $\lambda=1/4$, the bound becomes
$\Cbsgsone{1/2}(S_{0.25})=\tilde O(p^{0.406})$.

Following
Propositions~\ref{prop:C(Z_p)},~\ref{prop:bounds}, and
Theorem~\ref{th:random} the BSGS-1 $\alpha$-complexity of a
set of cardinality less than $\sqrt{p}$ lies between
$\sqrt{\alpha|S|/2}$ and $2\sqrt{\alpha p}$, where the
lower bound is trivial and the upper bound is approximated
up to a logarithmic factor by almost any subset of size
$\sqrt{p}$. In this section we construct a set with
succinct representation and a non-trivial BSGS-1
complexity. We start by stating without proof an important
combinatorial lemma known as the Zarankiewicz
problem~\cite{Zarankiewicz51}:
\begin{theorem}\cite[Ch.
IV.2]{Bollobas98-modern} Let $Z(n,s,t)$ be the maximum
number of ones that can be arranged in an $n\times n$
matrix such that there is no all-one $t\times s$ (possibly
disjoint) submatrix. Then
$$
Z(n,s,t)<s^{1/t}n^{2-1/t}.
$$
\end{theorem}
Notice that the asymptotic of the bound on $Z(n,s,t)$
depends on the smallest of the two dimensions of the
prohibited all-one submatrix. It is known that the bound is
tight (up to a constant factor) for $t=2,3$.

Our second combinatorial tool follows from a more general
upper bound due to A.~Naor and Verstra\"ete on the number
of edges in a bipartite graph without cycles of length $2k$
($C_{2k}$-free graph):

\begin{theorem}[\cite{NV05-2kgon}]\label{th:2kgon} The maximum number of edges in a $C_{2k}$-free
$(n,n)$-bipartite graph is less than $2kn^{1+1/k}$.
\end{theorem}

When $k=2$ the two theorems overlap. Indeed, a 0-1 matrix
is also a bipartite graph, where the rows and columns form
the vertex set and the non-zero elements indicate adjacency
of corresponding vertices. In this case an all-one $2\times
2$ submatrix represents a cycle of length 4 in the graph.
Our theorems fully reflect this relationship:
Theorem~\ref{th:bsgs1} can be proved using either the
Zarankiewicz or the Naor-Verstra\"ete bound; its
generalization Theorem~\ref{th:bsgs1general} makes use of
$C_{2k}$-free graphs, while Theorems~\ref{th:bsgs}
and~\ref{th:cbound} apply the Zarankiewicz bound.

\begin{theorem}\label{th:bsgs1}Suppose $S\subseteq \mathbb{Z}_p$ has the property that all
pairwise sums of different elements of $S$ are distinct.
Then
$$
\Cbsgsone\alpha(S)>(\alpha|S|/\sqrt{2})^{2/3}.
$$
\end{theorem}
\begin{proof}Take $X,Y\subseteq\mathbb{Z}_q$, such that $n=|X|=|Y|$ and
$|S\cap (X-Y)|>\alpha|S|$. Consider an $n\times n$ matrix
$M$, whose rows and columns are labeled with elements of
$X$ and $Y$ respectively. For each element $s\in S\cap
(X-Y)$ find one pair $x\in X$ and $y\in Y$ such that
$s=x-y$ and set the $(x,y)$ entry of the matrix to one.
Since $X-Y$ covers at least an $\alpha$-fraction of $S$,
the number of ones in the matrix is at least $\alpha|S|$.

We claim that $M$ does not contain an all-one $2\times 2$
submatrix. Assume the opposite: The submatrix given by
elements $x_1,x_2$ and $y_1,y_2$ has four ones. It follows
that all four $s_{11}=x_1-y_1$, $s_{12}=x_1-y_2$,
$s_{21}=x_2-y_1$, $s_{22}=x_2-y_2\in S$. Then
$s_{11}+s_{22}=s_{12}+s_{21}$, which contradicts the
assumption that all pairwise sums of elements of $S$ are
distinct. Applying the Zarankiewicz bound for the case
$s=t=2$, we prove that
$$
\alpha|S|<Z(n,2,2)<\sqrt{2}n^{2-1/2}=\sqrt{2}n^{3/2},
$$
which implies that
$n=\Cbsgsone\alpha(S)>(\alpha|S|/\sqrt{2})^{2/3}$.\hfill $\!\square$
\end{proof}

The sets where sums of pairs of different elements are
distinct are known in combinatorics as weak Sidon sets.
They are closely related to (strong) Sidon sets, also
called $B_2$ sequences, where all pairwise sums (of not
necessarily different elements) are distinct (for a
comprehensive survey see~\cite{Bryant04-survey} that
includes more than 120 bibliographic entries). Explicit
constructions of Sidon subsets of $\{1,\dots,n\}$ due to
Singer and Ruzsa have cardinality at least
$\sqrt{n}-n^{.263}$~\cite{Singer38,BC62-additive,Ruzsa93,BHP01}.

We additionally require that the sums be different modulo
$p$. The size of such sets is bounded from above by
$p^{1/2}+1$~\cite[Theorem 3]{HHO04}. The easiest shortcut
to constructing weak modular Sidon sets is to take a strong
Sidon subset of $\{0\dots \lfloor p/2\rfloor\}$ (see
also~\cite[Ch.~3]{Bryant02-thesis} and~\cite{GS80-golomb}).
Denser Sidon sets may be constructed for primes of the form
$p=q^2+q+1$, where $q$ is also prime~\cite{Singer38}.
Existence of infinitely many such primes is implied by
Schinzel's Hypothesis H and their density follows from the
even stronger Bateman-Horn
conjecture~\cite[A]{Guy04-unsolved}. Interestingly, modular
Sidon sets are useful not only in constructing sets with
high complexity, via Theorem~\ref{th:bsgs1}, but also for
solving the discrete logarithm problem in
$\mathbb{Z}_p$~\cite{CLS03}.

\comment{For a ``book proof'' of the following theorem we
refer the reader to the survey~\cite{Bryant04-survey} that
combines earlier results due to Singer, Erd\"os, Tur\'an,
and others:

\begin{theorem}[\cite{Singer38,ET41-Sidon,Lindstrom69-Sidon,Ruzsa93}]\label{th:sidon} The largest
Sidon subset of $\{1,\dots,n\}$ has between
$\sqrt{n}-n^{.263}$ and $\sqrt{n}+n^{.25}$ elements.
\end{theorem}

Whether the above lower bound can be improved to
$\sqrt{n}+O(1)$ is Erd\"os's \$500-dollar question (problem
C9 in~\cite{guy}).}

\section{Beyond the Basics}\label{s:beyond}

Theorem~\ref{th:bsgs1} can be generalized to make use of
Sidon sets of higher order. First, we prove that if all
$k$-wise sums of elements of $S$ are distinct (counting
permutations of the same $k$-tuple only once), then there
is a bound on the BSGS-1 complexity. Second, we provide a
result that there exist such sets of size
$\mathrm{\Theta}(p^{1/k})$.

\begin{theorem}\label{th:bsgs1general}Suppose $S\subseteq \mathbb{Z}_p$ is such that all
$k$-wise sums of different elements of $S$ are distinct (excluding
permutation of the summands). Then
$$
\Cbsgsone\alpha(S)>(\alpha|S|/(2k))^{k/(k+1)}.
$$
\end{theorem}
\begin{proof} Take $X,Y\subseteq\mathbb{Z}_p$, such that $\Cbsgsone\alpha(S)=|X|=|Y|=n$ and
$|S\cap (X-Y)|>\alpha|S|$. Instead of the matrix as in
Theorem~\ref{th:bsgs1}, consider a bipartite graph $G(X,Y)$, where
there is an edge $(x,y)$ if and only if $x-y\in S$ (keep only one
edge per element of $S$).

We claim that there are no $2k$-cycles (without repetitive
edges) in the bipartite graph $G$. Assume the opposite:
There is a cycle $(x_1$,$y_1$,\dots,
$x_k$,$y_k$,$x_1$,$y_1)$. Consider two sums:
$(x_1-y_1)+(x_2-y_2)+\dots+(x_k-y_k)$ and
$(x_2-y_1)+(x_3-y_2)+\dots+(x_k-y_{k-1})+(x_1-y_k)$. Not
only are the two sums equal, they also consist of $k$
elements of $S$ each, and these elements are all distinct
(as every element of $S$ appears as an edge of $G$ at most
once). A contradiction is found.

The number of edges in an  $(n,n)$-bipartite graph without
$2k$-cycles is less than $2kn^{1+1/k}$
(Theorem~\ref{th:2kgon}). Therefore $\alpha|S| <
2kn^{1+1/k}$, and
$n=\Cbsgsone\alpha(S)>(\alpha|S|/(2k))^{k/(k+1)}$. \hfill $\!\square$
\end{proof}

Bose and Chowla give a construction for subsets of
$\{1,\dots,q^k\}$ of prime size $q$ whose $k$-wise sums are
distinct (in integers, not modulo
$p$)~\cite{BC62-additive}. By choosing the largest prime
$q$ less than $p^{1/k}$ (which, for large $p$ is more than
$p^{1/k}-p^{0.525/k}$~\cite{BHP01}) an interval of length
$q^k/k$ with a $1/k$ proportion of the set's elements, we
guarantee that all $k$-sums are distinct in $\mathbb{Z}_p$ as well.
Unfortunately, \cite{BC62-additive} does not provide an
efficient sampling algorithm.

Along the lines of Theorem~\ref{th:bsgs1} we prove that
other verifiable criteria imply non-trivial bounds on the
BSGS and generic complexity.

\begin{theorem}\label{th:bsgs}Suppose $S\subseteq \mathbb{Z}_p$
is such that for any distinct $x_1$,$x_2$,$y_1$,
$y_2$,$z_1$,$z_2\in S$:
\begin{equation}\label{eq:det2x2}
\det\left(\begin{matrix}x_1-y_1 &
x_2-y_2\\
y_1-z_1 & y_2-z_2\end{matrix}\right)\neq 0.
\end{equation}
Then
$$
\Cbsgs{\alpha}(S)>(\alpha|S|/\sqrt{3})^{2/3}.
$$
\end{theorem}
\begin{proof} Take $L\subseteq \mathbb{Z}_p^2$ and
$C\subseteq\mathbb{Z}_p$, such that $|L|=|C|=n$ and $|I(L,C)\cap
S|>\alpha|S|$. As in Theorem~\ref{th:bsgs1} consider the
$n\times n$ matrix $M$ whose rows and columns are labeled
with elements of $L$ and $C$ respectively. For each element
$s\in S\cap I(L,C)$ set one entry in row $(a,b)$ and column
$c$ to one, where $s=(c-b)/a$. Thus, the total number of
ones in the matrix is exactly $m=|I(L,C)\cap S|$. If there
is a $2\times 3$ all-one submatrix in $M$, then
property~(\ref{eq:det2x2}) does not hold (three parallel
lines divide two other lines proportionally). The
Zarankiewicz bound implies that
$$
\alpha|S|<Z(n,3,2)<\sqrt{3}n^{2-1/2}=\sqrt{3}n^{3/2}.
$$
Hence $\Cbsgs{\alpha}(S)=n\geq (\alpha|S|/\sqrt{3})^{2/3}$.\hfill $\!\square$
\end{proof}

Constructing a large subset of $\mathbb{Z}_p$ with short
description satisfying the condition of the previous
theorem is a difficult problem. Fortunately, the
probability that a random 6-tuple of $\mathbb{Z}_p$ elements fails
to satisfy~(\ref{eq:det2x2}) is $2/p$~\cite{Schwartz80}.
This observation motivates the following definition:
\begin{definition}[$\S(N,k)$ family] Let $\S(N,k)=\{x_1,\dots,x_N\}$ be
a family of subsets of $\mathbb{Z}_p$, where $x_1,\dots,x_N\colon
\mathcal{K}\mapsto\mathbb{Z}_p$ are $k$-wise independent random
variables ($\mathcal{K}$ is the probability space).
\end{definition}

Properties of $\S(N,k)$ are established in the following
proposition:
\begin{proposition}\label{prop:Snk}
\begin{enumerate}\setlength{\topsep}{0in}\setlength{\itemsep}{0ex}\setlength{\parskip}{0in}
\item $\S(N,k)$ can be defined over $\mathcal{K}=\mathbb{Z}_p^k$.

\item For $k>1$,
$\Pr_{S\in_R \S(N,k)}[|S|\neq N]<N^2/p$.

\item If $h\in \mathbb{Z}[y_1,\dots,y_k]$ and $d=\deg(h)>0$, then
$$
\Pr_{S\in \S(N,k)}[\exists\textrm{ distinct }
z_1,\dots,z_k\in S\textrm{ with }
h(z_1,\dots,z_k)=0]<N^kd/p.
$$
\end{enumerate}
\end{proposition}

\begin{proof}
1. To construct $\S(N,k)$ we use a well-known $k$-universal
family of functions (following~\cite{CW77}). Let the
probability space be $\mathcal{K}=\mathbb{Z}_p^k$ and
$f_a(x)=a_{k-1}x^{k-1}+\dots+a_0$ for
$a=(a_0,\dots,a_{k-1})\in \mathcal{K}$. Define the random
variables $x_i=f_a(i)\colon \mathcal{K}\to\mathbb{Z}_p$ for $1\leq
i\leq N$. We claim that the variables $x_1,\dots,x_N$ are
$k$-wise independent. This follows from the system
$f_a(i_1)=y_1$,\dots, $f_a(i_k)=y_k$ having a unique
solution $a\in\mathcal{K}$ for any distinct
$i_1,\dots,i_k\in \{1,\dots,N\}$ and
$y_1,\dots,y_k\in\mathbb{Z}_p$. Notice that any $S\in\S(N,k)$ can
be easily enumerated and sampled from.

2. Let $I_{ij}$ be the indicator variable, which is equal
to 1 when $x_i=x_j$ and 0 otherwise. The cardinality of
$S=\{x_1,\dots,x_N\}$ is at least $N-\sum_{i<j}I_{ij}$.
Since $x_i$ and $x_j$ are independent for all $i\neq j$,
$E[I_{ij}]=1/p$. By linearity of expectation, the expected
value $E[\sum_{i<j}I_{ij}]<N^2/p$. By Markov's inequality
$\Pr[|S|\neq N]=\Pr[\sum_{i<j}I_{ij}\geq 1]<N^2/p$.

3. Let $I_{i_1,\dots,i_k}$ for all distinct $1\leq
i_1,\dots,i_k\leq N$ be the indicator variable that is 1 if
and only if $h(x_{i_1}$,\dots,$x_{i_k})=0$. By independence
of the variables and~\cite{Schwartz80}
$E[I_{i_1,\dots,i_k}]\leq 2/p$, which by linearity of
expectation and Markov's inequality implies that
$\Pr_S[\exists\textrm{ distinct } x_1,\dots,x_k\in
S\textrm{ with } h(x_1,\dots,x_k)=0]\leq
\Pr_S[\sum_{i_1,\dots,i_k} I_{i_1,\dots,i_k}\geq 1]<
N^kd/p.$ \hfill $\!\square$
\end{proof}

It follows that a randomly chosen set from the family
$\S(p^{1/6-\varepsilon},6)$ has size $p^{1/6-\varepsilon}$ with probability
at least $1-p^{-2/3}$ and satisfies the condition of
Theorem~\ref{th:bsgs} with probability at least
$1-2p^{-6\varepsilon}$.

\begin{figure}[htb]
\begin{center}
\psfrag{f1}{$x_1+y_2=x_2+y_1$}
\psfrag{f2}{$\left|\begin{matrix}x_1-y_1 &
x_2-y_2\\
y_1-z_1 & y_2-z_2\end{matrix}\right|=0$}
\psfrag{f3}{\scriptsize{$\left|\begin{matrix}
x_1 - y_1 & x_1 - z_1 & z_1(x_1 - y_1) & y_1(x_1 - z_1) \\
x_2 - y_2 & x_2 - z_2 & z_2(x_2 - y_2) & y_2(x_2 - z_2)  \\
x_3 - y_3 & x_3 - z_3 & z_3(x_3 - y_3) & y_3(x_3 - z_3)  \\
x_4 - y_4 & x_4 - z_4 & z_4(x_4 - y_4) & y_4(x_4 - z_4)
\end{matrix}\right|=0$}}
\psfrag{f4}{$x_1+y_2+z_3=x_3+y_1+z_2$}
\psfrag{x}{$x$}
\psfrag{x1}{$x_1$}
\psfrag{y1}{$y_1$}
\psfrag{z1}{$z_1$}
\psfrag{x2}{$x_2$}
\psfrag{y2}{$y_2$}
\psfrag{z2}{$z_2$}
\psfrag{x3}{$x_3$}
\psfrag{z3}{$z_3$}
\psfrag{x11}{$x_1$}
\psfrag{x12}{$x_2$}
\psfrag{x13}{$x_3$}
\psfrag{x14}{$x_4$}
\psfrag{x21}{$y_1$}
\psfrag{x22}{$y_2$}
\psfrag{x23}{$y_3$}
\psfrag{x24}{$y_4$}
\psfrag{x31}{$z_1$}
\psfrag{x32}{$z_2$}
\psfrag{x33}{$z_3$}
\psfrag{x34}{$z_4$}
\psfrag{l1}{$l_1$}
\psfrag{l2}{$l_2$}
\psfrag{l3}{$l_3$}
\psfrag{l4}{$l_4$}
\psfrag{ll1}{$l_x$}
\psfrag{ll2}{$l_y$}
\psfrag{ll3}{$l_z$}
\includegraphics[scale=0.9]{configurations.md}
\caption{\small ``Prohibited'' configurations
(Theorems~\ref{th:bsgs1},~\ref{th:bsgs1general}
and~\ref{th:bsgs},
Proposition~\ref{prop:12}).}\label{fig:configurations}
\end{center}
\end{figure}

To apply a similar argument to the all-powerful generic
complexity, we may show that for small constants $m_1$ and
$m_2$, the projections on the $x$ axis of the intersection
points of an irregular $m_1$ by $m_2$ grid (in which lines
need not be parallel) satisfy a certain relationship. Next,
a set $S$, where any $m_1m_2$-tuple avoids this
relationship, is to be constructed.

Let us see first why this argument works for some values of
$m_1$ and $m_2$, and then improve the parameters. Let
$m_1=4$ and $m_2=5$. There are $9$ lines that can be
described using 18 parameters. On the other hand, there are
20 points that form the intersection set of these lines.
Each of the 20 intersection points imposes a linear
equation on the parameters, and hence the system is
overdetermined (even if we exclude linearly dependent
equations). In particular, this implies that the
probability that a random 20-tuple of elements of $\mathbb{Z}_p$ is
coverable by a $4\times 5$ grid is negligible. We refine
this argument in the following proposition.

\begin{proposition}[Bipartite Menelaus' theorem]\label{prop:12}
Consider seven lines $l_{x,y,z},l_{1,2,3,4}$ forming an irregular
grid, and their twelve intersection points. Let $x_i$,$y_i$,$z_i$ be
projections on the $x$ axis of the intersection points of $l_i$ with
lines $l_x,l_y,l_z$. Then the following holds:
\begin{equation}
\det\left(\begin{matrix}
x_1 - y_1 & x_1 - z_1 & z_1(x_1 - y_1) & y_1(x_1 - z_1) \\
x_2 - y_2 & x_2 - z_2 & z_2(x_2 - y_2) & y_2(x_2 - z_2)  \\
x_3 - y_3 & x_3 - z_3 & z_3(x_3 - y_3) & y_3(x_3 - z_3)  \\
x_4 - y_4 & x_4 - z_4 & z_4(x_4 - y_4) & y_4(x_4 - z_4)
\end{matrix}\right)=0.\label{eq:twelvedet}
\end{equation}
\comment{
\begin{align}
0=\phantom{+}
 &(x_1-z_1) (y_1-y_2) (x_2-z_2) (x_3-x_4) (y_3-z_3) (y_4-z_4) -\notag\\
-&(x_1-z_1) (y_1-y_3) (x_2-x_4) (y_2-z_2) (x_3-z_3) (y_4-z_4) +\notag\\
+&(x_1-z_1) (y_1-y_4) (x_2-x_3) (y_2-z_2) (y_3-z_3) (x_4-z_4) +\notag\\
+&(x_1-x_2) (y_1-z_1) (y_2-z_2) (x_3-z_3) (y_3-y_4) (x_4-z_4) -\notag\\
-&(x_1-x_3) (y_1-z_1) (x_2-z_2) (y_2-y_4) (y_3-z_3) (x_4-z_4) +\notag\\
+&(x_1-x_4) (y_1-z_1) (x_2-z_2) (y_2-y_3) (x_3-z_3) (y_4-z_4).
\end{align}}
\end{proposition}
\begin{proof}Denote the $4\times 4$ matrix
in~(\ref{eq:twelvedet}) by $M$. Observe that if any of the seven
lines is vertical, (\ref{eq:twelvedet}) follows immediately.
Indeed, if $l_y=\{x=\mathrm{const}\}$, then $y_1=y_2=y_3=y_4$ and
the second and the fourth columns of $M$ are linearly dependent.
Moreover, $\det M$ is invariant under permutations of $l_x$,$l_y$,
and $l_z$, which takes care of vertical $l_y$ or $l_z$. If $l_i$
is vertical for some $1\leq i\leq 4$, then the $i$th row of $M$ is
all-zero, and $\det M = 0$.

If none of the lines is vertical, we can write down
equations for all of them in the Cartesian coordinates. Let
$l_{x,y,z}=\{a_{x,y,z}x + b_{x,y,z}\}$ and
$l_i=\{c_ix+d_i\}$ for $1\leq i\leq 4$. Each intersection
point imposes an equation on the parameters of the two
lines incident with it, a total of 12 equations in 14
unknowns.\comment{For instance, the intersection point of
$l_x$ and $l_1$ projects to $x_1$, which implies that
$$
a_xx_1+b_x=c_1x_1+d_1.
$$
There are 12 equations in 14 unknowns if we try to solve
the system for the lines' parameters given
$x_1,x_2,\dots,z_4$.} However, the system always has a
trivial solution, when all lines are equal. Rewrite the
system using new variables: $\tilde a_y=a_y-a_x$, $\tilde
b_y=b_y-b_x$, $\tilde a_z=a_z-a_x$, $\tilde b_z=b_z-b_x$,
$\tilde c_1=c_1-a_x$, $\tilde d_1=d_1-b_x$, etc. The result
is a homogenous system of 12 linear equations in 12 new
variables. It has a non-zero solution if and only if its
matrix is singular (only non-zero elements are shown):
$$
M'=\left(\begin{array}{cccccccccccc}
    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -x_1&   -1&    \cdot&    \cdot&    \cdot&    \cdot\\
    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -y_1&   -1&    \cdot&    \cdot\\
    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -z_1&   -1\\
  x_2&    1&    \cdot&    \cdot&    \cdot&    \cdot& -x_2&   -1&    \cdot&    \cdot&    \cdot&    \cdot\\
  y_2&    1&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -y_2&   -1&    \cdot&    \cdot\\
  z_2&    1&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -z_2&   -1\\
    \cdot&    \cdot&  x_3&    1&    \cdot&    \cdot& -x_3&   -1&    \cdot&    \cdot&    \cdot&    \cdot\\
    \cdot&    \cdot&  y_3&    1&    \cdot&    \cdot&    \cdot&    \cdot& -y_3&   -1&    \cdot&    \cdot\\
    \cdot&    \cdot&  z_3&    1&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot&    \cdot& -z_3&   -1\\
    \cdot&    \cdot&    \cdot&    \cdot&  x_4&    1& -x_4&   -1&    \cdot&    \cdot&    \cdot&    \cdot\\
    \cdot&    \cdot&    \cdot&    \cdot&  y_4&    1&    \cdot&    \cdot& -y_4&   -1&    \cdot&    \cdot\\
    \cdot&    \cdot&    \cdot&    \cdot&  z_4&    1&    \cdot&    \cdot&    \cdot&    \cdot& -z_4&   -1\\
\end{array}\right).
$$
One can verify that $\det(M)=\det(M')$.\hfill $\!\square$
\end{proof}

In the full version of the paper we give a geometric proof
of the proposition, deriving~(\ref{eq:twelvedet}) directly,
and explain the connection with classic Menelaus' theorem.
We also give an alternative statement of the theorem, which
puts it in the realm of projective geometry.

Proposition~\ref{prop:12} is the ``minimal'' condition that
holds for the $x$-coordinates of the intersection points of
two sets of lines in general position. Indeed, it follows
from the proof that for any assignment of distinct values
to the eleven variables $x_{1,2,3,4}$, $y_{1,2,3,4}$,
$z_{1,2,3}$ there is a configuration of lines whose
intersection points project to those variables. Other
configurations with as many or fewer intersection points do
not produce any conditions either. For example, six lines
intersecting two lines can project to any collection of
twelve points.

All geometric arguments
(Theorems~\ref{th:bsgs1},~\ref{th:bsgs1general}, and~\ref{th:bsgs},
Proposition~\ref{prop:12}) are illustrated
in~Fig.~\ref{fig:configurations}.

\begin{theorem}\label{th:cbound}If $S$ is chosen from $\S(p^{1/12-\varepsilon},12)$, then
with probability at least $1-6p^{-12\varepsilon}$
$$
\C\alpha(S)>(\alpha|S|/\sqrt[3]{4})^{3/5}.
$$
\end{theorem}
\begin{proof}Consider the set of lines $L\subseteq\mathbb{Z}_p^2$ such that
$\C\alpha(S)=|I(L)\cap S|$ and $n=|L|$. As in
Theorem~\ref{th:bsgs}, we apply the Zarankiewicz bound to
the $n\times n$ matrix, only now both the rows and the
columns are labeled with elements of the set $L$.
Similarly, only one occurrence of an element of $S$ as the
$x$-coordinate of the intersection of two distinct lines is
recorded in the matrix.

According to Proposition~\ref{prop:Snk}, $S$ avoids
solutions to the equation~(\ref{eq:twelvedet}), whose
left-hand side is a multivariate polynomial of total degree
6, with probability greater than $1-6p^{-12\varepsilon}$. Therefore
the probability that there exist 12 points in $S$ that can
be the intersection set of two groups of lines consisting
of 3 and 4 lines respectively is less than $6p^{-12\varepsilon}$.
Finally, as before,
$\alpha|S|<Z(n,4,3)<4^{1/3}n^{2-1/3}=\sqrt[3]{4}n^{5/3}=\sqrt[3]{4}\C\alpha(S)^{5/3}.$\hfill $\!\square$
\end{proof}

Unlike the proofs of
Theorems~\ref{th:bsgs1},~\ref{th:bsgs1general},
and~\ref{th:bsgs}, where the classes in which the lines are
grouped arise naturally, the use of bipartite Menelaus'
theorem in the analysis of generic complexity above might
appear less motivated. In fact, classic Menelaus' theorem
imposes a simple condition (a cubic equation) on the
intersection set of four lines. It is the second step of
the argument, where we translate absence of a certain
submatrix (subgraph) into sparseness of the entire matrix,
which becomes problematic: Unless $H$ is bipartite,
$H$-free graphs on $n$ vertices may have as many as
$\mathrm{\Theta}(n^2)$ edges according to the celebrated Tur\'an
theorem~\cite[Ch. IV.2]{Bollobas98-modern}.

\begin{figure}[htb]
\begin{center}
\psfrag{C(S)}{$\C1,\Cbsgs1,\Cbsgsone1(S)$}
\psfrag{sqrtp}{$\sqrt{p}$} \psfrag{p}{$p$}
\psfrag{p13}{$\sqrt[3]{p}$} \psfrag{p14}{$\sqrt[4]{p}$}
\psfrag{p15}{$\sqrt[5]{p}$} \psfrag{p16}{$\sqrt[6]{p}$}
\psfrag{p19}{$\sqrt[9]{p}$} \psfrag{p112}{$\sqrt[12]{p}$}
\psfrag{p120}{$\sqrt[20]{p}$} \psfrag{S}{$|S|$}
\psfrag{log}{log} \psfrag{bsgs1}{Theorem~\ref{th:bsgs1}
($\Cbsgsone1$)} \psfrag{bsgs}{Theorem~\ref{th:bsgs}
($\Cbsgs1$)} \psfrag{cbound}{Theorem~\ref{th:cbound}
($\C1$)} \psfrag{lemma1}{Prop.~\ref{prop:C(Z_p)}}
\psfrag{lemma2}{Prop.~\ref{prop:twoineq}}
\psfrag{random}{Theorem~\ref{th:random}}
\includegraphics[scale=0.8]{logscale.md}
\caption{\small Generic complexities and bounds (in
logscale). Propositions~\ref{prop:C(Z_p)}
and~\ref{prop:twoineq} bound the triangle that contains all
possible values for generic complexity. The theorems point
to lower bounds provable for complexities of their
respective constructions.\label{fig:allbounds}}
\end{center}
\end{figure}

\section{Conclusion}
In this paper we develop a theory of lower bounds in the
generic group model on the discrete logarithm problem
constrained to a subset $S\subseteq \mathbb{Z}_p$ known to the
attacker (constrained DLP). We give a first construction of
a set with succinct description whose generic complexity is
more than the square root of its size
(Theorem~\ref{th:cbound}). There exists an apparent gap
between our construction ($|S|=p^{1/12}$ and
$\C1(S)=|S|^{3/5}$) and a random set of size $p^{1/2}$
whose complexity is almost linear in its size. Bridging
this gap constitutes an interesting open problem whose
solution would shed some light on the intrinsic difficulty
of the discrete logarithm problem. We also define
restricted versions of the generic complexity that capture
the complexity of baby-step-giant-step algorithms. We give
an explicit, deterministic construction of a collection of
sets, whose complexity in respect to the weakest family of
baby-step-giant-step algorithms becomes near-optimal as
their size decreases (Theorem~\ref{th:bsgs1general}).
Various bounds and constructions are put together in
Fig.~\ref{fig:allbounds}.

\textbf{Acknowledgments.} The authors thank Constantin
Shramov for his crucial contribution to the geometric proof
of Theorem~\ref{th:bipartite}, and Fan Chung, Kevin
O'Bryant, Imre Ruzsa, and the anonymous reviewer of ANTS
VII for their advice and helpful comments.

redpajama_set_name: RedPajamaArXiv


text:
Q: mySQL table design for facebook style posts that suits one-to-many or many-to-many I am trying to build / design a table that will serve purpose to a post/comment system similar to google+ that can support bidirectional one-to-many/many-to-many relations. What I have currently is
member_id,
post_id,
post_body,
post_date,
post_flagged,
post_shared,
post_likes

*

*member_id = my members id's

*post_id = my auto increment column to give each post a unique id

*post_body = the actual post

*post_flagged = part of a moderation system I intend on building later

*post_shared = some form of grouping id's (not sure how this will work but think
google+ circles)

*post_likes = grouped member_id's of who likes the post.

I have a comment table thats pretty much the same as the above except it has a comment_id on top of the ones above listed to server as its auto incriminate column.
What I am ultimately seeking here currently is I guess a sanity check. Does the above construct/schema look like it might work? would you add/remove/alter it in any way? If not/or if so. Can anyone also suggest what might be a good way to do the post_shared column? Is there some type of object or means of storing data in that column that would serve purpose to the logic of Google+ Circles?

A: post_shared should not be in the main post table.
for a normalized solution, you would want a circles table, a users table, a posts table and some associative tables to tell which ones are related - something like
user_circles
post_circles

A: From what I understand, your post_shared column is what is really in question here. Let's say you have a post that is directed at 5 "circles" (we will steal this term from Google). How would you indicate that in your current setup?
The only way to do this in one field is something like {1, 2, 3, 4, 5} where those numbers are the circle id's. This isn't a very good practice.
The best way I can see to accomplish this would be to have this schema:

*

*Posts: post_id, post_body, post_flagged, post_likes

*Circles: circle_id, ...

*PostCircles: post_id, circle_id
The PostCircles table will show which posts are visible to which circles. In the example above, you have 5 rows in the PostCircles table. Let's say the post id is 1:
post_id    |    circle_id
1               1
1               2
1               3
1               4
1               5

Then you can use your query language to show display the appropriate posts, depending on which circles the viewer is in (note the user schema is not shown in this answer).

redpajama_set_name: RedPajamaStackExchange


text:
ABOUT PLEIADES ARTS
Pleiades [plee–uh-deez] n.
Arts: An artist-run community arts organization in Durham, NC.
Astronomy: a cluster of stars in the Taurus (bull) constellation.
Classical Mythology: seven daughters of Atlas pursued by Orion.
Pleiades Arts is a community-focused, artist-driven organization founded as Pleiades Gallery in 2013 and evolved as a nonprofit entity in 2017.
Our mission is to foster community appreciation for and engagement with the arts.
We believe original artwork is important in our daily lives: it brings beauty, pause, discussion, satisfaction, contemplation, and pleasure.
While the initial purpose of Pleiades Gallery was to provide a space for individual member artists to showcase and sell their artwork, the mission of Pleiades Arts has shifted such that broader community interests are at the heart of our purpose. Pleiades Arts will continue to offer artwork of exhibiting artists and will expand upon our community outreach through:
establishing arts education events
fostering diversity of artwork that is reflective of the region
providing a space for artists from underrepresented communities to exhibit visual and performance art
merging innovation with the arts to increase understanding and access to art
partnering with other civic organizations
hosting community art exhibits and events to address specific cultural and social issues
Renee Leverty, Kim Wheaton, Pamela Green, Cornelio Campos, Dorothy Browne, Darius Quarles, and Libby Bowling.
Why "Pleiades"?
We picked the name "Pleiades" as a way to represent connections in Durham. The cluster of Pleiades stars is represented on the Durham city flag (because Pleiades is located on the shoulder of Taurus, the bull constellation). So in our gallery we are a cluster of artists within the cultural constellation of Durham, the Bull City!
Please keep visiting us to see what new and exciting things are happening at Pleiades Arts!
109 E. Chapel Hill St.

redpajama_set_name: RedPajamaCommonCrawl


text:
Why Xavi recruitment plan at Barcelona could be hamstrung by registration issues
Home / Football News / Transfers / Why Xavi recruitment plan at Barcelona could be hamstrung by registration issues
By Andrew Thompson Published: November 17, 2021 3:57 pm
Last Updated: November 17, 2021 10:25 pm
Recruitment plans for Xavi in jeopardy
The new Barcelona regime under Xavi may have to go through a massive teething problem in the early weeks of its existence after the club revealed a potential issue that could scupper the transfer plans under the club icon.
Fabrizio Romano tweeted earlier today that club director of football Mateu Alemany announced that Barcelona will be unable to register any signings in January if they are unable to clear the decks of a handful of unwanted first-team options.
"Today, there is no possibility of signing in the winter market. But we're working. We will be able to register Xavi and by January we will see what can be done."
Dani Alves: "It's a dream! I didn't care how, I wanted to be at Barça. For free if necessary, whatever. My goal is to bring joy & enthusiasm. Xavi's mission, my mission. We have to get back together and transform the club again. Barça is more than a club". 🔵🔴 #FCB @barcacentre pic.twitter.com/vDdXzSzrkZ
— Fabrizio Romano (@FabrizioRomano) November 17, 2021
Despite the free signing of Dani Alves that was made official during his unveiling today, the potential speedbumps in the reinforcement plans that Xavi has championed since the outset of his tenure may be thrown into disarray.
Thankfully, Barcelona has been linked with trying to push a few players out of the Campo Nou in January, including Dutch international Luuk de Jong after a less than stellar spell in Catalunya. Additionally, the Blaugrana are apparently willing to part ways with star midfielder Frenkie de Jong after the breakthrough of both Gavi and Pedri into the first-team fold in conjunction with the financial struggles at the club currently.
Barcelona links to Adeyemi could suffer
Given Barcelona and their potential struggles to register new signings come January, a spanner could be thrown into the works regarding Xavi's interest in RB Salzburg's German wunderkind Karim Adeyemi.
SALZBURG, AUSTRIA – SEPTEMBER 29: Karim Adeyemi of Salzburg scores the penalty to 1:0 during the UEFA Champions League group G match between FC Red Bull Salzburg and Lille OSC at Red Bull Arena on September 29, 2021 in Salzburg, Austria. (Photo by Guenther Iby/SEPA.Media /Getty Images)
According to Gerard Romero, an agreement between the German international and Barcelona could be close to completion, but how that will be affected on the back of today's news remains to be seen.
Talks between Barcelona and Adeyemi's entourage are developing nicely, to the point that an agreement is close.
— @gerardromero pic.twitter.com/8wJnKHtoCG
— Barça Universal (@BarcaUniversal) November 16, 2021
As of yesterday, Barça was said to be prepared to slug it out with Bundesliga giants Borussia Dortmund to prize Adeyemi away from Austria after Xavi became a great admirer of his.
But should the club be unable to offload enough names from a bloated first-team squad that currently stands at thirty members, getting Xavi's regime off the ground and in working order could take much longer than anticipated.
This article was edited by Ben Browning.


text:
An unholy trinity: low growth, expansionary monetary policy, and political populism
Paul Diggle Economist
The combination of low economic growth, loose monetary policy and rising political populism provides a framework for understanding both the drivers and the consequences of the UK's vote to leave the European Union (EU). The same framework can be applied to impending referendums in Italy and Hungary, and to elections in Austria, France, Germany and the US.
The message is clear: markets cannot ignore the risk of adverse political developments in any of these countries.
The drivers of the UK's vote to leave the EU were numerous, and the consequences of the vote are ongoing. It will be down to the historians to make a full assessment of both. For now, however, a working framework is provided by the trinity of growth, policy and populism:
Low economic growth. UK real GDP growth has averaged 2.0% per annum in the six years since the financial crisis, well down on the 2.9% per annum achieved in the decade before the crisis. Real earnings growth has been negative on average in the years since the crisis, falling from above 2.5% per annum pre-crisis. Consumer confidence has also been depressed over this period. What economic growth there has been does not appear to have been evenly distributed across social classes and regions.
Loose monetary policy. The policy response to low economic growth has been an extraordinary loosening in monetary policy by the Bank of England (BoE), in the form of low interest rates and quantitative easing. This has provided a backstop to the economy, averting worse growth outcomes. But the effect of stimulative monetary policy has been felt much more strongly in asset prices than in the real economy. The FTSE 250 equity index (more representative of the domestic UK economy than the FTSE 100) stands 34% above its pre-crisis peak, but the economy itself is just 7% larger over this time. Meanwhile, UK bond yields are at record lows, meaning that bond prices are elevated. This boost to asset prices has exacerbated the uneven distribution of post-crisis growth. Fiscal policy, which may have been able to engineer more inclusive economic growth, has taken a back seat in supporting the economy.
Rising political populism. Taken together, the effects of low growth and loose monetary policy have created a sense of growing discontentment with the established economic and political order, and a search for answers outside the economic and political mainstream. One expression of this is the surge in the share of the popular vote for UK political parties other than the Conservatives, Labour and the Liberal Democrats, from a post-war average of 4.9% to some 24.8% at the 2015 general election. The referendum result itself is the most recent expression of anti-establishment sentiment.
This framework also offers a guide to where the UK economy may be headed next.
As the UK's new relationship with the EU is negotiated, the impact of uncertainty is likely to weigh on the already subdued rate of economic growth
As the UK's new relationship with the EU is negotiated, the impact of uncertainty is likely to weigh on the already subdued rate of economic growth. But further monetary policy support, as well as the depreciation in sterling, should provide a partial offset. With interest rates already low and space to loosen monetary policy limited, fiscal policy is also being used to support the economy. The (current) chancellor, George Osborne, has shelved his fiscal mandate to run a surplus by 2019/20 and announced plans to lower corporation tax. The expectation of policy loosening certainly appears to have supported the FTSE 250, which has pared back four-fifths of its initial post-referendum decline. In Scotland, meanwhile, popular discontentment with the referendum result has seen constitutional questions about membership of the United Kingdom come back onto the agenda.
These forces are likely to play out again in a host of referenda and elections in Europe and the US over the next 18 months: a referendum on constitutional reform in Italy, a referendum on refugee quotas in Hungary, and the re-run of presidential elections in Austria, all in October; the US presidential election in November; and general elections in the Netherlands, France and Germany in 2017. Post-crisis GDP growth everywhere but Germany is lower than pre-crisis trends, loose monetary policy rather than fiscal stimulus has been the policy response of choice, and polls suggest populist sentiment is on the rise in each country.
The most pressing concern is Italy. The referendum is on Prime Minister Matteo Renzi's proposal to downgrade the role of the upper house of parliament, thereby removing an impediment to his efforts at much-needed structural reform. But Renzi has made the tactical error of tying his own political future to the outcome of the referendum – should he not secure approval for constitutional reform, he is likely to resign.
The referendum therefore provides an outlet for populist anti-establishment sentiment, which has built in the face of Italian GDP growth that has been on average negative in the years since the crisis and a banking sector that is suffering under the weight of a large non-performing loan book and the negative interest rate policy of the European Central Bank. If the referendum results in Renzi's resignation and a general election, there is a chance that the eurosceptic Five Star Movement, currently a close second behind Renzi's Democratic Party in the opinion polls, forms the next government. The risk that Italy is 'the next domino to fall' cannot be dismissed.
The growing success of populist politicians and causes in a number of advanced economies is not only a consequence of low economic growth and a policy response that has done more to boost asset prices than real economic activity, but also a barrier to the sorts of structural reforms that offer the best chance of boosting global economic growth. Whether or not populist politicians actually gain power, their influence is likely to be felt via a reorientation in political priorities away from painful but much-needed structural economic reforms, and towards policies that play well with domestic audiences.
In southern European countries, that means exerting pressure on Brussels and Berlin to relieve fiscal targets. In northern and Eastern Europe, it probably means greater pushback on migration issues. And in the US, it may mean a rejection of the sort of free-trade agreements championed by earlier administrations. None of this speaks to the global economy pulling itself out of its current funk anytime soon; indeed, it only raises the already significant downside risks to global growth.
Image credit: © Ingram Publishing / Alamy Stock Photo
http://thinkingaloud.aberdeen-asset.us/en/thinkingaloud/the-bigger-picture/an-unholy-trinity-low-growth_-expansionary
Why the EU will reset Brexit countdown
How to survive a zombie company apocalypse
Week in Review: Down time
UK Private Investors: find out more
UK Advisers: find out more
UK Institutional Investors: find out more
Launch UK Pension Consultants site
Week in Review: 'gotta catch 'em all'
India: The Giant Awakens
The elements of ESG
Perhaps money doesn't make the world go around. When will the penny drop?
Aberdeen Asset Management
Martin Gilbert CEO
Lucy O'Carroll Chief Economist, Investment Solutions
Lucy O'Carroll Chief Economist, Aberdeen Solutions
The value of investments, and the income from them, can go down as well as up and you may get back less than amount invested.
The value of investments, and the income from them, can go down as well as up and you may get back less than the amount invested. Past performance is not a guide to future results. Tax treatment depends on the individual circumstances of each investor and may be subject to change in the future. We recommend that you seek financial advice prior to making an investment decision.
Aberdeen Standard Investments is a brand of the investment businesses of Aberdeen Asset Management and Standard Life Investments.
The details contained in this marketing communication are for information purposes only and should not be considered as an offer, investment recommendation, or solicitation, to deal in any of the investments mentioned herein and does not constitute investment research. Aberdeen Standard Investments does not warrant the accuracy, adequacy or completeness of the information contained herein and expressly disclaims liability for errors or omissions in such information and materials.
No information contained herein constitutes investment, tax, legal or any other advice, or an invitation to apply for securities in any jurisdiction where such an offer or invitation is unlawful, or in which the person making such an offer is not qualified to do so.
Third party websites provided by hyperlinks are completely beyond the control of Aberdeen Standard Investments. Accordingly, Aberdeen Standard Investments accept no responsibility for the accuracy, completeness and legality of the contents of such third party website, or for any offers, services and products contained therein.
Issued by:
Aberdeen Asset Managers Limited. Authorised and regulated by the Financial Conduct Authority in the United Kingdom. Registered Office: 10 Queens Terrace, Aberdeen, Aberdeenshire, AB10 1YG. Registered in Scotland No. SC108419.
Standard Life Investments Limited registered in Scotland (SC123321) at 1 George Street, Edinburgh EH2 2LL. Standard Life Investments Limited is authorised and regulated in the UK by the Financial Conduct Authority.
Get the latest commentary direct to your inbox.
-- Investor Type -- Consultant Institution Private Investor Wholesale Third Party
-- Country Select -- Afghanistan Åland Islands Albania Algeria American Samoa Andorra Angola Anguilla Antarctica Antigua and Barbuda Argentina Armenia Aruba Australia Austria Azerbaijan Bahamas Bahrain Bangladesh Barbados Belarus Belgium Belize Benin Bermuda Bhutan Bolivia, Plurinational State of Bonaire, Sint Eustatius and Saba Bosnia and Herzegovina Botswana Bouvet Island Brazil British Indian Ocean Territory Brunei Darussalam Bulgaria Burkina Faso Burundi Cambodia Cameroon Canada Cape Verde Cayman Islands Central African Republic Chad Chile China Christmas Island Cocos (Keeling) Islands Colombia Comoros Congo Congo, the Democratic Republic of the Cook Islands Costa Rica Côte d'Ivoire Croatia Cuba Curaçao Cyprus Czech Republic Denmark Djibouti Dominica Dominican Republic Ecuador Egypt El Salvador Equatorial Guinea Eritrea Estonia Ethiopia Falkland Islands (Malvinas) Faroe Islands Fiji Finland France French Guiana French Polynesia French Southern Territories Gabon Gambia Georgia Germany Ghana Gibraltar Greece Greenland Grenada Guadeloupe Guam Guatemala Guernsey Guinea Guinea-Bissau Guyana Haiti Heard Island and McDonald Islands Holy See (Vatican City State) Honduras Hong Kong Hungary Iceland India Indonesia Iran, Islamic Republic of Iraq Ireland Isle of Man Israel Italy Jamaica Japan Jersey Jordan Kazakhstan Kenya Kiribati Korea, Democratic People's Republic of Korea, Republic of Kuwait Kyrgyzstan Lao People's Democratic Republic Latvia Lebanon Lesotho Liberia Libya Liechtenstein Lithuania Luxembourg Macao Macedonia, the former Yugoslav Republic of Madagascar Malawi Malaysia Maldives Mali Malta Marshall Islands Martinique Mauritania Mauritius Mayotte Mexico Micronesia, Federated States of Moldova, Republic of Monaco Mongolia Montenegro Montserrat Morocco Mozambique Myanmar Namibia Nauru Nepal Netherlands New Caledonia New Zealand Nicaragua Niger Nigeria Niue Norfolk Island Northern Mariana Islands Norway Oman Pakistan Palau Palestinian Territory, Occupied Panama Papua New Guinea Paraguay Peru Philippines Pitcairn Poland Portugal Puerto Rico Qatar Réunion Romania Russian Federation Rwanda Saint Barthélemy Saint Helena, Ascension and Tristan da Cunha Saint Kitts and Nevis Saint Lucia Saint Martin (French part) Saint Pierre and Miquelon Saint Vincent and the Grenadines Samoa San Marino Sao Tome and Principe Saudi Arabia Senegal Serbia Seychelles Sierra Leone Singapore Sint Maarten (Dutch part) Slovakia Slovenia Solomon Islands Somalia South Africa South Georgia and the South Sandwich Islands South Sudan Spain Sri Lanka Sudan Suriname Svalbard and Jan Mayen Swaziland Sweden Switzerland Syrian Arab Republic Taiwan, Province of China Tajikistan Tanzania, United Republic of Thailand Timor-Leste Togo Tokelau Tonga Trinidad and Tobago Tunisia Turkey Turkmenistan Turks and Caicos Islands Tuvalu Uganda Ukraine United Arab Emirates United Kingdom United States United States Minor Outlying Islands Uruguay Uzbekistan Vanuatu Venezuela, Bolivarian Republic of Viet Nam Virgin Islands, British Virgin Islands, U.S. Wallis and Futuna Western Sahara Yemen Zambia Zimbabwe
-- Region Select -- EMEA APAC AMER
You have successfully subscribed to ThinkingAloud.
You can opt out of these communications at any stage via our preference centre.
For more information about how we handle your personal information please see our privacy policy.
Please tick this box if you do not wish to receive these communications.
You have successfully updated your preferences.


text:
CHWDP or HWDP  is a frequently used Polish acronym or initialism of the Polish phrase chuj w dupę policji, literally meaning "(put a) dick in the police's ass." This anti-authoritarian and anti-police  slogan, often written on walls in Poland, is used as a vulgar form of provocation against the police and authorities. The initialism was largely popularised by Polish hip hop music and Polish anarchists, where it is often used in lyrics and as graffiti. It is a specific expression of protest against the authorities, and against "the system" in general. It is more or less analogous to the English language expressions ACAB and "fuck the police".

In Polish orthography, Ch is a digraph. However as chuj is pronounced the same as huj, the acronym HWDP is commonly seen.

Popularity

The slogan is already very widespread in Poland, and its popularity is spreading to other countries, most notably Slovakia and Germany. The popularity of this slogan is rapidly growing.

Alternate expansions

One of the ways in which the popularity of the initialism is easily noticed is that it was given many alternative expansions. Still, the basic meaning is generally known. Others are merely jokes that are sometimes used to avoid awkward situations and to relieve the tension, e.g. when people who propagate this abbreviation talk with the police or by the policemen who want to avoid embarrassment when they are asked to expand the abbreviation during interviews.

Spread on the Internet
However, the popularity of this initialism is not limited to it being spraypainted on the walls in Poland. In fact, the initialism has also spread among the Internet users, both Polish and foreign.

See also
 ACAB

References

External links

Graffiti and unauthorised signage
Law enforcement in Poland
Profanity
Youth culture in Poland
Protests against police brutality

redpajama_set_name: RedPajamaWikipedia


This program is being phased out due to the expansion of our French Immersion program. However, we continue to offer the program to students currently studying Extended French through to their Grade 12 year. Please see the list of schools still offering this program.
The goal of this program is to develop overall skills and communication in French. Students in this program receive a minimum of 1,260 hours of instruction by the end of Grade 8. For more information view the Ministry of Education's - A Parents' Guide to French Immersion and Extended French document.
St. Isaac Jogues Catholic School, in Pickering.
For information on the Extended French Secondary Program, please click here.


We are the Time Sleuths!
With a passion for the past, we are here to help you discover your roots and solve historical puzzles. We act for individuals, corporates, film and television production companies, law firms and probate companies…and we love a mystery!
If you are intrigued about your roots but have never started the search or have been researching for years but have hit that brick wall, we can help, whether it is London, British or European ancestors.
We are based in London with access to the main UK archives but specialise in research worldwide, especially continental Europe, overcoming language barriers and cultural differences.
Please get in touch…and set us a challenge!


text:
Carlos Motta, Artist
Resumé/Bio
Ideological Monuments / Historical Relations (2012)
Ideological Monuments / Historical Relations is composed of 8 photographic triptychs, diptychs and single images of historical monuments photographed throughout Latin American cities. These monuments were erected to pay homage, memorialize and/or historicize political struggles in public space. This work establishes historical relations between ideologies and discourses of "conquest," "liberation," "ascension," "independence," and "oppression."
Ideological Monuments / Historical Relations # 1
(Monument to Óscar Arnulfo Romero (San Salvador), Monument to the Nameless Guerrilla Soldier (Managua), and Monument to Justice (Tegucigalpa))
27 x 9 inches (Triptych)
(Allegory of the Constitution—Monument to the Revolution (San Salvador), Monument to Simón Bolívar, El genio (Caracas), and Monument to Vasco Nuñez de Balboa (Panamá City))
(Ché Guevara (El Alto, Bolivia), Catholic University of Chile (Santiago) and Monument to Sandino (Managua))
(Monument to Salvador Allende (Santiago), Monument to the Constitution (San Salvador) and Monument to the Soldier (Tegucigalpa)
(Bust of a Martyr (Guatemala City))
11 x 9 inches (Single)
(Monument to the Workers (Managua), Detail of a mural by Apacheta (La Paz) and Monument to Students (Panama City))
(Monument to General Belgrano (Buenos Aires), Detail of a mural at Museo Nacional de Historia—Castillo de Chapultepec (Mexico City))
19 x 9 inches (Diptych)
(Traitor—Vandalized mural depicting Hugo Chávez (Caracas)) 11 x 9 inches (Single)


text:
Tag Archives: Bette Midler
Gloria Steinem is 86 years old; I wonder how she feels about getting the biopic treatment while she's still alive. She was a leader for the American feminist movement in the 60s and 70s. She is a journalist, activist, and the co-founder of Ms. magazine.
At least four actors portray Steinem in the various stages of her life, including Julianne Moore and Alicia Vikander. Director Julie Taymor clearly wants to impress us with a litany of Steinem's experiences, influences, and achievements. There are a lot. So many they start to lose their power, they start to feel less real. Which is counter-productive to the goal of celebrating Steinem's life. Reduced to a mere character, we never get a complete sense of who Gloria is as a person, Taymor gets trapped in an achievement-oriented cycle that feels more like separate segments in a shared universe than a narrative running like a river through a single life.
Individually, a lot of these chunks work. The talent is there, and the story-telling is inventive. Unfortunately, Taymor's flair as a director doesn't seem suited to Gloria's no-nonsense attitude. There is almost certainly an interesting story here, I'm just not sure this script ever had a firm grip on it, despite Taymor's accumulation of gifted actors and clever staging. It feels more invested in painting a fuller picture of history than it serves Steinem's particular place within it.
This entry was posted in Half-assed, Jay, Movie Reviews and tagged alicia vikander, Amazon Prime, Bette Midler, biopic, female directors, feminism in film, Janelle Monae, Julianne Moore, Lorraine Toussaint, strong female leads on October 10, 2020 by Jay.
Hocus Pocus (1993)
Q: How many witches were hanged in Salem?
A: The official death count for the Salem Witch Trials is 20 people: 19 victims were hanged at Proctor's Ledge, near Gallows hill, and one person was tortured to death. Four people also died in prison while awaiting trial. But ZERO of them were witches – they were just socially inconvenient women put to death for some man's ulterior motive.
Except.
Except 300 years ago, the Sanderson sisters were hanged in Salem for practicing witchcraft, and they actually deserved it. Winifred (Bette Midler), Sarah (Sarah Jessica Parker), and Mary (Kathy Najimy) are a trio of old hags who kidnapped a little girl to suck the youth right out of her, and then turned her would-be hero older brother into a cat for daring to interrupt. And that's just the stuff we know about. They were soon dangling from the gallows.
Alternate A: If you count the Sandersons, and we definitely do, Salem's dead witch count is actually 3. And the townsfolk are definitely aware of their legend, even 3 centuries later. And it turns out those witches were never very far off: a group of kids including new-to-town Max (Omri Katz), his kid sister Dani (Thora Birch), and the girl he's crushing on who's "really into witches" Allison (Vinessa Shaw), accidentally call them back when a virgin lights a black flame candle (so don't say I didn't warn you). Anyway, the witches immediately want to eat Dani and it takes an immortal talking cat to offer up pro tips for defeating witches.
For some reason this movie has achieved cult Halloween status, and as one of the few films in the genre that isn't horrifying, it makes for nice, family-friendly fare. I say this like I can't understand the appeal when in fact as a kid, I loved it too. One year my cousin and I made our own Sanderson Sister costumes (and yeah, it's problematic that there were only two of us, but since we both probably imagined ourselves to be the 'sexy one', it hardly mattered) and we were really proud to wear them, up until some well-meaning lady complimented my cousin's teeth…who was not wearing prosthetics. It is hands-down the worst thing that ever happened to me on Halloween and I once had the candy ripped from my little hands by teenage bullies. And technically it didn't even happen to me! But anyway, up to that point we were really smug and self-satisfied young witches with probably embarrassing handmade costumes.
Anyway, Disney World makes great use of Halloween time to break the Sanderson Sisters out of the vault. Not normally seen in the parks, they host the Villain Spectacular at Mickey's Not So Scary Halloween Party (other rarely-seen characters that also make an appearance for Halloween: Jack & Sally, Elvis Stitch, Cruella De Vil and more). We Assholes are actually headed for Disney on Saturday and November 2nd just happens to be the magical day when the parks erase Halloween and embrace Christmas, and yes, we're going to Mickey's Very Merry Christmas Party and Sandy Claws only knows who we'll meet there.
Fun Facts about Hocus Pocus:
Brother and sister Garry and Penny Marshall play husband and wife in the film. The dog held by Garry actually belongs to Kathy Najimy.
The animatronic cat was used again on Sabrina The Teenage Witch.
Rosie O'Donnell turned down the role of Mary. Jennifer Lopez auditioned for Sarah. Leonardo DiCaprio turned down the role of Max and did What's Eating Gilbert Grape instead.
Doug Jones, as in Shape of Water Doug Jones, appears in this film as a zombie (see below).
This movie came out in July of 1993 so that it would not compete with Disney's other Halloween offering that year, The Nightmare Before Christmas, which got the coveted October slot.
Real moths came out of Doug Jones' mouth. Sarah Jessica Parker ate a real spider.
While researching her family history for the show Who Do You Think You Are?, Sarah Jessica Parker discovered that her 10th great-grandmother, Esther Elwell, was arrested in Salem in the late 1600s for committing "sundry acts of witchcraft" and choking a neighbour to death. Esther's case never went to court; she escaped with her life and the accusation ended the Salem Witch Trials.
This entry was posted in Jay, Kick-ass!, Movie Reviews, Travelogues and tagged Bette Midler, Disney, Doug Jones, Garry Marshall, Kathy Najimy, Sarah Jessica Parker, Thora Birch on October 31, 2019 by Jay.


text:
Q: How to get related category/categories in WordPress archive page I am using WooCommerce in WordPress. I have few categories of products like these,
Example:
Product 1 Category (//parent)
-- Category 1
-- Category 2
-- Category 3
-- Category 4
Product 2 Category (//parent)
-- Category 10
-- Category 11
-- Category 12
-- Category 13

If I am in a archive page for Category 2(sub) How can I get all other category name under the parent category (Product 1 Category)  as a list.
what i'm trying
$args = array(
       'hierarchical' => 1,
       'show_option_none' => '',
       'hide_empty' => 0,
       'parent' => $parent_cat_ID,
       'taxonomy' => 'product_cat'
   );
$subcats = get_categories($args);
echo '
';
foreach ($subcats as $sc) {
       $link = get_term_link( $sc->slug, $sc->taxonomy );
echo '
'.$sc->name.'
';
     }
echo '
';
}

Out put should :
.Category 1
.Category 2
.Category 3
.Category 4

I have use below code which works fine in single-product.php page -
<?php
 $parent = get_category_parents( $cat, true, ' » ' );
echo $product->get_categories( ', ', '' . _n( 'Category:', 'Categories:', sizeof( get_the_terms( $post->ID, 'product_cat' ) ), 'woocommerce' ) . ' ', '.' );
?>

A: I usually do this by getting data from database
$result = mysql_query("SELECT * FROM wp_terms JOIN wp_term_taxonomy
ON wp_term_taxonomy.term_id = wp_terms.term_id
WHERE wp_term_taxonomy.parent = ".$parent_cat_ID."
AND wp_term_taxonomy.taxonomy = 'product_cat'");

A: I did this to solve the problem
  <?php
    $terms = get_the_terms( $post->cat_ID , 'product_cat' );
    foreach ($terms as $term) {
        $term_id = $term->term_id;
        $term_link = get_term_link( $term, $taxonomy );
        $term_name = $term->name;
        echo '' . $term_name . '';
    }
    ?>


text:
/**
 * Contains an SQL builder.
 */
package com.feedzai.commons.sql.abstraction.dml.dialect;

redpajama_set_name: RedPajamaGithub


The number of independent professionals, commonly referred to as freelancers, in the EU-28 rose by a quarter (24%) from 7.7 million to 9.6 million between 2008 and 2015. This is according to new research published by our own EFIP member in the UK: IPSE, the Association of Independent Professionals and the Self Employed. The news comes as the UK celebrates its most enterprising individuals on National Freelancers Day on 9 June.


text:
Q: Moving the dynamically drawn rectangle inside the canvas using MouseMove event I'm trying to move a dynamically drawn rectangle inside the canvas. I'm able to draw the rectangle dynamically with in the canvas and while trying to move the rectangle inside the canvas I'm facing problem
XAML :
   <Grid x:Name="Gridimage1" Margin="0,0,411,100">
      <Image Name="image1" HorizontalAlignment="Left" Stretch="Fill" VerticalAlignment="Top"></Image>
        <Canvas x:Name="BackPanel" Margin="20,67,0,0" Height="317" Width="331">
           <Rectangle x:Name="selectionRectangle" Stroke="LightBlue" Fill="#220000FF"/>
        </Canvas>
   </Grid>

C# :
After drawing the rectangle dynamically I'm adding the below mouse events.
selectionRectangle.MouseLeftButtonDown += new MouseButtonEventHandler(Rect1_MouseDown);
selectionRectangle.MouseMove += new MouseEventHandler(Rectangle_MouseMove_1);
selectionRectangle.MouseUp += new MouseButtonEventHandler(Rect1_MouseUp);
     # region "rectangle move"
    private bool drag = false;
    private Point startPt;
    private int wid;
    private int hei;
    private Point lastLoc;
    private double CanvasLeft, CanvasTop;
    private void Rect1_MouseDown(object sender, MouseButtonEventArgs e)
    {
        drag = true;
        Cursor = Cursors.Hand;
        startPt = e.GetPosition(BackPanel);
        wid = (int)selectionRectangle.Width;
        hei = (int)selectionRectangle.Height;
        lastLoc = new Point(Canvas.GetLeft(selectionRectangle), Canvas.GetTop(selectionRectangle));
       Mouse.Capture((IInputElement)sender);
    }

    private void Rectangle_MouseMove_1(object sender, MouseEventArgs e)
    {
        try
        {
            if (drag)
            {
                    var newX = (startPt.X + (e.GetPosition(BackPanel).X - startPt.X));
                    var newY = (startPt.Y + (e.GetPosition(BackPanel).Y - startPt.Y));
                    Point offset = new Point((startPt.X - lastLoc.X), (startPt.Y - lastLoc.Y));
                    CanvasTop = newY - offset.Y;
                    CanvasLeft = newX - offset.X;
                    selectionRectangle.SetValue(Canvas.TopProperty, CanvasTop);
                    selectionRectangle.SetValue(Canvas.LeftProperty, CanvasLeft);

            }
        }
        catch (Exception ex)
        {
            MessageBox.Show(ex.Message);
        }

    }
    private void Rect1_MouseUp(object sender, MouseButtonEventArgs e)
    {
        drag = false;
        Cursor = Cursors.Arrow;
        Mouse.Capture(null);
    }
    #endregion

Problem: I'm able to move the rectangle all over the window. I want only to move the rectangle inside the canvas margin.

I'm able to move the rectangle outside the canvas

A: You should be able to get the Bounds of your selectionRectangle and see if they exceed the Width and/or Height of your canvas before committing the drag operation.
selectionRectangle.MouseMove += new MouseEventHandler(Rectangle_MouseMove_1);

private bool drag = false;
private Point startPt;
private int wid;
private int hei;
private Point lastLoc;
private double CanvasLeft, CanvasTop;

private void Rectangle_MouseMove_1(object sender, MouseEventArgs e)
{
    try
    {
        if (drag)
        {
                var newX = (startPt.X + (e.GetPosition(BackPanel).X - startPt.X));
                var newY = (startPt.Y + (e.GetPosition(BackPanel).Y - startPt.Y));
                Point offset = new Point((startPt.X - lastLoc.X), (startPt.Y - lastLoc.Y));
                CanvasTop = newY - offset.Y;
                CanvasLeft = newX - offset.X;

                // check if the drag will pull the rectangle outside of it's host canvas before performing
                // TODO: protect against lower limits too...
               if ((CanvasTop + selectionRectangle.Height > BackPanel.Height) || (CanvasLeft + selectionRectangle.Width > BackPanel.Width) || CanvasTop < 0 || CanvasLeft < 0)
                    {
                        return;
                    }
                selectionRectangle.SetValue(Canvas.TopProperty, CanvasTop);
                selectionRectangle.SetValue(Canvas.LeftProperty, CanvasLeft);

        }
    }
    catch (Exception ex)
    {
        MessageBox.Show(ex.Message);
    }

}

A: if ((CanvasTop + selectionRectangle.ActualHeight > BackPanel.ActualHeight))
{
    CanvasTop = BackPanel.ActualHeight - selectionRectangle.ActualHeight;
}

if (CanvasLeft + selectionRectangle.ActualWidth > BackPanel.ActualWidth)
{
    CanvasLeft = BackPanel.ActualWidth - selectionRectangle.ActualWidth;
}

if (CanvasTop < 0)
{
    CanvasTop = 0;
}

if (CanvasLeft < 0)
{
    CanvasLeft = 0;
}


The UK Government announced on 23 November 2016 that the standard UK Insurance Premium Tax (IPT) will increase by 2% (from 10% to 12%), with effect from 1 June 2017. The higher rate of 20% for insurance supplied with selected goods and services (such as certain travel, motor cars, and domestic appliances) remains unchanged.
Our Adviser provides further details regarding this increase and offers some key points for you to consider in managing your total cost of risk including the premium tax liability thereon.


A musician, singer and songwriter, Elorm Adablah also known as EL, has admonished children to cultivate the habit of reading as this can help them achieve their life goals. This advice comes at a time when research shows that children's interest in reading, including that of adults, is seen to be waning.
According to EL, "No matter what you want to do in your life, as long as you read to educate and empower yourself, the sky is your limit." EL thus advises everyone to pick a book once a while and as often as one can do so and read.
The President of MUSIGA, Singer, Songwriter and Performer, Bice Osei Kuffour (Obour), has urged parents to patronize books written and produced buy Ghanaians. Obour made a case for the purchase of indigenous books in a documentary produced by the Ghana Book Development Council (GBDC).
Ramah Brew, a famous writer and actress, has strongly advocated the need for parents to do more for their children to cultivate the habit of reading. This comes at a time when research has shown that teens and adults are reading fewer books than it used to be.
As part of The Ghana Book Development Council's (GBDC) campaign, dubbed, "Learn to read; read to learn", initiated to create and increase awareness of the numerous benefits of reading, particularly to children, a documentaryhas been put together to inspire children to read. The documentary comprises prominent personalities and role models who still make time to read in spite of their busy schedule.
The Ghana Book Development Council (GBDC) has initiated an innovative campaign, dubbed"Learn to read; read to learn"to create and increase awareness of the numerous benefits of reading, particularly to children. The aim of the campaign is to encourage children to learn to read and after they have learnt to read, to continue to read for life. This will ultimately help to promote quality education, increase quality of life and general wellbeing, eradicate ignorance, poverty and disease and help in realising the UN Sustainable Development Goals (SDGs).
The Ghana Book Development Council (GBDC), an Agency under the Ministry of Education, which ismandated to oversee the development, regulation and effective planning of the Book Industry in Ghana, is providing Book Booths to Basic schools in the country to promote reading. The exercise forms part of GBDC's campaign, dubbed"Learn to read; read to learn" which has been initiated to create and increase awareness of the numerous benefits of reading, particularly to children.
In furtherance of promoting reading and creative writing, GBDC partnered with the Ghana Education Service (GES) and the Ghana Association of Writers (GAW) to establish the Ghana Association of Writers Schools Outreach Programme (GAWSOP) in 2014.


I didn't have any intention of covering a fun find at the Tower of Terror this week until I finished my original article for today and realized that today was in fact Friday the 13th! With that in mind, I give you a Tower of Terror Fun Find!
What is it? It's a standard Elevator Inspection certificate that you would find on most elevators. Let's first take a look at the inspection date on the sign. As we know from the narration at the preshow video the Hollywood Tower Hotel was struck by lightning on Halloween, 1939, aka, October 31, 1939. So we should be happy knowing that the elevator was fully operational on the day the building was struck. That should make you feel a little more at ease the next time you ride. Luckily for us, this is just the start of our Fun Find!
If you were to look at the bottom line of the plaque you will find that it was inspected by Cadwallader. Who is Cadwallader? The sixth episode of the first season, Escape Clause (not to be confused with the third film in the Santa Clause series), focused around a man who feared death and decides to make a deal for immortality with a man named Cadwallader. Cadwallader, the Devil in disguise, grants the wish and the man, knowing he won't die, begins to commit several crimes until he is to be put in jail. Realizing he will never die and spend eternity in jail he takes advantage of Cadwallader's escape clause and has a heart attack instantly while giving his soul to the devil.
Our final detail on the plaque that needs to receive some attention is the actual State ID Number of the elevator: 10259. What do these numbers refer to? The air date of the first Twilight Zone episode: October 2, 1959!


The boat's owner told Collier Sheriff's deputies that he was towing the boat back to Cape Coral when the tow line snapped.
An overturned boat found offshore from Clam Pass turned out to be a boat that had gone missing as it was being towed to Cape Coral, the Collier County Sheriff's Office reported Friday.
The Sheriff's Office was notified about the boat around 8:30 a.m. Thursday, and a marine unit found the boat about a mile west of Clam Pass, spokeswoman Kristi Lester said.
Deputies in dive gear searched the water around the boat and determined there was nobody in or near the boat, Lester said.
She said the boat's owner told deputies he had been towing the boat back to Cape Coral when the tow line snapped about 10 miles west of Marco Island and they had been unable to locate the boat.
A commercial salvage company was on its way to salvage the boat at the time of the investigation, Lester said.


I installed redhat linux 6.0 for server version.But i am not getting the Gnome window manager as i am getting when i installed linux workstation.In server mode it goes into Anotherlevel windows manager. I wants the login prompt where i select the different windows manager as i select in workstation.
So please give me proper solution because i am new user of linux.
after that at the prompt enter "linuxconf"
and at the miscelaneus services, select initial system services and mark the run level 5.
You can select which desktop to run from gdm (the graphical login screen).


The Republican Governors Association announced Tuesday it is reserving $1.7 million in television time in the last six weeks of the Connecticut race for governor, but whether it ultimately spends the money will depend on how the RGA views the winner of the GOP primary in August.
Reserving television time costs nothing. The RGA and Democratic Governors Association each tend to delay spending until the nominees are chosen and the groups can assess their strengths, weaknesses and the need for outside spending. In 2014 the first of the Republican expenditures was made in mid-August, after Tom Foley defeated John P. McKinney in the GOP primary.
The RGA contributed nearly $6 million in 2014 to an independent-expenditure group, Grow Connecticut, that spent $8.85 million, primarily on ads attacking Gov. Dannel P. Malloy, a Democrat who beat Foley in a rematch of their close race in 2010. Connecticut Forward, an independent group mainly funded by the Democratic Governors Association, spent $6 million, primarily on television ads attacking Foley.
Overall, outside spending on Connecticut's race for governor reached a record $18.2 million in 2014, a five-fold increase from 2010 that dwarfed the $6.5 million in public financing allotted to each of the major-party candidates for the general election.
Thompson declined to say whether the RGA will be directly spending money on the Connecticut race or working through an independent group, such as Grow Connecticut.
Ten gubernatorial candidates now intend to seek the endorsement of the Republican State Convention next month. Anyone who wins 15 percent of the vote on any ballot qualifies for a primary in August.
All but former hedge fund manager David Stemerman are seeking public financing of $1.25 million for the primary, which requires raising $250,000 in contributions of no more than $100 each, mainly from in-state donors, and qualifying for the ballot.
Bob Stefanowski, another candidate who has opted out of the voluntary public financing program, is skipping the convention and plans to qualify for the primary by petitioning.
Four Republican candidates for governor already have filed papers with the State Elections Enforcement Commission to pre-qualify them for public financing, assuming they make the primary ballot. They are: state Rep. Prasad Srinivasan, former U.S. Comptroller General Dave Walker, Shelton Mayor Mark Lauretti and Mike Handler, the chief financial officer of the city of Stamford.
Danbury Mayor Mark Boughton, former First Selectman Tim Herbst of Trumbull, Peter Lumaj and Steve Obsitnik all have reported raising more than $250,000 through exploratory and candidate committees. But none had filed their pre-qualification applications as of Tuesday.
New Britain Mayor Erin Stewart, a late entrant in the race for the GOP nomination, reported Tuesday she has raised $105,999 — $35,752 in a brief exploratory campaign and $70,247 since declaring her candidacy on March 19.


Are you still looking for an apartment for your family vacation? Or are you planning a skiing holiday with friends? In our house there are seven different apartments, from the small apartment for two people, to the apartment for large families or company trips - there is something for everyone.


The 4 star Maids Head Hotel offers the perfect location for a stay in the beautiful, historic city of Norwich. Experience the unique charm and character of the hotel in one of our stylish 84 en-suite bedrooms – everything from cosy single rooms to luxurious suites.
All rooms have a bath with shower over or a walk-in shower, tea and coffee facilities, Freeview television and an in-room iPad guest services directory providing hotel information, room service details and internet access.
From an overnight business stay in a contemporary double room, through a weekend exploring Norfolk based in a family room, to a luxurious romantic break in one of our newly refurbished suites, The Maids Head Hotel offers Norfolk's finest for hospitality.


text:
Alabama man saves family from attacker on gameday (True Story)
Oct 23 2021 December 9, 2021
The green tea tea-bagger strikes again!
Tuscaloosa, AL – Sean Lee, was enjoying a Saturday morning bath while his wife and two young daughters walked their lab puppies outside their house near the Bryant Denny Stadium in Tuscaloosa.
Suddenly, screams from his wife cut through the fall air.
Lee springs into action, fearing the worst.
Running out the front door he finds a pitbull attacking one of their puppies.
Mr. Lee instantly jumps on the attacking dog's back, grabs it by the neck, and tightens his hold until the dog is choked to sleep.
"Don't kill it, babe!" says his wife trying to protect her children from a gruesome scene.
Lee, a former fireman with decades of mixed martial arts training, expertly releases enough pressure so that he maintains control but doesn't allow the dog to die.
The specific choke hold Lee used to submit the dog is called a rear naked choke.
As it turns out, this name has never so accurately described a series of events until now.
Because at this moment Mr. Lee realizes he is still completely naked and dripping wet from his bath as he stands over the unconscious pitbull in his front yard with gameday traffic passing by towards the stadium.
After giving his neighbors a visceral preview of what Alabama would do to Georgia weeks later in the 2021 SEC Championship, Lee puts the pitbull into a dog cage, gets dressed, and calls Animal Services.
The pitbull was safely taken away and the attacked puppy was not seriously injured.
Mr. Lee only suffered minor scrapes and scratches from the struggling pitbull.
The Lee family was a little shaken up but were able to enjoy the rest of their gameday in Tuscaloosa knowing that daddy was a hero.
To this day no one believes the neighbors every time they tell the story of the naked Asian man who ran out of the house, jumped on a pitbull, and choked it to sleep on gameday.
Roll Tide.