How hard is this combinatorial optimisation problem?

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP).

First, let's restate the problem:
Given: values $N$ and $T$ and positive integer intervals $R_1$, $R_2$, $\ldots$, and $R_n$
Output: the largest possible value of $\sum_{i=1}^nf(x_i)$ (where $f$ is defined in terms of $N$ as described above) such that the variables $x_1, x_2, \ldots, x_n$ satisfy all of the following:

$x_i \in R_i$ for $i = 1,2,\ldots,n$
$\sum_{i=1}^nx_i \le T$
for all pairs $i,j$, if $\text{median}(R_i) \le \text{median}(R_j)$ then $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_j)}{x_j}$

We can assume without loss of generality that the $R_i$s are sorted by median. That is, assume that $\text{median}(R_1) \le \text{median}(R_2) \le \ldots \le \text{median}(R_n)$. If we do, the final condition can be simplified. It is both necessary and sufficient that $\frac{\text{median}(R_1)}{x_1} \le \frac{\text{median}(R_2)}{x_2} \le \ldots \le \frac{\text{median}(R_n)}{x_n}$.
(Note: this is not precisely correct. Assuming no intervals have the same median, this is correct, but if multiple intervals have the same median it is actually also necessary that the $x_i$ values chosen for those intervals have to all be the same. This makes things more complicated without really making the problem any harder, so I'm going to ignore this possibility for the rest of this answer.)

With that done, we can define the subproblems that we will use for our dynamic programming solution.
Given: all the inputs for the problem as well as (1) an index $k$ with $1 \le k \le n$, (2) a threshold $t$ with $0 \le t \le T$, and (3) a value $X \in R_k$
Output: the largest possible value of $\sum_{i=1}^kf(x_i)$ such that the variables $x_1, x_2, \ldots, x_k$ satisfy all of the following:

$x_i \in R_i$ for $i = 1,2, \ldots, k$
$x_k = X$
$\sum_{i = 1}^kx_i \le t$
for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Let $S[k][t][X]$ denote the output of this subproblem.

Note that the overall problem's answer can be expressed in terms of several subproblems: the overall answer is $\max_{X \in R_n}S[n][T][X]$.
Note also that the number of subproblems is small (polynomial in the size of the numbers in the input of the problem). In particular, $k$ takes on $n$ possible values, $t$ takes on $T+1$ possible values, and $X$ takes on $\sum_{i=1}^n|R_i|$ possible values. Each of these is polynomial in the numbers used as inputs to the problem. Therefore, the overall number of subproblems is also polynomial in the numeric value of the input. Thus, provided we can show that each subproblem can be solved in pseudo-polynomial time, it will also be the case that all the subproblems together can be solved in pseudo-polynomial time, and therefore that the overall problem can be solved in pseudo-polynomial time.

In order to actually solve the subproblems, we will use dynamic programming. In other words, we will build up a table of values for $S[k][t][X]$. We can compute these subproblems in order primarily by $k$. In other words, we can assume that by the time we are computing $S[k][t][X]$, the value of $S[k'][t'][X']$ has already been computed provided $k' < k$.
So how do we actually compute these values?
The base case, where $k=1$, is easy. $S[1][t][X]$ is defined as the largest possible value of $\sum_{i=1}^kf(x_i) = f(x_1)$ where $x_1 = X \le t$. Therefore, provided $X \le t$, we have that $S[1][t][X] = f(X)$. Otherwise, no such value is possible and so we can set $S[1][t][X]$ to $-\infty$ to indicate that no real value is achievable.
Otherwise, let's say we're trying to compute $S[k][t][X]$ for some $k > 1$. This value is defined as the largest possible value of $\sum_{i=1}^kf(x_i)$ subject to the following constraints:

$x_i \in R_i$ for $i = 1,2, \ldots, k$
$x_k = X$
$\sum_{i = 1}^kx_i \le t$
for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Since we know $x_k = X$, the value we are maximizing is $\sum_{i=1}^kf(x_i) = f(x_k) + \sum_{i=1}^{k-1}f(x_i) = f(X) + \sum_{i=1}^{k-1}f(x_i)$. This is the same as just maximizing $\sum_{i=1}^{k-1}f(x_i)$. What conditions do the variables $x_1, \ldots, x_{k-1}$ have to satisfy? We can reframe the above conditions as follows:

$x_i \in R_i$ for $i = 1,2, \ldots, k-1$
$\sum_{i = 1}^{k-1}x_i \le t - X$
for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$
it is the case that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$

By the final condition, only some of the possible values of $x_{k-1}$ are actually permissible values. In particular, we have the condition that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$, which can be rearranged to be $x_{k-1} \ge X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}$. Thus, $x_{k-1}$ must be some value from $R_{k-1} \cap [X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}, \infty)$. Call this other interval $R_{k-1}'(X)$
Suppose we fix some value $Y \in R_{k-1}'(X)$ and add the constraint that $x_{k-1} = Y$. At that point, we're trying to maximize $\sum_{i=1}^{k-1}f(x_i)$ subject to the following:

$x_i \in R_i$ for $i = 1,2, \ldots, k-1$
$x_{k-1} = Y$
$\sum_{i = 1}^{k-1}x_i \le t - X$
for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

But this is just the definition of $S[k-1][t-X][Y]$.
It should be pretty clear at this point that $S[k][t][X]$ is just the maximum over $Y \in R_{k-1}'(X)$ of $f(X) + S[k-1][t-X][Y]$. Note: if $R_{k-1}'(X)$ is empty then no choice of values is possible and so we again set $S[k][t][X]$ to $-\infty$. Similarly, we can assume that if $t-X < 0$ then the value $S[k-1][t-X][Y]$ is just defined to be $-\infty$ by default. (Note that this formula appropriate handles the case where some of the $S[k-1][t-X][Y]$ values are $-\infty$).
Anyway, assuming you deal with all the edge cases, this shows that you can compute $S[k][t][X]$ in terms of the previous values $S[k'][t'][X']$ with $k' < k$. The runtime of this computation is linear in the size of $R_{k-1}'(X)$, which is at most $|R_{k-1}|$. Therefore, the computation of each $S[k][t][X]$ is pseudo-polynomial in the input, implying (as previously argued) that the computation of all the subproblems together also runs in pseudo-polynomial time.

EDIT: I was asked to address two specific issues in the comments. First of all, what happens if the function $f$ can depend on which interval $R_i$ it is taken from. And second, what happens if not every interval has to contribute a value (i.e. if you are allowed to skip an $x_i$). I believe the problem is still solvable with the same pseudo-polynomial time dynamic programming approach. I also mentioned earlier that the solution above ignores the possibility that multiple ranges share the same medians. I have not edited the solution above, but to address these concerns, I'm adding a coded up version of my algorithm (using python), fixed to address all these issues.
I assume that the input consists of a value T (representing $T$) and a list Rs, whose elements represent the ranges $R_i$ and which can be looped over. I assume that the elements of Rs are in sorted order by median and that there exists a function median that can identify the median of any such range. I also assume that there exists a function f which takes as input two values: an index i and a value x. f(i, x) is used to represent $f_i(x)$.
def solve(T, Rs):
  if len(Rs) == 0:
    return 0

  # S is going to be the subproblem lookup table. S[k][t][X] will denote
  # the largest possible output value using xs only from ranges Rs[0]
  # through Rs[k] (with each range contributing at most one x), such that
  # the sum of the xs is at most t, and such that range Rs[k] does contribute
  # a value, and the value it contributes is X.
  S = []

  # base case
  layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
  S.append(layer)
  for t in range(T+1):
    for X in Rs[0]:
      if X <= t:
        S[0][t][X] = f(0, X)

  # inductive case
  for k in range(1, len(Rs)):
    layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
    S.append(layer)
    for t in range(T+1):
      for X in Rs[k]:
        # the minimum necessary condition is that X <= t
        if X <= t:
          # if no other range contributes an x, then the smallest possible
          # value is f(k, X)
          layer[t][X] = f(k, X)
          # if some other range does contribute an x, then there is a largest
          # index range which does so; the index of that range is some i < k
          # and we can loop over the possibilities
          for i in range(k):
            # we can also loop over the possible values of what x that range
            # contributed
            for Y in Rs[i]:
              # in order for this to be valid, the following must hold:
              if median(Rs[i]) / Y <= median(Rs[k]) / X:
                # also, if the medians are the same, we also have the
                # constraint that X=Y; therefore, this case is only valid
                # if the following holds
                if median(Rs[i]) != median(Rs[k]) or X == Y:
                  # the best possible value in this case is the following
                  value = f(k, X) + S[i][t-X][Y]
                  # if this is better than anything so far, use this value
                  S[k][t][X] = max(S[k][t][X], value)

  # Now lets actually get the overall answer. One possibility is to use no xs
  # from any range:
  best = 0

  # otherwise, there will be some largest index range which contributes an x
  # and it will contribute some specific X
  for k in range(len(Rs)):
    for X in Rs[k]:
      # the largest possible value in that case subject to all the constraints:
      value = S[k][T][X]
      # we can use that value instead of the best one saved if it's better
      best = max(best, value)

  return best


Computational complexity of random sampling

The answer depends on your computational model. Sometimes people just assume you can generate a Gaussian as a unit operation. However, if all you can generate is, say, random bits, and you want an approximate Gaussian, the complexity depends on the approximation you want.


Knowing if there are two solutions to the subset sum problem

Your (self) answer is ok, but you can also build a reduction in which there is no "trivial" solution.
Start from $X = \{ x_{1}, \ldots, x_{n} \}, x_i > 0$ with target sum $K$ and build:
$X' = \{  8 * x_{1}, \ldots, 8 * x_{n} \} \cup \{ 1, 1, 2 \}$ and target sum $K' = 8*K + 2$
In this case in order to solve the new problem $\langle X', K' \rangle$ you are "forced to solve" the original one, and there are at least two solutions to $\langle X', K' \rangle$ if there is a solution to $\langle X, K \rangle$.


Is the value of $\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf}$ polynomially computable?

Without any further constraints, this expression will in general be unbounded, so the maximum won't exist.

Let $V$ be $\{v_1,\ldots,v_n\}$ with $n\ge 2$. Pick $i\neq j$ such that $v_i,v_j$ are not both isolated. The submatrix of the Laplacian for $v_i,v_j$ has the form $\begin{pmatrix}d_i & -a_{ij} \\ -a_{ij} & d_j\end{pmatrix}$ with $a_{ij}\in\{0,1\}$ and $d_i,d_j\ge a_{ij}$, and $d_i+d_j>0$.

For any $\varepsilon>0$, define a function $f_\varepsilon:V\to\mathbb{R}$ by $f_\varepsilon(v_i) = \sqrt{n}-\varepsilon, f_\varepsilon(v_j) = \varepsilon - \sqrt{n}$, and $f_\varepsilon(v) = 0$ for all other $v\in V$. With this, your expression becomes

$(d_i + d_j + 2a_{ij})\frac{n-2\varepsilon\sqrt{n}+\varepsilon^2}{2\varepsilon\sqrt{n}-\varepsilon^2}$.

$(d_i+d_j-2a_{ij}) \ge 1$ by the above, and for $\varepsilon\to 0$, the numerator and denominator of the fraction converge to $n$ and $0$ (from above); therefore, the expression goes to $+\infty$.


Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?

This seems to be explicit or at least implicit in Lutomirski's 2011 "Component mixers and a hardness result for counterfeiting quantum money" - arXiv

Lutomirski formally defines component mixers as a family $\{M_i\}$ of one-to-one maps between elements of a set $S$ partitioned into $\{S_1,S_2,\cdots,S_c\}$.

He gives a number of example $S$'s, such as the set of all graphs on $n$ vertices, where each partition $S_1,S_2,\cdots,S_c$ corresponds to different isomorphism classes of graphs.  Each element $g\in S$ is a given graph on $n$ vertices, and is a member of only one partition $S_g$.  "Mixing" means to randomly draw another element $g'$ from the same $S_g$.

He notes that for many sets $S$ one can mix easily enough, with permutations or straight-line-programs.  Otherwise, he comments that:

  "In general, given a Markov chain over $S$ that does not mix between components but mixes rapidly over each component, each step of which consists of choosing uniform random sample from a set of invertible rules and applying that rule, then iterating that Markov chain to amplify its spectral gap will give a component mixer."

Lutomirski goes on to provide a $\mathsf{coAM}$ protocol for determining whether the number of components (partitions) is greater than $1$.


Lance, there is in fact a theorem which gives bounds on this. The Margolus-Levitin theorem bounds the rate of computation in terms of energy density. There is a nice trick which can then be played: If the local energy density exceeds a certain limit, a black hole will form causing an event horizon which will essentially prevent you from getting an answer by causally disconnecting that region of space-time from the rest of the universe. Seth Lloyd has a nice paper using this trick to estimate the computational power of the universe (Phys. Rev. Lett. 88, 237901 (2002), arXiv).

You can of course use similar reasoning on any finite region of space-time.


Interdisciplinary topics between control theory and theoretical computer science

Since you mentioned signal processing, you should look at the area of "compressive sensing".  Here is an excellent non-technical description of the main ideas involved: http://terrytao.wordpress.com/2007/04/13/compressed-sensing-and-single-pixel-cameras/


Choices for the group in Public Key Cryptography

Dan Boneh's survey article on the decisional Diffie Hellman problem lists several candidate groups for which the DDH problem is hard, reproduced here:

  Let $p=2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z}^*_p$. It is a cyclic group of prime order. This family of groups is parameterized by $p$.
  More generally, let $p = aq+1$ where both $p$ and $q$ are prime and $q > p^{1/10}$. Let $Q_{p,q}$ be the subgroup of $\mathbb{Z}_p^*$ of order $q$. This family of groups is parameterized by both $p$ and $q$.
  Let $N=pq$ where $p,q,\frac{p-1}2,\frac{q-1}2$ are prime. Let $T$ be the cyclic subgroup of order $(p-1)(q-1)$. Although $T$ does not have prime order, DDH is believed to be intractable. The group is parameterized by $N$.
  Let $p$ be a prime and $E_{a,b}/\mathbb{F}_p$ be an elliptic curve where $|E_{a,b}|$ is prime. The group is parameterized by $p,a,b$.
  Let $p$ be a prime and $J$ be a Jacobian of a hyper elliptic curve over $\mathbb{F}_p$ with a prime number of reduced divisors. The group is parameterized by $p$ and the coefficients of the defining equation.

In particular, #3 is not among the flavors listed in your question.


Given PSPACE $\ne$ EXP, is there a non-PSPACE-hard language in EXP - PSPACE?

The proof of Ladner's theorem doesn't use any special properties of P and NP and the same proof unchanged will show, assuming EXP<>PSPACE, there is a language L in EXP-PSPACE and not EXP-complete under either P-time or PSPACE-reductions.

You need the full Landner look-back trick to keep L in EXP.


Is there any quantum analog of the VP vs. VNP problem?

This is not quite an answer, but some observations that are too long for a comment. I've thought about this question before, but not being an expert in quantum I was never really able to resolve it. The thing you want for this is a polynomial $f$ (really, a family of polynomials $f_n$, one for each $n$) such that $f = (f_n)$ is in some sense complete for $\mathsf{BQP}$ (resp., $\mathsf{QMA}$). While there are many problems on polynomials that show up in quantum classes, they are typically more of the form "Given some input graph G, compute (the coefficients of, or the evaluation of) some polynomial $f_G(x)$ at some point $x$". For example, a natural thing to think of here is the Jones polynomial. Given a link, approximating its Jones polynomial at a root of unity is $\mathsf{BQP}$-complete. Evaluating the Jones polynomial given a link in general is $\mathsf{\# P}$-hard (see references e.g. here). So there are two issues here in using this to define "$\mathsf{VBQP}$": the first is that the Jones polynomial in general is $\mathsf{\# P}$-hard, so if you tried to use it you might end up with $\mathsf{VNP}$ again. Second, it's not just a single family of polynomials, it's a question of the above form (given an input object $G$, compute $f_G$, rather than evaluate $f_n(G)$ which is what we'd want).

Another approach you might try is to consider the amplitudes of the output of a quantum circuit as a polynomial in their inputs. But these amplitudes can be permanents, so again we quickly seem to run into $\mathsf{\# P}$- or $\mathsf{VNP}$-completeness.

Yet another approach you might try is to somehow mimic the "universal circuit" constructions for $\mathsf{VP}$-complete problems (those by Burgisser and then Raz, see, e.g., Mahajan's survey or the references in Section 5 of Mahajan-Saurabh) with universal quantum circuits. Here we run into the issue that there seems to be somewhat of a mismatch between quantum circuits and algebraic circuits. In particular, a quantum circuit on n qubits maintains $2^n$ amplitudes, whereas an algebraic circuit maintains a single ring element on each wire, so a total number which is polynomial in the size of the circuit (linear if you measure size by number of wires or have bounded fan-in). Quantum circuits that maintain much less information than this - e.g. stabilizer circuits or linear-optics circuits - seem not to capture the full power of $\mathsf{BQP}$.

On a related noted, $\mathsf{BPP}$, $\mathsf{MA}$, $\mathsf{BQP}$, and $\mathsf{QMA}$ are all semantic classes with no known syntactic characterization (see, e.g., this or this). My first instinct is that this is related to the fact that algebraic complexity classes like $\mathsf{VP}$ are syntactic, but I'm not sure that's right. At any rate, I don't think we know of any such semantic class with an algebraic analogue.

This is not to say that all of these approaches can't work, just to share some thoughts on them. I hope someone can get it to work!


... it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$.

That is enough for it to have an interactive proof. In fact, Lund et al. proved that every language in polynomial hierarchy (PH) has an interactive proof by using Toda's theorem ($\rm{PH} \subseteq P^{\#P}$). They reduced $L\in \rm{PH}$ to #P-complete language PERMANENT, and provided an algebraic method which can be used to prove PERMANENT interactively. (This is highly inaccurate; please refer to the paper for more info.)

Using their techniques, Shamir proved that IP=PSPACE.

It was previously proved that all IP has zero-knowledge proofs, so:

All languages in PSPACE have zero-knowledge interactive proofs.


In arXiv:quant-ph/0409035v2 Buhrman and Spalek present a quantum algorithm beating the Coppersmith-Winograd algorithm in cases where the output matrix has few nonzero entries.

Update: There is also a slightly improved quantum algorithm by Dörn and Thierauf.

Update: There is an improved quantum algorithm by Le Gall beating Burhman and Spalek in general.


Max-sum graph-partition for maximizing intra-edge weights?

I will consider the case of non-negative weights only. As I mentioned in the comment the problem is related to the minimum k-way cut problem where the goal is to partition a given graph G into k non-trivial components to minimize the number (or weight in the weighted case) of edges crossing the partition. This is the same as maximizing the number of edges in the partitions. Since k-way cut is NP-Hard the maximization problem is also NP-Hard. However, for fixed $k$, $k$-way cut can be solved in polynomial time. In terms of approximation here is an idea to get a simple $(1-2(k-1)/n)$-approximation which is good if $k$ is small compared to $n$. To see this, simply take the partition to be the $k-1$ smallest degree vertices and the rest of the vertices. In terms of the k-way cut the # of edges cut by this partition is at most $2(k-1)/n \cdot |E|$. Thus the number of edges remaining inside the large piece is at least $(1- 2(k-1)/n) |E|$.

Update: If the weights can be negative then I believe the problem is inapproximable via a reduction from k-coloring. Given a graph $G$, set each edge's weight to be $-1$. Thus we are seeking a $k$-partition to minimize the number of edges inside the parts. If $G$ is k-colorable then we can achieve 0, otherwise it will be at least 1. In terms of the negative weights the max value will be 0 if $G$ is k-colorable, otherwise no more than -1.


Are register based machines on von neumann architecture diametrically opposed to functional programming style?

Many hardware designs for executing functional programs have been proposed:

The Lisp Machine
Steele and Sussman's Scheme chip design
The Reduceron, by Naylor and Runciman

and more (lots are cited in the Reduceron papers).


One-sided errors in probablistic proof systems

Allowing completeness error has no problem, and it is often considered.  Here are some pointers.

On the other hand, generally speaking, disallowing soundness error removes the power of a model significantly.

In the case of interactive proof systems, disallowing soundness error renders interaction useless except for one-way communication from a prover to a verifier; that is, IP with perfect soundness is equal to NP.  This can be shown by considering an NP machine which guesses the verifier’s random bits and the transcript of the interaction which make the verifier accept [FGMSZ89].

In the case of probabilistically checkable proof (PCP) systems, the same reasoning shows that requiring perfect soundness makes randomness useless for choosing the locations to query.  More precisely, it can be shown that PCP(r(n), q(n)) with completeness c(n) and perfect soundness (even with adaptive queries) is equal to the class C of decision problems A=(Ayes, Ano) for which there exists a language B ⊆ {0,1}*×{0,1}*×{0,1}* in P such that

if x∈Ayes, then Pry∈{0,1}r(n)[∃z∈{0,1}q(n) such that (x, y, z)∈B] ≥ c(n), and
if x∈Ano, then ∀y∈{0,1}r(n) ∀z∈{0,1}q(n), (x, y, z)∉B,

where n=|x|.  (Note that in the definition of class C, the yes case does not require a whole certificate to be prepared before the verifier picks the random string y, unlike the usual definition of a PCP system.  A certificate can be prepared after knowing y, and only the queried portion of the certificate is needed, which is why the length of z is q(n).)  Combined with straightforward lower bounds, this implies the following:

PCP(log, log) with perfect soundness = P.
PCP(poly, log) with perfect soundness = RP.
PCP(poly, poly) with perfect soundness = NP.

Comparing these to the PCP theorems PCP(log, O(1)) = NP and PCP(poly, O(1)) = NEXP, we can see that requiring perfect soundness has a huge impact.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos.  On completeness and soundness in interactive proof systems.  In Randomness and Computation, vol. 5 of Advances in Computing Research, pp. 429–442, 1989.  http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps


Common false beliefs in theoretical computer science

This is one is common to computational geometry, but endemic elsewhere: Algorithms for the real RAM can be transferred to the integer RAM (for integer restrictions of the problem) with no loss of efficiency.  A canonical example is the claim “Gaussian elimination runs in $O(n^3)$ time.”  In fact, careless elimination orders can produce integers with exponentially many bits.

Even worse, but still unfortunately common: Algorithms for the real RAM with floor function can be transferred to the integer RAM with no loss of efficiency.  In fact, a real-RAM+floor can solve any problem in PSPACE or in #P in a polynomial number of steps.


Where is the counting hierarchy if polynomial hierarchy collapses?

Yes, the counting hierarchy collapses in this case: Suppose that $P^{\#P}\subseteq BPP$. We know that $P^{\#P}=P^{PP}$, so $P^{PP}\subseteq BPP$. Consider the second level of the counting hierarchy, $C_2^P=PP^{PP}$. By hypothesis, we have

$$C_2^P=PP^{PP}\subseteq PP^{P^{PP}}\subseteq PP^{BPP}\subseteq PP\subseteq P^{PP}\subseteq BPP $$

So the counting hierarchy collapses to $BPP$.

As for your second question, I don't know any implications that would follow from a weaker collapse of the counting hierarchy, i.e. $CH=PP$ or something weaker. That question has been asked before, here, without answers. This question asks whether $PH\subseteq PP$; but nothing more would necessarily follow if $CH$ collapses, even under that hypothesis. According to this answer, it is an open problem whether $PH^{\#P}$ collapses (note that $PH^{\#P}$ does not trivially collapse as a result of Toda's theorem).

There are at present, according to the Zoology active inclusion diagram, no oracles relative to which the counting hierarchy collapses to any level other than $CH=P^{\#P}$; that is, it is an open problem to find an oracle relative to which $P^{\#P}\subsetneq CH$ or indeed $P^{\#P}\subsetneq PSPACE$. Hence there are no oracles, therefore, supporting any argument relating non-trivial collapses of the counting hierarchy to the polynomial hierarchy.


Survey Article on the Theory of Recursive Functions?

A nice reference is "Part C" of Handbook of Mathematical Logic edited by Barwise. Part C includes the following chapters:

Herbert B. Enderton, Elements of recursion theory
Martin Davis, Unsolvable problems
Michael O. Rabin, Decidable theories
Stephen G. Simpson, Degress of unsolvability: a survey of results
Richard A. Shore, $\alpha$-recursion theory
Alexander Kechris and Yiannis N. Moschovakis, Recursion in higher types
Peter Aczel, An introduction to inductive definitions
Donald A. Martin, Descriptive set theory

The chapters are of very high quality and written by leading logicians. This handbook will take you quite far into the world of mathematical logic.


Generate random permutation via iid uniforms --- is inverse transformation possible?

It's possible that what the OP wants is as follows:

Fix an ordering. By the standard trick using hyperplane arrangements, each such ordering represents one of the n! congruent simplices that make up the unit hypercube in $n$ dimensions.

Now the goal is to define a way of sampling from this simplex with independent samples from the data (rather than trying to sample from the simplex directly).

In fact this can be done. Luc Devroye's book describes the procedure (see V.3), which essentially boils down to letting $x_i$ be an exponentially distributed random variable, normalizing them, and then setting $\rho(\pi(i))$ to be the partial sum $\sum_{j \le i} x_i$ (I'm over simplifying a little, so what I said isn't entirely precise, but it's the general idea).


Boolean functions with exponential size OBDD representation in all orders except one order?

If there is an variable ordering $\pi$ such that the OBDD size for $f$ with this ordering is $O(poly(n))$, then a lot of OBDDs with a similar variable ordering has a size of $O(poly(n))$.

To see this you can swap neighboring variables in $\pi$, i.e. for $\pi = (x_{\pi(1)}, \ldots, x_{\pi(n)})$ you construct $\pi' = (x_{\pi(1)}, \ldots, x_{\pi(i)}, x_{\pi(i-1)}, x_{\pi(i+1)}, \ldots, x_{pi(n)})$ for some $i$. The OBDD size for $f$ with variable ordering $\pi'$ is also polynomial because you can store the value of $x_{\pi(i)}$ by doubling the $x_{\pi(i)}$ nodes in the $\pi$-OBDD for $f$. Then you have the information of $x_{\pi(i)}$ and $x_{\pi(i-1)}$ at this nodes and you can use the $\pi$-OBDD to go on.

That means if you swap $O(\log n)$ variables you also have a polynomial size OBDD.


Piecewise Linear Circuit Identity Testing

In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$).  It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero).

Also, we can reduce SAT to this problem.  Consider a formula $\varphi$ in CNF, over variables $x_1,\dots,x_n$.  As is standard, we'll let $1$ represent "true" and $0$ represent "false".  Now it is easy to build a subcircuit that computes logical NOT ($x \mapsto 1-x$, and $1-x$ is linear), a subcircuit that computes logical OR (using your conditional gates), and a subcircuit that computes logical AND (again, using your conditional gates).  Thus, we can transform $\varphi(x_1,\dots,x_n)$ to one of your circuits, where the inputs are $x_1,\dots,x_n$ and the output is the truth value of $\varphi(x_1,\dots,x_n)$.  This circuit will be not identically zero if and only if $\varphi$ is satisfiable.  Also, the size of this circuit is polynomial in the size of $\varphi$.  Thus, if we could solve your problem in polynomial time for arbitrary circuits, then we could solve SAT in polytime and we'd have $P=NP$ -- which seems unlikely.

So, you should not expect an efficient and fully general solution to your problem, at least if you are working over a finite field.

If you are working over $\mathbb{Q}$ or $\mathbb{R}$, I don't have a proof that your problem is NP-hard (I suspect it probably still will be but I have no proof).

Of course, one pragmatic approach might be to try converting your problem to a SAT instance and applying an off-the-shelf SAT solver.  If you are working over the integers ($\mathbb{Z}$), you might also want to try formulating it as an integer linear programming (ILP) problem and then apply an off-the-shelf ILP solver.

Depending upon the size and complexity of your circuits, this might work reasonably well in practice -- though there is no guarantee that it will always run efficiently.

Incidentally, your problem is equivalent to the question: "given a linear decision tree, test whether its output will be identically zero for all inputs".

The equivalence can be seen by topologically sorting the circuit so it can be computed sequentially, and then noting that it forms a decision tree: each of the first three gates can be absorbed into the linear expression, and each instance of the fourth gate corresponds to a boolean decision (testing whether some linear expression of the inputs is $\ge 0$ or not).  In the subtree where this value is $<0$, you substitute in $X$ for each mention of the output of this gate; and substitute $Y$ in the subtree where this value is $>0$.  The depth of the decision tree is equal to the number of type-4 gates in your circuit.

I don't know the complexity of this problem, but perhaps these search times will help you identify whether there is anything relevant in the literature.


About the last question, the usual undecidability proof for universality could be adapted.

Recall that in this proof, one considers an instance $\langle \Sigma,\Delta,u,v\rangle$ of Post's correspondence problem, where $\Sigma$ and $\Delta$ are two disjoint alphabets, and $u$ and $v$ are two homomorphisms from $\Sigma^\ast$ to $\Delta^\ast$.  Then $$L_u=\{a_1\cdots a_n(u(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$ and $$L_v=\{a_1\cdots a_n(v(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$—where $w^R$ denotes the reversal of word $w$—are two DCFLs s.t. $L_u\cap L_v=\emptyset$ iff the original PCP instance was negative.  Letting $$L=\overline{L_u}\cup\overline{L_v}\;,$$one thus defines a CFL (since DCFLs are effectively closed under complement and CFLs under union), which is universal, i.e. equal to $(\Sigma\cup\Delta)^\ast$, iff the original PCP instance was negative.

Now, if $L$ is universal, i.e. if $L=(\Sigma\cup\Delta)^\ast$, then $L$ is closed under permutations.  Conversely, if $L$ is not universal, i.e. if $L_u\cap L_v\neq\emptyset$, there is at least one word $x$ of form $x=w(u(w))^R=w(v(w))^R$ for some $w$ in $\Sigma^+$.  Then $x$ does not belong to $L$, but it's easy to find a permutation of $x$ that belongs to $L$: for instance, permute the last letter of $w$ (which is in $\Sigma$) with the first of $(u(w))^R$ (which is in $\Delta$) to obtain a word in $\Sigma^\ast\Delta\Sigma\Delta^\ast\subseteq L$.

Hence $L$ is closed under permutation iff it is universal iff the original PCP instance was negative.


Number of mincuts of a graph without using Karger's algorithm

The $\binom{n}{2}$ bound I think was originally proven by Dinitz, Karzanov and Lomonosov in 1976, in "A structure for the system of all minimum cuts of a graph".  Perhaps you can find what you're looking for in this paper, but I'm not sure if it's online.


If we request that each $|V_i| \ge 3$, then this is the 2-factor problem,
see the book Combinatorial Optimization by Schrijver. If you allow $|V_i| = 2$,
then we can solve this by replacing each undirected edge by two directed ones and compute what is called a cycle-cover. This can be done in polynomial time by reduction to bipartite matching.


The problem is NP-complete already for $k=3$ (and I guess also for $k=2$).
We reduce the following problem to it:
For an input $r$-regular graph $G$, decide whether $G$ has an equitable $3$-coloring, i.e., one where the size of each color class is the same.
(I couldn't find a reference for this, but one can easily reduce the classical $3$-coloring problem to this by adding a few extra vertices and edges.)

The reduction is as follows.
For each vertex $v$ of the input graph $G$, define a set $S_v=\{\{u,v\}\mid uv\notin E(G)\}$.
For any subset $X$ of the vertices we have

$$|\cup_{\{v\in X\}} S_v|=|X|(n-1-r)-|X_2|$$

where $X_2$ is the set of non-adjacent pairs in $X$.
If $|X|\ge n/3$, this is at least

$$\frac{n(n-1-r)}3-\binom{\frac n3}{2}$$

with equality only if $|X|=n/3$ and all pairs in $X$ are non-adjacent.
Since in any grouping of the $S_v$ into three groups we have such an $X$, we are done.


Faster pseudo-polynomial time algorithms for PARTITION

One can solve the decision problem in $\tilde{O}(nA)$ time.

Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem.

If $S_1$ and $S_2$ are two subsequences that partitions $S$, then

$$F_S = F_{S_1} + F_{S_2}$$

where $A+B=\{a+b  | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise.

Claim: Computing $F_S$ from $F_{S_1}$ and $F_{S_2}$ takes $\tilde{O}(|S|A)$ time.

Proof: Apply 2D convolution on two tables of size $A\times |S|$.

The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum.
We have
$$
T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)
$$
Which shows $T_A(n) = \tilde{O}(n A)$.

The hidden $\log$ factor is $\log n \log nA$.


Is a PhD in TCS the best way towards achieving a career in industrial research?

The comments are all pretty spot on (and maybe they should be answers). To add to them:

In industrial research of the Google/Yahoo!/AT&T/MSR/IBM variety, there are definitely specific area interests, but there's also interest in people with broad interests and strong foundations. A Ph.D in TCS can provide such a broad set of interests and a strong foundation if you choose the right topics.

So for example you could do a Ph.D in computational geometry, focusing on combinatorial problems in incidence geometry, or you could focus on approximate high dimensional algorithms. It's possible that the second topic might allow you to "sell" yourself more effectively as a data analyst, especially if you can point to some awareness of the applications of your work (some papers etc).

So even if you were to do a Ph.D in TCS as a path towards industrial research, the success of this plan really depends on the kinds of topics you choose. In the long term, I think it'll make you very flexible and able to work on a variety of things, but you'll have to seek out that breadth during your education.


Epsilon-closure and DFA minimization algorithms for probabilistic NFA

Stefan Kiefer has some work on minimization of probabilistic automata. This should probably put you on the right track:
https://arxiv.org/abs/1404.6673.


What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

For an instance with $n$ men and $n$ women, the trivial upper bound is $n!$, and nothing better is known. For a lower bound, Knuth (1976) gives an infinite family of instances with $\Omega(2.28^n)$ stable matchings, and Thurber (2002) extends this family to all $n$.


Complexity of existence of simple polygonalization with prescribed area?

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete:

  Problem: GRID-EMPTY
  Instance: a set $S$ of $n$ grid points in the plane
  Question: Is there a simple polygon on this vertex set $S$ that does not contain any other grid points on its boundary or in its interior?

By Pick's theorem, every simple polygon with grid vertices that has $b$ grid points on its boundary and $i$ grid points in its interior has area $(b+2i-2)/2$.

For the scenario in GRID-EMPTY, the smallest possible area is $(n-2)/2$, and this area can be reached if and only if the answer to the GRID-EMPTY instance is YES.
Hence, you simple have to set $A:=(n-2)/2$ in Fekete's reduction and get NP-completeness of your question.


For rCVP, we can reduce the usual CVP problem to rCVP as follows. Given a circuit $C$ on $n$ inputs, produce a circuit $C'$ that on input $x=(x_0,x_1,\dots,x_n)$ outputs $C'(x)=(x_0 \oplus C(x_1,\dots,x_n),x_1,x_2,\dots,x_n)$.

For rEQ, we can similarly reduce the UNSAT problem (modifying the suggestion of Marzio De Biasi). Namely, given a formula $\varphi$ on $n$ variables, let $C_1$ on input $x=(x_0,x_1,\dots,x_n)$ output $(x_0 \oplus \varphi(x_1,\dots,x_n),x_1,\dots,x_n)$ and $C_2$ simply output $x$.


PAC-learning bound with epsilon-cover of hypothesis class

This follows from Massart's finite class lemma. Let $F$ is a binary function class restricted to some set $\{X_1,\ldots,X_n\}$, and let $P_n$ be the empirical (i.e., uniform) measure on this set. Then, for any $\epsilon>0$, the empirical Rademacher complexity of $F$ is bounded by
$$ R_n(F;X) \le \epsilon + \sqrt{\frac{2\log N_F(\epsilon)}{n}},$$
where $N_F(\epsilon)$ is the $\ell_2$ $\epsilon$-covering number of $F$ w.r.t. $P_n$. This is proved in display (1) here:
https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf
-- check out the course notes:
https://www.cs.bgu.ac.il/~asml162/Class_Material


Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)

Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$.

Note the small loss in parameters ($0.12$ is optimal versus guarantee of $0.1$).

Proof. Pick $m$ points $P \subset \{0,1\}^n$ uniformly at random and query $f$ at each $x \in P$.

Fix a subcube $S$ of size $2^{n-k}$. We have $\mathbb{E}[|S \cap P|]=m 2^{-k}$. By a Chernoff bound, $$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$$ Also $$\mathbb{P}[| \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | > \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$$

By a union bound over all ${n \choose k}2^k$ choices of $S$, we have $$\mathbb{P}[\forall S ~~ | \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | \leq \varepsilon] \geq 1 - {n \choose k} 2^k 2^{-\Omega(m 2^{-k} \varepsilon^2)}.$$ So by picking $m = O(2^k/\varepsilon^2 \cdot k \log n)$, we can ensure that, with probability at least $0.99$, we can estimate $\mathbb{E}_{x \in S}[f(x)]$ to within $\varepsilon$ for all subcubes $S$ of size $2^{n-k}$.

Setting $\varepsilon=0.01$, we prove the theorem: picking the subcube with the largest $| \mathbb{E}_{x \in S \cap P}[f(x)]|$ will, with high probability, satisfy the requirements. Q.E.D.


Graph encoding algorithms that you know of ?

If you have a binary encoding of the vertices of the graph you can represent the edges with the characteristic boolean function $\chi_E$ of the edge set $E$, i.e. $\chi_E(x,y) = 1 \Leftrightarrow$ there is an edge between the vertices encoded by $x$ and $y$.
This boolean function can be represented by e.g. Ordered Binary Decision Diagrams.

It is known that this OBDD representation is not larger than classical representations (adjacency matrix or adjacency lists) and for special graph classes (e.g. cographs and interval graphs) the OBDD size is smaller then the explicit representation (Nunkesser,Woelfel: Representation of Graphs by OBDDs). So you can hope that for good structured graphs the implicit representation is better.

In the case of trees I have shown (with the tools from the above paper) that the OBDD size is generally not better than the explicit representation and you can easily construct a tree so that the OBDD size is large.

Algorithms are called symbolic or implicit if they have access to the input graph only by this functional representation and perform functional operations to solve the problem. There is a good PhD thesis from Sawitzki about this topic but it is in german (PDF).

I think this is a kind of heuristical approach because you can't guarantee that there is a good implicit representation of the graph and so a fast symbolic alghorithm. Even if there exist a good implicit representation it is very hard to find this good one.


directed or bidirected in relation to mssp (Multiple source shortest path)

First, let's be completely clear about the definition of the multiple-source shortest path problem.  The input consists of the following:

a directed planar graph $G = (V,E)$ with $n$ vertices;
a non-negative weight $w(e)$ for every directed edge $e$;
an embedding of $G$ into the plane; and
a distinguished face $f$ of this planar embedding (the "outer" face).

Klein's algorithm computes a compressed representation of all shortest-path trees rooted at vertices of the designated face $f$, in $O(n\log n)$ time and space.  This representation allows us to retrieve the shortest-path distance from any vertex on $f$ to any other vertex in $O(\log n)$ time.

An explicit representation of these shortest-path trees would require $\Theta(kn)$ space, where $k$ is the number of vertices in $f$; in the worst case, this space bound is $\Theta(n^2)$.  Klein's observation, at least intuitively, is that the shortest-path trees for two adjacent source vertices are nearly identical; his data structure stores only the differences between adjacent trees.

Klein's algorithm works just fine for bidirected and undirected graphs.  For purposes of the algorithm, a bidirected graph is just a directed graph where the reversal of every arc is another arc, and an undirected graph is jut a bidirected graph where every arc has the same weight as its reversal.  In other words, a bidirected graph is a directed graph whose adjacency matrix is symmetric, and (in this context) an undirected graph is just a directed graph whose weighted adjacency matrix is symmetric.  Klein's algorithm requires no modifications whatsoever to handle these special cases.

Klein's algorithm does not compute shortest-path distances between arbitrary pairs of vertices; in every pair, the source vertex must lie on the designated face.  For a solution to the more general problem, see Sergio Cabello's paper "Many distances in planar graphs" [SODA 2006 and Algorithmica 2012].

You might also check out my upcoming journal paper with Sergio Cabello and Erin Chambers, which describes a different multiple-source shortest-path algorithm, which also works for higher-genus graphs.


Enumerating set combinations in an order that maximises the number of previously unseen subsets

There are $\sum_{j=1}^4 \binom{11}{j} = 561$ smaller subsets, and each $x^\phi$ contains $\sum_{j=1}^4 \binom{5}{j} = 30$ of them.

If you put all $462$ $5$-element sets in a priority queue with priority corresponding to the number of subsets which haven't yet appeared, after each pop you have to check $30$ subsets to see whether they're appearing for the first time, and for each $k$-element subset that is appearing for the first time you have to update the priorities of $\binom{11}{5-k}$ sets. There's an easy upper bound on the number of updates of $25410$.

As a follow-up optimisation, once every smaller subset has been seen (which happens after you've removed the first 90 elements from the priority queue), you can just iterate through the rest. If your priority queue is e.g. a binary heap, this will save you a lot of $O(\lg n)$ pops.


Consequences of a quasi-polynomial time algorithm for the graph isomorphism problem

As far as I can tell, if you ask simply about the consequences of the mere fact (as a black box) that GI is in QP, I think the answer is very little. The one thing I can think of, which is not a theorem but a consequence for research directions, is to Group Isomorphism. Since GroupIso reduces to GI and we don't even know if GroupIso is in P, putting GroupIso into P can be seen as an important obstacle to putting GI into P (if you think the latter might be the case).

However, since the trivial algorithm for GroupIso is $n^{\log n + O(1)}$, back when the complexity of GI was up at $2^{\tilde O(\sqrt{n})}$, we had a long way to go in improving the complexity of GI before GroupIso became an immediately relevant obstacle to putting GI into P. But if GI is in QP, then GroupIso becomes a much more relevant obstacle to further improvements in GI. (Of course, the exponent of the exponent in the quasi-polynomial is still a potentially relevant gap, but the gap becomes a lot smaller when GI is in QP.)


Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

First of all, Mahaney's Theorem says that merely assuming $\mathsf{P} \neq \mathsf{NP}$, there are no sparse $\mathsf{NP}$-complete sets. (Historically, Mahaney was motivated to study this precisely because of Berman-Hartmanis, but the theorem is independent of BH Isomorphism.)

The $\mathsf{AC}^0$ version of the isomorphism conjecture (with various restrictions on uniformity) is a theorem. See the following paper and references therein:

  Manindra Agrawal, The Isomorphism Conjecture for Constant Depth Reductions, JCSS 77 (special issue on Karp's Kyoto Prize): 3-13, 2011.

You may also be interested in other work of Agrawal, Allender, and others on related questions. Agrawal's and Allender's webpages have links to most of the relevant papers (I only say "most" in case I've missed a few that didn't involve either Agrawal or Allender, but I haven't done a thorough literature review recently).

On creativity, Joseph and Young's construction is still one of the main pieces of evidence against BH.


Conflicting definitions regarding TM and Recursively Enumerable languages

I wouldn't say that one definition has "prevailed".  If you look at the literature and textbooks, you'll see a large variety of definitions.

Different definitions might be useful in different contexts.  For example, if you're actually trying to program up a TM (for whatever reason) then the more expressive they are, the easier to program.  On the other hand, if you're trying to prove a lower bound or uncomputability result, picking the weakest TM might make life easier.  And the busy beaver function, for example, is usually defined relative to a fairly weak model.

I'd just recommend you use any model you feel comfortable with and tell the reader of your paper that is what you are using.


Does replacing each vertex of $G$ by $H$ increase treewidth of $G$ by at most $\Delta(G)$?

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that is $n$-regular. We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof:
Suppose that the treewidth of $G^*$ is less than $n(n-1)/12$. Therefore by standard results [1] its vertices can be partitioned to sets $A$, $S$, $B$ such that there are no edges between $A$ and $B$, and $|S| = n(n-1)/12$, $|A| \ge n(n-1)/4$, $|B| \ge n(n-1)/4$, and $|A| + |B| = n(n-1)11/12$.
We call the cliques $H$ in $G^*$ corresponding to vertices of $G$ clusters. The graph $G^*$ has $n$ clusters. Note that each cluster has vertices from at most one of $A$ or $B$. Let $A_f$ be the fraction such that $n A_f$ clusters contain vertices from $A$ and $B_f$ the fraction such that $n B_f$ clusters contain vertices from $B$.
Now, $A_f \ge 1/4$, $B_f \ge 1/4$, and $A_f + B_f \ge 11/12$.
Notice that if there is a cluster $v$ that contains vertices from $A$ and a cluster $u$ that contains vertices from $B$ then these clusters are connected by an edge $\{v_i, u_j\}$, both vertices in it unique to that pair of clusters, and at least one of $v_i$ and $u_j$ should be in $S$.
Therefore we get that $|S| \ge n^2 A_f B_f$, which we can solve with our constraints to a minimum value $|S| \ge n^2 A_f B_f \ge n^2 8/12 \cdot 1/4 = n^2 1/6$, which is a contradiction to the assumed size of $S$.
[1] http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf


I think you need to redraw your Venn diagram... any containment of complexity classes which relativizes will also algebrize, at least in the sense of Aaronson and Wigderson. That is, access to the "low-degree extension" of an oracle is only more powerful than access to the oracle. Similarly, any oracles showing that a separation requires "non-algebrizing" techniques implies that "non-relativizing" techniques are also required.


Partition a graph into node-disjoint cycles

A partition into vertex-disjoint cycles is the same thing as a 2-regular subgraph, more commonly known as a 2-factor. It can be found (if it exists) in polynomial time by an algorithm based on matching. E.g. see this link.

ETA Nov 2013: It seems from comments below that the reduction from the source linked above is wrong. However, the statement that the problem can be reduced to perfect matching remains correct. The correct reduction is in W. T. Tutte (1954), "A short proof of the factor theorem for finite graphs", Canadian J. Math. 6: 347–352.

Replace each vertex $v$ with degree $d$ by a complete bipartite graph $G_v=K_{d,\,d-2}$, and represent each edge $uv$ of the original graph by an edge from one vertex of $G_u$ to one vertex of $G_v$ (on the side of the bipartition with $d$ vertices) in such a way that each vertex of $G_v$ on that side of the bipartition has exactly one such edge incident to it.

Then a perfect matching in the modified graph has to match the $d-2$ vertices on their side of the bipartition of $G_v$ with $d-2$ out of the $d$ vertices on the other side, leaving exactly two free vertices that need to be matched with their neighbors in other subgraphs $G_u$. In this way, the perfect matchings of the modified graph correspond 1-for-1 with cycle covers of the original graph.


How to generate Skolem function in practice

First of all there are two Skolem transformations, one replaces universal quantifiers and preserves validity, the other one replaces existential quantifiers and preserves satisfiability of the formula. Your question is about the second kind, so I will present it this way, but the other version is dual (and at least for me easier to understand).

Lemma: let $F$ be a formula and $sk(F)$ a Skolem transformation of $F$. Then if there exists a model $\mathcal{M}$ s.t. $\mathcal{M} \models F$ there exists a model $\mathcal{N}$ s.t. $\mathcal{N} \models sk(F)$.

If we can show that $sk(F)$ is unsatisfiable, it has no model. But then also $F$ can not have a model.

Now, Resolution is a quite efficient method to show that a formula (in conjunctive normal form) is unsatisfiable. This leads to the following approach to proving the validity of some formula $F$:

Negate $F$
Skolemize, transform the formula into conjunctive normal form
Find a refutation for the CNF formula (a so called clause set)
Because $\neg F$ does not have a model, all interpretations of $F$ must be a model - in other words: $F$ is valid.

Nowhere in this procedure do you need the actual interpretation of a Skolem function, you just rely on the fact that one must exist as part of the model $\mathcal{N}$.


Parse structure of a range concatenation grammar (RCG)

So, I'm actually going to reply to your edits first, then come back to your original question.

re: Edit 1

In your first edit, you express some confusion over what a parse emitted by an Earley parser is; to explain that I'll jump into a quick refresher on the difference between parsers for deterministic context-free grammars (such as LR parsers) and an Earley parser (or other parsers, such as GLL or GLR) which can handle nondeterministic context-free grammars.

Fundamentally, a parser for a deterministic context-free grammar is one that, for any input, will parse it in at most one way: It can either give a unique parse, or fail to parse. As a result, its output is either nothing, or a valid parse tree.

A parser for a nondeterministic context-free grammar, on the other hand, may admit multiple valid parses. Grammars which can actually give rise to such situations are said to be ambiguous, though determining whether a given context-free grammar is ambiguous is undecidable. Because of this, its output is a potentially-empty set of parse trees. This is generally referred to as a "parse forest".

The shared parse forest, then, is merely a compact representation of such a set. Because the grammar is still context-free, a rule $R$ matching a subrange of the input $x$ will always result in the same parse forest - regardless of what sequence of rules led to applying $R$ at $x$. As a result, those two parse trees can share the parse forest generated by $R$ at $x$, drastically reducing the space and time requirements. (Another phrasing might be that, as $R(x)$ is a pure function, it can be memoized.)

re: Edit 2

As far as the interpretation of the predicate clause, I feel that the usual notation of range concatenation grammars somewhat obscures their nature.

Fundamentally, a range concatenation grammar is:

A set of predicates

Taking some number $n$ of arguments
Consisting of a disjunction of clauses

Splitting the arguments into ranges
Consisting of a conjunction of predicates

Queried at concatenations of ranges

The usual notation (as used in your original question) of $A(xay) → B(xy)$ can thus be desugared into:

$$
A(text) :=\\
let\ (x, a, y) := split(text, 3)\ in\\
B(concatenate(x, y)) \wedge a = ``a"
$$

re: Edit 3

  I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS

This is almost exactly the case. The "almost" comes from the concatenation behavior: If I have the example rule I used above, and I apply it at $A(``cbabc")$, I will arrive at $B(``cbbc")\wedge ``a" = ``a"$. If $B$ is defined as $B(xbby) → \epsilon$, then it will succeed - despite "bb" appearing nowhere in the original input. Thus, terminals match not against ranges, but against concatenations thereof.

re: Edit 4

The ranges spanning "anywhere in the original string" is as a result of the concatenation, rather than them being free to span arbitrary parts of the original string.

re: Edit 5

I presume you mean where Boullier says (found in the standalone paper (PS))

  The arguments of a given predicate may denote discontinuous or even overlapping ranges.

However, this does not mean they can be "anywhere freely" (introduced on the RHS), merely that they may "have come from anywhere". Consider the following rule: $A(xyz) → B(xy, yz)$ - here, $B$ takes two overlapping ranges as arguments.

re: Question

In a context-free grammar, a single parse tree is a recursive data structure, consisting of:

The rule name
The range of the input it matched at
The index of the matching clause
The parse trees of the rules the clause refers to

We can extend this bit by bit, and thus arrive at what a single parse tree for a range concatenation grammar looks like, and then apply the same optimization as Earley grammars do to recover a shared parse forest.

First, let's extend it to support concatenation. To do this, we'll move from ranges represented as $(start, end)$ pairs to lists of such ranges - the classic rope data structure.

Next, let's extend it to support splitting. This is a single additional member in the node: a list of positions the input rope was split at.

The third step is to support multiple arguments. Now, we will store an $n$-tuple of ropes, where $n$ is the predicate's arity. In addition, we need to store split information for each argument, making it a tuple of lists.

At this point, a node in our parse tree looks like this:

the predicate name
the $n$-tuple of ropes it was matched at
the index of the matching clause
the $n$-tuple of lists of split points
the parse trees of the predicates the matching clause refers to

That's it - a single parse tree of a range concatenation grammar.

Now, there are two members of the node that could differ between two parse trees matching the same input. The first is the same as for a CFG: the index of the matching clause. If two clauses can match, then we get two parse trees; one for each.

The second is the list of split points. Let's go back to the example rule $A(xay) → B(xy)$ for a minute, and ask it to match "cbabcacb". There are two points it could split at: $(``cb", ``bcacb")$ or $(``cbabc", ``cb")$. Each of these, then, also generates a distinct parse tree - assuming $B$ succeeds.

However, the predicates of a range concatenation grammar - like those of a context-free grammar - have bodies that refer only to the inputs to the predicate. They are thus context free (i.e. pure functions), and can be memoized.

Thus, one can follow a relatively simple evaluation strategy when parsing:

procedure match_A(args, already_matched)
  if contains(already_matched, ("A", args))
    return reference_to(already_matched[("A", args)])
  else
    results = []
    for C in clauses(A)
      SPLIT: for split_tuple in valid_splits(args)
        pred_results = {}
        for P in predicates(C)
          pred_results[P] = P.match(split_tuple)
          if empty(pred_results[P])
            next SPLIT
        push(results, {
          name: "A",
          matched: arg,
          clause: C,
          splits: split,
          subforests: pred_results
        })
    already_matched[("A", args)] = results
    return reference_to(already_matched[("A", args)])


Turing machines whose termination is unprovable?

Termination of a Turing machine (on a fixed input) is a $\Sigma^0_1$ sentence and all usual first-order arithmetic theories are complete for $\Sigma^0_1$ sentences, i.e. all true $\Sigma^0_1$ statements are provable in these theories.

If you look at totality in place of halting, i.e. a TM halts on all inputs, then that is a $\Pi^0_2$-complete sentence and for any computably axiomatizable consistent theory which is strong enough (e.g. extends say Robinson's $Q$ theory) there is a TM whose totality cannot be proven in that theory.


Multi-armed bandit problems where more than one arm can be selected?

Yes - Satyen Kale, Rob Schapire, and I have a recent paper (NIPS '10) on this very problem, where we consider choosing "slates" of arms instead of individual arms.  We consider the cases when position matters in the slate and when it doesn't.  We also analyze both the experts MAB "contextual" model and the expertless setting.


I did a survey on Twitter about this a while back, results here. A few of my favorites:

Parametric Polymorphism through Runtime Sealing, or, Theorems for Low, Low Prices! by
Jacob Matthews and Amal Ahmed, ESOP 2008 DOI:10.1007/978-3-540-78739-6_2
F-ing Modules by Andreas Rossberg, Claudio Russo, and Derek Dreyer, TLDI 2010
Cons should not cons its arguments and Cheney on the MTA, both by Henry Baker, SIGPLAN Notices 1992 and 1995. Baker has lots of other great paper titles, too.
How to Roll a Join: Asynchronous Incremental View Maintenance by Salem, Beyer, and Lindsay, SIGMOD 2000 DOI:10.1145/342009.335393
A Very Modal Model of a Modern, Major, General Type System by Appel, Mellies, Richards, and Vouillon, POPL 2007 DOI:10.1145/1190216.1190235
Clowns to the Left of me, Jokers to the Right, Conor McBride, POPL 2008 DOI:10.1145/1328438.1328474
Linear types can change the world!, Phil Wadler, Programming Concepts and Methods 1990 (note that the ! is signficant)


Enumerate all allocations of points in a simplex

I'd suggest using a recursive search.  Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z.  Then you can test whether there exists $w_x,w_y,w_z$ that would lead to that allocation, by testing feasibility of a linear program.  (For the allocation to be feasible, there are a bunch of linear inequalities that must hold on the variables $w_x,w_y,w_z$; test whether these can all simultaneously hold.)

Now, given a feasible allocation for $k$ points, pick one more point and try all three possibilities for whether that additional point is allocated to X, Y, or Z.  (In other words, you extend it to three possible allocations on $k+1$ points.)  Test which ones are feasible, and recurse on each of the feasible ones.

One can show that if there are $N$ feasible allocations in all, then this process will require at most $3mN$ recursive invocations.  Each recursive invocation involves solving a linear program, which can be done in polynomial time.  Thus, we obtain a procedure whose running time is polynomial in the number of feasible allocations.  The same result generalizes to more than three dimensions.


Maximum Polyhedron Volume in Given $n$ Points

This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest volume simplices and sub-determinants", arXiv:1406.3512 and SODA 2015. (They talk about the largest volume simplex contained in the convex hull, rather than the one that has the given points as vertices, but it amounts to the same thing since there is always an optimal contained simplex that has the given points as vertices.) They cite earlier hardness results on the same problem by Packer (ref.37 of the arXiv preprint) and Papadimitriou (ref.38).


You can make it valid depending on your definition of a valid network flow.
Let s and t be the source and sink, respectively. Depending on your problem you may no further restrictions of the network flow conservation of t and s. In most definitions there are even no further restrictions on that, as this would just complicate the definition (without helping much).

If you want to restrict such "superficial" network flows in your example, you may however further state that for each edge (u,v) with a flow (i.e. flow function f(u,v)>0) there must be a path from s to u where each edge on the path has a positive flow (i.e. f(e)>0).

You may further restrict the flow on s not to be negative and the flow on t not beeing positive, i.e. for sum for all u on f(s,u) must be positive and sum for all u on f(u,t) must be positive or 0.

This should then remodel a "more intuitive" network flow comparable with water flows :).

(Note that the restriction: the source must not send out any transport units does not help much to prevent such superficial flows as suggested in the question.)

However, typically one assumes that f(t,u)<=0 for all vertices u, i.e. the sink consumes everything which it retrieves.


I don't think the given inequality is true (I am not sure about the reverse inequality). Recall that $$
D_{KL}(q(x,y)\| p(x,y))=\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}} q(x,y)\log\bigg(\frac{q(x,y)}{p(x,y)}\bigg).
$$
Consider non-identical joint distributions $p$ and $q$ over $\mathcal{X}\times\mathcal{X}$ (so $\mathcal{Y}=\mathcal{X}$), with $p(x,y)=q(x,y)=0$ for $y\neq x$ (so the supports of both distributions are on the diagonals). Then
\begin{align}
D_{KL}(q(x,y)\|p(x,y))&=\sum_{x_1\in \mathcal{X}}\sum_{x_2\in \mathcal{X}}q(x_1,x_2)\log\bigg(\frac{q(x_1,x_2)}{p(x_1,x_2)}\bigg)\\
&=\sum_{x\in \mathcal{X}} q(x)\log\bigg(\frac{q(x)}{p(x)}\bigg)\\
&=D_{KL}(q(x)\|p(x))=D_{KL}(q(y)\|p(y)).
\end{align}
In general, these are not all zero or infinite, so the stated inequality will not hold.

However, I think one can say that
$$
D_{KL}(q(x,y)\|p(x,y))\geq \frac{D_{KL}(q(x)\|p(x))+D_{KL}(q(y)\|p(y))}{2}.
$$
This should follow from the Chain Rule:
\begin{align}
D_{KL}(q(x,y)\|p(x,y))&=D_{KL}(q(x)\|p(x))+D_{KL}(q(y\vert x)\|p(y\vert x))\\
&=D_{KL}(q(y)\|p(y))+D_{KL}(q(x\vert y)\|p(x\vert y)),
\end{align}
summed twice and then using the nonnegativity of divergence.


How to find a non-zero point of a non-zero polynomial of low degree?

If  (ceil(degree/n))+1  is "large", then there doesn't actually need to be such an X$\hspace{.02 in}$'.

$\Bigg(\hspace{-0.08 in}$The polynomial can be $\;\;\; \displaystyle\prod_{i\hspace{.02 in}\in \hspace{.02 in}\text{coordinates}} \: \left(\displaystyle\prod_{c\hspace{.02 in}\in (\mathbb{F}\hspace{.03 in}-\{0\})} (x_{\hspace{.02 in}i}-c)\hspace{-0.07 in}\right) \;\;\;$ and X can be the origin.$\hspace{-0.08 in}\Bigg)$

If "large" means larger than 1 plus [the minimum over the variables of the degree in that variable], then there's a uniform NC$^0$ algorithm that will, with no access to the polynomial, with neither

bit operations nor field operations nor equality tests on field elements ($\hspace{.03 in}$just copying them and

moving them around), output a polynomial-length list of elements of $\mathbb{F}^n$ such that at least one

of those elements is such an X'.  (When B is an upper bound on the bracketed expression from

the previous sentence, the algorithm will have B+2 distinct hard-coded field elements and output the  n$\cdot$(B+2)  results of replacing one of X's coordinates with one of the B+2 field elements.)

Thus, you need to either consider fields of "intermediate" size, or allow polynomials of

large (superpolynomial) degree.  (Arithmetic circuits can easily have exponential degree.)

A problem that's closer to canonical for  FRP ∩ PPP  (and is actually obviously in PPP) is

Input:    A (circuit encoding a) function  f : {0,1}n+1 -> {0,1}n

and a (circuit encoding a) function  g : {0,1}n -> {0,1}n+1

Correct Outputs:    elements x of {0,1}n+1 such that  g(f(x)) ≠ x
.


Model of MLTT with $\eta$ rule where function extensionality fails

The simplest one that I know about is the $\text{Set}$-based polynomial model ("container" model). Here, every context is interpreted as a family of sets, i.e. a $Q : \text{Set}$ together with an $A : Q \to \text{Set}$. We can view this as a set of questions together with sets of possible answers for each question, or a request-response protocol with at most two messages sent. Certain game semantics generalize this to arbitrary number of interactions in a protocol.
A morphism between $(Q, A)$ and $(Q', A')$ is a function $f : Q \to Q'$ with $g : (q : Q) \to A'\,(f q) \to A\,q$. So this is not a usual morphism of families, because we map answers in the backwards direction. Again, this can be viewed with the game/protocol intuition, as a synchronous translation between two protocols. The translator gets $q : Q$ from the "domain" agent, computes $f\,q$ and feeds it to the "codomain" agent, then receives an answer in $A'\,(f\,q)$ and translates it back.
Roughly speaking, most of the polynomial model of MLTT works by taking a plain $\text{Set}$ model and the opposite of a simply-typed "fibered" $\text{Set}$ model, and gluing them together. We need to take opposites of type constructions because of the flipping of mapping directions in answers. So when modeling the answer components, products become coproducts, the unit type becomes the empty type, and so on.
Function types and $\Pi$ types are an exception to this scheme, where there is non-trivial interaction between the question and answer components of the model.
See this for the simply typed case. See Pi.agda from this for a formalization of the dependent $\Pi$ case, or this for the same in a more general setting with heavier abstractions.
Regarding the failure of function extensionality: semantic $\Pi$ inhabitants can be viewed as bidirectional functions with forwards and backwards mapping components. However, the function application always projects out and applies the forwards component. Hence, if we have $(a : A) \to f\,a = g\,a$, this only expresses that $f$ and $g$ have the same forwards action, and does not say anything about the backwards actions. So $f = g$ generally does not follow.


Typo in the calculus of constructions paper?

You are correct, there is an error in that paper, and the rule should indeed read:
$$\frac{\Gamma\vdash M:\Delta}{\Gamma\vdash M\cong M} $$

the use of jugements of this style for equality (sometimes called "typed equality") originates already in Martin-Löf, I think (see here for example). It's often replaced with an untyped operational definition in modern treatments, where there is no jugement of the form $\Gamma\vdash N\cong M$, and conversion is defined on raw terms.

Somewhat counter-intuitively, proving that the system with typed conversion is equivalent to the one without types is very difficult, and was settled in 2010 by Siles and Herbelin.


Number of Hamiltonian cycles on random graphs

As Yuval said, Q1 is easy to answer using linearity of expectation (spoiler: $(n-1)!p^n$) . I don't know the exact answer to Q2, but it might be good enough if you know it's very low: for the range of $p$ where there is at least one cycle, it holds that $P[\text{there is more than one cycle} | \text{there is at least one cycle}]>1-1/n^{\log n}$ or so. In other words, once there is one cycle, there are many. The reason is that once there is one cycle, there are around $n^2$ ways to create another cycle from it by exchanging two edges of the cycle by the two "crossing" edges (this is called a "2-flip" or something in some of the relevant literature). For any pair of edges, the chance you can do that is $p^2$. So for all of these to fail, the chance is $(1-p^2)^{n^2}$ which is roughly $e^{-(pn)^2}$, which is pretty tiny.


direct connection between gradient descent and follow the (perturbed) leader algorithm or weighted majority?

Yes -- both gradient descent and the randomized weighted majority algorithm (often called multiplicative weights these days) are instantiations of the "Follow the regularized leader" framework. Gradient descent is what comes out if you regularize with the euclidean norm, and multiplicative weights is what comes out if you regularize with Shannon entropy.

See e.g. here (http://www.jennwv.com/courses/F11/lecture11.pdf) for a derivation of the weighted majority algorithm from this framework.


Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

Here is an explanation from Lipton's blog: Bait and Switch: Why Are Lower Bounds so Hard?

As Grochow observed, Rudich's insight applies equally well to $n^2$ lower bounds as to super-polynomial lower bounds.

Rudich's insight explains why any lower bound proof that it is based on the following method cannot work.

  "any computation that computes $f$ must make slow progress toward $f$. Each computational step can only get you a little bit closer to the final goal, thus the computation will take many steps."

Basically, there is no measure of progress that can survive the Bait and Switch trick of Rudich and successfully leads to a lower bound.


What kind of mathematical background is needed for complexity theory?

If you look at the answers to this TCS StackExchange question, you'll see that there's a possibility that pretty much any area of mathematics could be important in complexity theory. So, if you're really interested in some area of mathematics that doesn't seem to be related, go ahead and study it anyway. If it ever does become relevant to complexity theory, you'll be one of the few complexity theorists who understands it.


Using compression to improve edit distance computation

Crochemore, Landau and Ziv-Ukelson were, I believe, the first to consider (LZ) compression explicitly in this context. As mentioned in the comments above, the earlier technique of Masek and Paterson is also in effect a form of compression. Considering general grammar-compression (SLP) is, I believe, a relatively new idea. Using it for string comparison speedup is original to the paper you cite, although comparing grammar-compressed strings as such has been considered before. You will find references and discussion in the compression chapter of http://arxiv.org/abs/0707.3619 .


the paper you cite by Ercsey-Ravasz, Toroczkai is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical physics and spin glasses was uncovered mainly via "phase transitions" in the mid 1990s and that has led to a large body of work, see Gogioso[1] for a 56p survey. the phase transition coincides with what is known as "the constrainedness knife edge" in [2]. the exact same transition point does turn up in very theoretical analyses of computational complexity/ hardness eg [3] that also relate to early studies of transition point behavior in clique problems by Erdos. [4] is a survey/ video lecture on phase transitions and computational complexity by Moshe Vardi. [5][6] are overviews of phase transition behavior across NP complete problems by Moore, Walsh.

then there is scattered but maybe increasing study of the diverse connections of dynamical systems with computational complexity and hardness in a variety of contexts. there is a general connection found in [7] possibly explaining some of the underlying reasons for frequent "overlap". refs [8][9][10][11] are diverse but show a reoccuring theme/ crosscutting appearance between NP complete problems and various dynamical systems. in these papers there is some concept/ examples of a hybrid link between discrete and continuous systems.

chaotic behavior in NP complete systems is analyzed in [11].

A somewhat similar ref to Ercsey-Ravasz/ Toroczkai in the area of quantum algorithms in that the dynamical system is found to run "apparently" in P-time [12]

  In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.

[1] Aspects of Statistical Physics in Computational Complexity / Gogioso

[2] The constrainedness knife edge / Toby Walsh

[3] The Monotone Complexity of k-Clique on Random Graphs / Rossman

[4] Phase transitions and computational complexity / Moshe Vardi

[5] Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore

[6] Phase transition behavior / Walsh

[7] Determining dynamical equations is hard / Cubitt, Eisert, Wolf

[8] The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems / Just

[9] Predecessor and Permutation Existence Problems for Sequential Dynamical Systems / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates)

[10] A Dynamical Systems Approach to Weighted Graph Matching / Zavlanos, Pappas

[11] On chaotic behaviour of some np-complete problems / Perl

[12] New quantum algorithm for studying NP-complete problems / Ohya, Volovich


Is there a difference between incompleteness and unknowable?

Yes, there is a difference.

Incompleteness is a property of a formal system logic. Given a formal system $L$, we say that it is incomplete if there is a sentence $S$ such that $L$ does not prove $S$ and $L$ does not prove $\lnot S$.

Knowing is an activity of an agent, such as a human, or a robot which holds beliefs about its environment. To say that an agent knows a statement $S$ means that the agent correctly believes $S$ is the case.

So the first thing to make clear is that incompleteness and knowing are two very different sorts of things. It makes no sense to say that a formal system of logic "knows" that $S$ holds. And knowledge may be obtained by many different means, some of which are not related to logic. (For instance, I know that it is sunny outside at the moment through direct observation.)

There is a relation though: if an agent uses a sound formal system $F$ to prove a sentence $S$, then it will know $S$. This is what mathematicians do: they prove things so that they can correctly believe them. In that sense, your question may be understood as follows:

  Given the incompleteness of formal systems, are there some mathematical facts which we will never know? What if we give ourselves infinite time to exhaustively search through all proofs?

The answer is this: for a fixed formal system $F$, such as first-order logic with Zermelo-Fraenkel set theory (which is proclaimed by many to be the "official" formal system of mathematics), there is always a sentence $S$ such that $F$ neither disproves nor proves $S$. Even if we had infinite time so that we could check all proofs of $F$, we still would not be able to prove $S$, nor would we be able to disprove $S$ using $F$. There just isn't a proof, and it doesn't matter how much time we have. Consequently, we cannot acquire knowledge of $S$ by using the formal system $F$. This does not mean that $S$ is uknowlable. It just means that $F$ is not helping us determine whether $S$ is true, but there might be another formal system $F'$ which does.

Mathematicians are not forced to use a single formal system $F$ all the time. Mathematical activity and knowing by mathematicians is not the same as a fixed formal system. For instance, mathematicians might agree to add another axiom to set theory, and thus some previously undecidable sentences will become decidable (and therefore knowable). In fact, such changes do occur in the history of mathematics, although it is difficult to track them back in time because mathematicians did not know what a formal system of logic was before the work of the modern logicians (Peano, Frege, Russell, and others).

How, why, and whether mathematicians should change the underlying rules of mathematics is a question for a different day, and a different forum.

Supplemental: Let me address the question in the comments about the Twin Primes. I am going to take the formal system of Peano arithmetic $PA$, but any other formal system would do. Recall that:

$PA$ is consistent if it does not prove a contradiction.
$PA$ is sound if, for any sentence $\phi$, if $PA$ proves $\phi$ then $\phi$ is actually true.

Here we take truth with respect to the intended model, i.e., our mathematical reality (I am not going to get into a discussion of what that might be, the OP is presuming one.) A sound formal system is consistent, but a consistent formal system need not be sound.

Another point of importance is this: truth and provability are different! Do not confuse "we cannot prove something" with "it is neither true nor false". By definition truth is always determined, i.e., a statement must have a truth value, but it need not have a proof.

Let $TP$ be the statement of the Twin Primes conjecture. Here are the possibilities, assuming Peano arithmetic is sound:

If Twin Primes conjecture is true, then there is a sound formal system which proves it, namely Peano arithmetic extended with the axiom stating $TP$.
If Twin Primes conjecture is false, then there is a sound formal system which proves it, namely Peano arithmetic extended with the axiom stating $\lnot TP$.

We can also look at the other side:

If Peano arithmetic proves $TP$ then the Twin Primes conjecture is true.
If Peano arithmetic proves $\lnot TP$ then the Twin Primes conjecture is false.
If Peano arithmetic does not prove $TP$ and does not prove $\lnot TP$, then we may extend it at will with either $TP$ or $\lnot TP$. We will obtain a consistent formal system in either case, but it might be unsound.


Cobham's Result on Efficient Computations

You can try to look at the paper A new recursion-theoretic characterization of the polytime functions by Stephen Bellantoni and Stephen Cook, which has very nice discussion on Cobham's polynomial-time characterization in the introduction section. This paper also has pointers to other related works. You can easily find the paper somewhere on the web in case you are not subscribed to Springer.


Since $|e_i|$ is bounded by the diameter $d$, the $\ell_1$ norm is going to be trivially bounded by $nd$, likewise for the $\ell_2$ norm, except by $\sqrt{n}d$ (in fact the $\ell_p$ norm is bounded by $n^{1/p}d$).

The $\ell_1$ case turns out to be surprisingly easy to analyze.

For a path, it's easy to see that $\|\vec e\|_1$ is $O(n^2)$, so you can't do any better than $O(nd)$.

For a complete $k$-ary tree, you can divide it in half at the root, setting $w_{\text{root}} = 0$, ascending one side and descending the other until the leaves have $|e_i| = |w_i| = \log_k n$, producing $O(n\log_k n) = O(nd)$ again.

For a clique it doesn't really matter how you distribute the weights, since they'll all be within $1$ of each other, and that will yield $O(n) = O(nd)$ again.

When you realize that what we're talking about here is a function $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$, and then we're taking its $\ell_1$ norm, as long as you can arbitrarily distribute weights $e_i \in [-d/2,d/2]$ evenly across the range, the bound will be $O(nd)$.

The only way to change this is to play games with the mass. For instance, if you have several giant cliques at points that are necessarily balanced, like a giant clique with two paths of equal length jutting out of it, then you can count on a bound of only (for example) $O(d^2)$.

This may be true for expanders to some degree as well, but I'm not sure. I could imagine a case where you set $w_1 = 0$ in a regular graph and then let the values increase subsequently from every hop. It seems likely that the mean could possibly have the most mass, but I don't know if it would be enough to affect the bound.

I think that you could reason similarly about $\ell_2$.

EDIT:

In the comments we figured out a (loose) $\ell_2$ bound of $O(|E|/\lambda_2(L))$ using the constraints of the problem and some basic spectral graph theory.


Edge and vertex fault tolerance in graphs

The question is very general and so the following is only a partial solution.  My main motivation was to draw the connection between this and k-hitting sets.

As Arindam has pointed out, this problem (or the decision version thereof) could be used to solve the subgraph isomorphism problem: "Is $H$ a subgraph of $G$ if any $0$ edges of $G$ are removed?".  But as is often the case, we still want to know "is it possible to do better than the naive solution?"

The naive solution:

for i in 0 ... (|E(G)|-|E(H)|+1)
    for every i-subset of edges, S, in E(G)
        if H is not a subgraph of (G - S)
            return k=i-1 as the greatest number of edges that can be removed

Ignoring the obvious edge cases (returning $-1$ when $H$ is not a subgraph of $G$) then the cost is basically $\sum_{i=0}^k \binom{|E(G)|}{i}$ computations of he subgraph isomorphism problem on inputs (basically) $G$ and $H$.  And so, we are basically up against a possibly exponential number of subgraph isomorphism problems.

The problem can be restated as a hitting set problem (also known as a vertex cover of a hypergraph problem).  Let $S$ be the set of all sets, $T$, where $T$ is a set of $|E(H)|$ edges of $G$, and $H$ is isomorphic to $G - (E(G) - T)$.

Note, $S$ is not every mapping of $H$ onto $G$, but is every edge set that can be mapped to.

Let $h$ be the size of the minimum hitting set of $S$.  Then $k=h-1$.

This is neat, but it is not immediately useful.  Calculating a minimum hitting set is NP-hard, and the input into the problem is possibly exponential in the size of the input of our original problem.  Double-wam-o.

However, it does provide us with a case for a fast approximation.  If $|E(H)|$ is small (and by that I mean bounded by some constant $e_H$), then we have $|S| = O(\binom{|E(G)|}{e_H})$.  Also, an $e_H$-approximation can be computed in polynomial time.  Thus the real work is in finding $S$, which can be done with $\binom{E(G)}{e_H}$ cases of the graph isomorphism problem.  The naive solution does not compute in polynomial time when $E(H)$ is bound because $k$ is not bound.


Sample graph dataset for testing algorithms

The Stanford Large Network Dataset Collection appears to include a few weighted graphs. Unfortunately the road networks are apparently unweighted - I'm not sure if shortest-paths is motivated on any of the weighted graphs there.


The Knot Equivalence Problem.

Given two knots drawn in the plane, are they topologically the same? This problem is known to be decidable, and there do not seem to be any computational complexity obstructions to its being in P. The best upper bound currently known on its time complexity seems to be a tower of $2$s of height $c^n$, where $c = 10^{10^{6}}$, and $n$ is the number of crossings in the knot diagrams. This comes from a bound by Coward and Lackenby on the number of Reidemeister moves needed to take one knot to an equivalent one. See Lackenby's more recent paper for some more recent related results and for
the explicit form of the bound I give above (page 16).


On the stopping criterion of coordinate descent method

Here's one possible solution:
$$\nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1} \cdots \frac{\partial f(x)}{\partial x_n}\right]^T$$
The coordinate descent algorithm is exploring all the coordinate axes, so you have an estimate of $\hat{\nabla} f_i(x_k)=\frac{\partial f(x^k)}{\partial x_i}$. In particular, when $\Big| \hat{\nabla} f_i(x_k) \Big| < \epsilon \,\forall i$, then $|\nabla f(x_k)| < n\epsilon$, so setting $\frac{\epsilon}{n}$ as the stopping criterion for the maximum slope along the coordinate axes is a reasonable strategy.

(This gives you guarantees about the gradient and not the actual decrease, but I believe it can be modified because your function is a convex quadratic, not sure how off the top of my head)


Theoretical study of coordinate descent methods

(Edit notes: I reorganized this after freaking out at its length.)

Literature on coordinate descent can be a little hard to track down.  Here are some reasons for this.

Many of the known properties of coordinate methods are captured in umbrella theorems for more general descent methods.  Two examples of this, given below, are the fast convergence under strong convexity (hold for any $l^p$ steepest descent), and the general convergence of these methods (usually attributed to Zoutendijk).
Naming is not standard.  Even the term "steepest descent" is not standard.  You may have success googling any of the terms "cyclic coordinate descent", "coordinate descent", "Gauss-Seidel", "Gauss-Southwell".  usage is not consistent.
The cyclic variant rarely receives special mention.  Instead, usually only the best single choice of coordinate is discussed.  But this almost always gives the cyclic guarantee, albeit with an extra factor $n$ (number of variables): this is because most convergence analyses proceed by lower bounding the improvement of a single step,and you can ignore the extra coordinates.  It also seems difficult to say anything general about what cyclic buys you, so people just do the best coordinate and the $n$ factor can usually be verified.

Rate under strong convexity. The simplest case is that your objective function is strongly convex.  Here, all gradient descent variants have the rate $\mathcal O(\ln (1/\epsilon))$.  This is proved in Boyd & Vandenberghe's book.  The proof first gives the result for gradient descent, and then uses norm equivalence to give the result for general $l^p$ steepest descent.

Constraints. Without strong convexity, you have to start being a little bit careful.  You didn't say anything about constraints, and thus in general, the infimum may not be attainable.  I'll say briefly on the topic of constraints that the standard approach (with descent methods) is to project onto your constraint set each iteration to maintain feasibility, or to use barriers to roll the constraints into your objective function.  In the case of the former, I don't know how it plays with coordinate descent; in the case of the latter, it works fine with coordinate descent, and these barriers can be strongly convex.

More specifically to coordinates methods, rather than projecting, many people simply make the coordinate update maintain feasibility: this for instance is exactly the case with the Frank-Wolfe algorithm and its variants (i.e., using it to solve SDPs).

I'll also note briefly that the SMO algorithm for SVMs can be viewed as a coordinate descent method, where you are updating two variables at once, and maintaining a feasibility constraint while you do so.  The choice of variables is heuristic in this method, and so the guarantees are really just the cyclic guarantees.  I'm not sure if this connection appears in standard literature; I learned about the SMO method from Andrew Ng's course notes, and found them to be quite clean.

General convergence guarantee. What I know in this more general setting (for coordinate descent) is much weaker.  First, there is an ancient result, due to Zoutendijk, that all these gradient variants have guaranteed convergence; you can find this in the book by Nocedal & Wright, and it also appears in some of Bertsekas's books (at the very least, "nonlinear programming" has it).  These results are again for something more general than coordinate descent, but you can specialize them to coordinate descent, and then get the cyclic part by multiplying by $n$.

More specifically to cyclic coordinate descent, there's a paper by Luo & Tseng titled "On the convergence of the coordinate descent method for convex differentiable minimization".  These results require the infimum to be attainable. There are no rates here, only convergence guarantees, but these results have been applied to some more specialized settings to get rates; for instance, in boosting (in the special case that the infimum is attainable), Warmuth, Mika, Raetsch, and Warmuth ("on the convergence of leveraging") were able to show rates of $\mathcal O(\ln(1/\epsilon))$.

There are some more recent results on coordinate descent, I've seen stuff on arXiv.  Also, luo&tseng have some newer papers.  but this is the main stuff.

More convergence rates in the special case of boosting. Due to its importance, there has been other specialization in the case of boosting.  This is a pretty severe special case because your objective can be written $\sum_{i=1}^m g(\langle a_i, \lambda\rangle)$ where $g$ is a (convex) univariate function and the $(a_i)_1^m$ are fixed vectors ($\lambda$ is the optimization variable).  Bickel, Ritov, and Zakai ("some theory for generalized boosting algorithms") showed you can get $\exp(1/\epsilon^2)$ in general, and there are more recent results by other people showing $\mathcal O(1/\epsilon)$.  The difficulty in these is that the infimum is not assumed attainable.

The issue with exact updates. Also, it is very often the case that you do not have a closed form single coordinate update.  Or the exact solution may simply not exist.    But fortunately, there are lots and lots of line search methods that get basically the same guarantees as an exact solution.  This material can be found in standard nonlinear programming texts, for instance in the Bertsekas or Nocedal&Wright books mentioned above.

Vis a vis your second paragraph: when these work well.
First, many of the above mentioned analyses for gradient work for coordinate descent.  So why not always use coordinate descent?  The answer is that for many problems where gradient descent is applicable, you can also use Newton methods, for which superior convergence can be proved.  I don't know of a way to get the Newton advantage with coordinate descent.  Also, the high cost of Newton methods can be mitigated with Quasinewton updates (see for instance LBFGS).

Second, the place where these methods shine is where the presumed solution is sparse (in the $l^0$ sense).  Of course, there are NP-hardness issues with this kind of sparsity, but the point is that if you run $k$ iterations, you have $k$ nonzero entries.  These facts generalize to, say, using coordinate methods with SDP solvers, where each iteration you throw in a rank 1 matrix, thus with $k$ iterations you have a rank $k$ iterate.  There is a great paper on this topic, by Shalev-Shwartz, Srebro, and Zhang, titled "trading accuracy for sparsity in optimization problems with sparsity constraints".  Most specifically to the second paragraph of your question, this paper gives further properties on $f$ that allow fast convergence and good sparsity (true to its title).


Can a flow be decomposed in a given number of paths?

This is the proof given here, to show that the flow obtained after two iterations of Ford-Fulkerson algorithm can be decomposed into at most $3$ paths and a circulation. It is assumed that at each iteration, the algorithm picks the path that allows maximum flow.

Let the path obtained in first iteration be $P_1$ with flow $f_1$. And the path in the residual graph w.r.t this flow, picked by the algorithm in second iteration be $P_2$ with flow $f_2$. Clearly $f_1 \geq f_2$. Now consider the path $P_1$ with flow $f_1-f_2$. Removing this flow from the total flow, the remaining flow can be described as follows (for each edge $e$).

If $e \notin P_1$ and $e \notin P_2$ then $f(e)=0$.
If $e \in P_1$ and $e \notin P_2$ then $f(e)=f_2$.
If $e \notin P_1$ and $e \in P_2$ then $f(e)=f_2$.
If $e \in P_1$, $e \in P_2$ and $e$ is a forward edge in $P_1$, then $f(e)=2f_2$.
If $e \in P_1$, $e \in P_2$ and $e$ is a backward edge in $P_1$, then $f(e)=0$.

So the remaining flow is now $f_2$-integral, with a total flow of $2f_2$ from $s$ to $t$. We can show in general that if a flow is $r$-integral with a total flow of $kr$ from $s$ to $t$, then this flow can be decomposed into at most $k$ $s$-$t$ paths and a circulation. We can just start from $s$ and move along any edge carrying some flow and reach $t$. This gives an $s$-$t$ path with flow $r$ (or some multiple of $r$). Remove this flow and repeat this process again (walk from $s$ to $t$ along flow carrying edges). Finally, when there is no net flow let from $s$ to $t$, the remaining flow is a circulation. That this process ends in $k$ steps can be shown formally using induction.


Positive 1-in-3 SAT FPT or Fixed Parameter Intractable

No, since even the generalization to 1-in-at-most-3 is FPT for the same reason as vertex cover.

(With at most 3 variables per clause, there will be at most 3 cases for each step.)

I feel like that generalization should have a simple

poly-size kernel, but can't figure out any way of showing that.

The corresponding problem for at-most-1-in-3 constraints, where one wants

exactly k variables to be true, is W[1]-hard by reduction from independent set:

If k<2 then brute force, else:

There's a variable for each vertex and one other variable.

The constraints are  u , other_variable , v  for edges u,v.

Since 2≤k and other_variable is in every constraint, other_variable must be false, so

the satisfying assignments with exactly k Trues correspond to the independent k-sets.