At a high-level (ignoring the messier details), recryption that boosts bounded-depth homomorphism to unbounded-depth homomorphism works as follows:

Suppose you have a public-key "somewhat-homomorphic" encryption scheme with procedures:

$(PK, SK) \leftarrow Gen(1^{secparam}; coins)$: generates encryption/decryption keys
$c \leftarrow Enc(PK, m; coins)$: encrypts message $m$ as ciphertext $c$ under key $PK$
$m \leftarrow Dec(SK, c)$: decrypts ciphertext $c$ using key $SK$ to message $m$
$c^* \leftarrow Eval(C, c_1, ..., c_k)$: given ciphertexts $c_1, ..., c_k$ and a circuit description $C$, computes $c^* = Enc(C(m_1, ..., m_k))$

where "somewhat-homomorphic" means $Eval$ can only correctly (and succinctly) compute ciphertexts $c^*$ when the circuit $C$ has bounded depth (in some well-defined sense).

Correctness just means that w.h.p. over honest $(PK, SK) \leftarrow Gen$, for all $C, \{m_i\}_i$, we have $C(m_1, ..., m_k) = Dec(SK, Eval(C, Enc(PK, m_1; coins_1), ..., Enc(PK, m_k; coins_k)))$.
I.e. that if you use the scheme 'honestly,' you get correct decryption of (possibly $Eval$'d) ciphertexts.

That said, the observation is that the $Dec$ procedure, when written as a circuit, is a bounded-depth computation. Therefore, we can run $Eval$ on $C = \langle Dec\rangle$ when given (say) $SK_1$ and $Enc(PK_1, m)$ with BOTH encrypted under $PK_2$

To use this, we augment the $Gen$ procedure to first honestly generate two key-pairs $(PK_1, SK_1), (PK_2, SK_2)$. Then, $Gen$ creates a "recryption" key $RK_{1\rightarrow 2} = Enc(PK_2, SK_1)$ -- that is, the encryption of the key $SK_1$ under $PK_2$.

The scheme begins with the keys above, messages $\{m_i\}$ and a circuit $C$, and first creates ciphertexts $c^{(1)}_i = Enc(PK_1, m_i)$.

In order to recrypt, (conceptually) we can then doubly-encrypt the $\{c^{(1)}_i\}$ under $PK_2$. That is, create $c^{(2)}_i = Enc(PK_2, c^{(1)}_i) = Enc(PK_2, Enc(PK_1, m_i))$.

Then, under key $PK_2$, we perform (for each $i$) $Eval(\langle Dec\rangle, RK_{1\rightarrow 2}, c^{(2)}_i)$ obtaining a ciphertext $c^*_i$. By the correctness of $Eval$ and $Dec$, we have $c^*_i = Enc(PK_2, C(first\_plaintext, second\_plaintext)) = Enc(PK_2, Dec(SK_1, c^{(1)}_i)) = Enc(PK_2, m_i)$.

The 'messier details' in fact show that these $\{c^*_i = Enc(PK_2, m_i)\}$ are "fresh" ciphertexts under $PK_2$, meaning we have the full "bounded-depth" of $Eval$ available to us. Therefore, if $Eval$ can support at least the depth of the $Dec$ circuit, plus one, then you are able to perform unbounded-depth homomorphic computation (by further assuming circular security, and posting both $RK_{1\rightarrow 2}$ and $RK_{2\rightarrow 1}$, then toggling between the two keys with each recryption). In other words, you compute one step of the computation of some given circuit $C$, then you recrypt, and repeat.

P.S. If you go through significantly more effort (involving program obfuscation techniques), you can also obtain FHE without the circular security assumption. See: http://eprint.iacr.org/2014/882


totally-mixed 2SAT with exact cardinality?

Your problem is NP-complete.

I prove NP-hardness below by reduction from the clique problem (given a graph and a number, does the graph have a clique of that many vertices).

reduction

Suppose we are given a clique instance consisting of a graph $G = (V, E)$ with $m = |E|$ and $n = |V|$ and a number $k$. Then we will produce an instance of your problem consisting of a formula $\phi$ and a number $K$ as described below

First of all, we set $K = k + (n+1) \times {k \choose 2}$.

Next, lets describe the variables used in $\phi$. For each vertex $v \in V$, $\phi$ will include a variable $x_v$. For each edge $e \in E$, $\phi$ will include $n+1$ variables: $y_e^0, y_e^1, \ldots, y_e^n$.

Finally, lets describe the clauses included in $\phi$. Each clauses has the form $(a \vee \neg b)$, which is logically equivalent to $(b \to a)$, so I will write all clauses in implication form. For each edge $e \in E$, we include clauses $(y_e^n \to y_e^0)$, $(y_e^0 \to y_e^1)$, $(y_e^1 \to y_e^2)$, ..., and $(y_e^{n-1} \to y_e^n)$. The effect of these clauses is to enforce the equality of all the $y_e^i$s (for any fixed $e$) in any satisfying assignment. Next, for any edge $(u, v) \in E$, we also include clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$. The effect of these clauses is that in any satisfying assignment, if the variables $y_{(u,v)}^i$ associated with an edge are true then the variables $x_u$ and $x_v$ associated with the endpoints must also be true.

clique $\to$ satisfying assignment

Suppose that there is a clique $C$ of size $k$ in $G$. Then we can create a satisfying assignment for $\phi$ with exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

In particular, for $v \in V$, set $x_v$ to true iff $v \in C$, and for $e \in E$, set $y_e^i$ to true iff both endpoints of $e$ are in $C$.

There are $n+1$ variables $y_e^i$ for each $e$, and there are exactly $k \choose 2$ edges in $G$ with both endpoints in $C$ (since $C$ is a clique). Thus there are $(n+1) \times {k \choose 2}$ variables of the form $y_e^i$ that are set to true under this assignment. Furthermore, $|C| = k$, so there are exactly $k$ variables of the form $x_v$ set to true under this assignment. As desired, this assignment has exactly $K = k + (n+1) \times {k \choose 2}$ true variables.

Notice that $y_e^i = y_e^j$ for every edge $e$ and pair of indices $i, j$. Thus, the clauses of the form $(y_e^i \to y_e^{(i+1)~\text{mod}~(n+1)})$ are satisfied under this variable assignment.

Next, consider any edge $(u, v)$. If $y_{(u, v)}^0$ is true, then both $u$ and $v$ are vertices in $C$, so therefore both $x_u$ and $x_v$ are also true. Thus, clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ are also satisfied.

Since all clauses are satisfied, this is a satisfying assignment (which we already noted has exactly $K$ true variables).

satisfying assignment $\to$ clique

Next suppose we have a satisfying assignment of $\phi$ with exactly $K = k+ (n+1) \times {k \choose 2}$ true variables.

Any satisfying assignment has $y_e^0 = y_e^1 = \cdots = y_e^n$. Then let $y_e = y_e^0$. Define $n_y$ to be the number of true $y_e$s. Similarly, define $n_x$ to be the number of true $x_v$s. Notice that the number of true variables in the assignment is equal to $n_x + (n+1) \times n_y$. Furthermore, $0 \le n_x < n+1$ since there are only $n$ different $x_v$s. Thus, we can conclude that $n_x = K~\text{mod}~(n+1) = k$ and $n_y = \lfloor \frac{K}{n+1} \rfloor = {k \choose 2}$.

Let $C = \{v \in V~|~x_v~\text{is true}\}$ and let $E' = \{e \in E~|~y_e~\text{is true}\}$. Note that $|C| = n_x$ and $|E'| = n_y$ by definition. Then $E'$ is a set of ${k \choose 2}$ edges, and $C$ is a set of $k$ edges.

Notice that if $(u,v) \in E'$, then $y_{(u,v)}$ is true, and therefore $y_{(u,v)}^0$ is true; as a result, since clauses $(y_{(u,v)}^0 \to x_u)$ and $(y_{(u,v)}^0 \to x_v)$ must be satisfied, we can conclude that $x_u$ and $x_v$ are also true, and therefore that $u,v \in C$. Thus, if $e \in E'$ and $v$ is an endpoint of $e$ then $v \in C$.

Thus the set of endpoints of edges in $E'$ is a subset of $C$. Then $E'$ is a set of ${k \choose 2}$ edges whose set of endpoints numbers at most $|C| = k$. A set of ${k \choose 2}$ edges has only $k$ endpoints in total only in the case that the $k$ endpoints are a clique. In other words, it must be the case that $C$ is a clique and the edges in $E'$ are the edges in the clique.

Thus we have identified a clique of size $k$ in $G$.


Probability of two vertices being connected by some path in a random directed graph

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. After $k$ steps, check whether the vertex $v$ belongs to $\bigcup_{j=0}^k V_j$.

Note that this process is exactly the same in both the undirected and the directed case. Hence the answer, whatever it is, is identical for both models. Presumably in the undirected case the answer is known and can be looked up. Otherwise you can try to estimate it by estimating the sizes $|V_i|$ and so the probability $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ that $v$ belongs to $\bigcup_{i=1}^k V_i$.


Minimal clique edge cover vs minimalist (assignment-minimum) ones

Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$.
When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard to show that $C$ is minimalist. However replacing the two edges $\{a,b\}$ and $\{c,d\}$ with a single clique $\{a,b,c,d\}$ results in less number of cliques.


Finding the nearest node to a given set of nodes in a graph

I think Dijkstra's shortest path algorithm would be suitable for your problem. But since you want to find the shortest-path node from a set of nodes and not from just one node, you need to tweak it.

The algorithm is quite straightforward but a bit obtuse, try searching for animated expositions on YouTube.


logic in the presence of doubt, uncertainty, lies

There isn't really a single formalization of the kind of thing you are asking. There are many, many aspects to truth, trust, lies, and fallible reasoning, and this leads to an enormous variety of logical formalisms, each handling different aspects of this problem.

If you want to account for uncertainty about your hypotheses, the traditional route is via Bayesian probability theory. See E.T. Jaynes' (sadly incomplete) Probability Theory: the Logic of Science for a good exposition of this point of view.
One difficulty with probabilistic methods is that it is difficult to interpret quantifiers, essentially because limits do not necessarily exist. That is, a proposition may hold for all finite approximations, but fail to hold in the infinite limit.

Taking this into account leads you to view propositions topologically, which (a) leads you the Beth semantics of intuitionistic logic, and (b) also leads you to geometric logic. See Steve Vickers' Topology via Logic for an introductory exposition, and Peter Johnstone's Stone Spaces to jump into the deep end of the pool.

(However, to my knowledge there is not yet any satisfactory constructive account of probability theory.)
If you are interested in the difference between truth and belief, then you need to look at epistemic logic. The idea is to extend traditional logic with a modality $B_X(A)$, which is intended to read "$X$ believes $A$". See the SEP entry on epistemic logic for an introduction, and follow the bibliographic links in the article for more details.
However, when you have multiple agents, you also have to think about the difference between truth and assertion. This is particularly important in applications like authorization (e.g., I can look at a file, because the owner of the file has the right to delegate the right to look at it, and says that I can look at it). There is a huge amount of work on this; a good entry point into this literature is in Deepak Garg's PhD thesis, Proof Theory for Authorization Logic and its Application to a Practical File System.
Next, one of the traditional principles of logic is ex falso quodlibet: that is, $\bot \to A$ holds for all propositions $A$ — if you assume false, everything follows. If you are thinking about the possibility of believing false things (for example, someone has lied to you, or you have a database with errors in it), this is potentially disastrous. In practical reasoning, you don't want to derive a contradiction and then happily believe everything — you want to find a contradiction, and deduce that you have made an error.

The study of what happens to logic when you drop ex falso is called relevance logic, so named because the idea is that you should only make inferences from hypotheses that are relevant to the conclusion. Again, see the SEP article on relevance logic for more. Also, you might wish to tolerate contradictions in your logic system. In this case, the thing to look at is paraconsistent logic.
Next, you mentioned a worry that individual inferential steps might not be completely reliable. In traditional logic we accept the unrestricted use of modus ponens. That is, inside a proof, if we know $A \to B$ and $A$ hold, we can conclude $B$ holds, any number of times. If you start to consider the idea that individual inferential steps might not be completely reliable, then you might think that proofs depending on long chains of inferential steps are "less reliable" than short ones.

It's a bit tricky to formalize this, but it is one of the (several) motivations for ultrafinitism. See Mannucci and Cherubin's draft Model Theory of Ultrafinitism I: Fuzzy Initial Segments of Arithmetic, for an exploration of this idea (and some explanation of its connection to fuzzy logic).

Finally, note that that none of these approaches actually talk about Frankfurt's idea of bullshit as an assertion which is made with an indifference to its truth value. You probably want to look at J.L. Austin's theory of speech acts (e.g., his book How to Do Things With Words) to help organize your thinking on this, and if you try to formalize it, you will probably find Per Martin-Löf's judgemental methodology (see for example his Siena lectures) helpful.


Problem NP-complete for Euclidean geometry but in P for Non-Euclidean geometry?

Partial answer:

Maximum TSP is polynomial time solvable under polyhedral norms,
but NP-hard for Euclidean norms (optimization as well as decision
version). Whether the latter is also NP-easy is a different question.
(You might be able to define a somewhat artifical variant that is in NP,
since the instances created for the NP-hardness proof only require
bounded precision.)

A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir,
G. J. Woeginger, and R. Wodroofe.
The geometric maximum Traveling Salesman problem.
Journal of the ACM, 50:641-664, 2003.


No, there can't be such a surjection. Here's how to derive a contradiction, if there is a surjective map $f : A \to U_n$, where $A:U_m$.
Since $m\leq n$, we can pull $f$ back along the embedding $U_m \to U_n$. This gives a surjective map $f' : A' \to U_m$, and it is not hard to see that the type $A'$ is equivalent to a type in $U_m$. Thus we have a surjective map from a type (equivalent to a type) in $U_m$ into $U_m$, and the join construction can be applied with these hypotheses to conclude that the type $U_m$ itself is equivalent to a type in $U_m$. This is well-known to lead to a contradiction.


Rings and the set of all minimum s-t-cuts

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$.

Let $S=\bigcap\limits_{R\in\mathcal R}R$, $P=\bigcup\limits_{R\in\mathcal R}R\setminus S$ and $T=U\setminus(S\cup P)$. Construct a flow network $N$ with nodes $U\cup\{s,t\}$ and the following edges:

From $s$ to every element of $S$.
From every element of $T$ to $t$.
For all ordered pairs $(x,y)$ such that $x\in P$, $y\in P$ and $\forall R\in\mathcal R:x\in R\rightarrow y\in R$, from $x$ to $y$.

Each edge can have any positive capacity. Since $t$ is not reachable from $s$, maximal flow is $0$.

What remains is to prove that the set of source sides of minimal $s$-$t$ cuts is exactly $\mathcal R$. Firstly, I'll show that any set $R\in\mathcal R$ is a source side of an $s$-$t$ cut. By definition, $S\subset R$ and $T\cap R=\emptyset$, so edges from $s$ and edges to $t$ don't cross the cut. Edges in $P$ also don't cross the cut by definition, since for any such edge $x\rightarrow y$, if $x$ is in $R$, $y$ must be in $R$ as well.

Now I'll show that if $Q$ is a source side of a minimal $s$-$t$ cut, $Q$ must be in $\mathcal R$. Since maximal flow is zero, there must be no edges crossing the cut. Therefore, $S\subset Q$ and $T\cap Q=\emptyset$. If $Q=S$, the proof is done, because $S$ is a member of $\mathcal R$ by definition. Otherwise, let $Q'=\bigcup\limits_{x\in Q}\bigcap\limits_{R\in\mathcal R\wedge x\in R}R$. By definition, $Q'\in\mathcal R$, so it remains to show that $Q=Q'$.

Note that every intersection in the definition of $Q'$ is nonempty, because $Q\subset S\cup P$. Also, $Q'\subset S\cup P$. By definition, every element of $Q$ is contained in $Q'$. Suppose that there is an element $y\in Q'$ which is not in $Q$. Then $y\in P$ and there is an element $x\in Q$ such than $\forall R\in\mathcal R:x\in R\rightarrow y\in R$. Then $x\in P$, since otherwise $x\in S$ and $S\in\mathcal R$ is a counterexample. So, there must be an edge from $x$ to $y$, and it crosses the cut, a contradiction. Therefore, $Q=Q'$, so $Q\in\mathcal R$.

By the way, while the above solution requires directed edges, the answer is the same even if all the edges must be undirected (with the same capacity in both directions). The idea for the solution in this case is that you need such a network that, after the maximal flow is pushed through it, the residual graph is the same as the graph constructed using the solution above plus some edges from $T$ to $P$ and from $P$ to $S$ which don't change the set of minimal cuts. The details are left as an exercise to the reader.


What is the best way to get a close-to-fair coin toss from identical biased coins?

Tossing n biased coins and taking the parity of heads gets exponentially close to $\frac{1}{2}$.

[For a proof, consider a random variable that is -1 when heads and 1 when tails, then
the probability that there are an odd number of heads is just the $E\left[\frac{1}{2} + \frac{1}{2}\prod_i X_i\right] = \frac{1}{2} + \frac{1}{2}\delta^n$]

Perhaps this is also optimal for the following reason. Let $f$ be any composition function of these bits. Then, the $\text{Bias}(f) = \sum_S \hat{f}(S) \delta^{|S|}$ and the best $f$ seems to be the parity function (isn't it?).

If you are interested in composition functions of lower complexity, then perhaps a paper of Ryan O'Donnell on `Hardness amplification within NP' would be very relevant. There he uses monotone composition functions for hardness amplifications and the functions that work are characterized by their noise sensitivity.


Counting/Enumerating Minimal Edge Covers

Counting edge covers is #P-complete. You can find a proof here Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT. See also the stack-exchange discussion. One can probably modify the proof to show #P-completeness for minimal edge covers.
enumerating (minimal) edge covers can be done with polynomial delay as the hypergraph has bounded degree (see New Results on Monotone Dualization and Generating Hypergraph Transversals)
the following Low-Exponential Algorithm for Counting the Number of Edge Covers on Simple Graphs claims an $O(1.465575^{(m−n)} × (m + n))$ time algorithm. I am wondering whether one cannot do better.


Computer science (especially theory B) has many connections to category theory, and that is the usual context for lifting. The basic idea is that you might have two objects $X$ and $Y$ that interact in a very intuitive way for you, and so it is easy to define a good morphism $f: X \rightarrow Y$. You might have a more complicated object $Z$ that is easy to relate to $Y$, but it is not obvious how it relates to $X$. So you will look at a morphism $g: Z \rightarrow Y$ and then use category theory to lift $f$ to $Z$ using $g$.

In other words, you will find a morphism $h: X \rightarrow Z$ such that $gh = f$. For more info, see these slides.


Here is a counterexample, which I'm too lazy to draw. Let $G_1,G_2$ be diamonds, graphs on four vertices having five of the six edges. Connect matching vertices in $G_1$ and $G_2$ so that you get a connected cubic graph. It seems that there is no spanning tree in which every internal vertex has degree exactly $3$.


Is there a geometrical picture for adiabatic quantum computation?

a very challenging/advanced/provocative question; following, a brief/sketchy/tentative answer [maybe/hopefully better than none] considering geometry in QM computing in general & a few refs/leads. geometry is used in a variety of ways in QM in general, and it appears to be somewhat of an open question and challenging work-in-progress how to determine a coherent/natural "geometric picture" for QM, and there apparently are multiple ways to do it, and currently no generally-agreed, unified or standard approach. also, some directions can be highly abstract reflecting the direction of mathematical research developed largely independently of physics.

the 2-qubit state has been more extensively studied and there is more chance of creating a picture there 1st and maybe using it as a somewhat "toy" area that can be expanded later. (note that adiabatic QM computing is still based on qubits.) also there is a relatively new study of "quantum dischord" which is seen as promising by some (but also controversial) & might be part of the answer as in the following ref.

the Bloch sphere is a clear geometric picture for a single qubit and has some generalization for pure states.
Geometric picture of quantum discord for two-qubit quantum states Shi, Jiang, Sun, Du
Geometry of Discrete Quantum Computing Hanson, Ortiz, Sabry, Tai
Quantum computing: The power of discord Merali/Nature


Lower bounds for formulae sizes for addition

Counting the number of 1s in a given binary string is $\mathsf{TC^0}$-complete and cannot be decided using any polynomial-size CNF. In fact you need exponentially large CNFs to decide them. So if you want $y$ to be part of the input then the size is going to be exponential in $n$.

If $y$ is fixed, then there are CNF's with $O({n \choose y})$ gates: check if any $y$bits of $x$ are 1:
$$\exists I \in {n \choose y} \ \forall j \in I. \ x_{j} \land \forall j\notin I. \ \lnot x_j $$

For $y = \frac{n}{2}$ this gives an exponential-size CNF. I haven't checked it but I think the proof for parity not in $\mathsf{AC^0}$ can be adopted to prove an exponential size lower-bound for this function.

As I wrote before, in case we are interested in satisfiability and a reduction to 3CNF-SAT then the size is constant as we can decide in polynomial-time if the equality holds or not and depending on the answer return $\top$ or $\bot$.

Another question is to look for a CNF $\varphi(\vec{x}, \vec{y}, \vec{w})$ such that for all $\vec{a}$ and $\vec{b}$, $\Sigma_{1 \leq i \leq n} a_i = b$ holds iff $\varphi(\vec{a}, \vec{b}, \vec{w})$ is satisfiable, i.e. $\exists \vec{w} \ \varphi(\vec{a}, \vec{b}, \vec{w})$ holds. The lower-bound does not apply to such formula, in fact for any langauge $L \in \mathsf{NP}$ there is a polynomial-size CNF $\varphi(\vec{x},\vec{w})$ s.t.

$$ x \in L \Leftrightarrow \exists \vec{w} \ \varphi(\vec{x},\vec{w}).$$

I don't know what is the best known CNF size for
$\Sigma_{1 \leq i \leq n} x_i = y$ in this sense.
I don't think there is any good lower-bound for the following reason:
the reduction from circuit-SAT to 3CNF-SAT is very efficient: linear number of new variables, linear increase in size.
Any lower-bound would also give a similar lower-bound on the circuit size for deciding the equation and in general we don't have good circuit size lower-bounds.

An obvious upper-bound can be obtained from the same idea: the equation can be decided using two Threshold and one And, so this has a constant size $\mathsf{TC^0}$ circuit. The upper-bound follows from reducing evaluation of a $\mathsf{TC^0}$ circuit to 3CNF-SAT.


Mihalis Yannakakis has shown that the traveling salesman problem cannot be solved in polynomial time by using a symmetric linear program.

See the paper Expressing combinatorial optimization problems by Linear Programs, by Yannakakis.

This result was improved recently by  Fiorini,  Massar, Pokutta,  Tiwary, and De Wolf to drop the "symmetric" requirement in Yannakakis' result.


Distributions which are intractable to sample from?

I'll expand my comment to an answer. Many combinatorial structures in graphs are actually NP-hard to sample from.

The earliest example I can think of is JVV86 (Thm 5.1), which shows that there is no polynomial-time algorithm to randomly generate a cycle in a directed graph, unless NP=RP.

Similar results along this line are NP-hardness for sampling independent sets, colourings etc. See e.g. DFJ02, Sly10, GSV15. Note that the corresponding search problems are all easy.

The problem can also be defined by "soft" constraints. E.g., sampling from an anti-ferromagnetic Ising model is NP-hard. See JS93 (Thm 14).

Results of this sort are usually stated as NP-hard approximate counting problems, due to the standard self-reductions JVV86.


I now realize that a lower bound has indeed been established by Anthony and Bartlett (see the presentation here).

Edit 24-Sep-2018. This question has kept me occupied all of these years, and recently, I. Pinelis and I have obtained the exact optimal constant in the agnostic PAC lower bound to appear in Ann. Stat.


"long code test" and "dictatorship test"

"Long code" and "Dictator code" are two different names for the same code. Here's why:

Let's start with the natural definition of the long code: The message is an $n$-bit string $i$ (the reason I'm calling this $i$ and not $x$ becomes clear soon) and the encoding is a vector $y$ of length $2^{2^n}$ where the positions of $y$ are indexed by all possible Boolean functions that map $n$ bits to one bit. Moreover, $y$ at position $f$ is simply $f(i)$.

Now you can alternatively identify $f$ by its truth table. So you can also assume that the coordinate positions of $y$ are indexed by all possible strings of length $N := 2^n$ (i.e., all possible truth tables) and then $y$ at position $f=(f_1, \ldots, f_N)$ just encodes $f_i$.  So the $i$th codeword is the truth table of the $i$th dictator function (among the dictator functions mapping $N$ bits to one bit). So the long code and the dictator code are the same. In the long code interpretation, codewords correspond to $n$-bit points and codeword positions correspond to $n$-bit predicates. In the dictator code interpretation, codewords correspond to dictator functions on $2^n$ bits and codeword positions correspond to evaluation points.


A short answer is http://en.wikipedia.org/wiki/Graph_factorization.  A more comprehensive reference might be the classic "Matching Theory" by Lovasz and Plummer, which is the best on this topic.


Assume that $\mathsf{NP} \subseteq \mathsf{P}/\text{log(n)}$, does it imply that $\mathsf{P} = \mathsf{NP}$?

Yes. All advice strings of length log n can be cycled though in polynomial time.
The polynomial time algorithm for SAT would be:
For each of the polynomially many advice strings, try to use it to produce a satisfying assignment for SAT (using self-reducibility) in polynomial time. I would guess this is in the original Karp Lipton paper.


Sources for Algorithmic Evolutionary Game Theory

This is one of the topics where I have been looking for connections for a while. However, they don't seem all the prevalent. The folks working on theoretical biology and economics that use EGT, usually stick to dynamic systems theory and don't don the algorithmic lens. Thus, most results are of the AMath/Physics style, and not of the algorithms and discrete math style. If you are willing to pursue the dynamic systems approach, then there a survey by Hofbauer and Sigmund which is shorter and more recent than their book (I mention it and some passing comments in a previous answer).
One of the places replicator dynamics have been used in complexity related results, is by Marcello Pelillo and co-authors as a heuristic for solving max-clique (reduce max-clique to quadratic programming, solve quadratic programming by using replicator dynamics as your heuristic):

[1] Immanuel M. Bomze, and Marcello Pelillo [2000]. "Approximating the Maximum Weight Clique Using Replicator Dynamics." IEEE Transactions on Neural Networks 11(6)
[2] Marcello Pelillo, and Andrea Torsello [2006]. "Payoff-Monotonic Game Dynamics and the Maximum Clique Problem." Neural Computation 18: 1215-1258.

You can use their results to show that many natural question associated with evolutionary stable strategies are NP-hard (this kind of addresses question 2). In fact, Etessami & Lochbihler showed that it is worse than that and the question of ESS existence is both NP and coNP-hard, but in $\Sigma^P_2$. Recently, Conitzer tightened this to show that "does an ESS exist?" is a $\Sigma^P_2$-complete problem.

[3] Kousha Etessami, and Andreas Lochbihler [2008] "The computational complexity of evolutionarily stable strategies". International Journal of Game Theory, 37(1): 93-113. (First available in 2004 as ECCC tech report TR04-055).
[4] Vincent Conitzer [2013] "The exact computational complexity of evolutionarily stable strategies". The 9th Conference on Web and Internet Economics (WINE). (pdf).

A lot of the interesting EGT questions today are about games on graphs, and although there are some cool dynamic system results, like (also see this question for extensions of this approach):

[5] Hisashi Ohtsuki, and Martin Nowak [2006] "The replicator equation on graphs." _ Journal of Theoretical Biology_, 243 (1), 86-97 (link, blog post)

Most of the work goes through agent-based modeling (see this answer for a spread-of-disease modeling context). These models are usually much more welcoming to complexity and convergence statements. Look at the following book for more:

[6] Yoav Shoham and Kevin Leyton-Brown [2009], "Multiagent systems: algorithmic, game-theoretic, and logical foundations", Cambridge University press.

I think machine learning is a pretty straightforward way to approach EGT, since it is a natural halfway point between the relevant physics (statistical mechanics) and computer science. This has definitely been done, it would take me a bit to find a good reference, but a random reference (which also shows that EGT folks have considered other popular equilibrium concepts, like correlated equilibrium):

[7] Sergiu Hart and Andreu Mas-Colell [2000], "A simple adaptive procedure leading to correlated equilibrium", Econometrica 68(5): 1127-1150
[8] Antonella Ianni [2001], "Learning correlated equilibria in population games", Mathematical Social Sciences 42(3): 271-294.
[9] Ludek Cigler and Boi Faltings [2011], "Reaching Correlated Equilibria Through Multi-agent Learning", AAMAS 2011: 509-516

I definitely hope others give more specific answers, since this is a question I've always wanted to know more about.


Maximum rows to partially distinguish all the columns

This is not an answer, only an extended comment on a possible transformation of the problem (hope it is correct :-).

Each row can be "mapped" to a $n \times (n-1) / 2$ "extended" row. Each element of the extended row represents a pair of elements in the original row and is set to 1 if the two elements are different, set to 0 if the two elements are the same.

For example:

row_i = 10011
        ^1100   (*)
         ^011
          ^11
           ^0

extended_row_i = 1100 011 11 0

(*) note that in building the extended row, when the current bit (marked with ^)
is 0, the remaining bits are just copied and when the current bit is 1 the
remaining bits are inverted

We can extend each row and obtain an "extended" matrix. For example the matrix:

10011
01101
00011

Becomes:

1100 011 11 0
1101 010 10 1
0011 011 11 0

And the original problem reduces to find a submatrix of the "extended" matrix with exactly one 1 in each column.


Publishing by showing falsity of existing results

If you respectfully show that an important, i.e., often used/cited, result is false, I think that would be a significant contribution, since obviously those are often the results that have been scrutinized the most and people might build additional work off those results.


Moving a snake from one position to some other is PSPACE complete.
Snake is trivially in PSPACE.
We give a PSPACE hardness reduction from Hearn's Nondeterministic Constraint Logic.

Nondeterministic Constraint Logic

Let a constraint graph be a directed graph with edges of weight $1$ and $2$, such that every vertex has incoming weight $\geq 2$.
Given two constraint graphs, it is PSPACE hard to transform one into the other by reversing edges, one at a time, keeping the incoming weight of each vertex $\geq 2$.
This still holds if the graph is planar and each vertex has degree $3$, and either $1$ or all $3$ of its edges have weight $2$.
The former type of vertex is called And and the latter is called Or (see figure).

Snake

In our construction, the snake's head will be chasing its tail at some small distance and will be forced to repeat the same cycle with minor modifications.
We embed each edge of the constraint graph as in the figure (edges shown in red), where we indicate the position of the snake by thick lines.
An edge has two sides (vertices) and the snake takes the central route at the vertex to which the edge is directed.

To reverse an edge, the snake first clears the center route and then takes the center route once its head reaches the opposite vertex.

We embed vertices of the constraint graph as shown below, where each of the three colored parts is a half of an edge gadget shown above. The points where the edges touch make sure that the incoming weight of each vertex is at least $2$ by forcing the snake to take the center route of some edge gadgets.

Finally, the black lines of all edge gadgets are connected to form a single cycle, so the head of the snake chases its tail.
If between two edge gadgets, we make the black path sufficiently long, the snake must always traverse the black paths in the same cyclic order.

To show that the black paths can always be constructed in a planar manner, consider a spanning subtree (thick edges in the figure below) of the constraint graph.
Then we can make black edges follow this tree as illustrated below, resulting in a planar graph.

The target position of the snake can be derived by the same transformation.
Hence, reconfiguring a snake is PSPACE complete, even on planar graphs.


This is not an answer.  What follows is a simple proof that the construction for k=3 is indeed a counterexample.  I think that the asker knows this proof, but I will post it anyway because the proof is nice and this might be useful when people consider the case of larger k.

It is easy to verify that it is a shift-chain.  Let’s show that it does not have Property B.

In fact, the subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} already fails to satisfy Property B.  To see this, suppose that this hypergraph has a 2-coloring and let ci be the color of the vertex i.  Look at three hyperedges (145), (245), (345).  If c4=c5, then all of 1, 2 and 3 must be the opposite color to c4, but this would give a monochromatic hyperedge (123).  Therefore, it must be the case that c4≠c5.  Similarly,

c3≠c4 by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
c6≠c7 by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
c5≠c6 by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).

Therefore, we have c3≠c4≠c5≠c6≠c7.  But this implies c3=c5=c7, making the hyperedge (357) monochromatic.  This contradicts the assumption of the 2-coloring.


Clarification regarding Bounded Quadratic Congruence Problem

The NP-completeness of the original problem was proved by Manders and Adleman [1] using a reduction from 3-SAT. Their reduction is parsimonious. Thus, (taking into account that the number of prime factors is upper bounded by the length of the input $n$, while in the M–A reduction, it is at least $n^\epsilon$) your problem is complete for promise-FewP. Note that by Valiant–Vazirani, already promise-UP is NP-hard under randomized polynomial-time reductions, hence the same holds for promise-FewP. Thus, the problem is essentially as difficult as NP.

EDIT: The answer above assumes that in the question, the unclear phrase “the number of occurrences of $a$” means the number of residues $x<L$ such that $x^2\equiv a$. The OP indicates in a comment below that they rather intended it to mean the total number of residues mod $b$ that square to $a$. In the latter case, the problem is solvable in promise-ZPP: using the factorization of $b$, just compute all possible square roots of $a$ modulo $b$ by the usual algorithm (Tonelli–Shanks + Hensel’s lifting + Chinese remainder theorem).

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete
  decision problems for binary quadratics, Journal of Computer and System
  Sciences 16 (1978), no. 2, pp. 168–184.


"A simple linear time algorithm" by Klawe

There is also pseudocode for this algorithm given on p. 14 of Aggarwal and Tokuyama, "Consecutive interval query and dynamic programming on intervals." Discrete Applied Math 85 (1998). It starts out:

1: i=0;
2: r=min{n,2^(i+1)};

and has other differences from the pseudocode that you posted; at first sight, the Aggarwal and Tokuyama pseudocode seems quite a bit clearer. So it seems likely there was a typo in the original. Hopefully, this second paper gets the pseudocode correct. It certainly gives a good enough explanation of the algorithm for me to understand it and see why it works.

UPDATE: (Twice, now): The first update gave the response to questions in the comments. In the second update I corrected the restriction for when you can evaluate a cell. Here's what is going on (with possible fencepost errors in my explanation).

If you search A[j,j;n,n], you never have to search another square, you're done. That's what "5.2.3: Exit" means. You're not exiting the loop; you're exiting the program.

Why do you need to search A[j,j,n,n]? You have just found the minima of columns 2^i to r over rows 1 ... 2^i+1. Here 2^i + 1 <= j <= 2^(i+1). Because of the entries you've looked at in column r and the monotonicity of the matrix, you can conclude that you've already found the minimum in columns 1 through j-1, and the minimum in columns j..r is either the one you've already found or is in the matrix A[j,j;n,n]. Thus, you have to search A[j,j;n,n], and for the columns between j and r, you need to compare the minimum you find in A[j,j;n,n] with the minimum you've already found for that column (this comparison is step 5.2.2.1).

You can't evaluate an entry A[s,t] until for every column 1..s, you know the minimum in that column. Thus, in order to evaluate an entry A[s,t] when you're searching A[j,j;n,n], you first need to find the minimum in column s. This is why you need to run 5.2.1 and 5.2.2 concurrently. This means you can stop the concurrent 5.2.2 process when you reach column r. (You can see this because 5.2.2.1 says "j <= t <= r".)

So I guess this means that as soon as you find the minimum in column t in 5.2.1, you have to pass it to 5.2.2, do the comparison of the two candidate minima in column t, and now that you know the minimum in column t, you can use it to evaluate entries in row t. Technically, you could do this comparison any time between the point at which you know the minimum of column t in A[j,j;n,n], and the first point at which you need to evaluate a cell in row t. Offhand, I don't see any reason not to do it as soon as you learn the minimum of column t in A[j,j;n,n].


Yes, PCPs with imperfect completeness have been studied before. The main motivation is that for some natural and interesting problems, finding whether there is a perfect solution is actually easy (polynomial-time), while approximating the best solution, if this best solution is not perfect, is (or believed to be) hard.

Here are some examples:

The Unique Games Conjecture. Unique games with perfect completeness are easy, so the Unique Games Conjecture focuses on unique games with imperfect completeness.
Feige and Reichman showed NP-hardness for unique games for some constant completeness and soundness values (not c=1-delta s=epsilon as conjectured).
Linear equations. Linear equations with perfect completeness are easy (using Gaussian elimination), so hardness results for linear equations (e.g., Hastad's) focus on imperfect completeness.


$BPL$ with polylog random bits is in $L$

It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be decreased to $O(S)$.

In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can derandomize the algorithm completely by enumerating over all possible coin tosses.


Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$

It's easy, and in fact I suspect your proof that the "degree-3 version is NP-hard" is flawed somewhere, since the degree-3 version is also easy. Here's the argument for degree-2:

Suppose our constraint is $p(x) = 1$, and assume, since we're only interested in $p$ as a function, that it is reduced mod $x_i^2 = x_i$ (ie that it's multilinear). We can plug in zero, and if it fails to satisfy the constraint, we can conclude that $p$ has no constant term. Next, we try all points of Hamming weight 1. If they all fail to satisfy the constraint, then, since $p$ has no constant term, this means $p$ has no terms of degree 1. [To see this, think of what a Hamming-weight-1 input does to each monomial.] Next we try all points of Hamming weight 2, and, again, if these fail, then, since $p$ has no terms of degree at most 1, this means $p$ has no terms of degree 2. Since $p$ has degree at most 2, the only way these can all fail is if $p$ is the zero polynomial, and of course no solution exists in that case.

This keeps going to higher degrees: (the multilinearization of) $p$ has no terms of degree at most $r$ iff it's zero on all points of Hamming weight at most $r$. So for any constant degree, you get an efficient algorithm.


What is the fastest way to check for set inclusion?

You cannot solve it in $O(n^{2-\epsilon})$ time for any constant $\epsilon>0$ unless the Strong Exponential Time Hypothesis is false.

That is, if we had such an algorithm, we could solve $n$-variable CNF Satisfiability in $O((2-\epsilon')^{n})$ time for some $\epsilon'>0$.
The reason is that we could divide the variables in two equal parts $P_1$ and $P_2$ of $n/2$ variables each. For each part we construct
a family $F_1$ and $F_2$ respectively of subsets of the clauses in the following way. For each assignment we add a subset consisting of the
clauses not satisfied by the assignment. This construction runs in $poly(n)2^{n/2}$ time.

To finish the construction, we note that the original CNF instance has a solution iff there is a subset in $F_1$ which is disjoint to some subset in $F_2$.

Adding some extra elements to your ground set in addition to the ones for each clause, it is not too hard to embed this disjointness problem as a question of
set inclusion. You basically take the complements of the subsets in $F_1$. To make sure two sets in $F_1$ isn't counted as an inclusion you add a code from an anti-chain
on the extra elements. Another anti-chain code (on other extra elements of the ground set) is used on the subsets of $F_2$ to make sure no pair of subsets from $F_2$ form an inclusion.
Finally, all sets formed from $F_1$ includes all elements of $F_2$'s anti-chain codes.

This is a set inclusion question on $2^{n/2+1}$ subsets on a $d=poly(n)$ ground set. The argument basically goes back to some early paper of Ryan Williams (can't remember which).


A decision problem which is not known to be in PH but will be in P if P=NP

If an artificial example is really as good as a natural one, then I can indeed provide such an example!

Edit: Furthermore, my example is "somewhat" less of a cheat than the one suggested by Ravi Boppana (where we take L to be the empty language if P = NP and the halting problem otherwise), in that I'll define the language L by giving a finite procedure to decide whether $x \in$ L for any input x.  At no point will deciding whether x∈L require solving an "unbounded" mathematical question such as P vs. NP.

Without further ado: let $M_1, M_2, ...$ be an enumeration of polytime Turing machines.  For all $n$, let $M_{t(n)}$ be the lexicographically first $M_i$ that correctly decides 3SAT on all inputs of length $n$ or less.  Then define the language L as follows: for all inputs $x$ of size $n$, $x \in$ L if and only if the Turing machine encoded by $x$ halts in at most $n^{t(n)}$ steps when run on a blank tape.

Claim 1: If P = NP, then L $\in$ P.

Proof: If P = NP, then there's some fixed $M_i$ that solves 3SAT for all inputs; hence $t(n) \le i$ for all $n$. QED

Claim 2: If P $\ne$ NP, then L $\notin$ P.

Proof: If $t(n)$ increases without bound, then we can simply apply the Time Hierarchy Theorem. QED

Now, not only is L not in P assuming P $\ne$ NP: one presumes it wouldn't be in PH (or even PSPACE) either!

Incidentally, I wonder if anyone can improve the above construction, to get a language L which is in P if P = NP, but provably not in PH or PSPACE if P $\ne$ NP?


Is there a method for proving non-regularity of string transformations?

Your question is not entirely well defined: how are you given the transformation you start with?
For example, if you assume the transformation is given by e.g. a Turing machine, then clearly there is no algorithmic way of deciding whether it's a regular transduction.

However, it seems that what you're asking is whether there is some "machine-independent" characterization of string transductions (e.g., Myhill-Nerode).

While I don't know of such a characterization in general (I'm pretty sure no such characterization is known), there is such a characterization for string transducers with origin information, developed by Bojnaczyk.

You can start here.


Suppose you have $n$ numbers $x_1,\ldots,x_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC0, so in AC0 we can compute, for each $x_i$, a binary vector $v$, defined by $v_j = 1$ if $x_j \geq x_i$. In TC0 we can sort $v$ to $w$, and then locate (in AC0) the position $k$ such that $w_k = 1$ while $w_{k-1} = 0$ (where $w_0=0$, $w_{n+1}=1$). Given these values $k$ for each $i \in [n]$, we can compute the sorted array in AC0. In total, we get a TC0 circuit.


What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?

They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description of $g_x$ gives a uniform construction of $g_x$ from $x$. So we have $GC(x) \leq 2 + K(g) \leq K(x) + O(1)$.


Can boolean algebra be expressed in simply typed lambda caclulus?

The OP wrote above that the question is answered by a post on @AndrejBauer's blog.


Complexity of minimising polynomial formula size

You can reduce the co-NP-Complete TAUTOLOGY problem (given a Boolean formula, is it a tautology?) to the problem of minimizing formula size (since a formula is a tautology iff it's equivalent to TRUE). Moreover, TAUTOLOGY for 3DNFs (analogously to SAT for 3CNFs) is co-NP-Complete.


Weakly normalizing + confluent = strongly normalizing?

Is it the case that a confluent weakly normalizing system is strongly normalizing?  Why/why not?

No, it's not necessarily the case.

Weak normalization means: there exists a reduction strategy that will lead to a normal form.
People often use confluence to mean what rewriting people call "local confluence": this is the property that if $a \leadsto b$ and $a \leadsto c$, then $b$ and $c$ can be joined -- i.e., there exists a $d$ such that $b \leadsto^\ast d$ and $c \leadsto^\ast d$.

This does not rule out the existence of infinite reduction sequences.

As an example, start with the STLC and add a new base type $X$ and constant $c,d : X$ with the reduction rule $c \leadsto c$ and $c \leadsto d$.

There is a weak normalization strategy: use a weak normalization strategy for the STLC and immediately reduce any $c$ to $d$. The calculus is also Church-Rosser, since it inherits this property from the STLC. But it isn't strongly normalizing since you can reduce a $c$ forever.


Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

On popular request, here is my comment as an answer:

There is an oracle separating $\mathrm{PP}$ from $\mathrm{PSPACE}$: Jacobo Toran, A combinatorial technique for separating counting complexity classes, ICALP 1989. The best result for $\mathrm{P}^\mathrm{PP}$ that I know is a conditional result by Heribert Vollmer: Relating polynomial time to constant depth. TCS, 207: 159-170, 1998.


I am not sure if these results are known. If you define the $t$-thick upper (or lower, does not matter) shadow of $A_k$ as the sets of one level higher (resp. lower) that contain (resp. are contained in) at least $t$ sets from $A_k$, then what you ask for is the $(k+1)/2$-thick upper shadow. As far as I know it is open to determine the size of the smallest $A_k$ whose $2$-thick shadow is empty. Unfortunately I cannot point you to a reference but I think I heard it from Katona. (And in case I am wrong, then I remember incorrectly...)


About a random walk with constant spectral gap

No.

First we have the standard bound for how close the distribution is to stationary after $t$ steps. Letting $v$ be the initial distribution, we have (I write my matrices on the left)
$||(P^tv)_i-(P^t\pi)_i||\le ||P^tv-P^t\pi||_1\le \sqrt n ||P^t(v-\pi)||_2\le \sqrt n \lambda_2^n\sqrt n=n\lambda_2^t$ which is $\le \epsilon$ for $t=\log_{1/\lambda_2}(n/\epsilon)$.

Assume (i) and (ii) hold. So starting from $i$ (or any probability distribution), there is a $\ge \beta - \epsilon$ chance that it hits $j$ on the $\log_{1/\lambda_2}(n/\epsilon)=O_{\lambda_2,\epsilon}(\log n)$th step. If it hasn't hit, there is another $\beta - \epsilon$ chance it will hit in the next so many steps. The expected hitting time is at most $\sum_{m=1}^{\infty}(1-\beta+\epsilon)^{m-1}(\beta-\epsilon) mO_{\lambda_2,\epsilon}(\log n)=O_{\lambda_2,\epsilon,\beta}(\log n)$.


Art gallery variants with pairwise visibility?

I'm not aware of any such work.  However, I would expect that such a problem would be NP-complete and, for polygons with holes, would be as hard to approximate as Set Cover.  The relatively straightforward vertex/vertex guarding problem, in which guards can only lie on vertices and only vertices need to be guarded, is this hard (Eidenbenz, Stamm, and Widmayer (2001)).

For simple polygons, I expect such a problem would be:

NP-complete
APX-hard
Approximable to within a factor of $O(\log(\rm{opt}))$, where opt is the optimum number of guards.

The vertex/vertex guarding problem is APX-hard for simple polygons (Eidenbenz (1998)).

The best algorithms for the art gallery problem for simple polygons are based on building small $\varepsilon$-nets.  In simple polygons, the range spaces induced by visibility polygons have constant VC-dimension.  Circles do as well.  Therefore a range space induced by visibility polygons in a simple polygon, circles, and the intersections and unions thereof, will also have constant VC-dimension and you can get a $O(\log(\rm{opt}))$-approximation algorithm.

I thought about this problem a little for my thesis, but came to the opinion that there weren't any particularly interesting variants that didn't seem to reduce fairly closely to a known problem involving single-guarding.


I’ll comment on why a relation as in the question
$$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
(for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can.

The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $(2^n)!\bmod x$ for $x$ given in binary: simply evaluate the sum modulo $x$, using exponentiation by repeated squaring.

Now, if we could compute $y!\bmod x$ for arbitrary $y$, we could factor $x$: using binary search, find the smallest $y$ such that $\gcd(x,y!)\ne1$ (which we can compute using $\gcd(x,(y!\bmod x))$). Then $y$ must be the smallest prime divisor of $x$.

If we only can do powers of $2$ for $y$, we can still try to compute $\gcd(x,(2^n)!)$ for every $n\le\log x$. One of these will be a nontrivial divisor of $x$, except for the unfortunate case when there is an $n$ such that $x$ is coprime to $(2^n)!$, and divides $(2^{n+1})!$. This is equivalent to saying that $x$ is square-free, and all its prime factors have the same bit-length. I don’t know what to do in this (rather important, cf. Blum integers) case.


Consensus on P = NP in a world where RP = NP

Honestly speaking, I do not think that Stack Exchange is a suitable place to ask for a future prediction.  Despite this, I will post a response because it is fun to play with the idea of fortune telling.

As far as I know, the possibility of P≠RP=NP has not been ruled out.  Moreover, there is a language A such that RPA=EXPA [Hel83, Kur83], which immediately implies that PA≠RPA=NPA.  (I have not checked [Hel83] or [Kur83], and I took the result and the references from the remark after Theorem 6 in [Hel86].)  In other words, even proving the implication RP=NP ⇒ P=NP requires a nonrelativizing technique, and therefore it is understandable that this implication has not been proved.

(Lance Fortnow has discussed a similar result in the Computational Complexity blog: Oracle Results are Good For You.)

Now let’s turn to the fortune-telling part.

How much does this oracle result tell about the likeliness of P=NP in the world where RP=NP has been already proved?  Not much.  At the very least, it should not be taken as evidence that in the world where RP=NP has been proved, it is still likely to be difficult to prove P=NP.  In such a world, some new, powerful nonrelativizing techniques are known to human, and therefore it would not be reasonable to interpret “requires a nonrelativizing technique” as evidence for difficulty.

Speaking more broadly, if RP=NP has been proved despite all the beliefs (and also proof technique barriers) against it, then our current intuitive understanding about efficient computation is likely to be very wrong.  Obviously we cannot apply our current intuition to reason about the world where our current intuition fails spectacularly.  I do not think that we can make an educated guess about such a world except for what has been rigorously proved.

References

[Hel83] Hans Heller.  On relativized polynomial hierarchies extending to two levels.  In Proceedings of Conference on Computational Complexity Theory, pp. 109–114, UC Santa Barbara, March 1983.

[Hel86] Hans Heller.  On relativized exponential and probabilistic complexity classes.  Information and Control, 71(3):231–243, Dec. 1986.  DOI: 10.1016/S0019-9958(86)80012-2.

[Kur83] S. Kurtz (Stuart A. Kurtz?).  The fine structure of NP: Relativizations.  In Proceedings of Conference on Computational Complexity Theory, pp. 42–50, UC Santa Barbara, March 1983.


Non-bipartite connected cubic graphs have the unique optimal solution $x_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.

Proof: In a cubic graph, if you sum over all $3n/2$ constraints $x_i + x_j \le 1$, you have $\sum_i 3 x_i \le 3n/2$, and hence the optimum is at most $n/2$.

The solution $x_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.

In a bipartite cubic graph, each part has half of the nodes, and the solution $x_i = 1$ in one part is hence also optimal.

Any optimal solution must be tight, that is, we must have $\sum_i 3 x_i = 3n/2$ and hence $x_i + x_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.


What is a "level-r pseudo expectation functional"?

The degree $r$ pseudo-expectation operator operates on polynomials of at most degree $r$. Since the pseudo-expectation operator is positive semidefinite, we're guaranteed that the square of a polynomial (or sum of squares of polynomials) always has nonnegative pseudo-expectation.

Also, if we have a system of polynomial equations $\{p_i = 0\}$ of degree at most $r/2$, then we can construct the pseudo-expectation operator to be such that the pseudo-expectation $\tilde{\mathbb{E}}[p_i q] = 0$ for all polynomials $q$ of sufficiently small degree.

The intuition should be that if $\{p_i=0\}$ has a feasible solution, then $\mathbb{E}[ p_i(x) ] = 0$ where $x$ is a random feasible solution to $\{p_i = 0\}$ and $\mathbb{E}$ is the "actual" expectation operator.

But of course, it is not possible for us to directly sample this distribution. Instead we play a sort of game where we assume that we can evaluate various expectations of polynomials $\mathbb{E}[p]$ (that is, moments) of this distribution over feasible solutions, and 'combine' them together to get a feasible solution.

But of course, we don't really have those moments, either, because again it's too hard to sample the distribution. So we instead use the SoS algorithm to find a pseudo-distribution and pseudo-expectation operator that we can evaluate to get pseudo-moments $\tilde{\mathbb{E}}[p]$, and feed the pseudo-moments to the same 'combiner' algorithm as if they were actual moments, and sometimes we get an answer out that's actually not half bad.

Edit: It is better to consider the sum of squares SDP as optimizing a particular pseudo-expectation; for example, in Goemans-Williamson, we maximize $\tilde{\mathbb{E}}[ \langle x, Lx \rangle]$ where $L$ is the Laplacian and this corresponds to maximizing the value of our cut.


Algorithms for printing the digits of pi, minimizing the time spent between digits

($M(n)$ is "the time required to perform precision
$n$
multiplication.") $\:$ By page 10 of this paper,

a precision-$n$ approximation to $\pi$ can be computed in time $\;\; O\Big(\hspace{-0.04 in}M(n)\hspace{-0.02 in}\cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \;\;\;$.

By the very end of this paper, one can find a rational number $c$ such that for all $n$,

the first $n$ bits of $\pi$ are the first $n$ bits of every precision-$\hspace{-0.03 in}\lfloor (19.9\hspace{-0.04 in}\cdot \hspace{-0.04 in}n)\hspace{-0.04 in}+\hspace{-0.04 in}c\rfloor$ approximation

of $\pi$, so the first $n$ bits of $\pi$ can be computed in time $\;\;\; O\Big(\hspace{-0.04 in}M(n) \cdot \hspace{-0.02 in}\log(n)\hspace{-0.04 in}\Big) \:\:\:\:$.

Thus, if $\Theta$$(M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))$ has a time-constructible function, one can print $\pi$ "with the time

spent between printing digit" $n\hspace{-0.04 in}-\hspace{-0.05 in}1$ "and digit $n$ being" $\;\; O\Big(\hspace{-0.05 in}\big(\hspace{-0.02 in}M(n)\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)\hspace{-0.02 in}\big)\big/n\hspace{-0.04 in}\Big) \;\;$, $\;\;$ as follows:

(Recall that the 0th and 1th bits of $\pi$ are both "1".) $\;\;\;$ Set $\: i = 0  \:$ and $\: t_{curr} =1 \:$ and output "1", then run the following loop forever. $\;\;\;$ Compute [the first $2^{\hspace{.02 in}i+2}$ bits of $\pi$] and $\big[\hspace{-0.02 in}$an integer

$t_{next}$ in $\Theta \hspace{-0.04 in}\left(\hspace{-0.02 in}M\hspace{-0.04 in}\left(\hspace{-0.02 in}2^i\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{-0.02 in}\right)$ such that $t_{next}$ is an upper bound on the time it will take to compute

$t_{next}$ and those bits of $\pi \big]$. $\:$ At the start of those computations, output the $2^i\hspace{-0.03 in}$-th bit of $\pi$.

Interleaved with those computations, output a bit of $\pi$ approximately $t_{curr}\hspace{-0.03 in}\big/\hspace{-0.02 in}2^i$ steps after outputting the previous bit of $\pi$. $\:$ At the end of those computations, output the rest of the first $2^{\hspace{.02 in}i+1}$ bits of $\pi$, then increment $i$, set $\: t_{curr} = t_{next} \:$, $\:$ and go back to the beginning of this loop.

With the fastest known integer multiplication algorithm,

that would achieve $\;\;\; t\hspace{.02 in}(n) \: = \: (\log(n))^{\hspace{.02 in}2}\hspace{-0.05 in}\cdot 8$$\hspace{.02 in}\log^{\hspace{-.02 in}*}$$(n)$$\;\;\;$.

To avoid that general trick, one should probably impose a sublinear space bound.


How to compute the disagreement between hypotheses

One major task of computational learning theory is to try to handle questions like this for specific classes.  In general, if you assume no structure on the hypothesis space, you basically have no choice but to look at each hypotheses individually.  On the other hand, if there is a lot of structure, eg. if you assume the hypotheses are linear separators, say in $\mathcal{R}^2$, you can see that it's possible to be quite efficient even though there are infinitely many linear separators!

The same thing happens for trying to find the ERM (empirical risk minimizing) hypothesis in a class.  This is important for PAC learning. Sometimes it's easy, sometimes it's not.


Number of Vertex Covers: when it is polynomial and when it is superpolynomial

There's a close relation between the independence number of a graph and the number of its vertex covers, not close enough to completely answer your question but close: if the independence number is superlogarithmic then the number of covers is superpolynomial, and otherwise it's quasipolynomial.

More specifically if the independence number is $\alpha$, and the maximum independent set $I$ is the complement of a vertex cover $C$, then each of the $2^\alpha$ supersets of $C$ is also a vertex cover. So in this case if $\alpha \ge c\,\log_2 n$ then the number of covers is lower bounded by $n^c$. But each cover is complementary to an independent set and there can be only $O(n^\alpha)$ sets of at most $\alpha$ vertices, so if $\alpha \le c\,\log_2 n$ then this upper bound is $O(2^{c\, \log^2 n})$.


Is this a known combinatorial optimization/scheduling problem?

Your problem is equivalent to Shortest Common Supersequence (SCS) and was considered in $[1]$ by the name Scheduling on batch machines with precedence constraints as chains and compatibilities. If items in the problem are of the same color then such problem is in P and can be solved in $O(n^2)$  $[2]$.

What concerns approximability a good source is A compendium of NP optimization problems.

The lastest results on SCS can be found in $[3,4]$.

For practical algorithms see $[5]$ whose author states that "Hybrid MA-BS is a current state-of-the-art technique for the SCSP $[6]$ ".

Brauner N., Naves G. Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility.
Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).
Timkovsky V. G. Some Approximations for Shortest Common Nonsubsequences and Supersequences.
Gotthilf Z. and Lewenstein M. Improved Approximation Results on the Shortest Common Supersequence Problem.
Kubalik J. Efficient stochastic local search algorithm for solving the shortest common supersequence problem.
Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem.


perfect graphs were first motivated by information transmission theory originating with Shannon ie Shannon Capacity of graphs. they are called "perfect" by Berge because they can be used to model a noiseless or "perfect" information channel wrt transposition errors in transmission called "confounding". from intro in [3] which also has a very detailed history in the 1st chapter cowritten by Berge.

  When Claude Berge defined perfect graphs in 1961, he was motivated by a very practical problem: how do we maximize the rate at which information is sent through a (noisy) transmission channel while avoiding the introduction of errors because of the physical imperfections of the system?

[1] C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math.
20, No.1 (1996) 5-10.
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics
165-166 (1997) 61-70.
[3] Perfect Graphs by Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), J.L.R. Alfonsin (Author). Wiley. Ch1, Origins and Genesis by Berge & Ramírez-Alfonsín


Computability of infinite-dimensional vector space

Short answer

The general answer is that computability is easy for locally compact spaces, doable for separable spaces, and hard for non-separable spaces.

The short anwer for a particular example, namely $\ell^2$ is: in order to get computability on $\ell^2$ working, represent an element $x$ of $\ell^2$ by a program which accepts $n$ and gives (the list of coefficients of) a finite rational linear combination of the standard basis vectors which is within $2^{-n}$ of $x$ in the $\ell^2$ norm.

Long answer

One general way of equipping a space $X$ with computability is to choose a datatype $\mathtt{T}$ in your favorite programming language (it can be Turing machines and tapes if you're into 1950's memorabilia, otherwise I would recommend a reasonable programming language such as Haskell), and a realizability relation $\vdash_X$ on $\mathtt{T} \times X$, where $\mathtt{d} \Vdash_X x$ means "datum $\mathtt{d}$ represents (implements, realizes) the point $x \in X$". For instance, if $X$ is the space of all finite graphs, then $\mathtt{T}$ could be the datatype of adjancency matrices. If $Y$ is another space with a computability structure, then a map $f: X \to Y$ is said to be computable or realized if there is a program $\mathtt{p}$ such that $\mathtt{d} \Vdash_X x$ implies $\mathtt{p}(\mathtt{d}) \Vdash_Y f(x)$, i.e., $\mathtt{p}$ does to the representing data what $f$ does to points.

The most important principle to always keep in mind is that computability is about computability of structure, not computability of a bare set.

For instance, it makes no sense to ask "Is $\pi$ computable?" or even "Which elements of $\mathbb{R}$ are computable?" You must first make up your mind about what structure of $\mathbb{R}$ you want to consider, and then see if you can make it computable.
The correct computability structure on $\mathbb{R}$ turns out to be:

arithmetical operations must be computable (including the constants $0$ and $1$)
the order relation $<$ must be semidecidable,
there is a program which, given $d \vdash_{\mathbb{R}} x$ and $k \in \mathbb{N}$, computes a rational approximation of $x$ with precision $2^{-k}$,
the limit operator $\lim$ which assigns to every rapid Cauchy sequence of reals its limit, is computable. (A sequence $(x_n)$ is rapid if $|x_n - x_m| \leq 2^{-\min(n,m)}$ for all $m, n$. The point is that we need to have a known rate of convergence, any other rate would do just as well.)

If you leave out anything, or try to add more, you will get into trouble by either having many non-equivalent computability structures on $\mathbb{R}$, or none. A datatype for representing reals for which all of the above can be implemented is
$$\mathtt{nat} \to \mathtt{rational}$$
where a function $\mathtt{p}$ represents a real $x$ when, for every $n \in \mathbb{N}$, $\mathtt{p}(n)$ returns (a representatve of) a rational number $q$ such that $|x - q| \leq 2^{-n}$. (Such a function $\mathtt{p}$ may be represented by a Turing machine, or a piece of source code, or an expression in $\lambda$-calculus.)

Let us now look at an infinite dimensional space $\ell^2$. It is a real Hilbert space with a countable orthonormal basis, so the relevant structure is:

vector space structure: $0$, $+$, $-$ and scalar multiplication,
the scalar product: $\langle {-}, {-} \rangle$
completeness: given a rapid Cauchy sequence $(x_n)$ in $\ell^2$, we can compute $\lim_n x_n$
basis: for every $x \in \ell^2$ we can compute a sequence $(\lambda_n)$ of real numbers such that $x = \sum_n \lambda_n \cdot e_n$ where $$e_n = (\underbrace{0, \ldots, 0}_n, 1, 0, 0, \ldots)$$ is the canonical orthonormal basis.

Now the question is what datatype we should choose to represent $\ell^2$ so that all of the structure is computable. A simple one that works is
$$\mathtt{nat} \to \mathtt{list}(\mathtt{rational}),$$
i.e, we can represent an element $x \in \ell^2$ with a function $\mathtt{p}$ that accepts a natural number and returns a finite list of rational numbers. The realizability relation is
$$\mathtt{p} \Vdash_{\ell^2} x$$
is defined as follows: for every $n \in \mathbb{N}$, $p(n)$ is a list of rationals $[q_0, \ldots, q_m]$ such that $\|x - \sum_{i=0}^m q_i e_i\|_2 \leq 2^{-n}$. I leave it as an exercise to verify that with this representation we can indeed implement all of the structure of $\ell^2$, as stated above.

Further reading (sorry for blowing my own horn):
A. Bauer, J. Blanck:
Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions", J. UCS 16(18): 2496-2522 (2010)


Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth should be $\Theta(n^{1-1/d})$. This family of graphs is contained in the family of graphs of low density graphs in $\mathbb{R}^d$. I have a paper (with Kent Quanrud) on low density graphs: http://sarielhp.org/p/14/low_density/low_density.pdf. Sorry for the shameless self promotion, etc.


Literature for restrictions that make NPC-Problems to P

While there are numerous individual examples of sharp thresholds (2-coloring vs 3-coloring is another one), probably the best structural result along the lines you're looking for is Schaefer's dichotomy theorem.

Roughly speaking, the theorem looks at very general classes of problems (called constraint satisfaction problems) and completely characterizes (merely in terms of the kind of input) when the problem is NP-complete and when it's in P.

I haven't read it, but the linked wikipedia page indicates a recent survey by Hubie Chen that presents this result in a more general framework.


Removing recursion - a look into theory behind the scenes

You might want to look at the SECD machine. A functional language (though it could be any language) is translated into a series of instructions that manage things such as putting arguments of stacks, "invoking" new functions and so forth, all managed by a simple loop.
Recursive calls are never actually invoked. Instead, the instructions of the body of the function being called is placed on the stack to run.

A related approach is the CEK machine.

These have both been around for a long time, so there's plenty of work out there on them. And of course there are proofs that they work and the procedure for "compiling" a program into SECD instructions is linear in the size of the program (it doesn't have to think about the program).

The point of my answer is that there is an automatic procedure for doing what you want. Unfortunately, the transformation won't necessarily be in terms of things that are immediately easy for a programmer to interpret. I think the key is that when you want to iterize a program, you need to store on the stack what the program needs to do when you return from an iterized function call (this is called a continuation). For some functions (such as tail-recursive functions) the continuation is trivial. For others the continuation maybe very complex, especially if you have to encode it yourself.


Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices

Yes, there are several papers on this topic, and related ones, in the context of ant colony optimization algorithms for routing on ad hoc or mobile area networks (MANETs).  In a MANET, the nodes in the network graph are mobile, and if they move too far away from their neighbors, they fall out of range, hence the communication link is broken (i.e., the edge disappears from the network graph).  The routing problem essentially is: how do I keep all the vertices connected, and maintain efficient pathways between nodes, when links can disappear and reappear?  Of course, if a node moves out of range from all other nodes, it is the same as if the node were deleted from the network graph.

The paper An ant colony optimization routing based on robustness for ad hoc networks with GPSs  by Kadono et al. contains a "related work" section you will probably find interesting.  In this paper I've linked, there is an assumption of the availability of some GPS information, which probably does not apply to you; I chose it mainly for its discussion of other papers.  However, all these approaches assume something about how nodes can be deleted (or suddenly appear), in order to construct an efficient algorithm.  You'll have to decide what formal assumptions hold for the problem you are trying to solve.

Search phrases like "ant colony optimization MANET" or "ant colony optimization self-stabilization" may turn up other papers of interest to you.


I dreamt of a data structure, does it exist?

You're describing the classical Bentley-Saxe logarithmic method, applied to static sorted arrays.  The same idea can be used to add support for insertions to any static data structure (no insertions or deletions) for any decomposable searching problem.  (A search problem is decomposable if the answer for any union $A\cup B$ can be computed easily from the answers for the sets $A$ and $B$.)  The transformation increases the amortized query time by a factor of $O(\log n)$ (unless it was already bigger than some polynomial in $n$), but increases the space by only a constant factor.  Yes, it can be deamortized, thanks to Overmars and van Leeuwen, but you really don't want to do that if you don't have to.

These notes cover the basics.

Cache-oblivious lookahead arrays are the mutant offspring of Bentley-Saxe and van Emde Boas trees on steroids.


Generating set of a group and relation to diameter?

The answer to the first part of your question is yes.

Given a permutation group $G = \langle S \rangle$, there is a polynomial time algorithm (clearly more efficient than the brute force approach which has factorial complexity), the Schreier-Sims algorithm (https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm) which computes a base and strong generating set (BSGS) that can be used to compute the order of the group (hence decide if $G=S_n$).
A good reference seems to be Seress' Permutation Group Algorithms and especially chapter 4.

Also, this question can be solved in practice by using GAP $\texttt{IsSymmetricGroup}$ (https://www.gap-system.org/Manuals/doc/ref/chap43.html), which implements this method.


As time can be a resource, it is a bit unclear to me what you seek.

Nevertheless, you might want to look at weighted extensions of LTL, like Metric Temporal Logic first defined here. (Specifying real-time properties with metric temporal logic)


Follow-the-leader algorithm in swarm formation: literature on the subject?

Bernard Chazelle has done some work on the convergence of bird flocking, and he's considered models such as follow-the-leader and variants.


Infinitely large but locally finite computation problems

Just to give some ideas of what is possible (but somewhat non-trivial), here is one example: a distributed algorithm that finds a maximal edge packing on a bounded-degree graph.

Problem definition

Given a simple undirected graph $G = (V,E)$, an edge packing (or fractional matching) associates a weight $w(e)$ with each edge $e \in E$ such that for each node $v \in V$, the total weight of edges incident to $v$ is at most $1$. A node is saturated if the total weight of incident edges is equal to $1$. An edge packing is maximal if all edges have at least one saturated endpoint (i.e., none of the weights can be greedily extended).

Observe that a maximal matching $M \subseteq E$ defines a maximal edge packing (set $w(e) = 1$ iff $e \in M$); hence it is easy to solve in a classical centralised setting (assuming $G$ is finite).

Edge packings actually have some applications, at least if one defines an application in the usual TCS sense: the set of saturated nodes forms a $2$-approximation of a minimum vertex cover (of course this makes only sense in the case of a finite $G$).

Model of computation

We will assume that there is a global constant $\Delta$ such that the degree of any $v \in V$ is at most $\Delta$.

To keep this as close to the spirit of the original question, let us define the model of computation as follows. We assume that each node $v \in V$ is a Turing machine, and an edge $\{u,v\} \in E$ is a communication channel between $u$ and $v$. The input tape of $v$ encodes the degree $\deg(v)$ of $v$. For each $v \in V$, the edges incident to $v$ are labelled (in an arbitrary order) with integers $1,2,\dotsc,\deg(v)$; these are called local edge labels (the label of $\{u,v\} \in E$ can be different for $u$ and $v$). The machine has instructions with which it can send and receive messages through each of these edges; a machine can address its neighbours by using the local edge labels.

We require that the machines compute a valid edge packing $w$ for $G$. More precisely, each $v \in V$ has to print on its output tape an encoding of $w(e)$ for each edge $e$ incident to $v$, ordered by the local edge labels, and then halt.

We say that a distributed algorithm $A$ finds a maximal edge packing in time $T$, if the following holds for any graph $G$ of maximum degree $\Delta$, and for any local edge labelling of $G$: if we replace each node of $G$ with an identical copy of the Turing machine $A$ and start the machines, then after $T$ steps all machines have printed a valid (globally consistent) solution and halted.

Infinities

Now all of the above makes perfect sense even if the set of nodes $V$ is countably infinite.

The problem formulation and the model of computation do not have any references to $|V|$, directly or indirectly. The length of the input for each Turing machine is bounded by a constant.

What is known

The problem can be solved in finite time even if $G$ is infinite.

The problem is non-trivial in the sense that some communication is necessary. Moreover, the running time depends on $\Delta$. However, for any fixed $\Delta$, the problem can be solved in constant time regardless of the size of $G$; in particular, the problem is solvable on infinitely large graphs.

I have not checked what is the best known running time in the model defined above (which is not the usual model used in the field). Nevertheless, a running time that is polynomial in $\Delta$ should be fairly easy to achieve, and I think a running time that is sublinear in $\Delta$ is impossible.


What are the general direction and target question in the field of quantum error correction?

One big open question is the existence of "good" quantum LDPC codes. These are stabilizer quantum error correcting codes with constant check weight, constant rate and linear distance. Most recently there was a series of breakthroughs on this front by Hastings, Haah and O'Donnell (arXiv:2009.03921), Breuckmann and Eberhardt (arXiv:2012.09271) and Panteleev and Kalachev (arXiv:2012.04068).


Is there a notion of "inevitable reduction?"

I have never heard of this exact concept in rewrite theory, which certainly doesn't prove it hasn't been considered.

However, I will make the point that it may not be quite as useful a concept as it first appears, at least in classical rewrite theory because it behaves poorly under substitution:

If $t\rightarrow t'$ is an inevitable reduction, and $t$ contains a free variable $x$ which also appears in $t'$, then $t[u/x]\rightarrow t'[u/x]$ is never an inevitable reduction if $u$ is not normal (since if $u\rightarrow u'$ then $t[u/x] \rightarrow t'[u'/x]$ can avoid $t'[u/x]$).

It would seem that inevitable reducts are quite rare in general, even for pretty reasonable systems, except for normal forms (which are interesting for other reasons). Obviously this only holds for general notions of reductions; specific strategies might have many more (deterministic strategies only have inevitable reductions).

In general, rewrite theorists are more interested in which redexes need to be reduced (to hit normal forms) rather than which terms need to be hit. This has been studied quite a bit, under the name of needed reductions: a needed redex is one that must be triggered in order to reach a normal form. See e.g. Needed reduction and spine strategies for the lambda calculus or Reduction Strategies for Left-Linear Term Rewriting Systems.

I believe this latter notion is stable under substitution for reasonable systems (say, orthogonal).


How should I perform research as an Undergraduate

Yes, ask your professor to give you a problem that you may solve as an undergraduate. You can also look for publications that say that the problems are appropriate for undergraduates.

I think that a research project that you could do that would be interesting would be to create a language that would compile to the EVM (I suggest scratch https://scratch.mit.edu/).

Another would be to explore user interface design for voice systems like making an Alexa App or one that you create yourself to solve some problem that you face.

A good example can be found at http://www.ics.uci.edu/~theory/269/020125.pdf


Finding a ranking which minimizes the number of conflicts

This is a special case of metric $1$-medians, where the metric space is $S_n$ (the symmetric group on $n$ elements) with distance function number of inversions (i.e. the distance between two permutations is the number of pairs $i, j: i<j$ s.t. $i$ and $j$ are ordered differently). This distance metric is also known as Kemeny distance and is related to the weak Bruhat order.

This paper by Ailon, Charikar, and Newman considers this and related problems. The problem you're asking about is called Rank Aggregation in their paper. Look at their intro for more references. The problem is NP-hard. A simple 2-approximation is to pick the best of the given $k$ permutations (i.e. the permutation that minimizes the objective function). Here is a proof:

Let $\pi$ be the optimal permutation and $\pi_{j^*}$ the best of $\pi_1, \ldots, \pi_k$. For any $i, j \in [k]$, by the triangle inequality, $d(\pi_i, \pi) + d(\pi_j, \pi) \geq d(\pi_i, \pi_j)$. Sum over all $i, j$, and you get $2n\mathsf{OPT} \geq \sum_j{\mathsf{ALG}(j)}$, where $\mathsf{ALG(j)}$ is the cost of choosing $\pi_j$ as the solution, and $\mathsf{OPT}$ is the cost of the optimal solution. Since $\pi_{j^*}$ was chosen so that $\mathsf{ALG}(j^*)$ is minimum over all $\mathsf{ALG}(j)$ for $j \in [k]$, we have $\mathsf{ALG}(j^*) \leq \sum_j{\mathsf{ALG}(j)} /n$ and we have $\mathsf{ALG}(j^*) \leq 2\mathsf{OPT}$.

The paper I referred you to above has another, almost equally simple 2-approximation (but the proof is not that simple, though still not bad). They can show that the bad cases for the two approximation algorithms are different, and taking the better solution of the two gives 11/7 approximation factor.

Then there is also a PTAS by Mathieu and Schudy (Warren sometimes visits this site btw), by a reduction to weighted Minimum Feedback Arc Set in Tournamets (the same reduction is used in the previous paper, I think). Here is the link


Multiplication of circulant matrices with a diagonal matrix

This problem is essentially equivalent to matrix multiplication. Let's look at $\sum_{i=1}^{n}X_{i}RY_{i}$ first, where $X_i$ and $Y_i$ are diagonal matrices. If $A$ is the matrix with the diagonal entries of $X_i$ as the $i$-th column, and $B$ is the matrix with the diagonal entires of $Y_i$ as the $i$-th row, then the entry-wise product of $AB$ and $R$ is equal to $\sum_{i=1}^{n}X_{i}RY_{i}$. If all entries of $R$ are non-zero (even if it should not be full rank), then $AB$ can be reconstructed from $\sum_{i=1}^{n}X_{i}RY_{i}$. Hence the computational complexity of this problem is identical to the computational complexity of matrix multiplication.

For the case $\sum_{i=1}^{n}A_{i}DB_{i}$, where $A_i$ and $B_i$ are circulant matrices, we first have to apply FFT to $A_i$, $B_i$ and $D$, to get back to the case $\sum_{i=1}^{n}X_{i}RY_{i}$. We need $2n+1$ FFTs of size $n$ for this, so this adds $n^2\log n$ to the complexity.
Also in this case, it can happen that the FFT of $D$ has only very few non-zero entries. In this special case, the complexity will be quadratic times the number of non-zero entries. This can happen, if the i-th entry on the diagonal of $D$ is $r^i$, where $r$ is the $n$th root of unity. But already when $D$ has the same entries but permuted arbitrarily, the FFT of $D$ will not be sparse (in general).


A mathematical (categorical) description of type classes

How do type classes fit in this model?

The short answer is: they don't.

Whenever you introduce coercions, type classes, or other mechanisms for ad-hoc polymorphism into a language, the main design issue you face is coherence.

Basically, you need to ensure that typeclass resolution is deterministic, so that a well-typed program has a single interpretation. For example, if you could give multiple instances for the same type in the same scope, you could potentially write ambiguous programs like this:

class Blah a where
   blah : a -> String

instance Blah T where
   blah _ = "Hello"

instance Blah T where
   blah _ = "Goodbye"

v :: T = ...

main :: IO ()
main = print (blah v)  -- does this print "Hello" or "Goodbye"?

Depending on the choice of instance the compiler makes, blah v could equal either "Hello" or "Goodbye". Therefore, the meaning of a program would not be completely determined by the syntax of the program, but rather could be influenced by arbitrary choices the compiler makes.

Haskell's solution to this problem is to require that each type has at most one instance for each typeclass. To ensure this, it permits instance declarations only at the top level, and furthermore makes all declarations globally visible. That way, the compiler can always signal an error if an ambiguous instance declaration is made.

However, making declarations globally visible breaks the compositionality of the semantics. What you can do to recover is to give an elaboration semantics for the programming language -- that is, you can show how to translate Haskell programs into a better-behaved, more compositional language.

This actually gives you a way to compile typeclasses, as well -- it's usually called the "evidence translation" or "dictionary-passing transformation" in Haskell circles, and is one of the early stages of most Haskell compilers.

Typeclasses are also a good example of how programming language design differs from pure type theory. Typeclasses are a really awesome language feature, but they're quite ill-behaved from a proof-theoretic point of view. (This is why Agda does not have typeclasses at all, and why Coq makes them part of its heuristic inference infrastructure.)


Glencora Borradaile has an interactive graph with turnover time (among other information) for several journals from several sources.

However, not included is the first journal I think of with a fast turnaround time: Information Processing Letters (IPL).  I couldn't find any statistics, but rapid dissemination is their first goal.  When refereeing for a similar Elsevier journal with the same goal of rapid dissemination but with a slightly different scope, they requested my report within about 5 weeks.


Papers on fault handling in distributed systems

You might want to have a look at the works that won Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg the Edsger W. Dijkstra Prize in 2010:

Tushar D. Chandra and Sam Toueg. Unreliable Failure Detectors for Reliable Distributed Systems, Journal of the ACM, 43(2):225-267, 1996
Tushar D. Chandra, Vassos Hadzilacos and Sam Toueg. The Weakest Failure Detector for Solving Consensus, Journal of the ACM, 43(4):685-722, 1996.

These papers introduce the notion of failure detectors in a distributed system in a general and precise framework. Intuitively, they tried to study the minimal amount of failure information needed to solve consensus. It turns out that you don't need a perfect failure detector to solve consensus. Even unreliable failure detectors satisfying certain minimal conditions will suffice for the task. These papers were very influential on how to deal with failures in distributed systems.


Difference between locally testable and it's boolean closure

In ii), you say that $u$ being in $L$ can be deduced only by knowing $pref^k(u)$, $inf^k(u)$ and $suff^k(u)$.

This mean that $L$ can be given by a set $E\subseteq (X^*\times 2^{X^*}\times X^*)$, namely $u\in L$ iff $(pref^k(u),inf^k(u),suff^k(u))\in E$.

The reason why condition i) is stronger is because it forces $E$ to be of the form $P\times 2^I\times S$.

An example of a language which is in ii) but not i) is therefore given by $E=\{ (a,X^*,a),  a\in X\}$. This means that $L$ is just the language of words whose last letter is equal to the first. $L$ is locally testable with $k=1$ for condition ii), but it is not for any $k$ for condition i).


How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill")

Perhaps the corresponding decision problem is NP-complete; given an instance of SUBSET-SUM:

Given $K, x_1,...,x_n$ does exist $A \subseteq \{x_1, x_2, ..., x_n\}$ s.t. $\sum_{x_i \in A}x_i = K$?

Suppose that $k > 0, x_i > 0$ and let $k' = \sum_{i=1..n} x_i - K$

Now, if you pick two bins $B_1, B_2$ with sizes $k$ and $k'$, then $n$ items of sizes $x_i$ can be packed with cost $numparts = n$ if and only if the corrsponding SUBSET-SUM problem has a solution.


Partition into triangles in a 3-partite graphe

A recent paper by Custic, Klinz, Woeginger "Geometric versions of the three-dimensional assignment problem under general norms", Discrete Optimization 18: 38-55 (2015) contains (and proves) the following proposition:

  Proposition 5.1: Partition into triangles on 6-regular tripartite graphs is NP-complete.

Now just follow the reduction in the proof with a NO-instance, and you will get a 6-regular tripartite graph on $3q$ vertices that cannot be partitioned into $q$ triangles.


You could take a collective intelligence approach and try to determine similarity between various users based on their tastes of other images. If I like a bunch of images and another user likes majority of the same images, then it could be said that I will most likely like pictures the other user likes.

You might want to try and find information on Collaborative Filtering, Euclidean Distance/Pearson correlation (within the context of social networks.)


Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets)

The problem is coNP-complete and so unlikely to have a poly-time algorithm.  (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.)

Here is a simple reduction from 3-UNSAT $= \{\psi: \psi$ is an unsatisfiable 3-CNF$\}$.

Say $\psi(x_1, \ldots, x_t) = \bigwedge_{j = 1}^m (y_{j, 1}\vee y_{j, 2} \vee y_{j, 3})$, where
each $y_{j, a}$ is either a variable or a negated variable.

In your notation, let $A = B = \ldots = K = \{0, 1\}$, with $t$ such sets (one for each variable).  Think of each element of $S = A^t$ as an assignment to $x_1, \ldots, x_t$.  For each $j \in [m]$, create a Cartesian product set $S_j$ which describes the set of assignments that will falsify the $j^{th}$ clause.  Note that this can easily be done: we restrict precisely the 3 components corresponding to the variables appearing in this clause.

The union of the $S_j$'s equals all of $S = \{0, 1\}^t$ iff every assignment to $\psi$ falsifies some clause, i.e., iff $\psi$ is unsatisfiable.


As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case of (a variant of) the Prize-Collecting Travelling Salesman Problem (PCTSP), which seems to be introduced in [1] (NB: Technical report, written on typewriter. Hard to read):
Given a graph $G$ and a prize $w_v$ and a penalty $p_v$ for each vertex $v \in G$, you are asked to construct a tour that minimizes the cost of travelling, plus the penalty for every vertex you do not visit. In addition, you have the constraint that the combined prize for every vertex you do visit must be higher than some prescribed sum $W$.
If you are allowed to put negative values on your prizes, your problem can be formulated as a PCTSP this way:

Let $p_v = 0$ for every $v\in V$
Let $w_a = n$ for every $a\in A$
Let $w_b = -1$ for every $b\in B$
Let $W = n\cdot |A| - k$

It's worth it to add that having shorter routes often will lead to cheaper tours anyway. For example, if $G$ is metric, then you can just solve TSP on $G[A]$, as visiting any vertices in $B$ will be considered a detour.
[1] Balas, Egon, The prize collecting traveling salesman problem, Networks 19, No. 6, 621-636 (1989). ZBL0676.90089.


How hard is it to learn a linear modular function?

I assume you want an efficient algorithm, e.g., one whose running time is polynomial in $n$.  (If you don't care about running time, then heuristically about $4n/\lg m$ samples should suffice to uniquely determine $a,b,m,p$, and you can use exhaustive search over all possible $2^{4n}$ parameter choices to find the correct one.  Of course, the running time of this method is exponential in $n$, so I assume it is not what you are looking for.)

In the case where $p=m$, this generator is known as a linear congruential generator.  It is known to be weak.  See my answer to Cracking a linear congruential generator (on IT Security.Stack Exchange) for an efficient algorithm that breaks this pseudorandom generator.

To summarize the  security of the generator (when $p=m$): A constant number of samples is enough to break the generator.  The algorithm requires only simple arithmetic and requires only a constant number of additions and multiplications, followed by a gcd operation.  I don't know whether this generator going to be pseudorandom for any particular complexity class, like TC0 or AC0; perhaps others will have insights on that.

Note that if you are picky about requiring a cryptanalysis algorithm to succeed with probability 1, and run in polynomial time without any randomness, then you won't like my algorithm.  My algorithm runs in polynomial time, and succeeds in recovering $f$ on an overwhelming majority of inputs; as a consequence, it succeeds in distinguishing the output of this pseudorandom generator from a true-random stream with advantage close to 1.  In the cryptographic world, this constitutes a "break" of the security of the generator.  However, if you wanted a learning algorithm that succeeds (in recovering $f$) on all problem instances, and has a fixed running time, my algorithm isn't it.  (Then again, from an engineering perspective, if you want something that is guaranteed to succeed on all problem instances, you won't find it, since any real-life implementation always has some small chance of producing an incorrect answer, e.g., due to a cosmic-ray bit flip.  My algorithm infers $f$ correctly for all but an exponentially small fraction of inputs. You can choose parameters so the probability of error due to unlucky choice of inputs is smaller than the probability of error due to a cosmic ray causing a bit flip error. So from an engineering perspective, it's essentially as good as deterministic, for all practical purposes.  But it's possible it might not be what you are looking for, if you care more about complexity classes than about whether the generator is usefully secure in an engineering sense.)

In the general case, I don't know what the most efficient cryptanalysis algorithm will be, but I would be pretty surprised if this is secure.  Linear congruential generators are notorious in the cryptographic community for being insecure.  However, you might enjoy the following paper, which while it does not address the specific question you asked, is somehow related:

Inferring sequences produced by a linear congruential generator missing low-order bits.  J. Boyar.  J. ACM 36(1), pp.129--141, Jan 1989.

Also, since $m$ is not a divisor of $p$, note that there will be a statistical bias of the outputs of this generator.  In particular, values in the range $0 .. b-1$ will be slightly more likely than values in the range $b .. p-1$, where $b= p \bmod m$.  The magnitude of this bias depends (roughly) upon the size of $p/m$; the larger $p/m$ is, the greater the bias.  More precisely, the statistical variation distance between pseudorandom and random, due to this effect, is $\delta = 2b(m-b)/mp$, for a single sample.  Therefore, I would expect that $O(1/\delta^2)$ samples should suffice to distinguish the pseudorandom stream from a truly random stream, simply by exploiting this bias.  This attack does not take into account all of the available structure in the output of the generator, so I would expect that better attacks are probably possible.


Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

It is known that for every pair of naturals numbers n,a such that n <= a <= 2^n, there exists a minimal NDFA with n states whose corresponding equivalent minimal dfa has a states (over a four letter alphabet).

See the paper here: Deterministic blow-ups of minimal nondeterministic finite automata over a fixed alphabet.

Abstract of the paper:

  We show that for all integers n and α
  such that n ≤ α ≤ 2^n, there exists a
  minimal nondeterministic finite
  automaton of n states with a
  four-letter input alphabet whose
  equivalent minimal deterministic
  finite automaton has exactly a states.
  It follows that in the case of a
  four-letter alphabet, there are no
  "magic numbers", i.e., the holes in
  the hierarchy. This improves a similar
  result obtained by Geffert for a
  growing alphabet of size n + 2 (Proc.
  7th DCFS, Como, Italy, 23-37).

So, I suppose the answer to your question is, no.