Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

Luca, since a year has passed, you probably have researched your own
answer.  I'm answering some of your questions here just for the
record.  I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice).  I don't comment here on SDP
algorithms.

Note that the particular algorithms that you mention do not run in
nearly linear time.  (There is a nearly linear-time algorithm for
explicitly given packing or covering problems.  See
Beating Simplex for Fractional Packing and Covering Linear Programs.)
The algorithms you have in mind typically have variants that run in a
nearly linear number of iterations, but each iteration typically
requires at least linear time as well.  I discuss some of these
algorithms below.

Some useful functions

Before we start, here are some functions that we will use in the proof sketches.
(If you are interested in the algorithms, but not the proof details, you can skip ahead.)
For any vector $y$, define $\mbox{Lmax}(y)$ to be $\ln \sum_i \exp(y_i)$.
This function is an upper bound on $\max_i y_i$:
$$\max_i y_i ~\le~ \mbox{Lmax}(y) ~\le~ \max_i y_i + \ln m.$$
Analogously, define $\mbox{Lmin}(y)$ to be $-\mbox{Lmax}(-y)$,
a lower bound on $\min_i y_i$.

For convenience in what follows,
we use $g(y)$ to denote the gradient $\nabla \mbox{Lmin}(y)$ of Lmin.
We use $G(y)$ to denote the gradient $\nabla \mbox{Lmax}(y)$ of Lmax.

Explicitly, $g_i(y)$ is $\exp(-y_i)/\sum_{i'} \exp(-y_{i'})$
while $G_i(y)$ is $\exp(y_i)/\sum_{i'} \exp(y_{i'})$.

Lmin and Lmax are smooth in the following sense:
for any vectors $d\in[0,\varepsilon]^n$ and $y\in R^n$,
$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y)
~+~ (1-O(\varepsilon))\, d \cdot g(y)$$
and
$$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y)
~+~ (1+O(\varepsilon))\, d \cdot G(y).$$

Note that both of the gradients have 1-norm equal to 1:
$|G(y)| = |g(y)| = 1$.  (Throughout we use $|z|$ to denote the 1-norm.)

Note also that, for a matrix $A$,
the gradient of the function $x\mapsto \mbox{Lmin}(Ax)$ with respect to $x$
is (by the chain rule) $(g(Ax))^T A$.
More explicitly, the partial derivative of the function with respect to $x_j$
is $\sum_i A_{ij} \exp(-A_i x) / \sum_i \exp(-A_i x)$.
Likewise,  the partial derivative of Lmax$(Ax)$
with respect to $x_j$ is $\sum_i A_{ij} \exp(A_i x)/\sum_i \exp(A_i x)$.

Fractional Set Cover

Fix a Set-Cover instance.
Let $A$ denote the element/set incidence matrix.
Thus, $A_{es} = 1$ if $e\in s$, else 0,
and $A_e x$ is the extent that  fractional cover $x$ covers element $e$.

The LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$.
Given $\varepsilon\in (0,1)$, the algorithm is

Initialize all $x_s = 0$.  Let $N=\log(n)/\varepsilon$.
Repeat until $\min_e A_e x \ge N$:

2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x_s$.
      (Explicitly, choose $s$ maximizing $\sum_{e\in s} \exp(-\sum_{s'\ni e} x_{s'})$.)

2.2. Increase $x_s$ by $\varepsilon$.
Return $x/\min_{e} A_e x$.

The algorithm returns a $(1+O(\varepsilon))$ approximate solution
in $O(|x^*|\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of elements
and $x^*$ is the optimal fractional set cover (trivially $|x^*|\le n$).
(A similar algorithm appears in the paper Chandra mentioned.
Vertex Cover is of course a special case.)

(Remark: Note that the iteration bound does not depend on the number
of sets, just the number of elements.  Thus, the algorithm can be used
with an implicitly defined set system, as long as, given weights on the
elements, one can efficiently find a set of maximum (or near-maximum) total weight.
This kind of oracle is the same as the separation oracle required to apply
the ellipsoid algorithm to the dual problem. For packing problems such
as set packing, you need an oracle that, given weights on the elements,
returns a set minimizing the total weight.  For problems such as
multi-commodity flow, you might, for example, need to find a path
minimizing the sum of some given edge weights.)

Here's a sketch of the proof of the performance guarantee.
In each iteration, the partial derivative w.r.t. the chosen $s$
is at least $1/|x^*|$, where $x^*$ is the optimal fractional set cover.

(To see why, recall that the gradient of Lmin$(Ax)$ with respect to $x$ is $(g(Ax))^T A$.
If we were to choose a set $s'$ at random from the distribution $x^*/|x^*|$,
the expected value of the partial derivative with respect to $x_{s'}$
would thus be $(g(Ax))^T \,A x^*/|x^*|$.
Since $Ax^* \ge 1$, this is at least $|g(Ax)|/|x^*|$.
Since $|g(Ax)|=1$, this is at least $1/|x^*|$.
Thus, there must exist some $s$ giving partial derivative at least $1/|x^*|$.
Since the algorithm chooses $x_s$ in each iteration to maximize
the partial derivative, it achieves a partial derivative of at least $1/|x^*|$.)

Then, the step size $\varepsilon$ is chosen just small enough so that
no coordinate of $A x$ increases by more than $\varepsilon$.
Thus, because of the smoothness of Lmin,  increasing $x_s$
to $x_s+\varepsilon$ increases $\mbox{Lmin}(Ax)$ by at least
$(1-O(\varepsilon))\varepsilon/|x^*|$.

In this way, the algorithm maintains the invariant
$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^*| - \ln n.$$
(Note that Lmin$(\overline 0)$ equals $\ln n$.)

At termination, in the invariant, the $\ln n$ term is $O(\varepsilon)$ times the left-hand side,
so by calculation one gets $\min_e A_e x \ge  (1-O(\varepsilon)) |x|/|x^*|$.
After the normalization in the last line of the algorithm,
this implies $|x| \le (1+O(\varepsilon))|x^*|$.

FWIW, the inequalities involved in proving the invariant are essentially
the same as those involved in proving the Chernoff bound.
(In fact, this algorithm can be derived by applying the
method of conditional probabilities to a randomized-rounding
scheme that repeatedly samples sets from the distribution $x^*/|x^*|$
(with replacement), increasing $x_s$ for each sampled set $s$.
This derandomization of that gives the algorithm:
the underlying invariant is just that the pessimistic estimator stays below 1.
The exponential penalties in the pessimistic estimator come from the
using the Chernoff bound in the analysis of the rounding scheme.
This basic idea is explained further in the paper Chandra mentioned.)

Fractional Weighted Set Cover (and general fractional Covering)

To handle problems such as Weighted Set Cover efficiently,
we modify the algorithm to use non-uniform increments
(an idea due to Garg and Konemann).

The LP is $\min\{ c\cdot x : (\forall e) \sum_{s\ni e} x_s \ge 1\}$,
where $e$ ranges over the elements, $s$ ranges over the sets,
and all variables are non-negative.
To present the algorithm, first rewrite the problem as a general covering problem.
Let $A_{es} = 1/c_s$ for $e\in s$ and $A_{es} = 0$ otherwise.
Then (with a change of variables, scaling each $x_s$ by $c_s$),
the LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$,
which we can view as a general covering LP.
Here is the algorithm:

Initialize all $x_s = 0$.  Let $N=\log(n)/\varepsilon$.
Repeat until all covering constraints have been deleted:

2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x_s$.
     (Explicitly, choose $s$ maximizing $\sum_{e\in s} \exp({-\sum_{s'\ni e} x_{s'}})/c_s$.)

2.2. Increase $x_s$ by $\delta$, where $\delta$ is chosen maximally such that, for every remaining covering constraint $e$, the increase in $A_e \cdot x$ is at most $\varepsilon$.

2.3 Delete all covering constraints $e$ such that $A_e\cdot x \ge N$.
Return $x/\min_e A_e\cdot x$.

The algorithm returns a $(1+O(\varepsilon))$-approximate solution
in $O(n\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of covering constraints.
(Each iteration increases some remaining $A_e x$ by $\varepsilon$; this can happen
only $N/\varepsilon$ times to a constraint before it is deleted.)
The proof of correctness is via essentially the same invariant as for Set Cover.

Weighted Vertex Cover is a special case.

Maximum Fractional Bipartite Matching

Given a graph $G=(U,W,E)$,
the natural LP for the problem is $\max\{|x| : \forall v.\, \sum_{e\ni v} x_e \le 1\}$.

In matrix representation, this is a packing LP $\max\{|x| : Ax \le 1; x \ge 0\}$
with 0-1 coefficients ($A_{ve} = 1$ if $v\in e$).
Such problems do not require non-uniform increments, so a simple algorithm analogous to the unweighted Set Cover algorithm (but for packing) will do:

Initialize all $x_e = 0$.  Let $N=\log(n)/\varepsilon$.
While $A x < N$:

2.1. Choose $e$ minimizing the partial derivative of Lmax$(Ax)$ w.r.t. $x_e$.
      (Explicitly, choose $e$ to minimize $\sum_{v\in e} \exp(\sum_{e'\ni v} x_{e'})$.)

2.2. Increase $x_e$ by $\varepsilon$.
Return $x/\max_{v} A_v x$.

The algorithm returns a $(1-O(\varepsilon))$-approximate solution in $O(n\log(n)/\varepsilon^2)$ iterations.
(This is because each iteration increases $|x|$ by $\varepsilon$,
and finally, before normalization, $|x| = O(N n)$.)

Just for fun, here is a curious alternative algorithm for Perfect Bipartite Matching.
Recall that $G=(U,W,E)$.  Let $n=|U|=|W|$.

Initialize all $x_e = 0$.  Let $N=4\ln(n)/\varepsilon$.
Repeat $n\,N$ times:

2.1. Choose $u$ uniformly at random from $U$.
 2.2. Choose $w$ such that $(u,w)\in E$ minimizing $\sum_{e\ni w} x_e$.
 2.3. Increase $x_{uw}$ by $\varepsilon$.
Return $x/N$.

If $G$ has a perfect matching, the algorithm returns
an $x$ such that $|x|=n$, and, with high probability,
for all vertices $u\in U$, $1-O(\varepsilon) \le \sum_{e\ni u} x_e \le 1+O(\varepsilon)$,
and for all vertices $w\in W$, $\sum_{e\ni w} x_e \le 1+O(\varepsilon)$.
If you are interested in the details of the proof, please ask...

Mixed Packing and Covering

You may have asked about bipartite matching hoping for an example
of a mixed packing and covering problem, that is, one of the form
$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$
Here's one algorithm for such problems.
First, normalize so that $p=\overline 1$ and $c=\overline 1$.

Let $m$ be the number of constraints (rows in $P$ plus rows in $C$).

Initialize all $x_j = 0$.  Let $N=2\ln(m)/\varepsilon$.
While $P x < N$:

2.1. Choose $j$ so that the partial derivative of Lmax$(Px)$ with respect to $x_j$ is at most the partial derivative of Lmin$(Cx)$ with respect to $x_j$.  (Explicitly, choose $j$ such that $$\frac{\sum_i P_{ij} \exp(P_i x)}{\sum_{i}\exp(P_i x)} \le \frac{\sum_i C_{ij} \exp(-C_i x)}{\sum_{i}\exp(-C_i x)}.)$$

2.2. Increase $x_j$ by $\delta$, where $\delta$ is chosen maximally such that no constraint $P_i x$ or remaining constraint $C_i x$ increases by more than $\varepsilon$.

2.3. Delete all covering constraints $i$ such that $C_i x \ge N$.
Return $x/\max_i P_i x$.

Assuming the given problem is feasible, the algorithm
returns an $x$ such that $Px\le 1$
and $Cx\ge 1-O(\varepsilon)$.
The number of iterations is $O(m\ln(m)/\varepsilon^2)$,
because each iteration increases some constraint by $\varepsilon$,
and this can happen for each constraint at most $N$ times.

The proof of correctness is via the invariant
$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$
The invariant implies
$$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$
At termination the left-hand side is $\Omega(\log(m)/\varepsilon)$,
proving the performance guarantee.

In Step 2.1, the desired $j$ must exist as long as the original problem is feasible.
(This is because, for any feasible $x^*$, and any $x$,
if we were to choose a random $j'$ from the distribution $x^*/|x^*|$,
the expected value of the partial derivative of Lmax$(Px)$ with respect to $x_{j'}$
would be at most $1/|x^*|$ (see the previous proof sketch for Set Cover).
Likewise, the expected value of the partial derivative of Lmin$(Cx)$ with respect to $x_{j'}$
would be at least $1/|x^*|$.
Thus, there is an $j$ such that the partial derivative of Lmax$(Px)$ with respect to $x_{j'}$
is at most the partial derivative of Lmin$(Cx)$.)

Then the invariant is maintained in each iteration because,
by the choice of $x_j$ and $\delta$,
and the smoothness of Lmin and Lmax,
increasing $x_j$ to $x_j+\delta$
increases Lmax$(Px)$
by at most $1+O(\varepsilon)$
times the increase in Lmin$(Cx)$.

Learning (following experts / boosting)

One reference for understanding this connection is
Adaptive game playing using multiplicative weights, by Freund and Schapire.
Here is a quick summary to give the technical idea.

Consider the following repeated game.  In each round $t$:

You choose a probability distribution $p^t$ on $[n]$ (the $n$ so-called experts).
Knowing $p^t$, the adversary then chooses a payoff vector $a^t\in [0,1]^{n}$.
You receive payoff $p^t\cdot a^t$ for the round.

The game stops after some number of rounds.
Your goal is to minimize your regret
in comparison to any single expert (i.e., pure strategy) $i$.
That is, your goal is to minimize $(\max_i \sum_t a^t_i) - \sum_t p^t\cdot a^t$.

Fix any $\varepsilon>0$.
Let vector $y^t$ denote $\varepsilon \sum_{s \le t} a^s$, that is,
$\varepsilon$ times the vector sum of the payoff vectors up to time $t$.
Recall that $G(y)$ is the gradient of Lmax$(y)$.

Here's the basic strategy we will analyze:
On round $t$, choose $p^t$ to be $G(y^{t-1})$.

By inspection, this gives you payoff $a^t \cdot G(y^{t-1})$ in round $t$.

Because of the smoothness property of $F$,
$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon))  \varepsilon a^t \cdot G(y^{t-1}).$$
That is, in each round, $\mbox{Lmax}(y^t)$ can't increase by more than $\varepsilon(1+O(\varepsilon))$ times your payoff.
Since $\mbox{Lmax}(\overline 0) = \ln n$,
this maintains the invariant that $\mbox{Lmax}(y^t)$
is at most your total payoff times $\varepsilon(1+O(\varepsilon)$,
plus $\ln(n)$.
On the other hand, your regret in comparison to the best expert $i$
is $\max_i \sum_t a^t_i$, i.e., $\varepsilon^{-1} \max_i y^t_i$,
which is in turn at most $\varepsilon^{-1} \mbox{Lmax}(y^t)$.

Thus, your regret is at most $\varepsilon^{-1} \ln(n)$, plus $O(\varepsilon)$ times your total payoff.

Remark: I think, as Freund and Schapire point out, a "boosting" algorithm (in learning theory) is also implicit in this analysis.  See their paper for more details.

Minimizing total payoff

You can derive a similar strategy for the setting where the goal is to minimize,
rather than maximize, the total payoff.
Your regret, which you still want to minimize, is $\sum_t p^t\cdot a^t - \min_i a^t_i$.
In that case, the corresponding strategy is to choose $p^t$ to be the gradient of $\mbox{Lmin}(y^t)$.
With this strategy your regret is again at most
$\varepsilon^{-1} \ln n$ plus $O(\varepsilon)$ times your total payoff.

Connection to Lagrangian-relaxation algorithms

To see the connection to Lagrangian-relaxation algorithms, fix a Set-Cover instance.
Consider the latter type of game (with the goal of minimizing payoff),
where the experts correspond to the elements $e$ of your set system.
In each round, choose the probability distribution $p^t$
to be the gradient of Lmin$(y^t)$ as above,
and have the adversary choose the payoff vector $a^t$ as a function of $p^t$ as follows:
choose the set $s^t$ maximizing $\sum_{e\in s} p^t_e$,
then let $a^t_e = 1$ if $e\in s^t$, and $a^t_e = 0$ otherwise.

Given the correct stopping condition (discussed below),
this process gives you exactly the Set-Cover algorithm discussed at the start.

The performance guarantee of the algorithm follows from the regret bound as follows.
Let $X_s$ be the number of times the adversary chose set $s$ during the play.
Let $x^*$ be the optimal fractional set cover.
Let $T=|X_s|$ be the number of rounds played.
The regret bound implies
$$\textstyle \sum_t a^t\cdot p^t \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$

Using the definition of $a^t$, the $t$th payoff
(the $t$th term in the sum on the left)
equals $\sum_{e\in s^t} p^t_e$.
The adversary chose $s^t$ to minimize this payoff.
If the adversary had instead chosen $s^t$ randomly
from the distribution $x^*/|x^*|$, the expectation of
the payoff would have been
$$ \sum_s \frac{x^*_s}{|x^*|} \sum_{e\in s} p^t_e
~=~
\frac{1}{|x^*|} \sum_e p^t_e \sum_{s\ni e} x^*_s
~\ge~
\frac{1}{|x^*|} \sum_e p^t_e
 ~=~
\frac{1}{|x^*|}.$$
(Above we use that $\sum_{s\ni e} x^*_s \ge 1$ for all $e$, and $|p^t| = 1$.)
Since each payoff is at least $1/|x^*|$, the regret bound implies
$$ \frac{T}{|x^*|} \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$
By the definition of $X$,
we have $|X| = T$ (each round chooses one set),
and $\sum_t a_e^t = \sum_e [e\in s^t] = \sum_{s\ni e} X_s$,
giving
$$\frac{|X|}{|x^*|} \le  \varepsilon^{-1}\ln(m) +\min_e \sum_{s\ni e} X_s.$$
We make the process stop when $\min_e \sum_{s\ni e} X_s = \Omega(\varepsilon^{-2}\ln m)$,
so then (rearranging terms)
$$\frac{|X|}{\min_e \sum_{s\ni e} X_s}~ \le~ (1+O(\varepsilon)|x^*|.$$
That is, normalizing $X$ gives a fractional set cover
of size at most $(1+O(\varepsilon))$ times optimum.

Remark: In a sense, this learning theory interpretation
generalizes the algorithmic interpretation.  However, some
of the algorithmic techniques necessary for efficiency
(such as non-uniform increments and dropping satisfied
covering constraints) don't seem to carry over into the
learning theory setting naturally.  Likewise, algorithms for
mixed packing and covering LPs (e.g. these)
don't seem to have natural analogues in the learning-theory setting.


Planar graph via the intersection of fat thingies?

You didn't say the fat objects had to be two-dimensional, did you? Felsner and Francis prove that it's always possible with axis-parallel cubes in 3d. But, the proof involves Schramm's generalizations of Koebe-Thurston-Andreev, so it's not exactly a simpler result. They also mention along the way that for four-connected maximal planar graphs it's possible to use parallel-sided equilateral triangles.


In the streaming model, any constant approximation of the maximum requires $\Omega(N)$ space. Showing this for a small enough constant approximation follows by an easy reduction from the disjointness problem in two-party communication complexity. This is now very standard, but I will describe it below anyways.

Recall that in the disjointness problem Alice is given a binary string $x \in \{0, 1\}^N$, and Bob is given a string $y \in \{0, 1\}^N$, and they want to decide whether $x$ and $y$ have disjoint support. It is a classic result that this task requires that Alice and Bob exchange at least $\Omega(N)$ bits, even if they share random bits and only want to succeed with probability $2/3$ over the choice of randomness.

Assume there is a randomized streaming algorithm $A$ with space complexity $S$, which with probability $2/3$ computes a number $a$ such that $\frac{a}{F_\infty} \in (\frac{2}{3}, \frac{4}{3})$, where $F_\infty$ is the true maximum frequency of the $N$ elements. This gives a protocol for the disjointness problem with $S$ bits of communication, and therefore $S = \Omega(N)$. In the reduction, Alice simulates the algorithm $A$ and feeds it a stream which increases the frequency of element $i$ by $1$ for each $i$ such that $x_i = 1$. Then Alice takes the memory state of $A$ (which has only $S$ bits) and sends it to Bob, who then simulates $A$ starting from the state he received from Alice and feeds it a stream which increases the frequency of $i$ by $1$ for each $i$ s.t. $y_i = 1$. Then Bob decides that $x$ and $y$ have disjoint support if the output $a$ of $A$ is at most $4/3$.

For more information, see Alon, Matias, and Szegedy's beautiful paper, which introduced the streaming model and proved the first lower bounds.


Graph partitioning, balancing on within subset edge weights

The problem is called GRAPH CONDUCTANCE, and the best algorithm is by Arora et al.

  Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): (2009)

This is a more accessible version, by the same authors:

  Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)


Graph theory: definiton of the crown of a graph

Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ contain an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf


Möbius values of CNF and DNF lattices of a monotone Boolean function

OK so, more than one year later, here is the answer to this. We'll see Boolean valuations $\nu$ as the set of variables that are mapped to $1$.

We can show that $\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)^k \mu_\text{dnf}(\hat{0},\hat{1}) =  \sum_{\nu \models \phi} (-1)^{|\nu|}$.
In the literature, the quantity $\sum_{\nu \models \phi} (-1)^{|\nu|}$ is also called the Euler characteristic of $\phi$.

I'll only show that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$, because the proof is similar for $\mu_\text{dnf}(\hat{0},\hat{1}) = (-1)^k \sum_{\nu \models \phi} (-1)^{|\nu|}$.

Let $w \in \mathbb{R}$ be a weight. Define the mass of a valuation $\nu$ under $w$ as $m_w(\nu) = w^{|\nu|} (1-w)^{|\langle k \rangle \setminus \nu|}$, and the mass of $\phi$ under $w$ as $M_w(\phi) = \sum_{\nu \models \phi} m_w(\nu)$. (when $w \in [0,1]$ this can be seen as a probability.)

Define the functions $f,g: L_{\text{cnf}} \to \mathbb{N}$ by:

$f(d_\mathbf{s}) = M_w \left( (\lnot \bigvee_{i \in \mathbf{s}} C_i) \land \bigwedge_{i \in \langle k \rangle \setminus \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy exactly the (disjunctive) clauses $C_i$ for $i \in \mathbf{s}$.
$g(d_\mathbf{s}) = M_w \left( \lnot \bigvee_{i \in \mathbf{s}} C_i \right)$; in other words the total mass of the valuations that do not satisfy at least the clauses $C_i$ for $i \in \mathbf{s}$.

We have $g(x) = \sum_{u \leq x} f(u)$ for all $x \in L_{\text{cnf}}$. So by Möbius inversion formula $f(x) = \sum_{u \leq x} \mu_\text{cnf}(u,x) g(u)$.
    Moreover, for $u = d_\mathbf{s} \in L_\text{cnf}^\phi$, we have that $g(u) = (1 - w)^{|d_\mathbf{s}|}$.
    Now, since $M_w(\phi) = f(\hat{1})$ are the same polynomials in $w$, by identifying the coefficients of $w^{k+1}$ we get that $\mu_\text{cnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$.


SHORT ANSWER:
It is unknown whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

LONG ANSWER:
First of all, you refer to Bailey, Dalmau and Kolaitis, and their work on "Phase Transitions of $\mathsf{PP}$-complete Satisfiability Problems" in your question. Let me quote them:

'It is also worth noting that, although $\mathsf{MAJORITY \ SAT}$ is  $\mathsf{PP}$-complete, it is not known whether there is an integer $k \geq 3$, such that $\mathsf{MAJORITY}$ $\mathsf{kSAT}$ is $\mathsf{PP}$-complete.'

[http://www.sciencedirect.com/science/article/pii/S0166218X06004665 ]

It is, indeed, correct that Cook-Levin reduction is parsimonious and produces a 3CNF from a given CNF. As $\mathsf{\#CNF}$ is $\mathsf{\#P}$-complete, it immediately follows that $\mathsf{\#3CNF}$ is also $\mathsf{\#P}$-complete under parsimonious reductions. However, as already pointed in a comment, parsimonious reductions do not preserve majority. These reductions introduce auxiliary variables to reduce the size of the clauses, but in turn, these auxiliary variables increase the total number of assignments. For instance, consider the 4CNF which consists of a single clause:

$
\phi = (x_1 \vee x_2 \vee x_3 \vee x_4)
$

which is transformed into

$
\phi'=(x_1 \vee x_2 \vee y) \wedge (y \leftrightarrow (x_3 \vee x_4))
$

using the auxiliary variable $y$ and finally to the 3CNF

$
\psi= (x_1 \vee x_2 \vee y) \wedge (\neg y \vee x_3 \vee x_4) \wedge (y \vee \neg x_3 ) \wedge (y \vee \neg x_4).
$

This transformation clearly preserves the model count, but it is easy to see that the majority is not preserved. $\phi$ has 15 satisfying assignments out of 16 assignments whereas $\psi$ has 15 satisfying assignments out of 32 assignments. In the former, majority satisfiability holds whereas in the latter  majority satisfiability does not hold.

Therefore, NO, the proof that #3CNF is $\mathsf{\#P}$-complete can not be adapted to prove that $\mathsf{MAJ3CNF}$ is $\mathsf{PP}$-complete? It remains open whether $\mathsf{MAJ3CNF}$ is a $\mathsf{PP}$-complete problem under many-one reductions.

$\mathsf{MAJ3CNF}$ does not give much of an insight between the differences of $\mathsf{\#P}$ and $\mathsf{PP}$. Actually decision decision variant of $\mathsf{\#3CNF}$, say $\mathsf{D\#3CNF}$, is defined as follows: given a CNF $\phi$ and a number $m \geq 0$, decide whether $\phi$ has at least $m$ satisfying assignments. Note that for $\mathsf{D\#3CNF}$, we do not care about majority. Thus, we can transform any CNF into 3CNF using a parsimonous reduction, which proves that $\mathsf{D\#3CNF}$ is $\mathsf{PP}$-complete under many-one reductions. $\mathsf{MAJ3CNF}$ is simply a different problem than $\mathsf{D\#3CNF}$.


Paths of length $p$ in a Graph, $p$ a prime

The problem (let me call it $s$-$t$-prime-connectivity) is in P; more precisely, it is NL-complete.
NL-hardness is clear: we can reduce plain $s$-$t$-connectivity to $s$-$t$-prime-connectivity just by making sure that every vertex has a self-loop. Then, if there is any path from $s$ to $t$, there are paths of arbitrary lengths $\ge n$, and in particular, of prime lengths.
In order to check $s$-$t$-prime-connectivity in NL, we may use the following characterization, based on an idea of Yonatan N from the comments above:

Theorem. For any directed graph $G=(V,E)$ of size $n=|V|$, and $s,t\in V$, the following are equivalent:

There is a path from $s$ to $t$ of prime length $p>n$.

There are a simple cycle $C$ of length $d\le n$, and a path $P$ from $s$ to $t$ of length $a$ coprime to $d$ that intersects $C$.

There are $C$ and $P$ as in 2, where $a\le2dn\le2n^2$.

There is a path from $s$ to $t$ of prime length $p>n$, $p=n^{O(1)}$.

Proof:
$1\to2$: Let $P$ be a prime-length path from $s$ to $t$. If it has length $p>n$, it includes a simple cycle $C$; clearly, the length of $C$, being $\le n$, is coprime to $p$.
$2\to3$: Let $u$ be a vertex common to $P$ and $C$. Write $P$ as the concatenation of paths $P_0$ from $s$ to $u$, and $P_1$ from $u$ to $t$. It suffices to show that there is a path $P'_0$ from $s$ to $u$ whose length is at most $dn$, and congruent to the length of $P_0$ modulo $d$; and similarly for $P_1$.
This can be shown by the pigeonhole principle: if the length of $P_0$ is $\le dn$, we are done. Otherwise there are two occurrences of the same vertex in $P_0$ whose positions in $P_0$ modulo $d$ are the same; in other words, $P_0$ includes a cycle whose length is a multiple of $d$. We may delete this subcycle from $P_0$. We repeat this process until the length of the path drops below $dn$.
$3\to4$: We may assume $a>n$. By Linnik’s theorem, the arithmetic progression $a,a+d,a+2d,\dots$ contains a prime $p$ of magnitude polynomial in $n$; $p$ is the length of a path from $s$ to $t$ consisting of $P$ and several repetitions of $C$.
$4\to1$ is trivial.
QED
Condition 4 gives directly an NL-algorithm for $s$-$t$-prime-connectivity: nondeterministically guess a prime $p\le n^c$ (where $c$ is the implied constant), and a path from $s$ to $t$ of length $p$.
In fact, already condition 2 gives an NL-algorithm: nondeterministically choose to either guess a prime $p\le n$ and a path from $s$ to $t$ of length $p$, or: $d\le n$, a vertex $u$, a cycle of length $d$ starting from $u$, and a path from $s$ to $t$ passing through $u$, of length coprime to $d$. The space required by the algorithm consists of a constant number of vertices, the number $d$, and the length of the path being guessed modulo $d$; these all fit in $O(\log n)$ bits.


Construction of graphs where every pair of vertices have an unique common neighbor

If you get rid of the "no vertex of degree $n-1$" condition, the graphs with the property that every two vertices have exactly one common neighbor are exactly the friendship graphs (a set of triangles glued together at a common vertex); as the linked article describes, this is a theorem of Erdős, Rényi, and Sós. But obviously, all such graphs have a vertex of degree $n-1$; the only regular one is a triangle. So the answer to your question is that, no, a graph with the common neighbor property and without a degree-$n-1$ vertex does not exist.


Independent Node Degree in Undirected Graphs

Concerning the third question, triangle-free graphs have $\Delta^i(G) = \Delta(G)$. From Turán's theorem, we know that the maximum number of edges on a triangle-free graph is $\big\lfloor\frac{n}{4}\big\rfloor$, and this bound is tight for the complete bipartite graph $K_{n/2,n/2}$. Hence, at least in this case, you can have a dense graph with a large independent node degree, namely $d^i(v) = \frac{n}{2}$ for all $v$.


Free books (or course materials) on undergraduate algorithms

Jeff Erickson's lecture notes on Algorithms are free, with a Creative Commons license. Other than Algorithms, this site also contains lecture notes for Models of Computation, which are also with a CC license.


Which model of computation is "the best"?

I have always considered the standard Word RAM model to be "the best" in your sense. Everybody who learned to program in a language like C (or any loose equivalents like Java, etc) has precisely this model in mind when they think of a computer.

Of course, you sometimes need generalizations depending on the regimes in which you work. The external memory model is an important one to keep in mind. It applies not only when you work with disks, but also in understanding (forcing you to care about) cache. Of course, treating it too seriously can also lead to nonsensical results, since the pure external memory model doesn't count computation. Another generalization of the Word RAM is to parallelism, but there we are all a bit confused at the moment :)

An algorithm with an $O(n)$ running time will certainly run faster than one with $O(n \lg n)$ running time. It is a mathematical fact that the former is faster for large $n$ :) Your problem size may simply not be large enough for this to matter. Since you bring up sorting, let me assure you it will be very hard to beat radix sort with a comparison-based algorithm for reasonable $n$.

A final remark on algorithms and "reality": always keep in mind what you're trying to achieve. When we work in algorithms, we are trying to solve the hardest problems out there (e.g. SAT on 50 variables, or sorting a billion numbers). If you're trying to sort 200 numbers or solve SAT on 20 variables, you don't need any fancy algorithm. That's why most algorithms in reality are kind of trivial. This doesn't say anything bad about algorithmic research — we just happen to be interested in that unusual 1/1000 of the real problems that happen to be hard...


Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

According to this abstract, deciding whether a 4-regular planar graph has a Hamiltonian Path is NP-complete.

Edited to add: Call a path that is allowed to revisit nodes a walk. Let $G$ be a graph on $n$ vertices and let us impose a weight of 1 on each edge. Then, $G$ has a Hamiltonian path if and only if the minimum weight walk in G visiting each vertex has weight $n-1$. In other words, if you can compute the minimum weight of a Hamiltonian walk, you can can detect the existence of Hamiltonian paths.


What is schema theory within Genetic Algorithms

If I remember correctly (it's years since I last studied this), schema theory isn't really used for anything.  Rather, it's an attempt to explain why genetic algorithms seem to work well.  As I'm not an expert, I can only point you to a book that I remember reading about schemata, Melanie Mitchell's book


Where do people publish/submit their work on type theory?

You can follow the activities of the EUTypes network, and see what meeting are organized. The list of events is growing nicely. As for journals, I can think of Logical Methods in Computer Science and Mathematical Structures in Computer Science. I can also think of some journals which are owned by you know who, so not mentionable.


This idea, known as Time loop logic has been investigated by Moravec, Deutsch and Aaronson.


"Is it reasonable to expect reduction from ..."

unambiguous$\Pi$ to unambiguousSAT  ?

Yes, since SAT is NP-hard under reductions that preserve the number of solutions.

"and vice versa" ?
$\Pi$ is NP-complete and you've assumed that U$\Pi$ "has a randomized reduction from $\Pi$", so there is

a randomized reduction from USAT to U$\Pi$, since there's one from SAT to U$\Pi$.  For most natural problems, if U$\Pi$ is non-trivial then one can find a simple reduction from SAT to $\Pi$ that preserves number of solutions.  In particular, it's reasonable to expect a reduction from USAT to U$\Pi$.  However, I have no clue regarding whether-or-not there's necessarily

a better reduction from USAT to U$\Pi$ (than the one from $\Pi$ to U$\Pi$).

"Would that mean promiseNP has a complete problem?"  Yes, since it follows

from NP having complete languages that promiseNP unconditionally does too.

"In general if" unambiguousSAT "is in RP then NP=RP."

"Can we get something similar for" unambiguous$\Pi$?

Yes, as follows:

By NP-hardness of U$\Pi$ under randomized reductions,  NP $\subseteq$ BPP .    By search-to-decision, probabilistic polynomial-time algorithms can solve all of FNP.  By the definition of FNP,

one can efficiently deterministically check whether-or-not an alleged witness is valid.

Finally, if there are no valid witnesses, then one cannot incorrectly find such a witness.


a polynomial representation of boolean functions

Well done on your independent discovery.

This is a Hadamard matrix of Sylvester type, written in a different order. There is a massive literature on this topic. It is used in coding theory, cryptography, is directly related to Reed-Muller codes of degree 1, it can be used to obtain best affine approximations of functions, etc.

Ryan O'Donnell's notes on Analysis of Boolean functions available here which are now published as a book, Claude Carlet's chapters on Boolean
functions here are easily accessible online.

Just use the order $[1,X,Y,XY,Z,ZX,ZY,ZXY]$ which corresponds to lexicographic order over the integers, and apply the corresponding permutation to the columns as well.

In that order your matrix is simply the 3-fold Kronecker product $$H_2 \otimes H_2\otimes H_2$$of the basic 2 by 2 Hadamard matrix.

$$
H_2=\left(\begin{array}{cc} 1 & 1 \\ 1 & -1 \end{array}
\right),
$$

This paper considers efficient evaluation of Hadamard representation coefficients.


Since the figure is otherwise mostly symmetric, I believe the 3 I mentioned two sentences ago should be replaced with a 1.

Indeed, the 3 is obviously a typo.

  However, even if that is done, I do not see any way to determine the status of the zs even after...

  Am I missing something here?

After $r$ is revealed:

If it was a mine, you can reveal the numbers on the fields occupied by $r'$.
If it was not a mine, you can reveal the numbers on the fields occupied by $r$.

In both cases, you can deduce the status of the $z$s from the revealed numbers.


Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

EDIT 2: Updated the answer for the updated definition of typical.

I may be misunderstanding your definition of $P^*_{B'}$.  With that caveat, though, I believe your conjecture does not hold.  The proof is in two steps.

Lemma 1. For some $c_0>0$, for all $n>0$, there are strings $B$ and $B'$ such that $K(P^*_{B'} | B) \le c_0$ and $K(P^*_{B'}) = \ell(B) \ge n$.

Proof sketch.  Let $c_0$ be the length of any universal TM. Fix any $n>0$.

Fix any string $B'$ such that $K(P^*_{B'}) \ge 2n$.  (We discuss below our assumption that $B'$ exists.)
Let $B$ be the shortest program that generates $P^*_{B'}$, so that $K(P^*_{B'}) = \ell(B)$.
And $K(P^*_{B'} | B) \le c_0$, because given input $B$, the universal TM outputs $P^*_{B'}$.

Here's the justification for Step 1.  If $B'$ does not exist, then there are only finitely many minimal Kolmogorov structure functions.  I assume this is known not to hold, because otherwise $I(B : P^*_{B'}) \le K(P^*_{B'}) = O(1)$ for all $B$ and $B'$, and the conjecture would be trivially true (for some constant, at least).  Also, the post states "On the other hand, in the case of atypical $B$s, the length of $P^*_{B}$ may be significantly larger than $C$." Perhaps someone who knows more about this topic could confirm that there are infinitely many minimal Kolmogorov structure functions. $~~\Box$

This concludes the proof sketch for Lemma 1.  Next we show that the conjecture does not hold.

Lemma 2. For any $c > 0$, there are $\epsilon>0$ and a string $B'$ such that, for all sufficiently large $n$, for a random $n$-bit string $B$, with probability at least $\epsilon$, $I(B : P^*_{B'}) \ge c$.

Proof. Fix any $c> 0$.  Assume WLOG that $c\ge c_0$ from Lemma 1, and $c + \log(c) + c_1 + c_2 \le 2c$ for fixed constants $c_1, c_2$ defined in Steps 4 and 5 below. (Otherwise just increase $c$.)

Fix strings $B_0$ and $B'$ such that $K(P^*_{B'} | B_0) \le c$ and $K(P^*_{B'}) = \ell(B_0) \ge 4c$. (These exist by Lemma 1.)
Let $\epsilon=2^{-\ell(B_0)}$.  Consider any $n\ge \ell(B_0)$ and let $B$ be a random $n$-bit string.
The event that $B_0$ is a prefix of $B$ happens with probability at least $\epsilon$.  Assume this event occurs. To complete the proof we show that $I(B:P^*_{B'}) \ge c$.
First note that $$K(P^*_{B'} | B) \le K(P^*_{B'} | B_0) + K(B_0 | B) + c_1$$ (for some fixed $c_1$) because, given $B$, we can compute $B_0$ from $B$, then compute $P^*_{B'}$ from $B_0$.
Using $K(P^*_{B'} | B_0) \le c$ (from Step 1), and $K(B_0|B)\le \log \ell(B_0) + c_2$ (for some fixed $c_2$, using a TM that truncates its input $B$ to its first $\ell(B_0)$ bytes), this implies $$K(P^*_{B'} | B) \le c + \log \ell(B_0) + c_1 + c_2 \le \ell(B_0)/2.$$
(Using above our assumptions on $c$ and $\ell(B_0) \ge 4c$ from Step 1.)
Using this and $K(P^*_{B'}) = \ell(B_0) \ge 4c$ (from Step 1), we have $$I(B : P^*_{B'}) = K(P^*_{B'}) - K(P^*_{B'} | B) \ge \ell(B_0) - \ell(B_0)/2 \ge 2c.$$ $\Box$

I guess this completes the proof, but I'm unsure whether I've properly interpreted the post, because of the following statement in the post "the $P^∗_{B′}$ is provided with $n=\ell(B)$, in this case, since the goal is to generate $B$."  I'm not sure what it this means, as it seems to contradict the earlier definition of $P^*_{B'}$ in the post (which is used in the proof above).


If you look at things from a model-theoretic perspective, the basic ingredients you have are atoms, relations, and functions. Atoms could be modelled using nodes of the graph, and binary relations and single argument functions could be modelled using graphs. If you are willing to allow hyper-edges in your graph, then the remainder of the relations and functions can be modelled.

I don't think that there is anything deep to this observation.


The chromatic number of a graph as a functor

Sure, category theorists know such things, but I think for the difficult results that graph theorists care about, the generalities of category theory may at best help as an organizing principle. This is a bit similar to the theory of combinatorial species, which is a way of doing combinatorics inspired by category theory.

Here are some other basic observations, you can read more about such things in Lawvere's Qualitative distinctions between some toposes of generalized graphs, Categories in computer science and logic (Boulder, CO, 1987), volume 92 of Contemporary Mathematics, 261–299. American Mathematical Society.

The category of directed graphs is a presheaf topos on the site consisting of two parallel arrows (so that a presheaf is given by two sets $E$ and $V$ and maps $t : E \to V$ and $s : E \to V$), see A Guided Tour in the Topos of Graphs by Sebastiano Vigna.

For any given $n$, the category of $n$-colored graphs is a topos, because it is just the slice of the topos of graphs over the complete graph on $n$ vertices (an $n$-coloring of $G$ is just a morphism $G \to K_n$).

As Lawvere explains, several other categories of graphs are toposes because they are (equivalent to) toposes of monoid actions for a suitably chosen $M$. Let's just do one. Consider the monoid $M$ of endomaps on $2 = \{0,1\}$. There are four maps $2 \to 2$, we give them names: the identity map $i$, the constant map $0$, the constant map $1$, and the twist map $t$.

An object in the topos of $M$-sets is a set $S$ with a right $M$ action, which is a map $s : S \times M \to S$ satisfying $s(x, i) = x$ and $s(x, f \circ g) = s(s(x, f), g)$. Since there are only four elements in $M$, we might as well figure out what this means. Let $S_0 = \{x \in S \mid \exists y \in S \,.\, x = s(y, 0)\}$ be the set of those elements of $S$ that arise as actions of~$0$. We define $S_1$ similarly. Because $0 \circ g = 0$, it follows for every $g \in M$ and $x \in S_0$ that
$$s(x, g) = s(s(y,0), g) = s(y, 0 \circ g) = s(y, 0) = x.$$
So, the elements of $S_0$ are fixed by the action. Similarly, the elements of $S_1$ are fixed by the action.

To every $M$-set $(S,s)$ we associate a graph $G_S$ as follows. The vertices of $G_S$ are the elements of $S_0 \cup S_1$. The half-edges of $G_S$ are the elements of $S$. Given a half-edge $e \in S$, its source is the vertex $s(e, 0)$. The opposite half-edge of $e$ is $S(e, t)$, and because $t \circ t = 1$, tit follows that the opposite of the opposite is the original half-edge. An edge is a half-edge together with its opposite. The target of a half-edge is the source of its opposite half-edge, i.e., the target of $e$ is $s(s(e,t),0) = s(e,1)$. (There is an anomaly which we allow: a half-edge may be its own opposite.)

What sort of graphs did we get? They are symmetric graphs in which each edge consists of two half-edges. An edge may be degenerate when it is composed of two copies of the same half-edge. In addition, the graphs are reflexive in the sense that each vertex has a distinguished degenerate loop starting and ending at the vertex (this is because $S_0 \cup S_1 \subseteq S$).

Exercise: figure out what the morphisms are, and then show that the description in terms of reflexive symmetric graphs gives a category that it equivalent to the topos of $M$-sets.

Is this the sort of thing you were asking about?


As far as I can tell, UniqueSAT is exponentially dense, in the sense that it contains $2^{\Omega(n)}$ instances of size $n$. (This is a stronger requirement than $2^{n^\varepsilon}$ for infinitely many $n$.)
The following argument works even for the revised definition of "dense" introduced in version 5 of the question, where all instances of size up to $n$ are taken into account.  Note that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$.

Consider formulas in CNF with $v$ clauses, each clause containing exactly one literal, such that each variable occurs precisely once in the formula.
An example of such a "complete 1-SAT" formula for $v=3$ is $x_1\land x_2 \land \lnot x_3$, completely specifying the solution $x_1 = 1, x_2 = 1, x_3 = 0$.

We establish an exponential lower bound for the number of complete 1-SAT formulas of size $n$.
Logarithms are base 2.

Complete 1-SAT formulas each have precisely one solution, and with $v$ variables such a formula has size $v(1+\log v)$.
There are also $2^v.v!$ distinct complete 1-SAT formulas over $v$ variables.

We then just need to ensure that $v$ is as large as possible in terms of the instance size $n$.

Let $v = n/(\log n)^\delta$ for some $\delta = \delta(n)$.
For the size of complete 1-SAT formulas with $v$ variables to be precisely $n$ bits, we require that
$n = v(1+\log v)
= (n/(\log n)^\delta)(1+\log n - \delta\log\log n)$
so $1+\log n - \delta\log\log n = (\log n)^\delta$.
We can always choose $\delta$ appropriately to satisfy this expression; note that $1/2 < \delta < 1$ for large enough $n$, with $\delta \to 1$ as $n \to \infty$.

This already shows that there are at least $2^{n/\log n}$ such instances, so UniqueSAT is not sparse.

Moreover, the high order term of the exponent of $2^v.v!$ is then $n[(u/(1+u))-(\log e - 1)]$, where $u = \log n - \delta \log\log n$ and $\log e - 1 \approx 0.4427$.
(For instance, this follows from Robbins' bounds for the factorial function, $\log n! = n\log n - n\log e + 0.5\log n +r_n\log e + 0.5(1+\log \pi)$, where $1/(12n+1) < r_n < 1/(12n)$ for $n \ge 1$.)
Now $u/(1+u) > 1/2$ for large enough $n$, so there are $2^{\Omega(n)}$ complete 1-SAT instances, and hence $2^{\Omega(n)}$ UniqueSAT instances.


No.  Conjunctions of Horn clauses admit least Herbrand models, which disjunctions of positive literals don't.  Cf. Lloyd, 1987, Foundations of Logic Programming.

Least Herbrand models have the property that they are in the intersections of all satisfiers.  The Herbrand models for $(a \lor b)$ are $\{\{a\}, \{b\}, \{a,b\}\}$, which doesn't contain its intersection, so as arnab says, $(a \lor b)$ is an example of a formula which can't be expressed as a conjunction of Horn clauses.

Incorrect answer overwritten


Conditional Dependencies in Compiler Semantic Analysis Passes

In general, mutual recursion is the problem you are facing: some languages support it, some don't. The fact is that you can always compile mutual recursion away to simple recursion, using pairs of results instead of a simple result here is an explanation.

The laziness can also be compiled away, by creating thunks, or functions with void argument.

It turns out that in C, mutual recursion is allowed, so only the second trick is required.

int cond = 0;

int if_X(void){
  if(cond){return 0;} else {return Y();}
}

int X(void) {
  return if_X();
}

int if_Y(void){
  if(cond){return X();} else {return 1;}
}

int Y(void){
  return if_Y();
}


Takens himself did some CS work although not TCS work. He did some attractor reconstruction stuff with neural networks, for example (https://clgiles.ist.psu.edu/papers/NC-2000-learning-chaos-nn.pdf) and it does use his embedding theorem to suggest nonlinear autoregressive (time delay) neural nets, and look towards actual recurrent networks.

Overall, dynamical systems is closest to CS in neural network land because of the easy dynamical interpretation of the models. Try some of the Ganguli gang's publications (https://ganguli-gang.stanford.edu/pubs.html), esp. Exponential expressivity in deep neural networks through transient chaos

  apparently there have been recently methods designed to find these in a more automated way

Again, not theoretical, but I've used them for non-example time series data and they aren't incredible in practice, by the way. The denoising aspects of them is actually quite difficult.


Is Church-pentation implementable in Agda?

According to the paper you linked, I think the answer to the question you want to ask is, "no." Pentation is not definable in a stratified version of system F.

The paper says that their system can define every super-elementary function, and all definable functions are super-elementary. The super-elementary functions are level $\mathcal{E}^4$ in the Grzegorczyk hierarchy, and according to wikipedia, moving to the next hyper-operation requires one additional step in that hierarchy. So, $\mathcal{E}^4$ contains tetration, products and sums of tetration, and finite compositions of tetration, but pentation isn't included until $\mathcal{E}^5$. So it is beyond the capabilities of the stratified system F.

This also answers your other question (of course), because the union of all levels in the Grzegorczyk hierarchy is exactly the primitive recursive functions, and the Ackermann function is not primitive recursive. So it cannot be defined.

Now, Agda of course is capable of defining pentation (and the Ackermann function), because any Church numeral can be used to get an equivalent value of the inductively defined natural numbers, and then those can be used to compute the function and converted back to a Church numeral. But presumably that's not what you're interested in.

However, there is also another possibility. Agda's predefined universes are closed under induction-recursion. This means that (in a way) they contain universes of their own, and far, far more universes than exist in the predicative system presented in the paper (which only has $\omega$ many universes, I believe). You can of course define Church numerals for each of these universes. But, I do not know what effect adding quantity of universes (and ignoring structure besides Pi types) has on the ability to define functions on the Church numerals.

Edit:

I did some additional investigation to expand on my last idea, and was able to define pentation of Church numerals. Here is some code, with explanations.

module Pent where

open import Function
open import Level hiding (suc)
open import Data.Unit

import Data.Product
import Data.Nat as N
open N using (ℕ)

Most of this is just for convenience. I won't be cheating with the natural numbers, but they're easier to visualize at the end.

The following exhibits Set as a Mahlo universe. This means that for any A : Set and B : A → Set, there is a universe U : Set that is itself closed under A and B

module Mahlo (A : Set) (B : A → Set) where
  data U : Set
  T : U → Set

  data U where
    A' : U
    B' : A → U
    Π : (s : U) (f : T s → U) → U

  syntax Π s (λ x → t) = Π[ x ∈ s ] t

  T A' = A
  T (B' a) = B a
  T (Π s f) = (x : T s) → T (f x)

  infixr 4 _⇒_
  _⇒_ : U → U → U
  a ⇒ b = Π[ _ ∈ a ] b

I haven't included any universe structure in U besides Pi types. But this means that we can define the type of Church numerals over U, and easily build up to exponentiation of such numerals:

  CH : Set
  CH = (r : U) → (T r → T r) → T r → T r

  zro : CH
  zro r s z = z

  suc : CH → CH
  suc m r s = s ∘ m r s

  one : CH
  one = suc zro

  infixl 10 _+_
  _+_ : CH → CH → CH
  (m + n) r s = m r s ∘ n r s

  infixl 20 _×_
  _×_ : CH → CH → CH
  (m × n) r = m r ∘ n r

  infixr 30 _^_
  _^_ : CH → CH → CH
  (m ^ n) r = n (r ⇒ r) (m r)

However, that is where we get stuck for 'generic' universes about which we know nothing but that they have Pi types (i.e. we don't really know anything about A and B).

Next we define Church numerals valued in arbitrary Set levels:

CHURCH : (α : Level) → Set (Level.suc α)
CHURCH α = ∀(R : Set α) → (R → R) → (R → R)

It is possible to define tetration of CHURCH zero as follows:

_↑_ : CHURCH zero → CHURCH zero → CHURCH zero
(m ↑ n) R s z = n CH (_^_ m') one R' s z
  where
  open Mahlo R (const ⊤) renaming (A' to R')

  m' : CH
  m' = m CH suc zro

So, this might not look like anything special is going on, but it's actually a bit crazier than it first appears. We have two Church numerals over Set, and R : Set that is our result type. So, we use the fact that Set is Mahlo to find a universe U inside Set that contains R. This means that Church numerals over U also live inside Set, which means we can 1) lower our big church numeral m into them, and 2) repeatedly exponentiate the lowered numeral by itself n times. And since U contains R, the numeral we construct is able to iterate the R → R function on the R value to give our answer.

Now, since tetration is defined with a uniform type, it's easy to define pentation as you defined tetration:

_⇈_ : CHURCH zero → CHURCH (Level.suc zero) → CHURCH zero
(m ⇈ n) = n (CHURCH zero) (_↑_ m) (λ R s z → s z)

If you want to visualize the results, you can use the following:

module Visualize where
  open Data.Product

  toCH : ∀{α} → ℕ → CHURCH α
  toCH 0 R s z = z
  toCH (N.suc n) R s z = s (toCH n R s z)

  fromCH : ∀{α} → CHURCH α → ℕ
  fromCH m = lower $ m (Lift _ ℕ) (lift ∘ N.suc ∘ lower) (lift N.zero)

  lift₀ : (CHURCH zero → CHURCH zero → CHURCH zero) → ℕ → ℕ → ℕ
  lift₀ op m n = fromCH (op (toCH m) (toCH n))

  lift₁ : (CHURCH zero → CHURCH (Level.suc zero) → CHURCH zero) → ℕ → ℕ → ℕ
  lift₁ op m n = fromCH (op (toCH m) (toCH n))

  2↑2 2↑3 2↑4 3↑2 3↑3 : ℕ
  2↑2 = lift₀ _↑_ 2 2
  2↑3 = lift₀ _↑_ 2 3
  2↑4 = lift₀ _↑_ 2 4
  3↑2 = lift₀ _↑_ 3 2
  3↑3 = lift₀ _↑_ 3 3

  2⇈2 2⇈3 : ℕ
  2⇈2 = lift₁ _⇈_ 2 2
  2⇈3 = lift₁ _⇈_ 2 3

  tetr : ℕ
  tetr = 3↑3

  pent : ℕ
  pent = 2⇈3

Note, I got tired of waiting for 3↑3 to finish.

So, just to go back a bit, the universe creation principle I used was basically: for every set $R$ there exists a universe $U$ with $R \in U$, which is basically the Grothendieck universe axiom, except all of these universes are themselves inside the universe Set (and the universes are much weaker than set theoretic universes). But this is actually just scratching the surface of how powerful Mahlo is, because you'll notice I essentially did nothing with the B family. So I'm confident you can go beyond pentation with this. This is just the easiest one step further.

(To expand slightly on the last paragraph, the axiom "there exists a universe $V$ such that for every set $S \in V$ there exists a universe $U \in V$ such that $S \in U$" means (if I understand correctly) that $V$ is related to a 1-inaccessible cardinal/ordinal. But Mahlo cardinals/ordinals are hyper-hyper-hyper-...-inaccessible, which is well beyond that.)

Edit 2:

Here is a simpler development showing how you can define uniform tetration with $\omega+1$ universe levels. It uses the latest Agda to be able to talk about Setω, but you might be able to do it in older Agda versions if you inline CHURCH.

module PentPoly where

open import Level
open import Function
open import Agda.Primitive

module Gen (α : Level) where
  Church : Set (suc α)
  Church = ∀(R : Set α) → (R → R) → (R → R)

  one : Church
  one R s z = s z

  _+_  : Church → Church → Church
  (m + n) R s = n R s ∘ m R s

  _×_  : Church → Church → Church
  (m × n) R = n R ∘ m R

  _^_ : Church → Church → Church
  (m ^ n) R = n (R → R) (m R)

CHURCH : Setω
CHURCH = ∀(α : Level) (R : Set α) → (R → R) → (R → R)

_↑_ : CHURCH → CHURCH → CHURCH
(m ↑ n) α R s z = n (suc α) Church (_^_ m') one R s z
  where
  open Gen α
  m' : Church
  m' = m α

I think the way to think about this is that we're taking advantage of Setω being a limit of the universes below it. So any iteration we are asked to do occurs at some particular level below it, and we can iterate exponentiation one level above that. I think this means that we can get all hyper-operations with 'only' $\omega \cdot \omega$ universes.

I also realized my Mahlo above is wrong. It says that for every family on Set there is a universe (U,T) that contains that family. But Mahlo is actually the property that for every mapping between families of sets, there is a universe such that the mapping restricts to that universe. This looks like:

module Mahlo
    (f₁ : (X : Set) → (X → Set) → Set)
    (f₂ : (X : Set) → (Y : X → Set) → f₁ X Y → Set)
  where

  data U : Set
  T : U → Set

  data U where
    Π : (x : U) → (y : T x → U) → U
    reflect₁ : (x : U) → (y : T x → U) → U
    reflect₂ : (x : U) → (y : T x → U) → f₁ (T x) (T ∘ y) → U

  T (Π x y) = (v : T x) → T (y v)
  T (reflect₁ x y) = f₁ (T x) (T ∘ y)
  T (reflect₂ x y z) = f₂ (T x) (T ∘ y) z

  res : Σ[ x ∈ U ] (T x → U) → Σ[ x ∈ U ] (T x → U)
  res (x , y) = (reflect₁ x y , reflect₂ x y)

But this is even further unnecessary power from the perspective of the original question.


The complexity of checking whether two CNF have the same number of solutions

The problem is coNP-hard; you can easily reduce the UNSAT problem to this problem.

A more precise characterization is that the problem is C=P-complete.  In fact, one definition of the class C=P is that it is the class of problems which are polynomial-time many-one reducible to this very problem (usually this definition is stated in terms of GapP functions).  But since this does not tell much, let me define this class in another way.

Let C=P be the class of problems which are polynomial-time many-one reducible to the following problem: given a boolean circuit φ and an integer K (in binary), decide whether the number of satisfying assignments of φ is equal to K.  By a standard reduction which shows the #P-completeness of #3SAT, we can restrict φ to be a 3CNF formula without affecting the class.  The class C=P contains a class called US, which contains both UP and coNP.

With this definition, your problem is C=P-complete.  Actually, the C=P-hardness is easy to see from the definition of the class C=P (which uses 3CNF formulas).

To prove the membership in C=P, suppose that we are to decide whether two given CNF formulas φ1 and φ2 have the same number of satisfying assignments or not.  Without loss of generality we can assume that the two formulas have the same number of variables, say n.  Construct a boolean circuit φ which takes n+1 bits as input so that the number of satisfying assignments of φ is equal to c1 + (2n − c2), where c1 and c2 be the numbers of satisfying assignments of φ1 and φ2, respectively.  Then the number of satisfying assignments of φ is equal to 2n if and only if c1=c2.


Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.

Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one can obtain the desired permutation using a topological sort, and the corresponding value of $g$ will be the size of the feedback arc set.

Moreover, the problem of deciding whether there is a permutation $\sigma$ with $g(\sigma(x))\leq k$ is in NP: just guess the permutation and compute $g$.


These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.

Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.

So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.


what are known bounds on complexity of nontrivial graph automorphism

Determining if a graph has a nontrivial automorphism Cook-reduces (polynomial time Turing) to Graph Isomorphism (determine if a pair of graphs is isomorphic) (exercise for the reader).  It is not known to be equivalent to graph isomorphism.

In turn, graph isomorphism can be solved in $2^{\tilde O(\sqrt{n})}$ time and lies in $NP \cap coAM$.  In particular, it is not $NP$-complete unless the polynomial hierarchy collapses.


Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why.

(1) Fix a drawing of $K_{3,n}$. Without loss of generality we can assume that no two incident edges cross and that no two edges cross twice, for otherwise we can modify the drawing to eliminate these crossings without hurting the pathwidth. Every $K_{3,3}$ subgraph of $K_{3,n}$ has a crossing, there are $n-2$ ways of extending any particular crossing to a $K_{3,3}$ subgraph, and there are $\tbinom{n}{3}$ $K_{3,3}$ subgraphs. Therefore, the number of crossings is at least $n^2/6$. (Actually a tight bound approximately $n^2/4$ is known but it doesn't change the rest.)

(2) Set $S$ to be the set of all edges in $K_{3,n}$, and consider any linear arrangement of the crossings in the whole drawing. Repeat the following steps:

(2a) Consider the point of that arrangement that bisects the crossings between pairs of edges in $S$. Define an edge of $S$ to be "cut" if all of its crossing points with other edges in $S$ are in the same half of this bisection, and "uncut" otherwise.

(2b) If there are at least $\epsilon n$ cut edges of the drawing (for some suitable constant $\epsilon$), then each of them contributes an edge of the planarization that also crosses the bisection point of the linear arrangement. This shows that the linear arrangement has vertex separation number $\Omega(n)$, but since the pathwidth is just the minimum vertex separation number of a linear arrangement, the pathwidth is also $\Omega(n)$.

(2c) In the remaining case, there are very few cut edges, so most of the crossings in $S$ come from pairs of uncut edges, which must both be on the same side of the bisection.
Almost half of the $S$--$S$ crossings are on each side of the bisection, and at least one of the two sides of the bisection has fewer than half of the edges in $S$. Replace $S$ by the subset of edges on that side and repeat.

(3) Each repetition of steps (2a)–(2c) approximately doubles the density of crossings / pairs of edges in $S$, because the number of crossings is halved and the number of pairs of edges is quartered. This density already starts out constant and can't exceed one. Therefore, after a constant number of repetitions, step (2b) will succeed in finding a linear number of cut edges, showing that the pathwidth is at least linear.

As for your suggestion that bounded-degree bounded-pathwidth graphs have layouts whose planarization has bounded pathwidth: this seems indeed to be true.

Find a linear ordering of the vertices of the given graph with bounded vertex separation number: that is, at each point in a left-to-right sweep of the ordering there should be finitely many vertices left of the sweep point that have neighbors to the right. Draw the graph in a left-to-right sweep of this ordering, with its edges placed on horizontal tracks, with each of the partially completed vertices having a set of $O(1)$ tracks for its remaining edges to be connected to the right. Thus, the total number of tracks is the product of the degree with the pathwidth, $O(1)$. When you reach a new vertex, you can add nearly-vertical connectors to the tracks of other vertices that should be connected to it, and shorter connections to its outgoing tracks. Here's an example, with vertex separation number three, degree three, and three tracks per vertex.

This layout, also, has bounded separation number, because the only crossings are on tracks so there can be at most one vertex with an incomplete neighborhood per track. So the pathwidth of the planarization is also $O(1)$, and more precisely at most proportional to the product of the degree and the original pathwidth.


If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example:

1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly reverse them (e.g. whenever the source TM goes left, the target TM goes right and vice versa).

2a) Consider simulations or bisimulations.

2b) Along similar lines, you can consider when one TM can be transformed (by a computable function) to simulate the other one. This can be done at the level of step-wise behavior, or as Yuval suggested in the comments, at the level of input-output, that is, a morphism from $T_1$ to $T_2$ (or maybe the other way around) is a computable $f$ such that $T_1(x) = T_2(f(x))$ for all $x$.

3) Consider the transition graph of the Turing machine (each vertex is a complete description of the state of the machine and the tapes, with directed edges corresponding to the transitions the TM would make) and consider morphisms of graphs. For TMs this is a very coarse relationship, however, as it essentially ignores the local nature of computation (it ignores, for example, what the contents of the tapes are).

I think the real question is: what is it you want to know about TMs or to do with them? In the absence of this, it's hard to give arguments for any one definition over another, beyond naturality (in the usual sense of the word, not the categorical sense).


What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

Analyzing various gap sequences is very difficult, but it is easy to see that this would require at least approximately $n\cdot\pi(n)\sim n^2/\log(n)$ passes, since you are looping over the entire array once per prime. This makes it worse than some other simple gap sequences, such as $2^n\pm1$ or $(3^n-1)/2$, which are known to take only $\mathcal O(n^{3/2})$ passes. The other issue is the amount of time and space it would take to generate the gap sequence.
Generally a good gap sequence should grow exponentially. Intuitively we want to make $\mathcal O(\log(n))$ loops through the entire array, and with each loop involving as few swaps as possible overall. This would get you closer to $\mathcal O(n\log(n))$ complexity. There's more details on the linked Wikipedia concerning the complexity of shellsort and picking gap sequences.


There is a popular formal system called Lambda calculus. It is Turing complete and has great importance in the theory of programming languages. Lambda calculus is based on anonymous functions with very simple syntax. You start a new function with a $\lambda$, list the arguments, place a dot, and write down the return value. For example, $\lambda x.x$ is the identity function, $\lambda x.xx$ applies the functional argument $x$ to itself.

Since programming language designers know Lambda calculus very well, it seemed like a good idea to call anonymous functions in their language lambdas.


How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

$\def\pw{\mathcal P}$
It is an easy exercise to show that if we identify Boolean assignments to $n$ variables with subsets of $[n]=\{0,\dots,n-1\}$, then the solution sets of Horn CNFs are exactly the families $S\subseteq\pw([n])$ that are closed under nonempty intersections.

The picture is a little nicer for conjunctions of clauses each of which contains exactly one positive literal. Their solution sets are families closed under arbitrary intersections (where in particular the empty intersection is the full set), also known as closure systems or Moore families. These are in 1–1 correspondence with closure operators (functions $C\colon\pw([n])\to\pw([n])$ satisfying $X\subseteq C(Y)\iff C(X)\subseteq C(Y)$), consequence relations (relations ${\vdash}\subseteq\pw([n])\times[n]$ satisfying a handful of natural conditions), and I guess there are more similar combinatorial characterizations (https://oeis.org/A102896 or https://oeis.org/A102897 mention semilattices).

These two numbers only differ by a factor of two (given a closure system $S$, we may either retain $[n]\in S$ or throw it out without affecting anything else).

Alekseev proved that the number $\alpha(n)$ of closure systems on an $n$-element set satisfies

$$2^{\binom{n}{\lfloor n/2\rfloor}}\le\alpha(n)\le2^{\binom{n}{\lfloor n/2\rfloor}(1+o(1))}.$$

See http://www.renyi.hu/~ohkatona/paper_72.pdf for related information.


Can $L=SL$ be shown with the replacement product instead of the zig-zag product?

There is a paper already in 2005 that describes how to do this...
See https://people.seas.harvard.edu/~salil/research/derand_squaring-abs.html

I cannot say why people use zig-zag instead, other than perhaps they found the original reference readable enough that they did not need to look at secondary literature. At least for teaching purposes it seems the replacement product is simpler, as the above link shows.


A simplified version of card game Winner

This should probably be a comment, but it's too long.

A related game was studied by Jeff Kahn, Jeff Lagarias and Hans Witsenhausen, in the series of articles Single-Suit Two-Person Card Play I, II, III, and On Laskar's Card Game. In the game they studied, each player has $n$ cards, dealt from $2n$ cards numbered $1$ $\ldots$ $2n$. Each trick consists of two cards, the higher card wins the trick, and the winner leads. The object is to take the most tricks.

They proved a number of interesting facts about the optimal strategy, but were unable to find an efficient algorithm for optimal play, and were also unable to prove that it was NP-hard.

For the misère game, where each person tries to take the fewest number of tricks, they were able to give the optimal strategy.

For the most part, these results were obtained by first looking at the results of a computer program which found the optimal strategy for small instances, then looking for patterns to obtain conjectures, and finally proving these conjectures. I suspect that this would also be a fruitful approach to take for the OP's game.


Transition Diagram of a Universal Turing Machine

Here are some references:

Claude Shannon, "A universal Turing machine with two internal states", 1956.
Marvin Minsky, "A 6-symbol 6-state Universal Turing Machine", 1960.
Shigeru Watanabe, "5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines", 1961.

Also Odifreddi writes ["Classical Recursion Theory", vol I, p. 133]:

  "..., and explicit constructions of universal Turing machines are in Turing
  [1936], Wang [1957a] and in many textbooks, e.g. Hermes [1965], Minsky
  [1967], Arbib [1969], Hopcroft and Ullman [1979]. More information on
  the topic is in Davis [1956], [1957], Shannon [1956], Rogers [1967]
  and Priese [1979]."


Well, sure, it's possible.  But since we basically don't know how to prove that anything is hard, it doesn't look easy.

In the mid 90s I proved an $\Omega(n^2)$ lower bound for 3SUM in a variant of the linear decision tree model; my proof was later simplified by Ailon and Chazelle.  This model of computation has nothing corresponding to "memory"; the running time of an algorithm is defined simply as the worst-case number of (generalized) comparisons.  So adding a cache won't break these lower bounds; to beat $O(n^2)$ time, you have to do some non-obvious computation with the data in the cache.


Could a descriptive complexity version of Rice's theorem be used to separate AC0 and PSPACE?

Deciding the nontrivial properties of (an indexing) sets in a complexity class is as difficult as computing the graph of the universal function for the class. Intuitively this means that the only way to decide a nontrivial property is to simulate the machines and wait for answers. It seems to me that the idea of using such a property will just give what is known by the hierarchy theorems. (See theorem 4.2 of D. Kozen, "Indexing of subrecursive classes", 1978 for details and the exact statement of the theorem.)

We can decide the $grU_{AC^0}$ (the graph of universal function for $AC^0$) in $PSpace$, the reason is simply that $AC^0 \subseteq L$ and we have a universal machine for languages in $L$ in $PSpace$, so it is easy to simulate the $AC^0$ machines (or the descriptive complexity equivalent of $AC^0$ which is $FO$ queries) in $PSpace$. This means that that we can decide the property you have stated in $PSpace$. Since it is a nontrivial property, it is not decidable in $AC^0$. So this argument separates $AC^0$ from $PSapce$.

But is this surprising? No, since we already know a simpler way of stating (essentially) the same argument: $AC^0 \subseteq L \subset PSpace$, the last proper inclusion is by the space hierarchy theorem.


Your reduction from $3$SUM to $3$MUL works with a minor standard modification.
Suppose your original integers were in {$1,\ldots,M$}. After the transformation $x\rightarrow 2^x$ the new integers are in {$2,\ldots,2^M$}. We will reduce the range.

Consider any triple of integers $a,b,c$ in the new set $S'$.
The number of prime divisors of any nonzero $ab-c$ is $<2M$. The number of such triples is $n^3$. Hence the number of primes $q$ which divide at least one of the $ab-c$ nonzero numbers is at most $2Mn^3$.

Let $P$ be the set of the first $2M\cdot n^4$ primes. The largest such prime is of size at most $O(Mn^4\log Mn)$. Pick a random prime $p\in P$. With high probability $p$ will not divide any of the nonzero $ab-c$, so we can represent each $a\in S'$ by its residue, mod $p$, and if $3$MUL finds some $ab=c$ in $S'$, with high probability it will be correct for the original $3$SUM instance. We have reduced the range of the numbers to {$0,\ldots, O(Mn^4\log Mn)$}.

(This is a standard size reduction. You might be able to do better by considering the fact that the $ab-c$ are always differences of two powers of $2$.)


Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

In the paper: Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, the authors prove the following bound for Maximum Independent Set:

  For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ time. This nearly matches the upper bound of $2^{n/r}$.


What is higher-order in higher-order abstract syntax?

You can think of $\lambda$-abstraction as an operator $\Lambda$ which takes a function from terms to terms into a term:
$$\Lambda : (\mathsf{Term} \to \mathsf{Term}) \to \mathsf{Term}.$$
The type of $\Lambda$ is higher-order because it maps functions to objects, so it is a functional of rank 2. This is where the name comes from.

For example, if $\mathsf{id}$ is the identity map then $\Lambda(\mathsf{id})$ is the term $\lambda x . x$.

Constructors, for example $\mathsf{succ}$ as a constructor for the type of natural numbers, can naturally be viewed as first-order because they take terms to terms.

Of course, for the above to make sense, we need to be able to speak about functions between terms at the meta-level. And there are various subtleties: in principle one can have weird functions between terms that do not correspond to anything that can be written down in the syntax (consider a non-computable map). So if you're not careful, you're going to end up with "exotic terms" $\Lambda(f)$ that create a lot of trouble.

The usual solution is to somehow limit $\mathsf{Term} \to \mathsf{Term}$ to only "nice" functions. One possibility is PHOAS, another is to use a meta-theory such as Logical Frameworks in which only nice functions exist.


Data-structure for functions of independent sets

I wanted to post a comment, but with no "karma" it seems impossible... What about using dictionaries (hashmap, depending on the language you use) to store the values of your $f_i$ ? This way you don't have to know beforehand the size of the memory you will need, and gettin a function's value is not too slow.


Generalization bounds for multiclass learning when the output is vector space?

Sounds like you're trying to learn a map from vector space $X$ to vector space $Y$. The first thing that comes to mind is regression, which is a map from $X$ to $\mathbb{R}$. You can of course perform multiple regressions in parallel -- one for each dimension of $Y$ -- to learn a map from $X$ to $Y$. This has the shortcoming of ignoring any "interaction" or dependencies between the labels. You could first perform PCA on both the inputs in $X$ and the outputs in $Y$, and learn a map from the principal vectors of the input to the principle vectors of the output.

Another idea -- one that I'm particularly fond of -- is to perform Lipschitz extension. This assumes that $X$ and $Y$ are both metric spaces with known metrics. (A much more general setting than vectors spaces!) See the pioneering paper of von Luxburg and Bousquet, for example:
http://www.jmlr.org/papers/volume5/luxburg04b/luxburg04b.pdf


The significance of state complexity in automata and regular languages?

State complexity is really about concise description of an object (in this case, a regular language), not about computational complexity.  The general topic is called "descriptional complexity" in the literature and draws its inspiration, in part, from the classic 1971 paper of Meyer and Fischer entitled "Economy of Expression by Automata, Grammars, and Formal Systems" (see http://people.csail.mit.edu/meyer/economy-of-description.pdf ).  This is still an active area, with a yearly conference (DCFS - Descriptional Complexity of Formal Systems).

As for applications, any place where your program essentially relies on a finite-state machine (e.g., parsers) it will be good to have this finite-state machine as small as possible.


Simple model of computation with homoiconicity

The paper Typed Self-Representation by Tillmann Rendel, Klaus Ostermann and    Christian Hofer seems to satisfy the requirements, and it's typed too. Perhaps it doesn't satisfy the criteria of being a simple model of computation.


Graph problems with good characterization but not known to be in $P$

In one of my blog posts, I mentioned four problems (Factoring, Parity Games, Stochastic Games, A Lattice Problem) that are known to be in $NP \cap coNP$ but not known to be in $P$.

Parity Games and Stochastic Games can be considered as "graph problems".

Also, The Two Bicliques Problem is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.


"All-different hypergraph coloring" - known problem?

I believe this is known in the literature as the problem of finding a strong k-coloring for a k-uniform hypergraph.  This should be a good place to start: [PDF].


Multimodal logic with quantification over modal operators

In topos theory there are modal operators known as the Lawvere-Tierney operators. Such an operator is a certain endomorphism $j : \Omega \to \Omega$ on the subobject classifier. The object $J$ of all such operators is definable in the internal language of the topos, and so we can quantify over all $j$'s. My topos-theoretic knowledge is too poor to know whether anyone has done anything interesting with the object of all $j$-operators.

A related idea is the frame (or locale) of nuclei. If we think of a frame as a kind of logic (geometric logic, to be precise) then a nucleus is a modal operator on it. Once again, the nuclei of a frame themselves form a frame.


Holant problems and holographic reduction: simple graphs or multigraphs?

My concern is about the confusion between the use of the word "graph" to mean either a) a simple graph, without self-loops and parallel edges or b) a multigraph, that can have self-loops and parallel edges (i.e., multiple edges between the same pair of vertices).

In the literature about Holant problems, the word "graph" should be read as "multigraph" unless otherwise stated.  As you noticed, I tried to be more explicit about this in my thesis.  In my experience, different areas of math use terms mostly consistently within their own area but in ways that would be contradictory when considering multiple areas and read strictly.

In your first example, the proper notation is $\mathrm{Holant}([x,y,z]|[t_1,t_2,t_3,t_4])$.  This means that the input graphs are bipartite with one part having only vertices of degree 2 (and assigned the symmetric binary function $[x,y,z]$) and the other part having only vertices of degree 3 (and assigned the symmetric ternary function [t_1, t_2, t_3, t_4]).

Also (and I am sure you know this, but to be clear), a bipartite graph cannot have self loops.  So if a bipartite graph is not a simple graph, then it is because it has parallel edges.

1) Yes

2) Not immediately.  I think you have correctly observed that their reductions work for simple graphs.  It remains to verify if the hard problems that they were reduced from are also hard when further restricted to simple graphs.

3) There is no general fix.  In general, you have to reduce from problems that are hard for simple graphs.

4) Gadget 2 does not satisfy your condition.  Consider $N_1$.  The only two vertices of degree 2 without dangling edges have the same neighbor set.


What's the relation between OOP and category theory?

There are absolutely some relationships between the semantics and practice of OOP and category theory. This is somewhat unsurprising since both fields attempt to give a principled generic account of structure and behavior in a synthetic manner.

The most apparent work I am aware of is the categorical semantics of UML, which is admittedly different from OOP in the large, but I think captures much of the crux of the debate on the semantics of objects themselves. One example is Zinovy Diskin's Mathematics of UML.


Justifying asymptotic worst-case analysis to scientists

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis.  It therefore seems hard to justify to practitioners.

Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case.  Asymptotic analysis is also often much easier than proving reasonably tight bounds.  Worst-case asymptotic analysis is therefore a great place to start.

The work of Daniel Spielman and Shanghua Teng on smoothed analysis of Simplex seems to me a harbinger of what can happen when we start to gain a better understanding of the shape of a problem: tackling the worst-case first enables a more nuanced understanding to be developed.  Further, as Aaron Roth suggested in the comments, if the "usual" behaviour of a system is significantly different from its worst case, then the system is not yet completely specified and more work is needed to improve the model.  So going beyond worst-case generally seems important as a long-term goal.

As far as asymptotic analysis is concerned, it usually serves to keep a long and messy proof clear of distracting details.  Unfortunately there currently does not seem to be a way to reward the tedious work of filling in the details to obtain the actual constants, so that seldom seems to get done.  (Page limits also work against this.)  Careful analysis of the details of an asymptotic bound has led to actual algorithms, with good bounds on the constants, so I personally would like to see more of this kind of work.  Perhaps if more proofs were formalised using proof assistant systems, then the constants could be estimated with less additional effort.  (Or bounds on the constants, along the lines of Gowers' bound for the Szemerédi Regularity Lemma, might become more routine.)  There are also ways to prove lower bounds that are free of constants, by using more explicit machine models (such as deterministic finite-state automata).  However, such (near-)exact lower bounds for more general models of computation may require a lot of work, or be out of reach altogether.  This seems to have been pursued in ~1958–73 during the first heyday of automata theory, but as far as I can tell has since largely been left alone.

In short: in future, I think we'll see worst-case analysis as just a first step, and I hope we'll see expressions like $O$*$(n^k)$ with galactic hidden constants as just the first step.  I find it difficult to justify the current focus on worst-case asymptotic analysis to practitioners, but perhaps it is useful to see this as the beginning steps of a longer journey.


Fastest polynomial time algorithm for solving minimum cost maximum flow problems in bipartite graphs

See this paper. I think adopting their technique, many(usually scaling based) min-cost flow algorithms with running time $O(f(n,m))$ can run in $O(f(n_1,m))$ time. Here $n_1$ is the size of the smaller bipartition.

If $f(n,m)$ is the best possible run time for min-cost flow on general graphs with $n$ vertices and $m$ edges. There is an easy argument that you can't expect anything running in $o(f(n_1,m))$ time. (with some reasonable assumptions, like $n\leq m$, $f(n,cm)=O(f(n,m))$ for any constant $c$)

Proof: Otherwise, you can apply the standard vertex splitting operation to the input graph and use the bipartite min-cost flow algorithm and get a better running time.

Finally, if you are restricting cost and capacities things, these scaling algorithms is still pretty much state of the art(difference is at most $\log c$ for w/e parameter $c$ you care about). You can decipher that Theorem 3.5 to see which one of them gives you the best result.


Linearly independent Fourier coefficients

Isn't the following a counter-example?

Let $f(x)$ be the majority of $x_1, \ldots, x_{1/\epsilon^2}$, which is an indicator of a set of size $2^n/2$, so $d = 1$.  However, $\hat{f}(\{i\}) = \Theta(\epsilon)$ for $1 \le i \le 1/\epsilon^2$, so you have $1/\epsilon^2$ linearly independent large Fourier coefficients.


Best sources for communication complexity

Books:

Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006.
Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.)

Articles:

Alexander Razborov, "Communication Complexity".

Lecture Notes:

Toni Pitassi, "Communication Complexity, Information Complexity and Applications", 2012
Ran Raz, "Circuit Complexity and Communication Complexity".

Also check Sasha's remarks about communication complexity.


This type of problem has been the subject of quite a bit of study. You can find references by googling random self-reducibility, and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.


QPIP minimal client quantum capabilities

According to this paper:

https://arxiv.org/pdf/1509.09180.pdf

The client only needs the ability to prepare random single-qubit pure states.

You may also look at this paper for more information:

https://link.springer.com/article/10.1007/s00224-018-9872-3


Equivalent definitions of time constructibility

In the last few days I thought a lot about (fully) time-constructible functions and I will present what I found out by answering Q1 and Q3. Q2 seems too hard.

Q3:

Kobayashi in his article (the reference is in the question) proved that a function $f:\mathbb{N}\rightarrow\mathbb{N}$, for which there exists an $\epsilon>0$ s.t. $f(n)\geq (1+\epsilon)n$, is fully time constructible iff it is computable in $O(f(n))$ time. (note that it is irrelevant whether the input or output is in unary/binary since we can transform between these two representations in linear time). This makes the following functions fully time-constructible: $2^n$, $2^{2^n}$, $n!$, $n\lfloor \log n \rfloor$, all polynomials $p$ over $\mathbb{N}$ s.t. $p(n)\geq (1+\epsilon)n$ ... Kobayashi also proved fully time-constructibility for some functions that grow slower than $(1+\epsilon)n$, like $n+\lfloor\lfloor\log n\rfloor^q\rfloor$ for $q\in\mathbb{Q}^+$ ...

To continue with examples of fully time-constructible functions, one can prove that if $f_1$ and $f_2$ are fully time-constructible, then $f_1+f_2$, $f_1f_2$, $f_1^{f_2}$ and $f_1\circ f_2$ are also fully time-constructible (the later follows directly from Theorem 3.1 in Kobayashi). This altogether convince me that many nice functions are indeed fully time-constructible.

It is surprising that Kobayashi did not see a way to prove fully time-constructibility of the (nice) function $\lfloor n\log n\rfloor$ (and neither do I).

Let us also comment the definition from Wikipedia article: A function $f$ is time-constructible, if there exists a Turing machine $M$ which, given a string $1^n$, outputs $f(n)$ in $O(f(n))$ time.  We see that this definition is equivallent to our definition of fully time-constructibility for functions $f(n)\geq (1+\epsilon)n$.

Q1:

This question has a really interesting answer. I claim that if all time-constructible functions are fully time-constructible, then $EXP-TIME=NEXP-TIME$. To prove that, let us take an arbitrary problem $L\in NEXP-TIME$, $L\subseteq\{0,1\}^*$. Then there exists a $k\in\mathbb{N}$, s.t. $L$ can be solved by a NDTM $M$ in $2^{n^k-1}$ steps. We can assume that at each step $M$ goes in at most two different states for simplicity. Now define the function
$$f(n)=\left\{\begin{array}{ll}
  8n+2  & \mbox{if }\left(\mbox{first } \lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\mbox{ bits of } bin(n)\right)\in L\\
  8n+1 & \mbox{else}
 \end{array}
\right.$$

I claim that $f$ is time-construcible. Consider the following deterministic Turing machine $T$:

on input $w$ of length $n$ it computes $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ in $O(n)$ time
then it simulates $M$ on these bits, where the bits of $w$ determine which (formerly nondeterminisic) choices to take.
accept iff $\left(M\textrm{ accepts using choices given by }w\right)$.

Note that the length of $w$ ($=n$) is enough that it determines all nondeterministic choices, since $M$ on input $\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$ makes at most $n$ steps.

We can make  $T$ run in at most $8n+1$ steps. Now the following Turing machine proves that $f$ is time-constructible:

on input $w$ of length $n$ run $T$ and count steps in parallel so that exacly $8n$ steps are done.
if $T$ rejected or would reject in the next step, go to a halting state in the next step. Else, make one more step and then go to a halting state.

Now suppose that $f$ is fully time-constructible. We will prove that this leads to $EXP-TIME=NEXP-TIME$.

The following algorithm solves $L$:

on input $x$, let $n$ be the number with binary representation $x00\ldots 0$ ($|x|^{k-1}$ zeros). It follows that $x=\left(\textrm{first }\lfloor\sqrt[k]{\lfloor\log n\rfloor+1}\rfloor\textrm{ bits of }bin(n)\right)$.
compute $f(n)$ in time $f(n)$ and check whether it is divisible by 2.

This algorithm runs in exponential time and solves $L$. Since $L\in NEXP-TIME$ was arbitrary, $EXP-TIME=NEXP-TIME$.


will take a stab at answering this. there are no refs given in the question but it is given an acronym "EPRP" as if more than one person has studied it. does anyone know if that is the case? the questioner MC seems to have significant bkg in this area but it would help significantly to list some "nearby" refs known/reviewed to understand why they have some gap that doesnt (?) cover this supposedly special case.

it usually helps to find "nearest available refs" and determine how the problem is different or similar. here is a comprehensive ref that seems to consider closely related problem(s). think that the questioner MC should try to locate the nearest case of the problem in this ref, or maybe some other one, and then point out how this case asked about is specifically different than general problem cases given in the ref. the ref has a long list of related refs to also check for nearby/related problem(s). he considers the complexity of the problem and gives efficient P-time algorithms for various cases.

ON SOLVING UNIVARIATE POLYNOMIAL
EQUATIONS OVER FINITE FIELDS
AND SOME RELATED PROBLEMS
Tsz Wo Sze, Doctor of Philosophy, 2007

  ...we present a deterministic polynomial-time algorithm to
  solve polynomial equations over some families of finite fields. Note that polynomial
  equations are powerful constructs. Many problems can be formulated as polynomial
  equations.


It should be noted that finding combinators with certain reduction properties is always difficult, and finding the smallest such combinator may easily be undecidable (for trivial reasons, as it may be undecidable to prove that a certain application of the combinator even halts).

There are several simple open questions of a similar flavor, e.g. problems #4, #6 and #10 from the TLCA list of open problems.

One thing to note is that your combinator certainly needs to have at least 2 bound variables, one of which is duplicated (as does any complete set of combinators) and one needs to be erased. This puts a lower bound of 4, I think (2 abstractions and 2 appearances of a variable), which is not so far from the upper bound of 11.

Edit: Noam's comments and reference push the lower bound to 5! I wouldn't be surprised if the proof also requires the extra variable to appear as well, which would push us to 6.


Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

I didn't at first understand that the question Inapproximability of set cover: can I assume m=poly(n)? contains the answer to my own question. (Thanks to @Tsuyoshi Ito for pointing out.)

In short, the proof by Raz and Safra (and any other PCP-based proof) builds an instance of SET COVER where the number of subsets is a polynomial of the universe cardinality.


Dynamic and/or practical succinct data structures for triangulations

Take a look at the theoretical work of Castelli et al.  and also the latest papers of J. Barbay.

"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Succinct Representation of Triangulations with a Boundary. WADS 2005: 134-145"

"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Dynamic updates of succinct triangulations. CCCG 2005: 134-137"

"Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro: Succinct Representation of Labeled Graphs. Algorithmica 62(1-2): 224-257 (2012)"

For the implementation side, i would check CGAL and its triangulation data structures.


Does PPAD really capture the notion of finding another unbalanced vertex?

This is an interesting question, and I can only give a partial answer.

It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case

  MANY ENDS OF THE LINE (MEOL): Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ of sources of $G$, find a sink or a source $v\notin X$.

On the one hand, I find it hard to imagine a transformation of such graphs that could reduce a larger number of sources to one.

However, on the other hand, MEOL belongs to all commonly studied classes containing PPAD except possibly PPAD itself:

First, obviously,

  MEOL is in PPADS.

I will sketch below an argument that

  MEOL is in PPA

by reduction to the standard PPA-complete problem (the undirected version of AEOL). Assume we are given $G=(V,E)$ and $X$ as in the definition of MEOL.

If $|X|$ is odd, we can just make the graph undirected, include a matching on all but one vertex from $X$ (as in the argument on p. 505), and pass the result along with the remaining source from $X$ to the PPA oracle.

In general, let $s=|X|$, and $2^k$ be the largest power of $2$ that divides $s$. We define a new graph $G'=(V',E')$ whose vertices are $2^k$-element subsets of $V$. If $A,B\in V'$ are such sets, we put the edge $(A,B)$ in $E'$ if we can enumerate the sets as $A=\{a_0,\dots,a_{2^k-1}\}$, $B=\{b_0,\dots,b_{2^k-1}\}$ in such a way that $(a_i,b_i)\in E$ for each $i<2^k$.

Clearly, $G'$ is a directed graph with in-degree and out-degree at most $1$. An $A\in V'$ is a source (sink) iff it contains a source (sink, resp.) of $G$. (That is, if it contains both, it is an isolated vertex.) So, any such vertex would lead to a solution of the MEOL instance, unless $A$ is a “known source”: that is, $A\cap X\ne\varnothing$. We intend to make the graph undirected, and manipulate it so that the number of known sources is reduced to $1$ by including a matching on the remaining ones.

So, if $A$ is a known source, let $t=|A\cap X|$, which satisfies $0<t\le2^k$. If $t=2^k=|A|$, then simply $A\subseteq X$. The number of such sets is $\binom{s}{2^k}$. Recall that the multiplicity of a prime $p$ in $\binom ab$ equals the number of carries in the addition $b+(a-b)=a$ performed in base $p$. By the choice of $k$, it follows that $\binom{s}{2^k}$ is odd. Moreover, there are polynomial-time bijections between $[0,\binom ab)$, and $b$-element subsets of $[0,a)$. Using this, we can define a polynomial-time matching on all but one of $2^k$-element subsets of $X$. We include it in the graph, which reduces the number of known sources with $t=2^k$ to $1$.

For $0<t<2^k$, the carry-counting formula shows that $\binom st$ is even. Again, we can find an explicit matching on $t$-element subsets of $X$. We extend it to known sources $A$ with $|A\cap X|=t$ by applying the matching to $A\cap X$, and leaving $A\smallsetminus X$ fixed.

In this way, we produce an undirected graph with one known leaf vertex. We ask the PPA oracle for another leaf, and by construction, we can extract from it an answer for the MEOL instance.

As briefly mentioned by Papadimitriou, we can generalize PPA to classes PPA-$p$ for any prime $p$. An example of a PPA-$p$ complete problem is

  AUV-$p$: Given a directed graph $G$, and a vertex whose degree balance is ${}\not\equiv0\pmod p$, find another such vertex.

(See this answer for the equivalence of AUV-$p$ with Papadimitriou’s definition of PPA-$p$.)

PPA-$2$ is just PPA. The classes PPA-$p$ are assumed to be pairwise incomparable, and incomparable with PPADS. They all include PPAD.

There was nothing particularly special about $p=2$ in the argument I outlined above, and it can be easily modified to yield

  MEOL is in PPA-$p$ for every prime $p$.