Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?

There is an oracle $\mathcal O$ such that $\textsf{ZPP}^{\mathcal O}\not\subseteq \textsf{UP}^{\mathcal O}$. The inclusion is not known, and it would therefore require non-relativizing techniques to resolve the question (and probably even non-algebrizing techniques). On the other hand, the inclusion $\textsf{ZPP}\subseteq \textsf{UP}$ is conjectured to be true, because the Derandomization Hypothesis implies $\textsf{P}=\textsf{ZPP}=\textsf{BPP}$, and since $\textsf{P}\subseteq \textsf{UP}$, we get $\textsf{ZPP}\subseteq \textsf{UP}$.
Oracle sketch. The oracle $\mathcal O$ is constructed in phases. For the $n$-th phase, we fix the strings in $\mathcal O\cap \{0,1\}^n$. For a yes-input, we take a random subset $S\subseteq \{0,1\}^{n-1}$, and set $\mathcal O\cap\{0,1\}^n:=0S$. For a no-input, we set $\mathcal O\cap\{0,1\}^n:=1S$.
The language $\mathcal L$ which now has $\mathcal L\in \textsf{ZPP}^{\mathcal O}\setminus \textsf{UP}^{\mathcal O}$ asks the question: on input $1^n$, is it true that (1) $|\mathcal L\cap 0\{0,1\}^{n-1}|>\frac{1}{4}2^{n}$, and (2) not $|\mathcal L\cap 1\{0,1\}^{n-1}|>\frac{1}{4}2^n$? Because of the way we constructed the oracle, for any $n$ we always have either both (1) and (2) are true, or neither (1) nor (2), so it suffices for an $\textsf{RP}$ algorithm to check whether (1) holds, and for a $\textsf{co-RP}$ algorithm to check whether (2) holds. Hence $\mathcal L\in \textsf{RP}^{\mathcal O}\cap \textsf{co-RP}^{\mathcal O}=\textsf{ZPP}^{\mathcal O}$.
The details of diagonalizing against all $\textsf{UP}$-Turing Machines are omitted, but are standard.


The precise answer to your question is given by Oded Goldreich in his article "Bravely, Moderately: A Common Theme in Four Recent Works".

Here is the link: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf


Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

Obviously if $f(\Delta)=2\Delta$ then the bound holds.  However, I doubt this is what you meant.  Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such function.

Let $\alpha$ be the size of a maximum independent set in $G$.  Then it is easy to see that the fractional chromatic number satisfies the bound $\chi_f(G)\geq \frac n \alpha$.  One such example is the Kneser graph $K_{kb:b}$ for fixed integers $k$ and $b$.  This graph has fractional chromatic number $k = \frac n\alpha$, and chromatic number $(k-2)b+2$.  So for fixed $k$ and large $b$ the answer is no.

(See Section 3.1 of my thesis for more details. http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf)


From edge-disjoint paths to independent paths

It turns out that $f(k)=3$ for all $k\ge 3$. Recursive diamond graphs are extremal. See arXiv:1203.4483 for a proof.


Proof irrelevance in general is not implied by the theory behind Coq. Even proof irrelevance for equality is not implied; it is equivalent to Streicher's axiom K. Both can be added as axioms.

There are developments where it's useful to reason about proof objects, and proof irrelevance makes this nigh-impossible. Arguably these developments should have all the objects whose structure matters recast in Set, but with the basic Coq theory the possibility is there.

There is an important subcase of proof irrelevance that always holds. Streicher's axiom K always holds on decidable domains, i.e. equality proofs on decidable sets are unique. The general proof is in the Eqdep_dec module in the Coq standard library. Here's your theorem as a corollary (my proof here is not necessarily the most elegant):

Require Bool.
Require Eqdep_dec.
Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2.
Proof.
  intros; apply Eqdep_dec.eq_proofs_unicity; intros.
  destruct (Bool.bool_dec x y); tauto.
Qed.

For this special case, here's a direct proof (inspired by the general proof in Eqdep_dec.v). First, define we define a canonical proof of true=b (as usual in Coq, it's easier to have the constant first). Then we show that any proof of true=b has to be refl_equal true.

Let nu b (p:true = b) : true = b :=
  match Bool.bool_dec true b with
    | left eqxy => eqxy
    | right neqxy => False_ind _ (neqxy p)
  end.
Lemma bool_pcanonical : forall (b : bool) (p : true = b), p = nu b p.
Proof.
  intros. case p. destruct b.
  unfold nu; simpl. reflexivity.
  discriminate p.
Qed.

If you add classical logic to Coq, you get proof irrelevance. Intuitively speaking, classical logic gives you a decision oracle for propositions, and that's good enough for axiom K. There is a proof in the Coq standard library module Classical_Prop.


Somehow doing better than $O(n^d)$ looks hard. If the cell is significantly larger than its average expected size, one can use sampling, to find it. Formally, assume the bounded cells (in the plane) form a polygon of area $1$ (this polygon $Q$ can be computed in near linear time in the plane). Assume the largest bounded cell $C$ in the arrangement of lines has area $\alpha \gg 1/n^2$. Sample, $m = (\log n)/\alpha$ points from $Q$ - and let $P$ be the resulting point set. With high probability one of the points falls inside $C$, and computing all the faces in the arrangement containing points of $P$ takes $O(( n^{2/3} m^{2/3} + n + m)*\mathrm{polylog})$ time using standard magic (i.e., algorithms for computing many faces in the arrangement of lines).

It is now straightforward to apply binary search on $\alpha$, to get an algorithm that computes the largest cell, in time $O\Bigl( \bigl(n + 1/\alpha + n^{2/3}/\alpha^{2/3}\bigr) \mathrm{polylog n}\Bigr)$, where $\alpha$ is the fraction of area of the largest cell out of the total area of the bounded cells (i.e., the area of $Q$).


This is not an answer but maybe this will point you or someone else in the right direction.

I found the paper by D. Kozen and S. Zaks called "Optimal Bounds for the Change-Making Problem" wherein they give conditions for when a coin change instance's greedy change making algorithm is optimal.  I will use their notation.

  Given a coin change instance of $m$ distinct coins
  $$ ( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} ) $$
  $$ c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m $$
  a function $M(x)$ representing the optimal number of coins needed to make change for $x$ and a function $G(x)$ representing the number of coins needed to greedily make change for $x$, then if $M(x) \ne G(x)$, there exists a counterexample in the range
  $$ c_3 + 1 < x < c_{m-1} + c_m $$

They go on to show that

  If for every $x$ in the range $c_3 + 1 < x < c_{m-1} + c_m $
  $$ G(x) \le G(x-c) + 1$$
  $$ c \in (c_1, c_2, \cdots, c_m )$$
  then $G(x) = M(x)$ (i.e. the greedy algorithm is the optimal).

This gives us an "efficient" (up to pseudo polynomial time) test to determine whether a coin change instance is greedy or not.

Using the above, I have run a short simulation the results of which are plotted on a log-log scale below

Each point represents the average of 10000 instance creations for $m$ shown and each element chosen to be distinct but otherwise uniform and at random from the range of $[1 \cdots N]$.

Given that we know the probability of the greedy algorithm being optimal for $m=3$ goes as $\frac{8}{3} N^{-\frac{1}{2}}$, from just looking at the graph I would hazard a guess that the probability of the greedy algorithm being optimal goes as:

$$ p_m(N) \propto N^{-\frac{(m-2)}{2} } $$

where $p_m(N)$ is the probability that $m$ distinct coins drawn uniformly at random from the range of $N$ is greedy optimal (otherwise known as 'canonical').

In the large $m$ limit, the probability that the greedy solution is optimal goes quickly to 0 for any non-trivial value of $N$.  If the above equation holds, then it is easy to see, but there might be other ways of looking at it that give the same conclusion.  For example, looking at Borgs, Chayes, Mertens and Nair's Random Energy Model work indicate that the energy is too jagged at the bottom to expect local moves (i.e. greedy moves) to give an optimal solution.  This is of course for the Number Partition Problem and is only provided to give some intuition rather than a definite answer.

At the risk of answering a question that you did not ask, I wanted to point out that "real world" coin systems do not follow a uniform distribution for coin denominations.  For example, the USA has at least 12 denominations (including bills: $ (1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ) which do not appear to be uniformly distributed.  Perhaps looking at other distributions to generate the coin denominations would yield non-trivial results in the large system limit.  For example, a power law distribution might yield coin denominations that are more similar to the USA's.


Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

We can make one observation: adaptive access to the oracle doesn't help.  You might as well fix in advance the set of queries you plan to make to the oracle.  So, the condition is that there has to exist a polynomial-size set of candidate values of $b$, such that it is likely that at least one of those will work.

Why doesn't adaptive access help?  That's because you can assume without loss of generality that every oracle query returns 0.  In other words, given an adaptive algorithm for generating queries, run that algorithm with a fake oracle that always returns "no solution", record the list of queries it makes, and there's a list of candidate values of $b$ that a non-adaptive algorithm can use.  This yields a non-adaptive algorithm that performs as well as the adaptive algorithm.

As a consequence, since you want a deterministic algorithm that always succeeds, a necessary and sufficient condition is that there must exist a polynomial-sized, polynomial-time-constructible set $B \subset \mathbb{Z}_{>0}^m$ such that for all possible matrices $A$ there exists at least one $b \in B$ that works for $A$ (i.e., such that there exists $x$ so that $Ax=b$).


A mathematical problem in software watermarking

There is a straightforward solution, using known techniques for obfuscating point functions.

Background. First, go read the following papers:

Positive Results and Techniques for Obfuscation. Benjamin Lynn, Manoj Prabhakaran, Amit Sahai.  Eurocrypt 2004.
On Obfuscating Point Functions.  Hoeteck Wee.  STOC 2005.

Don't come back until you've read those papers, as my solution uses their scheme as a building block.  Short summary: "A point function is a Boolean function that assumes the value 1 at exactly one point."  A point function can be obfuscated in practice (e.g., in the random oracle model).

My solution. Choose the sequence $P$ randomly.  Define the auxiliary function $g$ by $g(P)=1$ and $g(P')=0$ for all other sequences $P'$ over $W$.  Note that $g$ is a point function.  Now let $\hat{g}$ be an obfuscation of $f$, e.g., using the techniques described above.  Choose $Q$ arbitrarily.   Finally, define $F$ as follows: on input $X$, $F$ first checks whether $\hat{g}(X)=1$, and if yes, outputs $Q$, otherwise it behaves normally (i.e., outputs $f(X_1),f(X_2),\dots,f(X_N)$.  This meets all of the requirements you identified.  You can modify this construction in a straightforward way to hide $Q$ as well, if you wish to.

Comment. I'm pretty skeptical whether this will be useful for building an obfuscation scheme that will be secure in practice; my suspicion is that it will not be useful.  You might be able to get some theoretical results, but I don't think those theoretical results will prove very useful in practice, because I expect there will be attacks that will work by violating the assumptions made in your security theorem  (e.g., the attacker will use dynamic analysis to find $P$, and then all security is lost).


Complexity of acyclicity of a "nondeterministic" graph

The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.
The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, force every candidate edge that could begin at the vertex $v_0$ to begin there. If no such $v_0$ exists, then there is no solution.


Halting problem, uncomputable sets: common mathematical proof?

The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map $e : A \to (A \Rightarrow B)$ then every $f : B \to B$ has a fixed point.

Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145.

For a nice introduction to these ideas, see this blog post of Andrej Bauer.


1-D set cover optimisation with connected subsets

The leftmost point must be covered by some interval. There is no harm in picking the longest interval that covers the leftmost point. Then iterate (after removing the interval and all covered points from the instance).

This is the well-known greedy algorithm for the "Interval Point Cover" problem;
see for instance the course page by Andranik Mirzaian for a full analysis.


Converting a Hardware description language to a functional programming language

You could write an interpreter for VHDL or Verilog in e.g. Coq or Isabelle/HOL and then prove that translated hardware descriptions do the right thing. I know that people have done this, at least for fragments of the hardware description languages, see e.g. A Formal Executable Semantics of Verilog.  Companies like Intel or AMD formally verify (parts of) the design of their chips. Have a look at Roope Kaivola's work.


Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

EDIT: original version missed an absolute value.  sorry!!

Hi Ian.  I will briefly outline two sample inequalities, one using a Lipschitz bound, the other using a bound on the second derivative, and then discuss some difficulties in this problem.  Although I'm being redundant, since an approach using one derivative explains what happens with more derivatives (via Taylor), it turns out that the second derivative version is quite nice.

First, with a Lipschitz bound: simply re-work the standard Jensen inequality.  The same trick applies: compute the Taylor expansion at the expected value.

Specifically, Let $X$ have corresponding measure $\mu$, and set $m := \textrm E(x)$.
If $f$ has Lipschitz constant $L$, then by Taylor's theorem

$$
f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,
$$

where $z \in [m, x]$ (note that $x\leq m$ and $x> m$ are possible). Using this and re-working the Jensen proof (I am paranoid and checked that the standard one is indeed on wikipedia),

\begin{align}
\operatorname{E}(f(X)) & =
\int f(x) \, d\mu(x)
\leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt]
& = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|).
\end{align}

Now, suppose $|f''(x)| \leq \lambda$.  In this case,

\begin{align}
f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt]
& \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2,
\end{align}

and so

\begin{align}
\operatorname{E}(f(X))
& \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt]
& = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2.
\end{align}

I'd like to briefly mention a few things.  Sorry if they are obvious.

One is that, you can't merely say "wlog $\operatorname{E}(X) = 0$" by shifting the distribution, because you are changing the relationship between $f$ and $\mu$.

Next is that the bound must depend on the distribution in some way.  To see this, imagine that $X \sim \textrm{Gaussian}(0, \sigma^2)$ and $f(x) = x^2$.  Whatever the value of $\sigma$, you still get $f(\operatorname{E}(X)) = f(0) = 0$.  On the other hand, $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$.  Thus, by changing $\sigma$, you can make the gap between the two quantities arbitrary!  Intuitively, more mass is pushed away from the mean, and thus, for any strictly convex function, $\operatorname{E} (f(X))$ will increase.

Lastly, I don't see how to get a multiplicative bound like you suggest.  Everything I have used in this post is standard: Taylor's theorem and derivative bounds are bread&butter in statistics bounds, and they automatically give additive, not multiplicative errors.

I will think about it though, and post something.  Vague intuition is it will need very strenous conditions on both the function and the distribution, and that the additive bound is actually at the heart of it.


Tim Gowers is a fan of this kind of thing.  See specifically his exposition of Razborov's method of approximations.

In his introduction, Gowers references my expository article on forcing, which is a (not entirely successful) attempt to do the same thing for forcing.  Forcing is normally thought of as a technique in logic and set theory, but it has found its way into TCS occasionally.  It comes up in the study of bounded arithmetic and propositional proof complexity (Krajíček and Takeuti are two researchers who have pursued this connection), and the concept of a generic oracle is related to the concept of a generic filter.


Set optimization problem - is it np-complete?

The answer below observes that a special case of the problem is solvable in polynomial time.  This does not fully answer the question in the post, but may give some insight on what might be needed for an NP-hardness proof, and may provoke additional interest in the post...

Observation. The problem in the post has an algorithm that, given any instance where each $c_i$ is an integer, runs in time polynomial in $n$ and $D = \sum_i c_i$.

Proof sketch.
Fix any input $(S, w, c, K)$ where $w,c\in\mathbb{R}_+^n$ and (WLOG)
$S=\{1,2,\ldots,n\}$.  Rephrasing the problem slightly, the goal is to find $M\subseteq S$ of size $K$ maximizing $\frac{\sum_{i\in M} w_i c_i}{\sum_{i\in M} c_i} - \sum_{i\in M} w_i$.

Consider the following dynamic program.
For any integers $(d_1, d_2, k, m)$ with $0\le d_1 \le d_2 \le D$, $0\le k \le K$, and $k\le m\le n$, define
$$\textstyle\phi(d_1, d_2, k, m)
= \max \Big\{ \sum_{i\in M} w_i (c_i / d_1 - 1) ~:~
M \subseteq [m],\, |M| = k, \, \sum_{i\in M} c_i = d_2\Big\}.$$
The desired solution is $\max_d \phi(d, d, K, n)$.

Partitioning the possible solutions for $\phi(d_1, d_2, k, m)$ into those that contain $m$ and those that don't, we get the recurrence
$$\textstyle\phi(d_1, d_2, k, m)
= \max\begin{cases}
\phi(d_1, d_2 - c_m, k-1,m-1) + w_m(c_m/d_1-1) \\
\phi(d_1, d_2, k, m-1).
\end{cases}$$
We leave the boundary cases as an exercise.

The number of subproblems is $O(n^2 D^2)$, and for each the right-hand side of the recurrence can be evaluated in constant time, so the algorithm runs in time polynomial in $n$ and $D$. $~~\Box$

Corollary. Unless P=NP, any reduction showing NP-hardness will reduce to instances where $D$ is not polynomial in $n$.

Remark. Unless I am mistaken, there is also a PTAS for the problem in the post, based on rounding the $w_i$'s then using dynamic programming. However, the existence of a PTAS has no direct bearing on whether the problem is NP-hard, as asked in the post.

I am also curious --- does anyone know whether the special case when $w_i=c_i$ (for each $i$) has a poly-time algorithm? (EDIT: it does, per Willard Zhan's comment this seems to be optimized by taking $M$ to contain the $k$ largest elements.)


Two way deterministic multihead counter automata or logspace TM with counter

A two-way deterministic (nondeterministic) multi-head finite automaton can be simulated by a logspace DTM (NTM), and vice versa.

So, for including class $ \mathsf{NL} $, you do not need a counter!

The value of the counter belonging to a two-way nondeterministic multi-head finite automaton with one-counter can be bounded by a polynomial, otherwise, the computation enters an infinite loop. Since both such a counter and the input heads can be simulated in logspace, $ \mathsf{LOGCFL} $ upper bound can be replaced with $ \mathsf{NL} $.

Note that any language recognized by a two-way deterministic (nondeterministic) one-head finite automaton with one-counter is in $ \mathsf{L} $ ($ \mathsf{NL} $).

There are many papers on these topics, e.g. this paper. You can find more after some googling. (Check also Lemma 1 of this paper.)


Hardness of 3-dimensional matching variant

EDIT (Aug 1):

I posted a small report with a more detailed proof on my blog; the reduction idea is the same, but the "gadget" used are better explained (you can also directly download the pdf from here)

The problem seems NP-complete and this is a possible reduction from SET COVER.

Suppose you have an universe $A$ of $n$ elements: $A = \{a_1,...,a_n\}$, a collection of $m$ subsets $\mathcal{S} = \{S_1,S_2,...,S_m\}$ (with $S_i \subseteq A$) and an integer $k$. The SET COVER problem asks for a sub-collection $\mathcal{C} \subseteq \mathcal{S}$ of size at most $k$ such that $\bigcup_{S_i \in \mathcal{C}} S_i = A$ (with $|\mathcal{C}| \leq k$).

The reduction to your problem (I call it 3DM-relaxed, 3DMR) can be done in the following way.

The subsets $S_i$ are simulated using one or more elements of the set $X$, the elements of the universe $A$ are simulated using elements of the sets $Y$ and $Z$ ($a_{2j}$ is simulated with an element $y_{a_{2j-1}}$ of $Y$, $a_{2j-1}$ is simulated with an element $z_{a_{2j}}$  of $Z$).

We start with $X = \{ e_1,e_2,...,e_{k} \}$ that will force the $|\mathcal{C}|=k$ constraint.

Then, for every subset $S_i$ we create the triple: $(x^1_{S_i}, y_{S_i}, dum)$, where $dum$ is a new element of $Z$; and add the $k$ triples:
 $(e_1,y_{S_i}, dum),(e_2,y_{S_i}, dum),...,(e_{k},y_{S_i}, dum)$

Note that all $dum$ elements are distinct!

In this way at most $k$ of the $x^1_{S_i}$ will be "free" to cover the elements representing the $a_j$: indeed the $(e,\cdot,\cdot)$ triples can include at most $k$ of the $y_{S_i}$, the remaining $m-k$ must be included by the corresponding $(x^1_{S_i},\cdot,\cdot)$ triple.

To link the $x^1_{S_i}$ to the elements $y_{a_{2j}}, z_{a_{2j-1}}$ that correspond to the elements of the universe in $S_i$, we add three bridge triples:
$(x^1_{S_i},y_{B_i},z_{B_i})$,
$(x^2_{S_i},y_{B_i},dum)$,
$(x^3_{S_i},dum,z_{B_i})$

At this point the elements of $A$ can be linked to $x^2_{S_i}$ and $x^3_{S_i}$ (or we can further extend the capacity of $S_i$ adding more bridge triples).

For example adding the triples:

$(x^2_{S_i},y_{a_2},z_{a_1}), (x^3_{S_i},y_{a_4},z_{a_3})$ we simulate the set: $S_i = \{ a_1, a_2, a_3, a_4\}$.

The fundamental point is that if $x^1_{S_i}$ is "used" to cover the element $y_{S_i}$ (blue edges in the figure) then:

$x^2_{S_i}$ must be used to include element $y_{B_i}$ and cannot be used to include elements $y_{a_2}, z_{a_1}$ (red edges in the figure);
$x^3_{S_i}$ must be used to include element $z_{B_i}$ and cannot be used to include elements $y_{a_4}, z_{a_3}$ (red edges in the figure).

Some of the $S_i$ included in the cover can have a  non-empty intersection; so we must be sure that two distinct $x^p_{S_i}, x^q_{S_j}$ that are linked to the same element $a_i$ (i.e. we have the triples $(x^p_{S_i}, a_i, \cdot), (x^q_{S_j}, a_i, \cdot)$) can be included in the matching. For this purpouse for every $x^p, p > 1$ we add a triple with two dum elements: $(x^p, dum, dum)$ (green edges in the figure below).

Finally we can add as many distinct triples $(x, y, dum_i), (x, dum_j, z)$ as needed to be able to garbage collect all the dum elements $dum_i \in Z$ and the dum elements $dum_j \in Y$ (otherwise the would not be included in the matching) if they are left alone.

Also note that if there are too many $S_i$, the elements $e_i$ can be included in the matching using their $z_{dum}$ element in $Z$ (only the pair $(e_i, z_{dum})$ is picked).

The resulting 3DMR instance has a solution if and only if there is an set cover $\mathcal{C}$ of $A$ of size at most $k$.

In the figure a triple $(x,y,z)$ is represented with two edges $(x,y),(x,z)$ of the same color. As an example, if $x^1_{S_1}$ corresponding to $S_1 = \{a_1,a_2,a_3,a_4\}$, must be used to include $y_{S_1}$ (blue edges), then it cannot be used to include the elements $z_{a_1},y_{a_2},z_{a_3},y_{a_4}$ (red edges).


Auction theory - Selling Multiple Items via Social Networks

the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+19+17+11+10 and the second is 20+19+17+14+11. So D's payment is 10.

p.s. there is a typo in one of the constraints for the two allocations, which is updated in the paper.


What are "$\mu$-recursive functions" and $\mu$-calculus?

If it is the μ-recursive functions you are interested in (and not the μ-calculus, which is a totally different thing as slimton pointed out) it makes the most sense if you start looking at the primitive recursive functions (PRFs). The set of PRFs is interesting in it self and it turns out that the μ-recursive functions can be introduced by an extension of it.

Here are some slides that seems to be a relatively gentle introduction:
Link


How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule?

This can take exponentially many steps, as Laakeri explained.
You can build a system that cycles with period $p$.  In particular, the update rule is $x_i = x_{i-1 \bmod p}$ for all $i$, with variables $x_0,\dots,x_{p-1}$.
Let $p_1,\dots,p_k$ be the first $k$ primes.  Concatenate $k$ disjoint systems, each of which cycles with period $p_i$.  Then the period of the entire system is the product $p_1 \cdots p_k$.  The system involves $p_1+\dots+p_k$ variables.
If you have $n$ variables, then we can take $k$ to be approximately $\sqrt{4n/\log n}$.  Now the product of the first $k$ primes is roughly $e^{k \log k}$, or in other words, $e^{\Theta(\sqrt{n/\log n})}$, which is exponential in $n$.
This shows that the period of a system, and thus the time to reach a cycle (by your definition), can be exponential in the number of variables.


Finding the size $k$ subset in a metric space that maximizes the min distance between elements

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-approximation, and that this factor is actually optimal by a reduction to clique.

I skimmed it, so I might be missing some subtle points, but the idea of the proof seems quite simple: take an optimal $S\subseteq X$ with $\vert S\vert=k$, with objective value $\mathsf{OPT}$. Note that the $k$th point you add in the greedy algorithm will attain the closest distance (to another point) in the greedy solution, so it suffices to show that the last point you add must have distance at least $\mathsf{OPT}/2$ from the previous $k-1$ points you selected. This is seen by noting that the $k$ (open) metric balls of radius $\mathsf{OPT}/2$ around each point in $S$ are disjoint; as a result, at least one of these balls does not contain any of the first $k-1$ points you have chosen. The respective center in $S$ is therefore an option at step $k$ which attains a pairwise distance of at least $\mathsf{OPT}/2$ from all previously chosen points, so the same must be true of the greedy point chosen at the $k$th step.


P and NP classes explanation through lambda-calculus

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define.

From the point of view of computational complexity they seem to behave differently.
The main reason people use Turing machines and not $\lambda$-calculus to reason about
complexity is that using $\lambda$-calculus naively leads to unrealistic complexity measures, because you can copy terms (of arbitrary size) freely in single $\beta$-reduction steps, e.g. $(\lambda x.xxx)M \rightarrow MMM.$ In other words, single reduction steps in $\lambda$-calculus are a lousy cost model. In contrast, single Turing-machine reduction steps  work great (in the sense of being good predictors of real-world program run-time).

It is not known how fully to recover
conventional Turing-machine based complexity theory in
$\lambda$-calculus. In a recent (2014) breakthrough Accattoli and Dal Lago
managed to show  that
large classes of time-complexity such as $P$, $NP$ and $EXP$ can
be given a natural $\lambda$-calculus formulation. But smaller
classes like $O(n^2)$ or $O(n \, log\, n)$ cannot be presented
using the Accattoli / Dal Lago techniques.

How to recover conventional space   complexity using
$\lambda$-calculus is unknown.


I recommend you taking a look at this book chapter:

J. L. Szwarcfiter, A Survey on Clique Graphs, Recent Advances in Algorithms and Combinatorics,
CMS Books in Mathematics 2003, pp 109-136.

In there, many characterizations of clique graphs of specific classes are given. For example, it is mentioned that the clique graphs of chordal graphs are the dually chordal graphs and clique graphs of proper interval graphs are also proper interval graphs, and not trees and paths as you supposed.


Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

Yes, because you made the approximation irrelevant.  Reduce from k-SAT:

Each variable contributes one element to $\mathcal{U}$ and each clause

contributes k+1 elements to $\mathcal{U}$, one for each literal and one more.

Each literal contributes one set to $\mathcal{S}$  -  The elements are [[the element of $\mathcal{U}$ from

the literal's variable] and [the [elements from the clauses] which are [for that literal]]].

Each clause contributes  2k-1  sets to $\mathcal{S}$    -    One for each non-full subset of the set of literals,

but the other element from the clause must be in each of those  2k-1  elements of $\mathcal{S}$.

For a subset of $\mathcal{S}$ to be pairwise disjoint, it cannot have sets from opposite literals and

cannot have more than one set from any given clause.  For a subset of $\mathcal{S}$ to cover $\mathcal{U}$,

it must have at least one set from each variable and at least one set from each clause.

Thus exact covers must have exactly one set from each variable and from each clause.

Each element of $\mathcal{S}$ is from

[[no clauses and exactly one variable] or [no variables and exactly one clause]],

so all exact covers have exactly    number of variables  +  number of clauses    elements of $\mathcal{S}$.

For any assignment which does not satisfy the k-SAT formula, the subset of $\mathcal{S}$ induced by that assignment is disjoint from at least one clause's set of k+1 elements of $\mathcal{U}$, no other clauses' sets intersect any of those sets of k+1 elements of $\mathcal{U}$, and no single element of $\mathcal{S}$ covers all of those k+1 elements of $\mathcal{U}$.  Thus non-satisfying assignments have zero extensions to exact covers.

For any assignment which does satisfy the k-SAT formula, each clause has exactly one element

of $\mathcal{S}$ from the set of that clause's literals which are false, one can trivially find the set of those elements of $\mathcal{S}$, and using that set to extend [the subset of $\mathcal{S}$ induced by the assignment]

gives an exact cover.  Since elements of $\mathcal{S}$ from clauses do not have any elements of $\mathcal{U}$

from other clauses, satisfying assignments have no other extensions to exact covers.

Therefore your problem is ETH-hard under strongly parsimonious reductions.


Reference for the number of samples needed to distinguish two probability distributions

So here, you only have two options: either your samples come from $p$, or from $q$ (and you know explicitly both).

By definition of the statistical/total variation distance, we have
$$
d_{TV}(p,q) = \sup_S( p(S)-q(S))
$$
where the supremum is taken over all measurable sets $S$. I haven't looked at the paper, but assuming all is nice (finite), the $\sup$ is a $\max$ and achieved for some particular set $S^\ast$, that you can compute given $p,q$.

So at this point, you have an explicit set $S^\ast$, the values $p(S^\ast)$, $q(S^\ast)$ which by definition satisfy
$$
p(S^\ast) = q(S^\ast) + \varepsilon
$$
and you know that the unknown distribution $h$ is either $p$ or $q$. So to distinguish between the two cases, it suffices to estimate $h(S^\ast)$ up to an additive $\frac{\varepsilon}{2}$, which can be done straightforwardly with $O(1/\varepsilon^2)$ samples.

Side remark: this can be improved a little if both $p(S^\ast), q(S^\ast)$ are both $O(\varepsilon)$ themselves. In which case, distinguishing between the two cases only requires $O(1/\varepsilon)$ samples. (The "hard case" basically is to distinguish $1/2$ from $1/2+\varepsilon$, which requires $\Omega(1/\varepsilon^2)$ samples.)

Second remark: usul refers,in his answer, to a harder problem, composite hypothesis testing. In this problem, you only have one distribution $p$, and want to distinguish between (i) $h=p$ and (ii) $d_{TV}(h,p)>\varepsilon$ (that is, the second option is not a singleton $\{q\}$, but the much larger set of all distributions that are $\varepsilon$-far from $p$). In this case, you need a lot more samples: as a function of the (explicitly known) $p$, this will be basically* $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}/\varepsilon^2$ (see [VV14]), where $\lVert p^{-\max}_{-\Theta(\varepsilon)}\rVert _{2/3}$ is a functional of the distribution $p$ (equal to $\Theta(\sqrt{n})$, for instance, when $p$ is the uniform distribution on a set of $n$ elements). See also [BCG16] for an alternative, also tight* characterization of this quantity in terms of another functional.

$*$ The two characterizations are tight in most cases, except some pathological/strange ones.

[VV14]  G. Valiant and P. Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, 2014. [full version]

[BCG16] E. Blais, C. Canonne, and T. Gur. Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)
Manuscript, 2016. [ECCC TR16-168]


Does p-isomorphism preserve phase transition?

Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with respect to some parameter $m(x)$. Then so does $L_2$, with respect to the parameter $m_2(y) := m(\varphi^{-1}(y))$. (This relies on the fact that "phase transition" talks about the fraction of satisfiable instances jumping from 0 to 1, as a fraction of an exponential number of instances of a given size, and p-isomorphisms preserve densities up to a polynomial.)

I'm not sure this is such a meaningful statement, however, because the parameter $m_2$ above can be totally unnatural from the point of view of $L_2$. Most phase transitions of interest are with respect to some natural parameter (e.g. clause-to-variable ratio in k-SAT, density of a graph, etc.). But those natural parameters are defined in terms of some "internal" structure to the instances, not by just treating the problem instances as abstract strings in $\Sigma^*$ ($\Sigma$ your finite alphabet). But p-isomorphism does just treat inputs as abstract strings, and "knows nothing" about the internal structure that we like to impose on them. So, sure, you can say that all paddable languages have a phase transition since k-SAT does. But that doesn't tell you if, for example, solvability of quadratic Diophantine equations exhibits a phase transition in terms of any parameter that is natural from the point of view of Diophantine equations...


Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

Unfortunately I am not aware of any complete and sound algorithm for solving this task. As far as I am aware, most techniques consist of Stochastic Local Search algorithms.

TSPTW (Traveling Salesman Problem with Time Windows) is a good example of your problem. For the particular case where constraints are not hard so that they result in a penalty, the best results have been derived with Ant Colony Optimization [1]. Another algorithm known as the Nested Rollout Policy Adaptation [2] has been used as well. Finally, Monte-carlo has been tried (I cite [3] but there are surely a number of references in this regard)

Hope this helps,

Bibliography

[1] Manuel López Ibáñez and Christian Blum, "Beam-ACO for the tranveling salesman problem with time windows", Computers & OR 37 (9), 1570--1583 (2010)

[2] T. Cazenave and F. Teytaud, "Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows", LION 6, Springer (2012)

[3] A. Rimmel, F. Teytaud, and T. Cazenave, "Optimization of the nested monte-carlo algorithm on the Traveling salesman problem with time windows", Applications of Evolutionary Computation, 501--510 (2011)


How/Why are linear systems so crucial to computer science?

The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.

Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that.

This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me.

This is one reason why linearity has such power. There are probably many others.


Efficient representation of set of partial order

Restrictions on pre-orders

You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order with a list of forbidden relationships: that is, we specify $a < b$ using a pre-order which specifies $a \leqslant b$ along with many other relationships, and by separately specifying that $b \leqslant a$ is forbidden.

We may similarly represent $a \not\cong b$ by having any pre-order in which at least one of $a \leqslant b$ or $b \leqslant a$ fails to hold. (I got this confused in a previous edit.)

So: we will consider how to represent pre-orders, and presume that we have a list of further restrictions representing relations of the type $\leqslant$, $\geqslant$, and $\cong$ which we forbid between certain pairs. (For each pair $(a,b)$, there are then four possibilities for forbidden relations, including the the case of no forbidden relation.) The forbidden relations I would represent as a list, which we will later iterate through exactly once; however, in order to be able easily to remove restrictions when computing the order $P_{a,b}$ from a pre-order $P$, you might want to combine this list structure with an $r \times r$ array $F$ which stores for each $1 \leqslant a < b \leqslant r$ what sort of relation (if any) is forbidden between $a$ and $b$.

Representing pre-orders

You can easily represent a partial order by a transitive reduction: a minimal relation (naturally represented as a directed graph, via adjacency lists for immediate predecessors and immediate successors) subject to the constraint of having the partial order as its transitive closure. For a pre-order, you can instead use a relation $R$ which would be the transitive reduction if you "collapsed" all sets of equivalent elements to a single item each; where for all $i \leqslant j$, we have $(i,j) \in R$ if and only if $\exists k: i \leqslant k \leqslant j$ implies that $j \leqslant i$. That is, $(i,j) \in R$ only if one of the following holds:

$i < j$ and $\neg\exists k: i < k < j$;
$i \leqslant j$ and $j \leqslant i$.

Such a relation can be easily computed by reduction to computing the transitive reduction of the partial order obtained, as I described, by collapsing equivalence classes (using only one representative node for each equivalence class, and then copying relations across the class). This can be done in time $O(r^3)$ or better.

Given such a representation of pre-orders $P$ by reductions $R$, one may decide $(i,j) \in P$ by testing $(i,j)$-connectivity in $R$, e.g. by breadth-first search. This, of course, takes time $O(n)$. However, one can quite efficiently compute the reduction $R_{i,j}$ of the pre-order $P_{i,j}$ for $i<j$, by

copying the immediate successors of $j$ and sharing them with $i$,
copying the immediate predecessors of $i$ and sharing them with $j$,
removing the relation $(i,j)$ from $R$.

The complexity of this is essentially the sum of the in-degree of $i$ and the out-degree of $j$. I imagine that you would also like to remove the prohibition on $i \leqslant j$ and/or $j \leqslant i$ at the same time; we can achieve this simply by removing any restrictions which are stored at $F[i,j]$ or $F[j,i]$ as appropriate.

Representing subsets of $S \subseteq P_r$

Assuming that all you want to use the subsets $S \subseteq P_r$ for is to check compatibility of individual pre-orders with the elements of $S$, I think the best approach is to store an $r \times r$ array where each element $(i,j)$ contains a collection which indicates the labels of all pre-orders $P \in S$ such that $(i,j) \in P$. (That is: you do not need to store any forbidden relationships.)

The collection may as well be a simple list, for small sets $S$ or if the orders which it contains don't have too many common relations (e.g. minimal and maximal elements in common); otherwise use your set-implementation of choice (e.g. balanced search trees) instead. This can be updated simply by adding a new relation $P'$ to the entries for all pairs $(i,j)$ which are contained in $P'$. If $P'$ is represented by a reduction $R'$, one may do this by a depth-first search from its minimal elements (which one may store a list of in the representation), and performing depth-first search to find all descendants of each element.

If one maintains a list of traversed nodes along each path of the traversal, one may add each newly traversed node to the descendants of each of those already on the list; after finishing a traversal, pop the node off the list and mark it as visited.
For each visited node, we copy its descendants to any nodes on the traversal-list, rather than re-traversing it.

This is also a good thing to do, to compute a more explicit representation of $P'$ from $R'$, once your interest in $P'$ becomes dominated by testing $(i,j) \mathbin{\in?} P'$. This will take time $O(r^2)$, as there is essentially unit cost to reverse each edge $(i,j) \in R$, and to record each of the descendants of any $i \in [1,r]$ throughout the traversal. If $s = |S|$ and you use trees for collections at each index $(i,j)$, constructing the representation for $S$ takes time $O(r^2 s \log s)$, with the $\log s$ factor being saturated in the case where many elements of $S$ share many pairs $(i,j)$ in common. This works best for partial orders which are sparse and essentially unrelated, which would reduce both the expected overlap for pairs $(i,j)$ and the number of entries $(i,j)$ for which any relationship is recorded in the traversal of its reduction.

Having this representation of $S$, you can test incompatibility of $P$ with $S$ (where $P$ is given by a reduction $R$) as follows.

Initialise a list of all of the elements of $S$, representing those which are potentially compatible with $P$.
Iterate through your forbidden relations, and remove from the list of potentially compatible relations, any element of $S$ which violates any of the constraints. (That is, if $a \leqslant b$ is forbidden, remove any element of $S$ for which that relation holds; and similarly for any element of $S$ fo which $a \cong b$, if that relation is forbidden.)
Perform a breadth-first search of $R$: and at each link $(i,j) \in R$ traversed, remove from the list of potentially-compatible orders any order $P$ for which $j < i$, by checking for each order on the list whether this is the case.

If the list of potentially-compatible orders ever becomes empty, then $P$ is incompatible with $S$. Otherwise, the list contains at least one partial order in $S$ with which $P$ is compatible.

We can bound each index search $(i,j)$ for a potentially-compatible order by $O(\log s)$, for $s =|S|$; this will happen for each "reduced" relation in $P$, that is for every ordered pair in $R$. If $m = |R|$, then the worst case is $O(ms \log s) \subseteq O(r^2 s \log s)$, in the case that every element of $S$ is compatible with $P$. If you have $f = |F|$ forbidden relationships, then iterating through these and eliminating potentially compatible relations takes time $O(f \log s)$; this is also dominated by $O(r^2 \log s)$, though the larger $f$ is the faster the subsequent compatibility-checking becomes.


Type-theoretic interpretation of Skolemization

Skolemization corresponds to the so-called type theoretic axiom of choice, which is briefly discussed in section 1.6 of the HoTT book.

This provides an equivalence along which we can swap $\Sigma$ and $\Pi$ types. Assuming $A : U$, $B : A \to U$ and $C : \prod_{a : A} B\,a \to U$, we have an equivalence:

$$ac : \Big(\prod_{a : A}\sum_{b : B\,a}\,C\,a\,b\Big) \simeq \Big(\sum_{(b : \prod_{a : A} B\,a)} \prod_{a : A} C\,a\,(b\, a)\Big)$$

The proof of this very simple, e.g. in Agda we have the following (proving isomorphism instead of equivalence for simplicity now):

open import Data.Product
open import Function
open import Relation.Binary.PropositionalEquality

iso : Set → Set → Set
iso A B =
  ∃₂ λ (f : A → B)(g : B → A) → (∀ x → f (g x) ≡ x) × (∀ x → g (f x) ≡ x)

ac : ∀ {A : Set}{B : A → Set}{C : ∀ a → B a → Set}
     → iso ((a : A) → Σ (B a) λ b → C a b)
           (Σ ((a : A) → B a) λ b → (a : A) → C a (b a))
ac = (λ f → proj₁ ∘ f , proj₂ ∘ f)
   , (λ {(b , c) a → b a , c a})
   , (λ _ → refl)
   , (λ _ → refl)

Going from left to right along the equivalence, we convert an existential variable into a function abstracting over the universal variable in scope. We can also use this iteratively, to move all $\Sigma$-s from a mixed-quantifier type to a prefix.

From a more operational perspective, this corresponds to lambda lifting, a program transformation used in compilers, which lifts definitions into an outer scope by adding extra function parameters for bound variables.


Decidability of inductive invariant existence in Presburger arithmetic

The inductive invariant separator problem for Presburger arithmetic is undecidable.

I am unaware of a proof in the literature to point you at. (It seems so straightforward a question I assume it is somewhere out there.) The proof I came up with follows roughly the same construction as the halting problem. Here is a brief overview. We first assume a decision procedure $D$ exists and then construct a machine $S$ with input $M$. $S$ uses $D$ to decide non-termination of $M$ on itself and then $S$ reverses the output. We then use the construction of $S$ to show that $D$ must give an incorrect answer on the execution of $S$ on itself.

Instead of a reduction to the halting problem, the proof is for all intents and purposes a restatement of the proof of the halting problem. It is a bit verbose as will require that the exact strongest post condition can be expressed.  (If a simpler proof is possible, I'd be very interested in hearing it.) Now on to the gory details.

The inductive invariant separator problem for Presburger arithmetic is for a given 4-tuple $\left<\bar v,Init,Next, Bad\right>$ where $\bar v$ is a finite set of variable names, $Init$ and $Bad$ are Presburger formulas whose free variables are in $\bar v$, $Next$ is Presburger formula whose free variables are in $\bar v$ or $\bar{v}'$ (a primed copy of $\bar v$) does there exist a formula $\phi$ in Presburger arithmetic with free variables in $\bar v$ such that:

$Init \implies \phi$
$\phi \land Next \implies \phi'$
$\phi \implies \lnot Bad$

where $\phi'$ primes all of the free variables in $\phi$.

Suppose this problem is decidable. There then exists a Turing machine $D'$ that decides the separator problem (for a given encoding of Presburger formulas). Let $D$ be a deterministic Turing Machine that simulates $D'$. $D$ terminates and decides the separator problem.

A variable assignment over a finite set of variables $\{v_i\}$ is a conjunction $\bigwedge v_i = c_i$ where $c_i$ is an integer constant.

I will also assume the existence of a Turing machine to Presburger arithmetic compiler $C$ with some reasonable, but strong restrictions. $C$ takes as input a Turing machine $M$ with a unique final state, $term$, and an input $w$, and constructs presburger formulas $Init$ and $Next$ over a finite set of variables $\bar v$. Informally we require the paths of the Presburger formulas to simulate the execution of $M$ on $w$. Further, we require it to be a step simulation. Formally, we require that:

$C$ assigns a unique constant to all control states in $M$ and let the constant for $term$ be $\left<term\right>$,
$C$ includes a variable $pc$ in $\bar v$ that tracks the control state of $M$ at every step in the execution,
$C$ generates $Init$ to be in the form of a variable assignment over $\bar v$,
$C$ ensures that $Next$ to have a unique successor on variable assignments over $\bar v$ (that are reachable from $Init$) if $M$ is deterministic,
for there to exist an injective function $f$ from a state of $M$ (control and tape) to a variable assignment over $bar v$ such that $Next$ has a successor, the initial state of $M$ on $w$ is mapped to exactly $Init$ and the control state of $M$ consistently assigns $pc$,
$C$ is deterministic, and
$C$ terminates.

Now construct the Turing machine $S$ that takes a Turing machine $M$ as input and does the following (in pseudocode):

S(M):
   Run C(M,M) to get v, Init and Next
   Simulate D on v, Init, Next, Bad := (pc = <term>)
   If D says a separator exists:
     terminate
   If D says no separator exists:
     loop: goto loop

We now show $D$ cannot give a consistent answer on $S$ with the input $S$.  Start executing $S(S)$. $C$ terminates with $Init$ and $Next$ that can simulate $S$ with the input $S$. We now setup a correspondence between state $i$ of the execution of $S(S)$, $s_i$, and the $i$th variable assignment $\bar v_i = f(s_i)$ of the execution of $Next$ starting from $Init$. $S$ is deterministic by construction so by the properties of $C$, $Next$ must have unique successors on variable assignments and $Init$ is a variable assignment. (For reference, $f(s_0)=\bar v_i=Init$.)

Suppose $D$ says a separator exists. Let $\phi$ be such a separator. The execution of $S(S)$ then reaches $term$ in $k$ steps. (This includes executing $C$ and $D$.) Now $\bar v_1 \ldots \bar v_k$ is a counter example to $\phi$ being a separator as it reaches $pc = \left<term\right>$. $D$ gave an inconsistent answer.

Now suppose $D$ says no such separator exists. $S(S)$ then reaches the control state $loop$ in $k$ steps. All states after $k$ are then identical $s_{k+1}=s_{k+2}=\ldots$. The corresponding variables assignment sequence after $k$ must then assign each variable to the same constant. Let $\phi = \bigvee_{i=1}^{k+1} \bar v_i$. (Note: $\phi$ is now exactly the reachable variable assignments by $Next$ starting from $Init$.) Then

$Init \implies \phi$ as $Init$ is exactly $\bar v_1$.
$\phi \land Next \implies \phi'$ as $Next$ is deterministic and for all $i$ if $\bar v_i$ holds then $\bar v_{i+1}'$ holds.
$\phi \implies \lnot Bad$ as each variable assignment $\bar v_i$ implies $pc \neq \left<term\right>$.

Thus $\phi$ is an inductive invariant separator for $\left<\bar v,Init,Next, Bad\right>$ and $D$ gave an inconsistent answer.

$D$ must always give an inconsistent answer and thus a decision procedure does not exist.

Doing this exercise really made me appreciate Jerome Leroux's work on separators for vector addition systems.


Partitioning graphs while minimizing inter-partition edges

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.

Satish Rao. Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.

Horst D. Simon and Shang-Hua Teng. How Good is Recursive Bisection?
In  SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.


Here are some recent papers on PCPs with small query complexity that I found interesting:

arxiv.org/pdf/1305.1979
eccc.hpi-web.de/report/2013/179/download
wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf
eccc.weizmann.ac.il/report/2015/085
cs.utexas.edu/~danama/papers/par-rep/final3.pdf
cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf
eccc.hpi-web.de/report/2016/160

Also, this paper is somewhat older, but it is interesting and can help understanding the context to some of the previous papers. In addition, if I may recommend a paper of my own, I think this paper contains open problems that might be useful.


What's the difference between Moggi's computational metalanguage and Moggi's lambda calculus?

The terminology can be a bit confusing but yes there are two languages
in for instance Moggi's "Notions of Computations as Monads" (free link
here: https://core.ac.uk/download/pdf/21173011.pdf).

In that paper, the languages are called $\lambda_{ml}$, the
metalanguage, and $\lambda_{pl}$ the "programming language". I believe
$\lambda_{pl}$ plays the role of the computational lambda calculus but
I may be mistaken.
One confusing aspect is that both languages have an explicit type
constructor $T$ representing the monad, but they are used differently.

$\lambda_{ml}$ is a "pure" language with a monad $T$, i.e., all
manipulation of the monad is explicit in the types and the function
type $\tau_1 \to \tau_2$ is the type of pure functions. Observe the
bind rule (from figure 3 on page 9):

$$\frac{x   : \tau \vdash_{ml} e_1 : T \tau_1 \quad
        x_1 : \tau_1 \vdash_{ml} e_2 : T \tau_2 }
       {x :\tau \vdash_{ml} let_T x_1 \Leftarrow e_1 in e_2 : T \tau_2}$$

$e_1$ and $e_2$ are explicitly typed as terms of $T \tau_1, T\tau_2$
to mark that they are effectful. Every effectful expression is really
a pure term with monadic type. This is similar to how we program with
monads in Haskell where Haskell plays the role of the metalanguage and
the monad encodes effects but really we are always manipulating "pure"
terms (I put "pure" in quotes as Haskell has its own effects of
divergence and error).

We can see this in the semantics of the metalanguage: a term $x:\tau
\vdash_{ml} e : \tau'$ denotes a morphism $[\tau] \to [\tau']$, the
monad doesn't arise unless we mention it.

On the other hand, $\lambda_{pl}$ is intended to be an effectful
call-by-value programming language. As such a term $x : \tau
\vdash_{pl} e : \tau'$ is a possibly effectful term that returns
values of type $\tau'$, similar to languages like SML and OCaml. That
is why in the paper the function type is written $\tau \rightharpoonup
\tau'$ because it is the type of effectful functions, not pure
functions.

Compare the bind rule here (from figure 5 on page 11):
$$\frac{x   : \tau \vdash_{pl} e_1 : \tau_1 \quad
        x_1 : \tau_1 \vdash_{pl} e_2 : \tau_2 }
       {x :\tau \vdash_{pl} let x_1 \Leftarrow e_1 in e_2 : \tau_2}$$

The monad doesn't appear explicitly, but in the semantics this uses the
Kleisli extension of $e_2$.
In the semantics, we see that the terms of the programming language
are interpreted in the Kleisli category of the monad, so a term $x :
\tau \vdash_{pl} e : \tau'$ denotes a morphism $[\tau] \to T[\tau']$.

$\lambda_{pl}$ does include an explicit monad constructor $T$, which
SML and OCaml don't have as a primitive type constructor because $T a$
is equivalent to unit -> a because -> means effectful function.


Confluently Persistent String Data Structure

What you seem to be looking for is not a data structure for strings themselves, but a grammar for representing concurrent actions on strings. The field of study for this is Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation


this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with "big data" research directions.

Tradeoff Algorithms in Streaming Models, Andrea Ribichini, p7:

  We have devised several algorithms for fundamental graph problems in the
  W-Stream model, including connected components, minimum spanning tree,
  biconnected components and single-source shortest paths. To the best of
  our knowledge, our algorithms are the first to allow effective space/passes
  tradeoffs for such problems in a data streaming setting.

this ref includes other refs/surveys which might be helpful.

  Despite the heavy restrictions imposed by the [classical streaming] model, major success has
  been achieved for several data sketching and statistics problems, for which
  a constant number of passes and polylogarithmic working memory have
  been proven enough to find approximate solutions (see [4, 16, 17] and the
  extensive bibliographies in [7, 29]).

also:

Trading off space for passes in graph streaming problems
Camil Demetrescu,
Irene Finocchi,
Andrea Ribichini


Approximately sampling from convex polyhedrons with quantum computers

As the post acknowledges, the existence of a classical polynomial-time algorithm to estimate the volume of a convex polytope is a game-changer.  A quantum algorithm is much less likely to be interesting unless it is competitive with classical algorithms.   After all, without that criterion, any classical algorithm could simply be called a quantum algorithm instead.

That said, there is still room for a polynomial speed-up, and the main, known viewpoint for that type of speedup is a quantum walk, especially considering that the classical acceleration in this case is based on a good random walk.   (Indeed, any quantum algorithm can be viewed as a quantum walk, but for some algorithms this is not necessarily enlightening.)   Various papers in the QC literature have pointed out that the algorithms to estimate the volume of a convex polytope use random walks, and that there could be an acceleration from a quantum walk.  So, it appears that researchers know this suggestion, but that no one has tried to work out what polynomial acceleration you might get for this problem.   You might not get anything if the best classical algorithm has some sort of spoiler, such as a separate stage which is not a random walk with comparable running time.

Here is a collection of papers that all mention the basic idea in passing; again, Google Scholar seems to suggest that no one has gone further.

arXiv:quant-ph/0104137 - Quantum Walks on the Hypercube
arXiv:quant-ph/0205083 - Quantum random walks hit exponentially faster
arXiv:quant-ph/0301182 - Decoherence in Discrete quantum walks
arXiv:quant-ph/0304204 - Controlling discrete quantum walks: coins and intitial states
arXiv:quant-ph/0411065 - Quantum walk on a line with two entangled particles
arXiv:quant-ph/0504042 - Entanglement in coined quantum walks on regular graphs
arXiv:quant-ph/0609204 - Quantum speedup of classical mixing processes
arXiv:0804.4259 - Speed-up via quantum sampling
A random walk approach to quantum algorithms
Discrete quantum walk for solving nonlinear equations over finite fields

The other side of the classical algorithms to estimate the volume of a convex polytope is linear programming.   I don't know there has been any progress finding a quantum acceleration for that.  It seems difficult to avoid a stage of linear programming in order to put the convex polytope in a favorable position for sampling.


How is rebalancing of DHTs handled in case of failure or addition of new node?

That's the whole purpose of consistent hashing. When you add a new node, you compute its hash key, find the two nearest neighbors on the hash ring and link the node in between them. When the hash function has good statistics, you expect a uniform distribution of hash keys, resulting in good load balancing. You don't have to redistribute the existing keys. Removal of nodes works analogously.

In summary, there's no global coordination to achieve even coverage of the key space. That is an emergent property of the hash function. The only coordination is local in the form of linking and unlinking nodes into the circular list of nodes on the ring.

Incidentally, if nodes were only ever added and not deleted, low-discrepancy sequences would be a better choice than hashing (such sequences are particularly simple in one dimension). But in the real world, nodes are added and deleted in an unpredictable pattern. Hashing is better able to cope with those conditions; the trade-off is worse discrepancy in the monotone growth case. Using a low-discrepancy sequence would also require new nodes to coordinate with a key manager, though no existing keys need to be redistributed.


Can we prove weak normalization for System F by induction on a transfinite ordinal

In a very silly way, weak normalization for any reasonable system can be proved by induction on a constructive ordinal, provided of course that weak normalization holds. Indeed, the statement that System F has weak normalization is formalizable in arithmetic as a $\Pi^0_2$ sentence, and as such is provable (since it's true) by transfinite induction along a non-natural constructive ordinal-notation of height $\omega^2$. (See this question on the mathematics stack exchange for how this ordering could work.)

However, as jbapple mentions, we don't know of a "natural" ordinal notation that works. We don't even know how to define "natural", but the one above isn't natural (since to see that it's well-founded we'd have to know weak normalization of System F to begin with), whereas the standard ones for $\varepsilon_0$, $\Gamma_0$, and various larger ones using ideas from large cardinal axioms, are natural.

Hopefully one day someone will come up with an ordinal notation for second order arithmetic that everyone will agree is natural, and then that could be used in an honest way to prove weak normalization for System F.


This looks a lot like the I/O API described by Felleisen et al in A Functional I/O System (or Fun for Freshman Kids).  Basically, you write (in the simpler, non-distributed setting), a series of event handlers, each of which accepts the current state, and returns an updated state. Finally, there's a to-draw handler, which produces the "output" for each state.

If we recast this API slightly, we can package up the handlers and the current state together, and each time a handler returns both a new state and a new set of handlers.  We might call this package of state and operations an "object". :)  If we then make the result a pair of this object, and the "output", then we have exactly the type of resumptions.

Interestingly, in the paper, Felleisen et al do exactly this when moving to the distributed setting -- every operation returns a pair of new state and "output" in the form of messages to be sent to the other participants in the system.


Maximum weight matching with classes of edges in a multi-edge bipartite graph

Your problem is closely related to the so-called "Exact red-blue bipartite matching" problem, see for instance http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs.

The case with two colors is unlikely to be NP-hard, since it is known to belong to RNC$^2$.
I think that this randomized result can be translated to your problem.

The case where the number of colors is part of the input is NP-hard,
and this hardness argument easily transfers to your problem.


Submitting other people's work to the arXiv

This should be perfectly acceptable if it is framed as an exposition article. There is a long tradition of expository articles in mathematics (one example that comes to mind is Thurston's exposition of a method developed by Conway to determine if the plane can be tiled by a given shape, see here). Just make sure that the abstract and the introduction convey that all you're doing is to explain Szelepcsényi's proof.


Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise

Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low entropy (there are only two possibilities for $K$). If the eavesdropper stores the first message (which was an encryption of $K$), then she can use it to figure out which of the two candidate values for $K$ is plausible (i.e. is consistent with some short key $K_{RW}$) once she sees the second message.

This problem is essentially unavoidable: taken together, the two messages form an encryption of $M$ (the fact that they were sent separately doesn't affect a passive eavesdropper who sees both). It is easy to show that, using only a short key, one cannot achieve even Russell and Wang's relaxed notion of security in a setting where $M$ has low entropy.

For a lower bound on the key length (as well as further constructions), see Dodis and Smith: https://eprint.iacr.org/2004/219
[Disclaimer: I am an author.]


Automata and a kind of pumping lemma on state transition function

The following argument works as long as $f_w$ is injective. The same ideas should also work for general $f_w$. Indeed, below I show how they give a bound $|w| \leq O(n!)$. However, even further down I show a much better bound, $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$, which is tight up to the constant $2$.

Consider some word $w$ which is the minimal length word resulting in $f_w$, and suppose that the range of $f_w$ is $Q$. We want to show that $|w| \leq n!$.
Let $w_{\leq i}$ denote the prefix of $w$ of length $i$. If $f_{w_{\leq i}} = f_{w_{\leq j}}$ for some $i < j$ then $f_{w_{\leq i} w_{>j}} = f_w$, contradicting the assumption that $w$ has minimal length. We conclude that $f_{w_{\leq i}}$ is different for all $i$. Since the range of $f_w$ is full, all $f_{w_{\leq i}}$ must be permutations of $Q$. Since there are $n!$ permutations of $Q$, we conclude that $|w| \leq n!-1$.

Suppose now that $f_w$ is not injective, and write $w = x_1\ldots x_k$, where each step passing from $x_i$ to $x_{i+1}$ decreases the image. The same argument as before shows that $|x_1| \leq n!$, $|x_2| \leq n!/1!$, $|x_3| \leq n!/2!$, and so on. In total, we get that $|w| \leq n!(1+1+1/2+1/6+\cdots) \leq e n!$.

We can do slightly better. For example, if $f_{x_1}(q_1) = f_{x_2}(q_2)$ then when bounding $x_1$, it is enough to consider permutations up to a permutation of the images of $q_1$ and $q_2$, and so when $k \geq 2$ we can conclude that $|x_1| \leq n!/2$. This argument probably gives $|w| \leq (3/2)n!$. One can probably push the argument further, but that would require looking across the boundaries of the segmentation $w=x_1\ldots x_k$.

The following construction shows that $n!-1$ cannot be replaced by anything smaller than roughly $e^{\sqrt{n\log n}}$. Landau's function $g(n)$ is the maximal order of an element in $S_n$. It is known that $g(n) = e^{(1\pm o(1))\sqrt{n\log n}}$. Given an element $\pi \in S_n$ of maximal order, we can construct an automaton over the one language alphabet $\{a\}$ in which $Q = \{1,\ldots,n\}$ and $f_a = \pi$. The word $a^{g(n)-1}$, which generates the permutation $\pi^{-1}$, cannot be shortened.

Consider again the case of injective $f_w$. We can think of the letters of $w$ as generating a subgroup of $S_n$. Babai and Seress show that the diameter of the corresponding Cayley graph is at most $e^{(1+o(1)) \sqrt{n\log n}}$. This means that every permutation in the subgroup, including $f_w$, can be written as a word over the letters of $w$ and their inverses of length at most $e^{(1+o(1)) \sqrt{n\log n}}$. Since the order of each permutation is at most $e^{(1+o(1))\sqrt{n\log n}}$, we can replace the inverse of each letter by at most $e^{(1+o(1))\sqrt{n\log n}}$ copies of itself, obtaining a word of length $e^{2(1+o(1))\sqrt{n\log n}}$. This bound can perhaps be improved by looking at the construction of Babai and Seress.

In the general case, segment $w=x_1\ldots x_k$ as before, where $k \leq n$. A similar argument shows that $|x_i| \leq e^{2(1+o(1))\sqrt{n\log n}}$, and so $|w| \leq e^{2(1+o(1))\sqrt{n\log n}}$.

This still leaves open the value of the smallest $\ell(n)$ such that the minimal word $w$ with given $f_w$ has length at most $\ell(n)$. Our arguments show that $e^{(1+o(1))\sqrt{n\log n}} \leq \ell(n) \leq e^{2(1+o(1))\sqrt{n\log n}}$, leaving a small gap.


Does polynomially bounded number of witnesses and polynomial time decidability imply polynomial time enumeration?

Yes, you can do this unconditionally in $\mathrm{FP^{NP}}$, which equals $\mathrm{FP}$ by your assumption.

The algorithm is a version of binary search: if the witnesses you want to count are binary strings of length $n^k$, then compute by iteration on $i\le n^k$ the list of all their prefixes of length $i$. This list has polynomial length during the computation since there are only polynomially many witnesses in total, and given a prefix of length $i$, we can check which of its extensions of length $i+1$ are prefixes of a witness by an $\mathrm{NP}$ query.


If $\min(m,n)=1$, the maximum number of edges in a planar bipartite graph with $m$ vertices on one side of the bipartition and $n$ on the other side is $m+n-1$ (just connect them in a star). Otherwise, the maximum number is $2(m+n)-4$.

The upper bound (any bipartite planar graph with $V$ vertices has at most $2V-4$ edges) follows by combining Euler's formula $V-E+F=2$ with the observation that all faces have at least four edges, and each edge belongs to at most two faces, so $E\ge 2F$. Use this inequality to eliminate $F$ from Euler's formula and you get $E\le 2V-4$.

For the lower bound, choose two vertices from the side with $m$ vertices and form a complete bipartite graph $K_{2,n}$ with $2n$ edges. Then, choose one of the quadrilateral faces of this graph and place the remaining $m-2$ vertices into it, connecting each one to both of the vertices of the other color within the same face, adding $2(m-2)$ more edges.

As for the number of distinct maximal planar bipartite graphs on this many vertices, I don't know, but it's certainly some kind of exponential.


Reasons for which a graph may be not $k$ colorable?

You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof system for requiring $k$ colors. The only axiom is $K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of this proof system.


Another edge partitioning problem on cubic graphs

Perhaps I don't understand the question, but the way I interpret it, Colin's answer seems correct. It is enough to find the minimum possible k for which such partition exists, say k_0. (This is a partition with maximum number of K_21's.) There is a partition for any k between k_0 and 3n/2, because splitting K_21 into two K_11's increases the sum of cardinalities by 1. The K_21's in your partition induce a matching in the line graph of G, so this k_0 corresponds to the maximum matching in the line graph, and this matching can be found in polynomial time.


Efficient algorithm for generating data dependency DAG from lists of memory ranges and access modes

Build an interval tree storing all of the ranges that have been written.  That data structure lets you efficiently determine, for any given memory address, the time when it was most recently written.

In particular, scan through the operations in chronological order.  When you see a write operation, update the interval tree.  Also, for each operation (read or write), check the interval tree to find all intervals that overlap it, and add them to the DAG.  This will build up a dependency DAG with no redundancies.

Each update to the tree can be done in $O(\log N)$ time.  Also, the overlap check can be done in $O(k + \log N)$ where $k$ is the number of intervals that overlap for that particular query.

The running time will depend on the size of the resulting dependency graph, but if that graph has $M$ edges, then the total running time will be $O(M + N \log N)$.  In particular, since this DAG can have at most $O(N^2)$ edges, the algorithm certainly runs in $O(N^2)$ time -- and possibly much faster, if the resulting dependency DAG is sparse.


What is the state complexity of the copy language?

The technique described by Yuval:

Do there exists polynomial size CFG that describe this finite language?

(
you may also read:
Lower bounds on the size of CFGs for specific finite languages
)

allows to show very easily an exponential lower bound for CFGs.
Let $G$ a grammar in Chomsky Normal Form for $L_n$.
For every word $w\in \{0,1\}^n$ there exists at least one non-terminal $A(w)$ accepting a subword $s(w)$ of $ww$ having length between $n/2$ and $n$. Let $p(w)$ be a position in $ww$ where this subword occurs. There are at least $n/2$ bits common to all words $w,w'$ such that $A(w)=A(w')$ and $p(w)=p(w')$. Consequently, there can be at most $2^{n/2}$ words that have the same $A(w)$ and $p(w)$. Hence there are at least $2^{\Theta(n)}$ non-terminals.

Furthermore, the PDA can be converted into a CFG in CNF, of polynomial size so this also gives the $2^{\Theta(n)}$ bound on the state complexity of $L_n$.


SAT - Hardness of determining backbone literals

The complexity is co-NP complete because you're converting to unsatisfiability of $F \land \lnot l$. I have a proof of the completeness in my PhD thesis, Claim 2 (if I may blatantly advertise myself).

There's a small problem for unsatisfiable formulas, if your definition of a backbone means that all the literals are backbone for an unsatisfiable formula, then the problem stays in co-NP. If, however, the set of backbone literals is empty for an unsatisfiable formula, you also need NP.


Finding a sub rectangle with maximum sum

In Tadao Takaoka, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, In Electronic Notes in Theoretical Computer Science, Volume 61, 2002, Pages 191-200 you can find a simplified algorithm (the original is by Tamaki and Tokuyama) that runs in sub-cubic time for $m \times n$ arrays:

$$O ( m^2 n (\log \log m / \log m)^{1/2}) $$

From the paper: ... Bentley's algorithm is cubic and the Tamaki-Tokuyama algorithm is sub-cubic for a nearly  square array. Their algorithm is heavily recursive and complicated. We simplify the latter algorithm, and achieve sub-cubic time for any rectangular array ...

They also give a more practical algorithm whose expected time is close to quadratic for a wide range of random data.


Set query in a universe with overlapping sets

One can reverse the roles of elements and sets. This can be seen by considering a Boolean matrix of size $m\times n$ where there are $m$ sets and $n$ is the size of the universe. The $i$th row corresponds to the characteristic vector of the $i$th set. Transposing this matrix reverses the roles of sets and elements ($n$ sets and $m$ elements).

Now the question of whether there exists a set containing two items is the same of asking if two sets intersect (after reversing the roles). In a paper that has recently been accepted to WADS 2015, (arxiv version here. see Theorem 3), we show various tradeoffs for the fully dynamic set intersection problem. Since adding/deleting a set corresponds (after role reversal) to adding/deleting an element to or from a bunch of sets, then in terms of the question in mind the update time would be $S\cdot N^{1-\epsilon}$ and the query time is $N^\epsilon$, where $S$ is the size of the set, $N$ is the sum of the sizes of all of the sets, and $0\leq \epsilon\leq 1$. Notice that different points on this tradeoff curve use a different amount of space, specifically $O(N^{2-2\epsilon})$ words. In particular, for constant query time, the space usage is $O(N^2)$ words and the update time is $O(N)$.

However, for the particular scenario where one is interested in poly log query time, we have a preprint (arxiv version here) that in particular shows that unless the 3SUM conjecture is false, if one is interested in sub-polynomial query time, then the constructing of a static data structure for disjointness queries requires $\Omega(N^{2-o(1)})$ time. This immediately implies a lower bound for the incremental version of the problem, where one is only allowed to add elements to sets. In particular, since the total number of elements in sets, counting multiplicity, is $N$, each element that is being added must spend $\Omega(N^{1-o(1)})$ time.

As such, a (polynomially) more efficient update time does not seem likely, even when allowing poly-log query time.


There is such a c if and only if GI "can be tested to be in polynomial time",

since one can pad with nc isolated vertices.

I don't know of any results on random self reducibility of GI.


I give a rough idea to solve the problem in polynomial time.

In the optimal solution, the flow on each edge is unidirectional.
The final value of each element is not far from the mean. Also $\sum_{i<k}A'_i$, the prefix-sum of the optimal $A'$, is bounded in a range at most $O(n^2)$.
Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum_{i<k}A'_i=R$. Then $T(k,R)$ can be computed from $T(k-1,R')$ for all possible $R'$.

These imply a dynamic programming algorithm with polynomial time complexity.


How do I figure out how to combine simpler quantum gates to create the gate I want?

There are standard ways to approximate any unitary operation with just CNOTs, Hs, and Ts. In the specific case of the Toffoli gate you don't need something so general.

Start with the Toffoli gate:

Use a construction that relies on operations having a square root to cut the worst-case number of controls from 2 to 1:

Use a construction that moves controls off of arbitrary single-qubit operations and onto CNOTs:

Oh hey that looks kinda familiar ;)

Now simplify by sliding gates around so that some of them cancel. Zs can move over controls, but not over NOTs (but can hop over the space between two NOTs that undo each other). It's also useful to know how to move a CNOT over another CNOT's control by introducing a third CNOT. Hadamards cancel when paired, and turn Zs into Xs (and vice versa) when hopping since $HX = ZH$. Anyways, after some fiddling...:

(Note: $T = Z^{1/4}$ and $T^\dagger = Z^{-1/4}$)

You can confirm the circuit works by toying with it in Quirk.

These constructions are explained in more detail in textbooks such as Nielsen and Chuang. The 'moving controls' one is particularly tricky, because you have to find $A$, $B$, $C$ such that $ABC=I$ but $AXBXCe^{i\theta}=U$. Or you can read a few blog posts about making a controlled-by-every-other-wire NOT using $O(n)$ basic gates that also uses these constructions but explains them in more detail.


Formal proof of correctness of Levenshtein distance

As pointed out in a comment above, the answer is yes, in Lean.  See the paper and the code as linked into comments.
I was rather hoping Agda or Idris... but perhaps the Lean formalization is actually constructive.


Inapproximability of set cover: can I assume m=poly(n)?

Yes, the number of sets m in a set-cover instance is polynomial in the number of elements.
By the way -- the state of the art hardness results for Set-Cover are:

With Noga Alon and Muli Safra, we showed how to use the Raz-Safra/Arora-Sudan PCP to get a better constant $c$ in the hardness factor $c\log n$.
http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps

Feige showed how to get the optimal hardness factor $(1-\epsilon)\ln n$, assuming $NP\not\subseteq DTIME(n^{\log\log n})$.
http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf

I recently published a note on how to adapt Feige's reduction to an NP-hardness result (i.e., a result based on $P\neq NP$), assuming a plausible conjecture about PCPs (A conjecture I call "The Projection Games Conjecture" - a specialization of the 1993 "Sliding Scale Conjecture" to projection games).
http://eccc.hpi-web.de/report/2011/112/
(I later found out that the reduction gives an optimal tradeoff between $\epsilon$ and the reduction blow-up).


Computing the existence of a path in a code execution graph

As such, your problem seems to be NP-complete. To see the membership in NP, you can first guess a path, and then check that this path ends with $V_q$ and is valid. For the hardness part, we can directly reduce from the Boolean satisfiability problem (SAT), which itself is NP-hard. The problem SAT takes as input a formula in conjunctive normal form (CNF), and outputs YES if the formula is satisfiable, and NO otherwise. Let $F = C_1 \land \ldots \land C_m$ be a CNF over variables $\{x_1,\ldots,x_n\}$, where each clause $C_i$ is a disjunction of literals. We will construct an instance graph $G_F$ of your problem with distinguished nodes $V_0$ and $V_\top$ such that there exists a valid path from $V_0$ to $V_\top$ if and only if $F$ is satisfiable. For every variable $x_i$, $1 \leq i \leq n$, $G_F$ has a node $V_{x_i}$ and a node $V_{\overline{x_i}}$, and you have one “indicator” $I_{x_i}$, with possible values being $\{\text{TRUE}, \text{FALSE}\}$. The node $V_{x_i}$ assigns $I_{x_i}$ to TRUE (i.e., you have $I_{x_i} := \text{TRUE}$), while the node $V_{\overline{x_i}}$ assigns $I_{x_i}$ to FALSE. Now, we have an (directed) edge between the node $V_0$ and the node $V_{x_1}$, as well as between $V_0$ and $V_{\overline{x_i}}$. For $1 \leq i < n$ we have the edges $(V_{x_i},V_{x_{i+1}})$, $(V_{x_i},V_{\overline{x_{i+1}}})$, $(V_{\overline{x_i}},V_{x_{i+1}})$, and $(V_{\overline{x_i}},V_{\overline{x_{i+1}}})$. For now, a path in the graph simply assigns a Boolean value to each variable, so we now need to construct the part that “checks” that this assignment satisfies $F$. For every clause $C_i$, $1 \leq i \leq m$, we construct a graph gadget $G_{C_i}$ encoding that $C_i$ is satisfied. For instance, suppose that $C_i$ is the clause $x_4 \lor \overline{x_2} \lor x_3$. Then $G_{c_i}$ has an entry node $V_{C_i,x_4}$, and nodes $V_{C_i,\overline{x_2}}$ and $V_{C_i,x_3}$. You have a “switching” edge from $V_{C_i,x_4}$ to the entry node of $G_{C_{i+1}}$ that checks that $I_{x_4} = \text{TRUE}$, and a switching edge from $V_{C_i,x_4}$ to $V_{C_i,\overline{x_2}}$ that checks that $I_{x_4} = \text{FALSE}$, and so on. You then chain these gadgets in series and plug that chain to the already partially constructed graph $G_F$ (that guesses an assignment), and construct the node $V_\top$ in the expected way (I'll leave the missing details), and voilà: there is a path from $V_0$ to $V_\top$ in $G_F$ if and only if $F$ is satisfiable.

Now, the fact that your problem is NP-hard is not necessarily the end of the world, since, as you said yourself, you can still get good results with a simple brute-force strategy. There are two things that you could investigate:

maybe your graphs have a particular structure that actually makes the problem solvable in polynomial time;
if not, you could consider using a SAT solver (such as Glucose), with an encoding similar to this question, for instance. Sometimes this gives really good results and you don't even need to optimize the thing.


There is a simple algorithm for V3.
I'll use the convention that there are $(2n)^3$ possible clauses,
so $2^{8n^3}$ formulas.
(This is just for simplicity - if you don't want all $8n^3$ clauses to be considered valid, it wouldn't affect the following argument.)

Pick a random assignment from $\{0,1\}^n$.
For each of the $7n^3$ possible clauses that are true on this assignment,
include the clause with probability $1/2$.
Each formula $\phi$ will appear with probability proportional to
its number of satisfying assignments.
The $m$-clause variant is similar: pick a set of size $m$
out of the $7n^3$ clauses.


If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$.  (This follows from the definition, in terms of number of accepting paths of an NP verifier.)

This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case you mention, because the function grows faster than $2^{poly(N)}$.  But for the $n$-queens problem as modeled in the paper, this is just an artifact of the authors' decision to let the input value $n$ be encoded in binary.  If the expected input was the unary string $1^n$, then $f(1^n) :=$ (number of valid $n$-queen configurations) would certainly be in #P, by a simple NP verifier that checks validity of a given configuration.

If you want to explore some functions that (conjecturally) lie outside of #P for more interesting reasons, consider e.g. these:

UNSAT:  $f(\psi) := 1$ if $\psi$ is an unsatisfiable Boolean formula, otherwise $f(\psi) := 0$.  This function is not in #P, unless NP = coNP.  It is probably not in the more general counting class GapP, either; that is, UNSAT is probably not the difference f - g of two #P functions.  However, it lies in the more general counting complexity class $P^{\# P}$, which in fact contains the entire Polynomial Hierarchy by Toda's theorem.

You might not like that example because it is not a natural "counting problem".  But the next two will be:

$f(\psi(x, y)) :=$ the number of assignments to $x$ such that the Boolean formula $\psi(x, \cdot)$ is satisfiable for some setting to $y$.
$f(\psi(x, y)) :=$ the number of $x$ such that, for at least half of all $y$, $\psi(x, y) = 1$.

The latter two problems are not known to be efficiently computable even with oracle access to #P. However, they are computable within the so-called "counting hierarchy".  For some more natural problems classified within this class, see e.g. this recent paper.

Counting Nash equilibria is apparently #P-hard, see here.  Also, even problems where the search problem is easy can be #P hard to count, e.g. counting perfect matchings.


What is the minimal extension of FO that captures the class of regular languages?

FO(LFP) captures PTIME on ordered structures, and strings are ordered structures.  So the languages definable by FO(LFP) include all regular languages and much much more.
http://dx.doi.org/10.1016/S0019-9958(86)80029-8

Ebbinghaus and Flum's textbook contains an exercise that asks to show FO(TC^1) (first-order logic extended with transitive closures of binary relations) is equivalent to MSO on strings. In the same exercise, $\{ a^n b^n \mid n \geq 1 \}$ is used as an example to show FO(TC^2) is more expressive than MSO on strings.  All FO(TC) formulas are clearly equivalent to FO(LFP) formulas.


What's the approximation factor of this Max k-Cut approximation?

This is called the edge-contraction heuristic, in which an upper bound $(k-1)/(k+1)$ on the approximation ratio can be shown. See section 3 of the work by Kahruman et al. for reference.
Imagine whenever we combine two nodes u, v into a group, instead of forming a group we contract the edge (u, v) between these two nodes, and updates the weight of all the edges incident to the newly formed node. Repeat the procedure until there are only k nodes left. Lemma 3.1 in the above paper shows that the sum of weights of the first $i$ edges being contracted (denoted as $W_i$) satisfies the following inequality:
$$W_i \leq \frac{2iW}{(n-1)(n-i-1)} \text{,}$$
where $W$ is the sum of weights of all edges.
This can be derived from
$$W_{i+1} \leq W_i + \frac{W-W_i}{({n-i\atop 2})} \text{,}$$
since we always contract the lightest pair, the weight of the contracted edge cannot surpass the average weight.
One can see that the cut formed by this algorithm has weight $W_C = W-W_{n-k}$,
and by observing that $W \geq W^*$ where $W^*$ is the weight of the optimum cut,
we have our desired approximation ratio:
$$W_C \geq W-\frac{2(n-k)W}{(n-1)(k-1)} \geq \frac{k-1}{k+1}W^* \text{.}$$
For k=2, the algorithm gives a 1/3-approximation to the Max cut problem.


Does an infinitely long tape make any difference when proving theorems about Turing Machines?

Yes it makes a huge difference!  A Turing machine with a finite tape is just a finite automaton, which we know are much less powerful.  For example, a TM with a finite tape cannot compute a context free grammar.  All of this is in theory, of course.


Euclidean-squared max-cut in low dimensions

The constant does tend to 1/2 as the dimension increases. In d dimensions, you can have d+1 points at distance one from each other, so the the sum of distance-squared is ${d+1 \choose 2}$ and the maximum cut is at most $(d+1)^2/4$, which is a $\frac 12 \cdot \frac {d+1}{d}$ fraction of the total weight


What is the probability of a virus spreading through a network given a virus source node?

there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference & distinguish between random virus spreading and network- (graph-) based spreading.

Network Forensics: Random Infection vs Spreading Epidemic Milling, Caramanis, Mannor, Shakkottai

  Computer (and human) networks have long had to contend
  with spreading viruses. Effectively controlling or curbing an
  outbreak requires understanding the dynamics of the spread.
  A virus that spreads by taking advantage of physical links
  or user-acquaintance links on a social network can grow explosively
  if it spreads beyond a critical radius. On the other
  hand, random infections (that do not take advantage of network
  structure) have very different propagation characteristics.
  If too many machines (or humans) are infected, network
  structure becomes essentially irrelevant, and the different
  spreading modes appear identical. When can we distinguish
  between mechanics of infection? Further, how can this be
  done efficiently? This paper studies these two questions.
  We provide sufficient conditions for different graph topologies,
  for when it is possible to distinguish between a random
  model of infection and a spreading epidemic model, with
  probability of misclassification going to zero. We further
  provide efficient algorithms that are guaranteed to work in
  different regimes.


I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful difference between “BPP-like”, “RP-like”, or “ZPP-like” randomized polynomial-time algorithms, as we can check the correctness of any purported solution in deterministic polynomial time. Thus, while the class of NP-search problems solvable in probabilistic polynomial time has been studied for a long time, it has not been generally called “Search-BPP”. In particular, the class is mentioned in Papadimitriou’s seminal papers [1,2], where it is denoted FZPP.

[1] Christos Papadimitriou, On inefficient proofs of existence and complexity classes, Annals of Discrete Mathematics 51 (1992), pp. 245–250, doi: 10.1016/S0167-5060(08)70637-X.

[2] Christos Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences 48 (1994), no. 3, pp. 498–532, doi: 10.1016/S0022-0000(05)80063-7.


Complexity of $\{0,\pm1\}$ determinant in sparse cases?

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$.

If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the algebraic complexity of matrix multiplication and the determinant are essentially the same, this comes very close* to showing the exponent of matrix multiplication is 2.

More precisely: given a matrix $M$ as above, embed it as the upper-left corner of an $n^2 \times n^2$ matrix as follows:

$M' = \left(\begin{array}{cc} M & 0 \\ 0 & I_{n^2-n} \end{array}\right)$

Then $M'$ is an $N \times N$ matrix $(N=n^2)$ satisfying your conditions, and $\det M' = \det M$, so if your question had a positive answer then we could compute $\det M' = \det M$ in $O(N) = O(n^2)$ operations.

*-The main differences are: (1) using bit complexity, and (2) restriction to $\{0,1,-1\}$ entries. However, while it is possible, I have little reason to suspect that these restrictions significantly change the complexity of matrix multiplication from $O(n^\omega)$.


A probabilistic set with no false positives?

One answer is to use a big hash table and when it fills up start replacing elements in it rather than finding (nonexistent) empty slots elsewhere for them. You don't get the nice fixed-rate of false answers that you do with Bloom filters, but it's better than nothing. I believe this is standard e.g. in chess software for keeping track of positions that have already been searched.


Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

I would rephrase the question as follows:

  Consider the function $F$ and the family of functions $F_{a,b}$ defined as
  $$F_{a,b}(x) = F(a,b,x) =ax+b.$$
  Can we compute $F_{a,b}$ faster than the complexity of $F$?
  If yes, given $a$ and $b$, can we algorithmically find such an algorithm?

As babou wrote I think the answer depends on your computation model.
Let me explain one case:
Consider polynomial size circuits with unbounded fan-in AND, OR, and NOT gates.
Time is defined as the depth of the circuit.

$F$ is complete for $\mathsf{TC}^0$, so it requires super-constant depth, the best known upper-bound requires roughly depth $\lg n/\lg \lg n$.

If we fix $a,b$ then $F_{a,b}$ is in $\mathsf{AC^0}$ and therefore can be computed by a constant depth circuit.
But the depth is constant only in $n$, not in $a,b$.
Can we obtain a dependence of depth on $a$ and $b$ which is better than the more uniform case? The answer is no.

Another model is algebraic circuits with binary plus and times gates and constants.
$F$ can be computed in depth $2$.
It is easy to see that $F_{a,b}$ cannot be computed in depth $1$.

Now assume a modified algebraic model where we have unbounded fan-in gates.
Now $F_{a,b}$ can be computed in depth $1$ by applying addition on $a$ copies of $x$ and one copy of $b$ in one step. $F$ still requires depth $2$.


this ref covers it.

  In sections 5 & 6 we use the elliptic integral to express the probability, less than one, that certain biased random walks return to the origin. The probability of a return to the origin for these walks can then be computed accurately and easily using Gauss' arithmetic-geometric mean (AGM) method to evaluate the elliptic integral.

[1] Recurrence of Simple Random Walk in the Plane
Terence R. Shore and Douglas B. Tyler
The American Mathematical Monthly
Vol. 100, No. 2 (Feb., 1993), pp. 144-149


Bounding the gap between quantum and deterministic query complexity

As far as I know, the general bounds you state are essentially the best known. Changing the model slightly, Midrijanis has shown the bound that $D(f) = O(Q_E(f))^3$, where $Q_E(f)$ is the exact quantum query complexity of $f$; there are also tighter bounds known in terms of one-sided error (see Section 6 of this paper).

In terms of more specific, but still general, classes of functions, there is a paper of Barnum and Saks which shows that all read-once functions on $n$ variables have quantum query complexity $\Omega(\sqrt{n})$.

Although this progress has been limited, there has been considerable progress in lower bounding the quantum query complexity of specific functions; see this review for details (or e.g. the more recent paper of Reichardt, which proves that the most general version of the ''adversary'' bound characterises quantum query complexity).


Poly-time Algorithm for Non-Linear Optimization

In general, even approximating a global optimum of a quadratic program, the simplest case of a nonlinear program, is NP-Hard (http://web.cs.ucdavis.edu/~rogaway/papers/qp.pdf), not to mention finding an exact solution of it (http://www.sciencedirect.com/science/article/pii/002001909090100C).

The polynomial-time solvability of a nonlinear program depends on its convexity, which means that your matrix $Q\in R^{n\times n}$ should be positive semidefinite (i.e. $\forall x\in R^n,\,x^TQx\geq 0$). An easy way to check this in polynomial time is to check the sign of the smallest eigenvalue of $Q$. In the case of a convex quadratic program, you can simply deploy an interior-point algorithm for quadratic programming, which has a poly-time worst case complexity.  These facts can be generalized for nonlinear programming.

As @Austin pointed, there's a way to convert your program to a Quadratically Constrained Quadratic Form. These problems are NP-Hard in general, but you can achieve an $\frac{4}{7}-$approximation of it's solution using an algorithm by Yinyu Ye, which solves an SDP-relaxation of the program.


A nice book on this topic: "Optimization Methods for Logical Inference", V. Chandru, John N. Hooker, Wiley, 1999