Almost-P and related definitions I'm pretty sure this has a trivial answer but it's always faster to ask the community :-)

I understand that, relative to a random oracle, P=BPP. But this is sometimes phrased via the shorthand "Almost-P=BPP", which I find rather confusing.

Complexity zoo defines Almost-P as "The class of problems that are in $P^A$ with probability 1, where A is an oracle chosen uniformly at random."

Logically, L belonging to Almost-P would then mean that: With probability 1 over a random instantiation of an oracle tape A, there is a polynomial time Turing machine T(A) that decides L.

Now, the poor BPP machine trying to decide L would have no idea which T(A) to simulate. The choice of T(A) may wildly vary depending on A.

Should Almost-P (similarly, Almost-anything) be rather defined as the set of languages L for which there is a polynomial time Turing machine T with an oracle tape such that, with probability 1 over the instantiation of the oracle tape, the language decided by T ends up being L?

Under neither of the above definitions does the statement BPP=Almost-P seems to be logically equivalent to "relative to a random oracle A, $P^A=BPP^A$".

My question is now, what is the precise definition of the class Almost-P (or, for that matter, Almost-anything)? And/or, what am I missing above?

The question seems to be predicated on a misunderstanding: the statements “relative to a random oracle $A$, $\mathrm{P}^A=\mathrm{BPP}^A$” and “$\mathrm{Almost\text-P}=\mathrm{BPP}$” are not meant to be rephrasings of each other. The complexity zoo refers to a paper of Bennett and Gill, which proves the former statement (and many other things) in detail, but it also separately claims the second statement (though they do not use the $\mathrm{Almost\text-P}$ notation, and do not really give a proof).

The definition of $\mathrm{Almost\text-P}$ in the zoo is correct.

The proof of $\mathrm{Almost\text-P\subseteq BPP}$ goes as follows. Let $L\in\mathrm{Almost\text-P}$. Since there are only countably many Turing machines, there exists an oracle polynomial-time Turing machine $M$ such that $M^A$ computes $L$ with positive probability $\epsilon>0$. Using the Lebesgue density theorem, there exists a finite oracle prefix $A_0$ such that relative to random oracles $A$ that extend $A_0$, $M^A$ computes $L$ with probability $\ge3/4$. We can hardwire $A_0$ into the Turing machine, and simulate access to the rest of the oracle by random coin flips to obtain a randomized poly-time machine for $L$ with probability of success $\ge3/4$. Thus, $L\in\mathrm{BPP}$.


Complexity Class NEXP$^\text{NP}$ I have a problem which is in NEXP$^{\text{NP}}$ and can also be solved by an alternating TM using exponential time and just one alternation (starting in an existential state).

Is there anything known about NEXP$^{\text{NP}}$? Is it equal to NEXP or some other class? Are there complete problems other than the generic one (given an NEXP$^{\text{NP}}$ machine and a word, does it accept?).

A natural $\text{NEXP}^{\text{NP}}$-complete problem is deciding a sentence of Presburger arithmetic with an $\exists^*\forall^*\exists^*$-quantifier prefix (as shown here). Further complete problems related to database theory have been studied here.


Does a given regular language contain an infinite prefix-free subset? A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other.

The question is:

What is the complexity of checking whether a regular language given as an NFA contains an infinite prefix-free subset?

Answer (due to Mikhail Rudoy, here below): It can be done in polynomial time, and I think in even in NL.

Paraphrasing Mikhail's answer, let $(\Sigma,q_0,F,\delta)$ be the input NFA in the normal form (no epsilon transitions, trim), and let $L[p,r]$ (resp. $L[p,R]$) be the language obtained by having state $p$ as initial state and $\{r\}$ as final state (resp. state $p$ as inital and the set $R$ as final). For a word $u$ let $u^\omega$ be the infinite word obtained by iterating $u$.

The following are equivalent:

The language $L[q_0,F]$ contains an infinite prefix-free subset.
$\exists q \in Q$, $\exists u \in L[q,q]\smallsetminus\{\varepsilon\}$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.
$\exists q \in Q$ $L[q,q] \neq \{\varepsilon\}$ $\forall u \in L[q,q]$ $\exists v \in L[q,F]$ so that $v$ is not a prefix of $u^\omega$.

Proof:

3$\Rightarrow$2 trivial.

For 2$\Rightarrow$1, it suffices to see that for any $w \in L[q_0,q]$ we have that $w (u^{|v|})^* v$ is an infinite prefix-free subset of $L[q_0,F]$.

Finally, 1$\Rightarrow$3 is the "correctness" proof in Mikhail's answer.

Your problem can be solved in polynomial time.

To begin, convert the given NFA to an equivalent NFA with the following additional properties:

There are no epsilon transitions
All states are reachable from the start state

Helpful subroutine

Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate the truth value of the following statement: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$." Furthermore, this subroutine will run in polynomial time.

First, construct the NFA $S$ with $|s| + 1$ states which accepts all strings that are not prefixes of $s^n$ for any $n$ ($|s|$ non-accept states in a loop to keep track of where in the "pattern" of $sssss\ldots$ we are so far, and one accept state for if we have already deviated from that pattern). Next, construct the NFA $N'$ which is exactly like $N$ but has $q$ as its start state. Finally, construct a final NFA $N''$ whose language $L(N'')$ is $L(S) \cap L(N')$ using the standard NFA intersection construction. Note that all of these constructions are polynomial in the size of the input.

Then simply test whether the language of $N''$ is empty (which can be done in polynomial time with a simple graph search). $L(N'') = \emptyset$ if and only if $L(S) \cap L(N') = \emptyset$, or in other words every string in $L(N')$ is not in $L(S)$. In other words, the language of $N''$ is empty if and only if $N'$ accepts only strings that are prefixes of $s^n$ for some $n$. This can be rephrased as exactly the statement we were trying to evaluate: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$."

Main algorithm

Consider the set of states in the NFA that are in some loop. For each such state, $q$, do the following:

Let $P_2$ be any simple loop containing $q$. Let $s$ be the string corresponding to loop $P_2$. Since the NFA has no epsilon transitions, $s$ is not empty. Then apply the subroutine to the NFA, state $q$, and string $s$. If the subroutine tells us that every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ then continue to the next state $q$. Otherwise, output that the given NFA's language contains an infinite prefex-free subset.

If we try every state $q$ that is in a loop and the algorithm never outputs, then output that the given NFA's language does not contain an infinite prefex-free subset.

Correctness (first half)

First, suppose that the above algorithm asserts that the given NFA's language contains an infinite prefex-free subset. Let's say that this output was selected while considering some loop $P_2$ and some state $q$. As before, $s$ is the string corresponding to $P_2$. Then we know according to the subroutine that not every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ (as this is the only output of the subroutine that would lead to the main algorithm outputting at that $q$).

Let $P_3$ be a path whose existence is asserted by the subroutine: a path from $q$ to an accept state such that the corresponding string $t$ is not a prefix of $s^n$ for any $n$.

Let $P_2'$ consist of $m$ copies of $P_2$ where $m$ is sufficiently large that $m|s| > |t|$. Since $P_2$ is a loop through $q$, $P_2'$ can be treated as a path from $q$ to $q$. The string corresponding to $P_2'$ is $s^m$

Let $P_1$ be a path from the start state to $q$ (which exists since every state is reachable from the start) and let $r$ be the string corresponding to this path.

Then the path consisting of $P_1$, $x$ copies of $P_2'$, and $P_3$ is an accepting computation path. The string corresponding to this path is $r(s^m)^xt$. Thus, the NFA accepts every string of the form $r(s^m)^xt$. This is an infinite set of strings accepted by the NFA, and I claim that this set of strings is prefix-free. In particular, suppose $r(s^m)^xt$ is a prefix of $r(s^m)^yt$ with $y > x$. In other words, $t$ is a prefix of $(s^m)^{y-x}t$. Since $(s^m)^{y-x}$ has length $m(y-x)|s| \ge m|s| > |t|$, this implies that $t$ is a prefix of $(s^m)^{y-x} = s^{m(y-x)}$. But we know by the output of the subroutine that $t$ is not a prefix of $s^n$ for any $n$. Thus, $r(s^m)^xt$ cannot be a prefix of $r(s^m)^yt$, and as desired the set of strings is prefix-free.

Thus, I have shown that if the main algorithm outputs that the given NFA's language contains an infinite prefex-free subset then this is in fact the case.

Correctness (second half)

Next, I will show the other half: if the given NFA's language contains an infinite prefex-free subset then the main algorithm will output this fact.

Suppose the given NFA's language contains an infinite prefix-free subset. Let $A$ be the set of (accepting) computation paths corresponding to these strings. Notice that $A$ is an infinite set of accepting computation paths whose corresponding strings are never prefixes of each other.

Say that a state is "looping" in the NFA if there exists a loop in the NFA through that state and "non-looping" otherwise. Consider all paths from the start state to any looping state which pass through only non-looping states (except for the one looping state where they end up). Let $P$ be the set of these paths. Each path $p \in P$ cannot have a loop as then the states in that loop would be looping states and so $p$ would pass through a looping state. Thus, the lengths of paths in $P$ are bounded above by the number of states in the NFA and so $P$ is finite (for example, if the start state is a looping state then the only such path is the empty path).

We can partition $A$ into $|P|+1$ subsets based on how that computation paths in $A$ starts. In particular, for $p \in P$, let $A_p$ be the set of all computation paths in $A$ that start with path $p$ and let $B$ be the set of all other paths in $A$. Clearly, all $A_p$s and $B$ are disjoint and their union is the entire set $A$. Furthermore, $B$ contains only paths that never pass through a looping state, and therefore never loop; thus $B$ is finite. We can conclude then that some $A_p$ must be infinite (otherwise $A$ would be a union of finitely many finite sets).

Since $A_p$ is infinite, there are infinitely many computation paths, none of whose strings are prefixes of each other, that are accepting paths starting with $p$. Let $q$ be the state reached at the end of path $p$. We can conclude that there are infinitely many accepting paths, call this set $A'$, starting at $q$ all of which correspond to strings that are not prefixes of each other.

During the main algorithm, we run the subroutine on state $q$ and some string $s$. This subroutine tells us whether every accepting path starting at $q$ corresponds to a string that is a prefix of $s^n$ for some $n$. If this were the case, then all the infinitely many accepting paths in $A'$ would be prefixes of $s^n$ for various $n$, which would imply that they are all prefixes of each other. This is not the case, so we conclude that when the main algorithm runs the subroutine on state $q$, the result is the other possible outcome. This, however, leads the main algorithm to output that the NFA's language contains an infinite prefix-free subset.

This concludes the proof of correctness.


Bounds on sum of squares of node degrees in undirected graphs Admittedly, this is less of a research-y question (and admittedly, a little non-algorithmic trivial question), but I am hoping to get some meaningful answer.

Given an undirected graph $G = (V, E)$, with $n = |V|$ vertices and $m = |E|$ edges, what is a good upper bound on $\sum_{v \in V} \deg^2(v)$ in terms of $m$ and $n$.

Two obvious upper bounds are $O(n^3)$ and $O(m^2)$, which are quite weak for extremely sparse and extremely dense graphs respectively. Is there any reference to find a non-trivial (asymptotic) bound? For example, can we bound it as $O(m^\alpha n^\beta)$ for some $\alpha < 2$ and $\beta < 3$?

It's $\Theta(m^2)$ for multigraphs (consider a graph with $m$ edges between the same pair of nodes and all other nodes isolated) and $\Theta(mn)$ for simple graphs (the sum of squared degrees equals the number of directed two-edge walks; each edge can be continued to form a two-edge walk in $O(n)$ ways; consider $K_{m/n,n}$).


What do you call the join of two optimization problems? I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with objective function $m_{\max}$. I am studying what I would like to call the "join" or "direct sum" of these two problems, the problem of maximizing $m_{\max}(x, w) - m_{\min}(x, w)$, though I don't know the correct name for such a problem. In my particular case, each problem on its own has a trivial algorithm that produces optimal solutions, but together, the problem is intractable. Has the structural complexity or approximability of optimization problems of this form been studied in a general way?

(The fact that one is a maximization problem and one is a minimization problem is not crucial here, they could both be the same type of optimization.)

I think this falls in the category of multi-objective function optimization problems.

To be specific, it's a linear scalarization of an optimization problem with two objective functions.

I don't know this field very well, but I expect their complexity has been studied.


Separating words with random DFAs One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$.  I am curious if there any results about the ability of a random DFA to separate two given (nonrandom) strings.

Clearly a random DFA with sufficiently many states separates strings with high probability.  Specifically, if $u,v \in \Sigma^n$, a random DFA with $O(n)$ states is unlikely to ever revisit the same state once it reaches the first place where $u$ and $v$ differ, and therefore separates $u$ and $v$.

Can we do better?  Ideally, what is the smallest $f(n)$ s.t. that a random DFA with $f(n)$ states separates strings of length $n$ with positive probability (or perhaps probability $\ge 1/2$)?  A brief search didn't turn up many results on the properties of random DFAs; all I could find was http://arxiv.org/abs/1311.6830.

[Edit: this answer does not work, see comments.]

This is just an informal idea and I don't know if it helps, but it's too long to be given as a comment. Also, I am not at all familiar with random DFAs, so maybe I have a wrong intuition of how you should reason about probabilities on them, but hopefully this is not entirely worthless.

I will suppose that your bounds should depend on how much $u$ and $v$ differ; if they don't, it seems clear to me that the worst case are strings differing only by their first character (strings differing at a set $X$ of positions have more chances of being told apart than strings differing at a set $Y \subset X$ of positions, I'd say, and putting the difference as early as possible gives you opportunity to resynchronize).

I will also look at the probability that the words are distinguished, namely, they reach different states. I guess you would then need to adapt for being accepted or rejected based on how your random DFAs allocate final states. If each state has a probability 1/2 of being final, then when the strings end up at the same state they are not distinguished, and when they end up at different states they have probability 1/2 of being distinguished.

Now I will consider the word $w$ obtained from $u$ and $v$ as follows: $w_i = 1$ if $u_i = v_i$, and $w_i = 0$ otherwise. I think it is clear that $w$ is the only interesting thing to consider about $u$ and $v$.

Now, define $p(i)$ the probability that we are at the same state after reading prefixes of length $i$ of $u$ and $v$, and $q(i) = 1 - p(i)$ the probability that we aren't.

I think we have $p(i+1) = p(i) + q(i)/n$ when $w_{i+1}$ is $1$. Intuitively, we are at the same state after reading $i+1$ letters either when we were at the same state after reading $i$, or when we were at two different (random) states, we drew two transitions to random states, and they happened to be the same one. Likewise, we have $p(i+1) = 1/n$ when $w_{i+1}$ is $0$: you are drawing two random states, no matter where you started from.

From this I think you could compute the probability of being at the same state after reading $u$ and $v$.


Estimator for sum of independent and identically distributed (iid) variables This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.

Consider the Chernoff bound described in Theorem 1 of this paper:

  Theorem 1. Let $X_1,\ldots,X_n$ be discrete, independent random variables such that $E[X_i] = 0$ and $|X_i|<1$ for all $i$. Let $X:=\sum_{i=1}^n X_i$ and $\sigma^2$ be the variance of $X$. Then,
  $$\Pr\left[|X|\ge \lambda\sigma\right] \le 2e^{-\lambda^2/4}$$
  for any $0\le\lambda\le 2\sigma$.

I want to apply this estimator for a computation, but the variance of the variables $X_i$ is unknown to me. Apart from that, my variables satisfy all the conditions of Theorem 1. In fact, my variables are independent and identically distributed (iid).

On the other hand, there is Chebyshev's inequality for finite samples which does not require knowledge of the variance (or mean) of a given random variable and replaces it with the corresponding values of my given sample.
 However, the estimator is not good enough for my application and I was wondering if there is an estimator similar to Theorem 1 but not featuring the variance of the distribution itself.

Intuitively speaking, it would be nice to have the best of both worlds: If that is not possible, then what is the best bound I can achieve for a sum of iid variables, without any knowledge about their variance?

Edit. I will explain the application in greater detail. I have a tree, at its leaves $v$ are labels $\ell(v)$ with values from the interval $[-1,1]$. I want to know whether these values sum to zero, but summing them up would take too long, because there are too many of them. However, I can easily do a random walk from the root to a leaf. Viewing the tree as a decision tree this way, let $p(v)$ be the probability of each leaf $v$. I then sample a couple of leaves $v_1,\ldots,v_n$ and compute the values $\tfrac{\ell(v_i)}{P\cdot p(v_i)}$, where $P$ is an upper bound for $\tfrac{1}{p(v)}$. Under the null hypthesis that the leaf lables sum to zero, the expected value of a random variable sampling this fraction is
$$\sum_v p(v) \cdot \frac{\ell(v)}{Pp(v)} = \frac{1}{P} \sum_v \ell(v) = 0.$$
Hence, I am in the situation of Theorem 1. I compute
$$t=\sum_{i=1}^n \frac{\ell(v_i)}{P\cdot p(v_i)\cdot\sigma}$$
and by Theorem 1, $2e^{-t^2/4}$ is an upper bound for the probability that this sample was obtained under the assumption of the null hypothesis. Now, this works very well for small test instances when I compute $\sigma$ - which actually requires me to search the entire tree. For larger instances, that's exactly what I am trying to avoid, so I need something different. It would be less of a problem to use the mean or the standard deviation of my sample, for instance.

Note that
$$\textstyle
\sigma^2 = E(X^2)- E(X)^2 = E(X^2) = E(\sum_{i=1}^n X_i^2) + E(\sum_{i\ne j} X_i X_j).$$
Since $X_i$ and $X_j$ are independent, this means $\sigma^2 = n E(X_1^2)$. In my application, the expected value of $X_1^2$ is so small that reasonably large sample sizes cannot negate the effect that $\sigma^2$ is very small.

You need McDiarmid's inequality, or in particular the Hoeffding inequality, which is a simplification:

Given $n$ independent $X_i$ with the property that $X_i \in [a_i, b_i]$, and $X = (1/n)\sum X_i$, then

$$ \text{Pr}(|X - EX| \ge t) \le 2 \exp(\frac{2t^2n^2}{\sum (b_i - a_i)^2}) $$


Linear diophantine equation in non-negative integers There's only very little information I can find on the NP-complete problem of solving linear diophantine equation in non-negative integers. That is to say, is there a solution in non-negative $x_1,x_2, ... , x_n$ to the equation $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$, where all the constants are positive? The only noteworthy mention of this problem that I know of is in Schrijver's Theory of Linear and Integer Programming. And even then, it's a rather terse discussion.

So I would greatly appreciate any information or reference you could provide on this problem.

There are two questions I mostly care about:

Is it strongly NP-Complete?
Is the related problem of counting the number of solutions #P-hard, or even #P-complete?

I am not an expert on this at all, but I would like to get a constructive discussion started. Here is an attempt, based on the math.stackexchange.com question Count the number of positive solutions for a linear diophantine equation. The stuff is related to Erhart polynomials, which I know nothing about, and I think also to @SashoNikolov's comments above.

Define $N(a_1, a_2, \ldots, a_n; b)$ to be the number of non-negative solutions of the Diophantine equation
$$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$$
where coefficients $a_i$ are positive and $b$ is non-negative. If I am getting my recursions right, then we have
$$N(a_1; b) = \begin{cases}
1 & \text{if $a_1 \mid b$} \\\\
0 & \text{otherwise}
\end{cases}$$
and
$$N(a_1, \ldots, a_{n+1}; b) =
\sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)
$$
Now, the sum is a bit long (measured in terms of the length of the input), but we might hope to find a better way of computing it than to actually run through all the $k$'s. We know it's going to be a polynomial in $b$, but I do not see how to compute the polynomial fast enough.


Is it possible to design an efficient approximation algorithm for one NP-complete problem based on Shor's algorithm? Is it possible to design an efficient approximation algorithm for an $\sf{NP\text{-}complete}$ problem based on reductions from Shor's algorithm?

Are known any (classical) approximation algorithms for an $\sf{NP\text{-}complete}$ problem that uses Factoring as oracle?

There are ways to see that either the answer is probably no, or that the question means more than one thing and has a negotiable answer.   On the one hand, the PCP theorem says that many, but not all, NP-hard problems are still NP-hard to approximate.   The standard belief is that Grover's search algorithm, which gives you a quadratic speedup but no more than that, is the best quantum algorithm for the hardest NP-hard problems.  This leaves fairly little wiggle room to expect any quantum algorithm to have any special relation to approximation to NP-hard problems in general.

Some NP-hard problems are easier to approximate than the ones amenable to the PCP theorem.   However, the difficulty of approximation is then highly variable.

Meanwhile Shor's algorithm does something very specific:   It finds the period of a periodic function on the integers or on $\mathbb{Z}^n$.   This problem is also in the complexity class SZK, for example.   Maybe you could cook up an approximation problem to an NP-hard problem that lands you in SZK or period-finding, but I suspect that there aren't any known, natural examples of that.


Applications of Takens' theorem to TCS? My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to blame).

If I understood correctly the Wikipedia page on Takens' theorem, and some discussions I had with people in applied (physics-related) fields that mentioned it to me, Taken's theorem essentially states that

  if one has a system parameterized by a state (time-dependent) $x(t)\in\mathbb{R}^d$, then under some natural assumptions on $x$ (in particular, smooth enough) there exists $k$—related to the underlying dimension of the manifold on which $x$ "lives— and some "lag" $\tau$ such that
  $$
y(t) \stackrel{\rm def}{=} (x_1(t), x_1(t+\tau),\dots,x_1(t+(k-1) \tau)\in\mathbb{R}^k
$$
  is information-theoretically equivalent to the original parameterization $x$; and moreover, this new parameterization, now living in a "shadow manifold," preserves the topology of the original manifold.

(All imprecisions above definitely mine, I cannot claim I fully understand the theorem.)

This does strike me as a very useful tool, similar in spirit to some type of dimension reduction:

bringing in domain-specific knowledge (to figure out $\tau$ and $k$, although apparently there have been recently methods designed to find these in a more automated way)
allowing easy measuring (no need to perform a computationally heavy mapping for the change of parameters: instead, focusing in a single lagged coordinate of the data is enough)

My question is: has this theorem, or some version of it, been applied or explored in the context of computational learning? If so, where can I find references of it? If not, is there a reason why—e.g., "it does not apply in the usual settings we consider because [...]"?

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

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

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

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


NP-hardness of minimum distance over a code There happens to be this NP-complete question,

Minimum-Distance-Over-$\mathbb{F}_{2^m}$

Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in \mathbb{F}_{2^m}^n$ of weight $\leq w$ s.t $Hx=0$?

Is there some "easy" proof of this? (as opposed to say what I can partly fish out of this paper, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=641542)
Is there any variant of it where the hardness is true even if I assume that $H$ has at least $r$ linearly independent columns? (and such a condition gets automatically satisfied if the rows of $H$ define a code?)

Berlekamp, McEliece and Van Tilborg
[On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)]
proved that deciding if a binary code contains a code word of weight $w$ is NP-complete. In http://statweb.stanford.edu/~cgates/PERSI/papers/85_04_radon.pdf
Diaconis and Graham prove that deciding if a binary code of length $2m$ contains a code word of weight $n$ is NP-complete.


Hardness when restricted to an infinite number of far apart instance sizes Is there a result that rules out (under common complexity theoretic assumptions) that one can solve an NP-hard problem in polynomial time for an infinite number of possibly very far apart instance sizes? To be precise, I have an infinite ascending sequence of numbers $n_1, n_2, n_3, \dots$ and want to show that one cannot solve the NP-hard problem in polynomial time when restricted to inputs of sizes $n_i$.
A naive idea to prove the statement would be to take an instance of size $n$, "pad" it to the next largest value $n_i$ and solve it in $n_i^{O(1)}$. However, this creates no contradiction, because it could be that the $n_i$ are spaced so far apart that the next largest $n_i$ is exponential in $n$.
It appears to me that this question is not related to Mahaney's theorem, since for a given $n_i$ we allow all instances of size $n_i$, not just a sparse subset.
I am not fixed on the classes P and NP. A similar hardness result for other classes would also be highly appreciated.

The algorithmic problem is to tell if two finite groups (given by their multiplication tables) are isomorphic.
It is not known if this can be solved in polynomial time in the cardinality of the group. But for groups of prime order this can be solved in constant time.


Interesting real life problem similar to subsetsum /bin packing problem I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :

I have large number of cable reels/drums (let's say in the order of 10,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.

I have to cut a large number of cables of different lengths (that randomly varies from 10 meter to 1000 meter).

I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total drums used for the whole allocation (b) Maximize the length of waste cables (e.g. instead of wasting two 10 meter cable, when absolutely necessary, I would try to waste one 20 meter) to increase the chance of re-usability.

I have used a dynamic algorithm (similar to solving a subset sum problem) to find the best fit for a specific cable reel/drum and get a fairly good solution.

However, this is not the most optimum solution for the following reasons :

(1) I don't know at the beginning which drum to take first for the allocation. The sequence at which I start allocation vastly affects the overall wastage.

(2) When there are multiple perfect combinations possible for zero wastage for a particular drum, choosing right combination from that for a overall optimization is my challenge.

(3) I end up making zero wastage for a drum, where I should actually keep some deliberate wastage to use up some specific cable, that will lead me to a over all minimized wastage. That means, making zero wastage for a drum is not necessarily the best solution, (especially when the cable lengths are in the order between 300 to 800 meter)

Can anybody please guide me with some ways to improve the situation.

Your problem is at least as hard as bin-packing.  In particular, optimizing objective (a) basically is the bin-packing problem (in particular, bin packing is the special case where all drums have equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete.  Consequently, your problem is NP-hard, too.  All the usual hardness results about bin packing apply to your problem as well: there is no polynomial-time approximation scheme (unless P=NP); and bin packing is known to be strongly NP-complete, so there is no hope for a pseudo-polynomial time solution, either.

If you want a pragmatic approach to solve this in practice, or at least get as good a solution as possible, I would recommend formulating it as an instance of integer linear programming (ILP) and applying an off-the-shelf ILP solver.  In particular, you can formulate the problem of minimizing objective (a) as an ILP instance, in the same way as for bin-packing.  Then, off-the-shelf ILP solvers might be effective: even if they don't find the optimal solution, they typically have a way to output the best solution found after a certain amount of computation time, and that might be pretty close to optimal.  Of course, it is not a silver bullet; in the worst case it might take exponential time.  There's no way to know in advance whether it will work well enough.  The only way to tell is to try it and see.

Objective (b) amounts to maximizing a sum-of-squares objective function (per your comment).  This can't be expressed using integer linear programming, but it can be expressed as an instance of quadratic integer linear programming.  You could try formulating it as an instance of mixed-integer quadratic programming (MIQP) and then applying an off-the-shelf MIQP solver.  However, MIQP is substantially harder than ILP, so I don't know whether it will work well on problem instances of the size you have.


Are there non-closed complexity classes for which there are complete problems? Is saying that a class is non closed analogous to stating there are complete problems that have not been identified for that class under a certain type of reduction?

I assume that you are asking about the relation between a complexity class having a complete problem under a certain notion of reducibility and the same complexity class being closed under the same notion of reducibility.  It is a common misunderstanding that these two notions are related.  They are not!

For example, SAT is an NP-complete problem under polynomial-time Turing reducibility.  But NP is not closed under polynomial-time Turing reducibility unless, say, NP=coNP.  On the other hand, PH is closed under polynomial-time Turing reducibility, but PH does not have a complete problem unless the polynomial hierarchy collapses to a finite level.

This is not to say that complete problems and the closure property are unrelated.  For example, consider the equivalence that P=NP if and only if SAT∈P.  One explanation for this equivalence is that it holds because SAT is NP-complete under polynomial-time Turing reducibility and P (not NP!) is closed under the same notion of reducibility.  Of course, this is a little contrived explanation for this equivalence because we do not have to use Turing reducibility and we can use many-one reducibility instead, under which both P and NP are closed.  But when we consider classes of relation problems such as FP and FNP and consider polynomial-time function reducibility, then we have to be careful about which class is closed and which class is not, because FNP is not necessarily closed under polynomial-time function reducibility.  Still, the notion of FNP-complete problems is useful because FP is closed under polynomial-time function reducibility.


1-way Quantum Finite Automata Example Question I'm attempting to clarify my understanding in the example presented in Section 2.2 of 1-way Quantum Finite Automata: Strengths Weaknesses and Generalizations (this alternative link may also be useful). This example provides a very stripped down example of a 1-QFA with the following transition rules:

$V_a|q_0\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle + \frac{1}{\sqrt 2}|q_{rej}\rangle$,

$V_a|q_1\rangle = \frac{1}{2}|q_0\rangle + \frac{1}{2}|q_1\rangle - \frac{1}{\sqrt 2}|q_{rej}\rangle$,

$V_{\$}|q_0\rangle = |q_{rej}\rangle$,

$V_{\$}|q_1\rangle = |q_{acc}\rangle$

For instance, if I'm in $q_0$ and I process an $a$ as input, I apply the first rule. My understanding is that I would have a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of staying in state $|q_0\rangle$, a $||\frac{1}{2}||^2 = \frac{1}{4}$ chance of progressing to state $|q_1\rangle$ and a $||\frac{1}{\sqrt 2}||^2 = \frac{1}{2}$ chance of ending the computation and rejecting the string.

I would imagine the automata for this to look like the following image

I'm not entirely sure if that is correct however. The probabilities mentioned in the paper for acceptance of the string $aa$ is $\frac{1}{4}$ while the probability of rejection is $\frac{3}{4}$. Just wondering if someone could either point out a flaw or validate what I have conceptually in mind for the example.

Thanks.

Reworked automata model to more accurately reflect the probabilities:

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really meaningful to compute the amplitudes of the state to be measured over $|q_{0}⟩$ and $|q_{1}⟩$ and to put them on the diagram, for the automata does neot measure the projectors $|q_{0}⟩\langle q_{0}|$, and $|q_{1}⟩\langle q_{1}|$. In other words, this numbers do not represent probabilities, they do not correspond to outcomes of the measurement to be performed. Therefore, labeling the arrows of the diagram with this numbers would give a potentially-misleading illustration of how the measurement process is working.

Although I might say things you already know, let us elaborate on the topic a bit to clarify the meaning of the transition diagrams you depicted. It is important to highlight that after reading a symbol $a$ and applying $V_a$, the automata does not perform a measurement in the standard computational basis: $$\{|q_0⟩,|q_1⟩,|q_{acc}⟩,|q_{rej}⟩\}$$ Instead, the automata measures this complete set of orthogonal projectors:

$P_{acc}=|q_{acc}⟩\langle q_{acc}|$
$P_{rej}=|q_{rej}⟩\langle q_{rej}|$
$P_{non}= |q_{0}⟩\langle q_{0}|+|q_{1}⟩\langle q_{1}|$

In other words, the measurement has three possible outcomes: (acc) the automata measures an accepting state and halts; (rej) the automata measures a rejecting state and halts; (non) the automate measures something else, does not halt, and reads next symbol (non states for non-halting).

Now, this is a problem I see in your diagrams: if you had a state $(|q_{0}⟩+|q_{1}⟩)/2$ before some measurement, and you happened to obtain the outcome (non), the state would remain invariant after the measurement (just apply $P_{non}$ and check). Therefore, depicting the probability of transition to either $|q_{0}⟩$ or $|q_{1}⟩$ creates confusion.

Taking all said into account it is easy to follow the calculation given in your main reference. In order to illustrate everything said, and, for completeness, I will quote it with here with some minor comments (though I added some modifications, I do not know whether this type of quoting is acceptable;  if its is not, please, let me know or edit the answer yourself):

  The automaton starts in $|q_0\rangle$.

  Read "a".  $V_a$ is applied,
  giving $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle+
\frac{1}{\sqrt{2}} |q_{rej}\rangle$.
  This is observed. Two outcomes are possible. With probability
  $(1/\sqrt{2})^2=1/2$, a rejecting state is observed.
  Then, the superposition collapses to $|q_{rej}\rangle$,
  the word is rejected and the computation terminates.
  Otherwise (with probability $1/2$), a non-halting state is observed and the
  superposition collapses to $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$.
  In this case, the computation continues.
  Read "a" again. A simple computation (we leave the details out)
  shows that $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$ is mapped
  to itself by $V_a$.
  After that, a non-halting state is observed. (There are no
  accepting or rejecting states in this superposition.)
  Read final symbol \$. The transformation $V_{\$}$ corresponding
  to the right endmarker $\$$ is done. It maps
  the superposition to $\frac{1}{2} |q_{rej}\rangle+\frac{1}{2} |q_{acc}\rangle$.
  This is observed. With probability $(1/2)^2=1/4$, the rejecting state $q_{rej}$
  is observed. With probability $1/4$, the accepting state $q_{acc}$ is observed.

  The total probability of accepting is $1/4$, the probability
  of rejecting is $1/2+1/4=3/4$.


How can I construct sorting network for $k$ numbers How can I construct a sorting network for $k$ numbers?

My goal is to implement sorting networks in Java for $k$ in the range $[3,\hspace{-0.03 in}32]$.

To be even more specific, I only want to sort integers.

I found some implementation in this article (pages 2-3), but I don't understand it.

I been trying to convert this problem to SAT. I started with a simple non-optimal network: $[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01]$ (source). The idea is to convert it to SAT, find the shortest equal-satisfiable SAT formula, and convert it back to a network representation. The problem is that in the network, the order of comparisons is important, so I don't know hot to convert it to SAT. It sounds like some one has already been trying to do something like this, but I don't understand it completely.

Related question.

there is some research angle here dating at least to Knuth's Art of Computer Programming and presumably earlier in finding optimal sorting networks for low $n$. its intractable to find optimal sorting networks for small $n$ but it has been done up to about $n=10$ eg as in this recent notable paper, also using SAT. details about how to reduce the problem to SAT are in the paper. basically a large SAT formula encoding is built that asserts "these boolean variables configure a circuit that sorts all inputs for size $n$". (the more nonresearch angle is to use existing sort algorithms or sorting network configurations as mentioned in the paper by Har-Peled you cite to generate the (nonoptimal) circuits, this is more like a CS/EE exercise.)

Optimal Sorting Networks Daniel Bundala, Jakub Závodný

  This paper settles the optimality of sorting networks given in The Art of Computer Programming vol. 3 more than 40 years ago. The book lists efficient sorting networks with n <= 16 inputs. In this paper we give general combinatorial arguments showing that if a sorting network with a given depth exists then there exists one with a special form. We then construct propositional formulas whose satisfiability is necessary for the existence of such a network. Using a SAT solver we conclude that the listed networks have optimal depth. For n <= 10 inputs where optimality was known previously, our algorithm is four orders of magnitude faster than those in prior work.


What is the precise definition of Random K-SAT? There are 4 different constraints we can have when defining Random K-SAT. 1)Total number of literals in a given clauses is exactly K or AT most K
2)A given literal can be used with or without replacement in the same clause (A or A or A)
3)A given variable can be used with or without replacement in the same clause (A or ~A or ~A)
4)A given clauses can be used with or without replacement in a given formula
What would be the most "correct" definition? What are the cons and pros of using these different definitions?

As was pointed out at the beginning of this discussion in the comments, there is not necessarily a single "right" definition for random $k$-SAT.

That said, the two most common variants of random $k$-SAT are both fixed clause length (FCL) models, meaning that exactly $k$ literals appear in each clause. These variants both disallow repeated variables and literals within a clause, but differ in whether they allow repeated clauses within a formula. Nevertheless, they are essentially the same as will be discussed below.

Two main models:

The Selman random model - Repeated clause are allowed. Kyle gave this nice reference in the comments to his answer, but incorrectly assumed that the model disallowed repeated clauses. The linked (slightly different) version of the paper contains a more detailed discussion of the random model in Section 3: "This method of generation allows duplicate clauses in a formula... However, as N gets large duplicates will become rare because we generally select only a linear number of clauses."

The Achlioptas random model - Repeated clauses are disallowed. We treat generating a random formula as selecting $m$ clauses u.a.r. from the $2^k {n \choose k}$ total possible clauses without replacement. See Ch.8 of the Handbook of Satisfiability [1]  (Random SAT by Achlioptas) as a reference. This model seems more prevalent in the theoretical literature, possibly because so much of it was written by Achlioptas himself.

Equivalence of phase transition locations:

However, the phase transition (50% satisfiability threshold) occurs at the same clause-to-variable ratio regardless of which of these models is chosen for essentially the reason that Selman et al. noted in their paper.

Let $A(n,m,k)$ denote the expected number of identical pairs of clauses in a Selman random $(n,m,k)$-SAT instance. The probability of a given pair of clauses being identical is $p = 1/(2^k {n \choose k})$, whereas the total number of pairs of clauses is $N = {m \choose 2}$. By the linearity of expectation, $A(n,m,k) = p \cdot N = {m \choose 2}/{2^k {n \choose k}}$.

By Theorem 3 in  [1], the provable upper bound on the location of the $k$-SAT phase transition, using the Achlioptas model occurs when $m = O(2^k n)$. Fixing $k \geq 3$ and setting $m = O(2^k n)$ we get

$A(n,m,k) = {m \choose 2}/{2^k {n \choose k}} = O(m^2)/O(n^k) = O(n^2)/O(n^k)$.

Then, because $k \geq 3$, $\displaystyle \lim_{n \rightarrow \infty} O(n^2)/O(n^k) = 0$, meaning that in expectation there will be zero repeated clauses around the $k$-SAT phase transition when generating random SAT formulas using the Selman model.

Shameless self promotion - I discuss these topics briefly in Section 4.1 of my master's thesis.

Random QBF

As it turns out, the situation is much more interesting for random QBF. What are AFAIK the first three papers on random QBF each proposed a new random model, critiquing their predecessor.

See the following papers:

Cadoli et al. "Experimental Analysis of the Computational Cost of Evaluating Quantified Boolean Formulae." AI*IA 1997
Gent + Walsh "Beyond NP: the QSAT phase transition." AAAI/IAAI 1999
Chen + Interian "A Model for Generating Random Quantified Boolean Formulas." IJCAI 2005


How are Futures described in terms of category theory? Is there a useful description of futures or promises in terms of category theory? In particular, what could the categorical dual of Future be?

As it happens, I'm writing a paper about this now. IMO, a good way to think about futures or promises is in terms of the Curry-Howard correspondence for temporal logic.

Basically, the idea behind futures is that it is a data structure representing a computation that is in progress, and upon which you can synchronize. In terms of temporal logic, this is the eventually operator $\Diamond A$. This has a monadic structure:
$$
\begin{array}{lcl}
\mathrm{return} & : & A \to \Diamond A \\
\mathrm{bind} & : & (A \to \Diamond{B}) \to \Diamond{A} \to \Diamond{B}
\end{array}
$$
in which the $\mathrm{return}$ operation spawns a process that immediately returns its argument, and $\mathrm{bind}$ creates a new process which waits for $a$'s value, applies $f$ to that value, and then waits for the $B$-value before returning. The Promises/A proposal for CommonJS calls the monadic bind  operation then, and Scala 2.10 just gives it the standard monadic interface.

The dual to the eventually operator $\Diamond{A}$ is the always operator $\Box{A}$ of temporal logic, which says that at every instant, you get an $A$. When you pass from a Kripke semantics of temporal logic (where you just model provability) to a categorial semantics of a $\lambda$-calculus (where you model lambda-terms/proofs also), it turns out there are actually multiple ways to do this.

The simplest thing you can do is to take $\Box{A} \triangleq A$, on the grounds that once you have an $A$, you always have it. This works, but is kind of boring, IMO. :)

The most natural (IMO) thing to do is to take $\Box{A} \triangleq \mathsf{Stream}\;A$, which permits you to get a (potentially different) $A$ at each instant. Then, you can see the comonadic style of functional  reactive programming (FRP) (first proposed by Tarmo Uustalu and Varmo Vene) as the dual to monadic style of programming with futures.

However, the comonadic $\lambda$-calculus as they suggest, despite its elegance, causes a serious loss of expressiveness relative to programming explicitly with streams, since the category of free coalgebras they use turns out to have too few global elements to denote many interesting programs, especially fixed points.

Nick Benton and I have argued for programming explicitly with streams in our paper Ultrametric Semantics of Reactive Programs. Subsequently, Alan Jeffrey suggested using LTL as a type system in his paper LTL types FRP, an observation that Wolfgang Jeltsch also made in his paper Towards a Common Categorical Semantics for Linear-Time Temporal Logic and Functional Reactive Programming.

The difference between the view Nick and I take, and the one that Alan and Wolfgang take is best understood (IMO) by comparing the construction given in Birkedal et al.'s First steps in synthetic guarded domain theory: step-indexing in the topos of trees with Alan's paper. The topos of trees (presheaves over the natural numbers ordered by size) is very similar to category of ultrametric spaces Nick and I used, but much easier to compare with  Alan's category (presheaves over a discrete category of time), since these are both presheaf categories.

If you're interested in futures specifically for concurrency, then it might be a better idea to look at CTL rather than LTL, though. AFAIK, that's presently unexplored territory!

EDIT: here's a link to the draft. The paper is mostly about implementing typed FRP, so the language is synchronous. But most of the discussion of futures/events in section 3.3 should basically apply to truly concurrent languages as well.


Integer programming with a fixed number of variables The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.

I interpret that as follows.

Integer programming in general still is NP-complete but if my typical problem size at hand (say about 10.000 variables, an arbitrary number of constraints) is feasible in practice then I could construct an algorithm that scales polynomially in the number of constraints but not in the number of variables and constraints.
The result is also applicable for binary programming since I can force any integer to 0-1 by adding an appropriate constraint.

Is my interpretation correct?

Does this result have any practical implications? That is, is there an implementation available or is it used in popular solvers like CPLEX, Gurobi, or Mosek?

Some quotes from the paper:

  This length may, for our purposes, be defined to be n · m · log(a +
  2), where a denotes the maximum of the absolute values of the
  coefficients of A and b. Indeed, no such polynomial algorithm is
  likely to exist, since the problem in question is NP-complete

  [...]

  It was conjectured [5], [10] that for any fixed value of n there
  exists a polynomial algorithm for the solution of the integer linear
  programming problem. In the present paper we prove this conjecture by
  exhibiting such an algorithm. The degree of the polynomial by which
  the running time of our algorithm can be bounded is an exponential
  function of n.

The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.

  Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$
  arithmetic operations and space polynomial in $L$. Here $L$ is the
  number of bits in the input and $n$ the number of variables in the
  integer linear program.

Thus, the problem is fixed-parameter linear parameterized by the number of variables.

1) Yes, Integer Linear Programming is "still" NP-complete. The running time of the theoretical result above depends only linearly on the number of constraints, so it scales nicely in the number of constraints. However I know of no actual implementation of this algorithm.

2) Yes, making the variables take binary values is straightforward as you observed.

Update. The dependence on $L$ can actually be improved in the running time for Integer Linear Programming. Based on Clarkson (1995) and Eisenbrand (2003) (see the comments below) one can obtain an algorithm with running time $$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$$
where $m$ is the number of constraints and $s$ is the maximum number of bits required to encode a constraint or the objective function.


Graph partitioning, balancing on within subset edge weights I'm interested in pointers to algorithms (approximation algorithms are fine) that attempt to partition a graph into two subsets such that the sum of the edge weights within each subset is (approximately) equal, and the sum of the edge weights between the two subsets is (approximately) minimal.

Any pointers are much appreciated.

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

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

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

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


What would a very simple quantum program look like? In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first programs I ever wrote was something like

for i = 1 to 10
  print i
next i

Can anybody give an example of code of comparable simplicity that would utilize quantum photonic chips (or similar hardware), in pseudocode or high level language? I am having difficulty making the conceptual jump from traditional programming to entanglement, etc.

Caveat Emptor: the following is heavily biased on my own research and view on the field of QC.  This does not constitute the general consensus of the field and might even contain some self-promotion.

The problem of showing a 'hello world' of quantum computing is that we're basically still as far from quantum computers as Leibnitz or Babbage were from your current computer.  While we know how they should operate theoretically, there is no standard way of actually building a physical quantum computer. A side-effect of that is that there is no single programming model of quantum computing.  Textbooks such as Nielsen et al. will show you a 'quantum circuit' diagram, but those are far from formal programming languages: they get a little 'hand-waving' on the details such as classical control or dealing with input/output/measurement results.

What has suited me best in my research as a programming language computer scientist, and to get the jist of QC across to other computer scientist, is to use the simplest QC model I've come across that does everything.

The simplest quantum computing program I have seen that contains all essential elements is a small three-instruction program in the simplest quantum programming model I've come across.  I use it as you would a 'hello world' to get the basics across.

Allow me to give quick simplified summary of the The Measurement Calculus by Danos et al.1  that is based on is based on the one-way quantum computer2: a qubit is destroyed when measured, but measuring it affects all other qubits that were entangled with it.  It has some theoretical and practical benefits over the 'circuit-based' quantum computers as realized by the photonic chip, but that is a different discussion.

Consider a quantum computer that has only five instructions: N, E, M, X and Z.  Its "assembly language" is similar to your regular computer, after executing one instruction it goes to the next instruction in the sequence. Each instruction takes a target qubit identifier, we use just a number here, and other arguments.

N 2          # create a new quantum bit and identify it as '2'
E 1 2        # entangle qubits '1' and '2', qubit 1 already exists and is considered input
M 1 0        # measure qubit '1' with an angle of zero  (angle can be anything in [0,2pi]
             # qubit '1' is destroyed and the result is either True or False
             # operations beyond this point can be dependent on the signal of '1'
X 2 1        # if the signal of qubit '1' is True, execute the Pauli-X operation on qubit '2'

The above program thus creates an ancilla, entangles it with the input qubit, measures the input and depending on the measurement outcome performs an operation on the ancilla. The result is that qubit 2 now contains the state of qubit 1 after Hadamard operation.

The above is naturally at such low level that you wouldn't want to hand-code it. The benefit of the measurement calculus is that it introduces 'patterns', some sort of composable macros that allow you to compose larger algorithms as you would with subroutines.  You start off with 1-instruction patterns and grow larger patterns from there.

Instead of an assembler-like instruction sequence, it is also common to write the program down as a graph:

 input                .........
    \--> ( E ) ---> (M:0)     v
(N) ---> (   ) ------------> (X) ---> output

where full arrows are qubit dependencies and the dotted arrow is a 'signal' dependency.

The following is the same Hadamard example expressed in a little programming tool as I would imagine a 'quantum programmer' would use.

edit: (adding relation with 'classical' computers)  Classical computers are still really efficient in what they do best, and so the vision is that quantum computers will be used to off-load certain algorithms, analogous to how current computer offloads graphics to a GPU. As you have seen above, the CPU would control the quantum computer by sending it an instruction stream and read back the measurement results from the boolean 'signals'.  This way you have a strict separation of classical control by the CPU and quantum state and effects on the quantum computer.

For example, I'm going to use my quantum co-processor to calculate a random boolean or cointoss.  Classical computers are deterministic, so its bad at returning a good random number.  Quantum computers are inherently probabilistic though, all I have to do to get a random 0 or 1 is to measure out a equally-balanced qubit.  The communication between the CPU and 'QPU' would look something like this:

 qrand()       N 1; M 1 0;
 ==>  | CPU | ------------> | QPU |  ==> { q1 } ,  []
                 start()
      |     | ------------> |     |  ==> { } , [q1: 0]
                 read(q1)
      |     | ------------> |     |
                  q1: 0
 0    |     | <-----------  |     |
 <==

Where { ... } is the QPU's quantum memory containing qubits and [...] is its classical (signal) memory containing booleans.

Danos et al. The Measurement Calculus. arXiv (2007) vol.
quant-ph
Raussendorf and Briegel. A one-way quantum computer.
Physical Review Letters (2001) vol. 86 (22) pp. 5188-5191


Clustering massive data sets in practice If you have a very large data set of $n$ vectors and you want to cluster them according to some metric measure, what is the current state of the art when you can not afford to do more than $\Theta(n)$ work?  I am interested in methods that work well in practice as well as having nice theoretical properties.

A web search brings up "A sublinear time approximation scheme for clustering in metric spaces" by P. Indyk as the most cited paper in the area.

At the risk of sounding immodest, I wrote a short survey on stream clustering a few years ago. It's a little out of date, but not overly so, and doing forward citations will get you to the recent work in the area.


W[1]-hard problems on bounded degree graphs Do you know problems which are W[1]-hard even for bounded degree graphs?

Metric Dimension is hard on graphs with degree at most 3, but it is W[2]-hard.
Red-Blue Nonblocker used to be W[1]-hard on bounded degree graphs but there was an error in the proof (book of Downey Fellows 2013), and it is hard only if blue vertices are of bounded degree.

Ball and Trap I remains $W[1]$-hard when restricted to binary trees.

Theorem 5 states:

  Theorem 5. Ball and Trap I remains $W[1]$-hard restricted to binary trees,
  the maximum number of traps per vertex is one per color, and balls are placed
  on neither leaves nor parents of leaves.


Which SAT problems are easy? What are "easy regions" for satisfiability? In other words, sufficient conditions for some SAT solver to be able to find a satisfying assignment, assuming it exists.

One example is when each clause shares variables with few other clauses, due to constructive proof of LLL, any other results along those lines?

There's sizable literature on easy regions for Belief Propagation, is there something along those lines for satisfiability?

I guess you know the classical result of Schaefer from STOC'78, but just in case.

10.1145/800133.804350

Schaefer proved that if SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in GF(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).


What is the minimum required depth of reductions for NP-hardness of SAT? As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.

My questions is what is the minimum required depth for the reductions?
More formally,

  What is the least $d$ such that
  SAT is $\mathsf{NP}$-hard w.r.t $\mathsf{AC^0_d}$ many-one reductions?

It seems to me that $\mathsf{AC^0_2}$ should be sufficient? Does anyone know a reference?

Reposting my comment:

From a quick look, it seems like your question should be answered by "Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem, JCSS 57: 127-143, 1999." They say "we prove that all sets complete for NP under AC0 reductions are complete under reductions that are computable via depth two AC0 circuits." But I may be missing something.


Approximation algorithms for dominating set problem I am working on approximation algorithms for minimum dominating set problem. In particular, I am interested in graphs classes restricted by forbidden induced subgraphs.
Since the domination problem and its variants have been extensively studied, I suppose someone may worked on this before.
So, the question is:

Does someone knows papers where it is studied approximation algorithms for domination problem for graphs classes defined by forbidden induced subgraphs?

Thanks in advance.
Kind regards.

The class of line graphs can be characterized by a finite family of forbidden induced subgraphs (Beineke).  A dominating set in a line graph G corresponds to an edge dominating set of the root graph of G (and vice versa), and the size of minimum edge dominating set can be approximated by factor of 2 in polynomial time.

http://en.wikipedia.org/wiki/Line_graph
http://en.wikipedia.org/wiki/Edge_dominating_set


Is there a useful notion of being “approximately computable” It seems that we can define a notion of being “approximately computable” where a set, $S$, is approximately computable if there is a family of computable functions $f_n(x)$ such that $$\lim_{n\to\infty} f_n(x)=\chi_S(x)$$ Under this definition, I believe that the halting set is approximately computable and that a set is computable if and only if it is uniformly approximately computable.

I haven’t been able to find anything online about this notion, or any other notion, of approximately computable. This doesn’t seem particularly novel, and I’m surprised I can’t find any resources on it. Has an idea of “approximately computable sets” been studied? Do they all collapse to merely computable for a reason I haven’t seen?

By diagonalization, there are set that aren’t approximately computable under my definition. It seems likely that any reasonable definition of “approximately computable” would similarly only apply to $\aleph_0$-many sunsets of $P(\mathbb N)$. Assuming that there is a reasonable definition, is there a criteria (perhaps a level of the arithmetic hierarchy) where all sets above that level are not approximately computable?

I am thinking about this because I’ve been reading about combinatorial game theory recently, and about games with only uncomputable winning strategies. It seems plausible that a computer might be able to play a game extremely close to optimally in some sense, perhaps that they play the closest to optimally of all programs of size $\leq n$. Sets that don’t have a computable approximation seem like candidates for building games where computers can only play the game poorly. If anyone has references for investigations of this idea, I would be very interested in that as well.

If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very well studied within computability-theory.

There are also other, not equivalent, notions of almost computable that go by names such as generically computable and coarsely computable, see e.g.
Jockusch et al.: Asymptotic Density and the Theory of Computability: A partial survey.


Why would one ever use an Octree over a KD-tree? I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar data structure for partitioning 3-D Euclidean spaces, but one that works at fixed regular intervals, from what I gather.

A bit of independence research seems to indicate that kd-trees are typically superior in performance for most datasets -- quicker to construct and to query. My question is, what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)? A summary of the advantages and problems of both types would me most appreciated.

As an extra, if anyone could elaborate on the usage of the R-tree data structure and its advantages, I would be grateful for that too. R-trees (more so than octrees) seem to be applied quite similarly to kd-trees for k-nearest-neighbour or range searches.

The cells in a $kD$-tree can have high aspect ratio, whereas octree cells are guaranteed to be cubical. Since this is a theory board, I'll give you the theoretical reason why high aspect ratio is a problem: it makes it impossible to use volume bounds to control the number of cells that you have to examine when solving approximate nearest neighbor queries.

In more detail: if you ask for an $\epsilon$-approximate nearest neighbor to a query point $q$, and the actual nearest neighbor is at distance $d$, you typically end up with a search that examines every data structure cell that reaches from the inside to the outside of an annulus or annular shell with inner radius $d$ and outer radius $(1+\epsilon)d$. If the cells have bounded aspect ratio, as they are in a quadtree, then there can be at most $1/\epsilon^{d-1}$ such cells, and you can prove good bounds on the time for the query. If the aspect ratio is not bounded, as in a $kD$-tree, these bounds do not apply.

$kD$-trees have a different advantage over quadtrees, in that they are guaranteed to have at most logarithmic depth, which also contributes to the time for a nearest neighbor query. But  the depth of a quadtree is at most the number of bits of precision of the input which is generally not large, and there are theoretical methods for controlling the depth to be essentially logarithmic (see the skip quadtree data structure).


Is there a typed lambda calculus which is consistent and Turing complete? Is there a typed lambda calculus where the corresponding logic under the Curry-Howard correspondence is consistent, and where there are typeable lambda expressions for every computable function?

This is admittedly an imprecise question, lacking a precise definition of "typed lambda calculus." I'm basically wondering whether there are either (a) known examples of this, or (b) known impossibility proofs for something in this area.

Edit: @cody gives a precise version of this question in his answer below: is there a logical pure type system (LPTS) which is consistent and Turing complete (in a sense defined below)?

Alright I'll give a crack at it: In general for a given type system $T$, the following is true:

  If all well-type terms in the calculus $T$ are normalizing, then $T$ is consistent when viewed as a logic.

The proof generally proceeds by assuming you have a term $\mathrm{absurd}$ of type $\mathrm{False}$, using subject reduction to get a normal form, and then proceeding by induction on the structure of such a term to get a contradiction.

It is natural to wonder if the converse holds, i.e.

  For any type system $T$, if $T$ is logically consistent, then every well-typed term in $T$ is normalizing.

The problem with this is that there is no real most general notion of "type system", and even less agreement on the meaning of logical consistency for such systems. However, we can empirically verify that

  For most known type systems which have a logical interpretation, the converse does indeed hold.

How does this tie into Turing Completeness? Well, for one, if type-checking is decidable, then Andrej's argument shows that one of the following must hold:

The set of all well-typed programs is not Turing Complete.
There is a non-terminating well typed program.

This tends to suggest that:

  Type systems which have a logical interpretation and are consistent and are recursively enumerable are not Turing Complete.

Giving an actual theorem rather than a suggestion requires making the notion of type systems and logical interpretations mathematically precise.

Now two remarks come to mind:

There is an undecidable type system, the intersection type system which has a logical interpretation and can represent every normalizing $\lambda$-term. As you remark, this isn't quite the same as being Turing Complete, as the type of a total function may need to be updated (refined, in fact) before applying it to the desired argument. The calculus is a "curry style" calculus and is equal to STLC +
$$ \frac{\Gamma\vdash M:\tau\quad \Gamma\vdash M:\sigma}{\Gamma\vdash M:\tau\cap\sigma} $$
and
$$\frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\tau}\quad \frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\sigma}$$
It is clear that the "interpretation" $\cap=\wedge$ leads to a consistent logical interpretation.
There is a class of type systems, the Pure Type Systems, in which such a question might be made precise. In this framework however, the logical interpretation is less clear. One might be tempted to say: "a PTS is consistent if it has an uninhabited type". But this doesn't work, since types may live in different "universes", where some might be consistent and some not.
Coquand and Herbelin define a notion of Logical Pure Type Systems, in which the question makes sense, and show

  Every inconsistent, non-dependent LPTS has a looping combinator (and so is Turing Complete)

Which answers the question in one direction (inconsistent $\Rightarrow$ TC) in this case. As far as I know, the question for general LPTS is still open and quite difficult.

Edit: The converse of the Coquand-Herbelin result is not as easy as I thought! Here is what I came up with so far.

A Logical Pure Type System is a PTS with (at least) the sorts $\mathrm{Prop}$ and $\mathrm{Type}$, (at least) the axiom $\mathrm{Prop}:\mathrm{Type}$ and (at least) the rule $(\mathrm{Prop},\mathrm{Prop},\mathrm{Prop})$, with the further requirement that there are no sorts of type $\mathrm{Prop}$.

Now I'm going to assume a particular statement of Turing Completeness: fix an LPTS $L$ and let $\Gamma$ be the context

$$ \Gamma = \mathrm{nat}:\mathrm{Prop},\ 0:\mathrm{nat},\ S:\mathrm{nat}\rightarrow \mathrm{nat}$$

$L$ is Turing Complete iff for every total computable function $f:\mathbb{N}\rightarrow\mathbb{N}$ there is a term $t_f$ such that
$$ \Gamma \vdash t_f : \mathrm{nat}\rightarrow \mathrm{nat}$$
and for every $n\in\mathbb{N}$
$$ t_f\ (S^n\ 0)\rightarrow^*_{\beta} S^{f(n)}\ 0$$

Now Andrej's diagonalization argument shows that there are non-terminating $t$ of type $\mathrm{nat}$.

Now it seems like we are half-way there! Given a non terminating term $\Gamma \vdash \mathrm{loop}:\mathrm{nat}$, we want to replace occurrences of $\mathrm{nat}$ by some generic type $A$ and get rid of $0$ and $S$ in $\Gamma$, and we will have our inconsistency ($A$ is inhabited in the context $A:\mathrm{Prop}$)!

Unfortunately this is where I get stuck, since it is easy to replace $S$ by the identity, but the $0$ is much harder to get rid of. Ideally we would like to use some Kleene recursion theorem, but I haven't figured this out yet.


Complexity of finding the square root of a perfect square What is the complexity of precisely finding the square root of a perfect square?

The square root of an $n$-digit number can be computed in time $O(M(n))$ using e.g. Newton’s iteration, where $M(n)$ is the time needed to multiply two $n$-digit integers. The current best bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$, provided by Fürer’s algorithm. See http://en.wikipedia.org/wiki/Methods_of_computing_square_roots for more square root algorithms, and http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations for an overview of computational complexity of arithmetical operations.


A data structure for sets of trees. Tries allow for efficient storage of lists of elements.  The prefixes are shared so it is space efficient.

I am looking for a similar way to efficiently store trees.  I would like to be able to check for membership and to add elements, knowing if a given tree is a subtree of some stored trees or if there exists a stored tree being a subtree of the given tree is also desirable.

I would typically store about 500 unbalanced binary trees of height less than 50.

EDIT

My application is some kind of model checker using some sort of memoization. Imagine I have a state $s$ and the following formulae: $f = \phi$ and $g = (\phi \vee \psi)$ with $\phi$ being a complex subformula, and imagine I first want to know if $f$ holds in $s$.  I check if $\phi$ holds and after a lengthy process I obtain that it is the case. Now, I want to know if $g$ holds in $s$. I would like to remember the fact that $f$ holds and to notice that $g \Rightarrow f$ so that I can derive $g$ in $s$ almost instantly.
Conversely, if I have proved that $g$ does not hold in $t$, then I want to tell that $f$ does not hold in $t$ almost instantly.

We can build a partial order on formulae, and have $g \geq f$ iff $g \Rightarrow f$.  For each state $s$, we store two sets of formulae; $L(s)$ stores the maximal formulae that hold and $l(s)$ stores the minimal formulae that do not hold. Now given a state $s$ and a formula $g$, I can see if $\exists f \in L(s), f \Rightarrow g$, or if $\exists f \in l(s), g \Rightarrow f$ in which case I am done and I know directly whether $g$ holds in $s$.

Currently, $L$ and $l$ are implemented as lists and this is clearly not optimal because I need to iterate through all stored formulae individually. If my formulae were sequences, and if the partial order was "is a prefix of" then a trie could prove much faster. Unfortunately my formulae have a tree like structure based on $\neg, \wedge$, a modal operator, and atomic propositions.

As @Raphael and @Jack points out, I could sequentialise the trees, but I fear it would not solve the problem because the partial order I am interested in would not correspond to "is a prefix of".

You might want to check out g-tries. This is essentially the data structure you're looking for, but designed for use with general graphs instead of just trees. As such, I'm not sure that g-tries have good theoretical guarantees -- I think they use a graph canonization algorithm as a subroutine -- but in practice they seem to work well.

(Don't be scared that the linked paper is about "network motifs in biological networks": the g-trie is a perfectly good abstract data structure for graphs.)


What is a zipper, and how does it relate to a tree-like structure? I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers be generalized to any data structure?

A zipper, in general, is a data structure with a hole in it. Zippers are used for traversing/manipulating data structures, and the hole corresponds to the current focus of the traversal. Typically there is also an element of the data structure under consideration, so that one has a (list) zipper and a list or a (tree) zipper and a tree. The zipper allows the programmer to efficiently move around the data structure, even replacing the element at the focus. The pair of the zipper and the element in the focus satisfy the constraint that placing the element at the focus in the hole gives the original data structure.

Zippers can be generalised to arbitrary inductive data types. The concept can be defined in type-indexed fashion (See type-indexed data types). They are also related to the idea of the derivative of a data structure, and has been studied from a Category Theoretic perspective.


Finding subgraphs with high treewidth and constant degree I am given a graph $G$ with treewidth $k$ and arbitrary degree, and I would like to find a subgraph $H$ of $G$ (not necessarily an induced subgraph) such that $H$ has constant degree and its treewidth is as high as possible. Formally my problem is the following: having chosen a degree bound $d \in \mathbb{N}$, what is the "best" function $f : \mathbb{N} \to \mathbb{N}$ such that, in any graph $G$ with treewidth $k$, I can find (hopefully efficiently) a subgraph $H$ of $G$ with maximal degree $\leq d$ and treewidth $f(k)$.

Obviously we should take $d \geq 3$ as there are no high treewidth graphs with maximal degree $<3$. For $d = 3$ I know that you can take $f$ such that $f(k) = \Omega(k^{1/100})$ or so, by appealing to Chekuri and Chuzhoy's grid minor extraction result (and using it to extract a high-treewidth degree-3 graph, e.g., a wall, as a topological minor), with the computation of the subgraph being feasible (in RP). However, this is a very powerful result with an elaborate proof, so it feels wrong to use it for what looks like a much simpler problem: I would just like to find any constant-degree, high-treewidth subgraph, not a specific one like in their result. Further, the bound on $f$ is not as good as I would have hoped. Sure, it is known that it can be made $\Omega(k^{1/20})$ (up to giving up efficiency of the computation), but I would hope for something like $\Omega(k)$. So, is it possible to show that, given a graph $G$ of treewidth $k$, there is a subgraph of $G$ with constant degree and linear treewidth in $k$?

I'm also interested in the exact same question for pathwidth rather than treewidth. For pathwidth I don't know any analogue to grid minor extraction, so the problem seems even more mysterious...

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers.
We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$.
https://arxiv.org/abs/1410.1016 The proof is shorter than the one
for grid minors but it is still not that that easy and builds on several previous
tools.

Suppose you settle for an easier target - degree 4 and treewidth $\Omega(k^{1/4})$ then you can get it much more easily via  result of Reed and Wood on grid-like minors. https://arxiv.org/abs/0809.0724

Another easy result you can obtain is the following which is a starting point for some of the more involved proofs. You can get a subgraph of degre  $\log^2(k)$
and treewidth $\Omega(k/\mathsf{polylog}(k))$. You can see the treewidth sparsifier paper for the argument to achieve this.


How can I prove formally semantic equivalence of programming languages? I would like to compare two languages which are from different programming paradigms. Both langauges are object oriented languages, but one of them a multiparadigm language because it supports functional programming style as well.

I wrote some example codes in imperative style and functional style which are absolutely different in syntax but equivalent in semantics.

I have some experiences about operational semantics, the WHILE language and so on from my university studies and I was wondering how I could give a formal definiton about semantic equivalence of an imperative and a functional language.

I was looking for a clear and nice article about this topic on google scholar but i have not found any useful yet.

Thanks for helping!

Comparing two programming languages is difficult  is a difficult
problem, and far from being solved. The key issue is that there are many different ways languages can be compared, and none of them is compelling.

The most widely used approach, coming from logic, is to
consider translations between the languages to be compared.
The general
idea is as follows:  if we
have a translation into from $L_1$ into $L_2$, say, then
$L_2$ is at least as expressive as $L_1$.

Unfortunately, things are not quite that easy.
By the Church-Turing thesis you know that you can
always find such translations
(for Turing-complete languages). So the very existence of
translations is not discreminating enough to distinguish
programming languages. And yet, everybody who has programmed in
different languages (e.g. Assembler vs Scala) knows that some
languages are easier to program than others.

This conundrum is
usually approached by putting restrictions on what counts as a
translation functions. The idea here is  that the translation functions
'measure' how much 'rearrangement' is necessary when translating
from one language to the other: the more 'rearrangement'
required, the less expressive the target language. Restrictions
on translations control what kind of 'rearrangement' we consider.
If we can show that
no translation exists that satisfies a bunch of restrictions, then
the languages are substantially different in expressivity.

In this sense e.g. the $\pi$-calculus is very expressive because
we can often find translations meeting various restrictions when
translating from a language $L$ into the $\pi$-calculus. Conversely,
purely functional languages are not so expressive, because when we
translate $L$ into a purely functional language, the translation functions
often violate various constraints.

Here is a far from exhausting list of popular restrictions
for this purpose:

The translation should preserve termination.
The translation should preserve the structure of
programs (mathematically: translation should be a
homomorphism): $$trans(f(P_1, ..., P_n)) = trans(f)(trans(P_1),
  ..., trans(P_n)).$$ This constraint is usually referred to as
compositionality of the translation.
While compositionality can often not be achieved when we try to
compare very different languages $L_1$ and $L_2$, A weaker form
almost always holds: (simplifying a bit) there is a fixed
program $Q$ for each constructor $f$ such that $$trans(f(P_1, ..., P_n)) = trans(f)(Q,
  trans(P_1), ..., trans(P_n)).$$ I like to call this
compositionality-up-to-OS, because the fixed program $Q$ acts
like an operating system.
The translation should preserve the (asymptotic space or time)
complexity of programs. (The Slot and van Emde Boas thesis says
that polynomial-time translations are always possible, so we
might need finer distinctions than preservation of run-time up
to a polynomial factor.) The theory of NP-completeness can be
seen in this light.
The translation should exhibit operational correspondence: We
say an encoding $trans(.)$ is operationally corresponding if it is
Whenever $P →^* Q$ then $trans(P) →^*≈ trans(Q)$. Moreover, whenever $trans(P) →^* Q$ then there is $P'$ such that $P
  →^* P'$ and $Q →^*≈ trans(P')$. Here ≈ is the chosen notion of program
equality in the target language.
Divergence reflection: this means that whenever $trans(P)$ diverges, then so does $P$.
Success sensitiveness: Given a criterion of program
success (e.g. the ability of output a chosen value) on both
source and target, an encoding $trans(.)$ is success sensitive if $P$
is successful if and only iff $trans(P)$ is successful.
Full abstraction, we want $P \simeq_1 Q$ iff $trans(P) \simeq_2 trans(Q)$,
where $\simeq_1$ is the chosen notion of program equality in the source language
of the translation and $\simeq_2$ does that job in the target.
Preservation of program size:  the translation should not lead to substantial
increases in program size.
Name invariance: each program has a finite number of
'interaction points' that the outside can use to interact with
the program, e.g. free variables.  We can require that
encodings commut with injective renamings of 'interaction
points'.

The relationships between those criteria, like the whole field
of programming language expressiveness, is ill-understood.

A pioneering paper in the study of programming language expressiveness is

M. Felleisen, On the Expressive Power of Programming Languages.

where key concepts from logic, such as conservative extension of
theories are generalised to programming languages.


#SAT Solver download Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an approximation.

You can do this with SAT4J, simply by iterating over all models: http://www.sat4j.org/howto.php#models. I imagine that most SAT solvers have this ability.


How good of an approximate 2-coloring can you get of the halved cube graph? We say that a 2-coloring $col : V_G \rightarrow \{0, 1\}$ of a graph $G$ is $\epsilon$-approximate if $Pr_{(w, v) \in E_G}(col(w) \neq col(v)) \geq \epsilon$. For every $n$, what is the maximum $\epsilon_n$ for which the halved cube graph has an $\epsilon_n$-approximate coloring $col_n$? The halved cube graph is the graph you get by using the same construction as the Boolean cube but flipping 2 bits instead of 1 to get from vertex to vertex, and then throwing out one of the two identical connected components. What is the family of colorings which witnesses this? Is there a natural coloring which comes close to the optimum, ideally approaching it asymptotically?

The answer is $\epsilon_n = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2}$.

First, here's a formal definition of the halved cube graph $H_n$. The vertices are bitstrings of the form $a_1a_2\ldots a_n$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$. Two vertices $a_1a_2 \ldots a_n$ and $b_1b_2\ldots b_n$ are adjacent if and only if they differ in exactly two bits.

Define coloring $col_n$ of $H_n$ as follows: $$col_n(a_1a_2\ldots a_n) = a_1 \oplus a_2 \oplus \cdots \oplus a_{\lceil\frac{n}{2}\rceil}$$.

Consider the probability that a uniformly random edge has different colors on its two endpoints. It should be easy to see from the definition that an edge whose endpoints differ in bits $i$ and $j$ has different colors on both end points if and only if exactly one of these two indices is at most $\lceil\frac{n}{2}\rceil$. Furthermore, if we choose a uniformly random edge, then the pair of indices at which that edge's endpoints differ also ends up uniformly random (among all possible pairs of indices). Thus, the probability we are looking for is equal to the probability that a uniformly random pair of indices has the property that one index is at most $\lceil\frac{n}{2}\rceil$ while the other is not. There are $\left(\lceil\frac{n}{2}\rceil\times \left(n-\lceil\frac{n}{2}\rceil\right)\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ pairs with this property and $n \choose 2$ pairs in total. Thus, the probability we are looking for is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$. In other words, we have shown that coloring $col_n$ is an $\epsilon_n$-approximate coloring.

If $v = a_1a_2\ldots a_n$ is a vertex and $i$ is an index, then define $V(v, i) = \{v\} \cup \{b_1b_2\ldots b_n \in N(v)~|~a_i \ne b_i\}$ (where $N(v)$ is the set of neighbors of $v$). It is easy to show that all vertices in $V(v,i)$ are adjacent.

Consider the following procedure:

choose a vertex $v$ uniformly at random from $H_n$
choose an index $i$ uniformly at random from $\{1, 2, \ldots, n\}$
choose two vertices in $V(v, i)$ uniformly at random
output the edge between those vertices

This procedure samples an edge of $H_n$ with some probability distribution. It is possible to show that every edge is sampled with the same probability (this is somewhat annoying to prove, but you could argue this by symmetry). Therefore, this procedure can be thought of as a method of uniformly sampling an edge from $H_n$. We will prove below that for any fixed $v$ and $i$, the probability that a two random vertices from $V(v, i)$ have different colors is always at most $\epsilon_n$. Then if we sample an edge using the above procedure, the conditional probability that the two vertices at the third step have two different colors (given the outcomes of the first two steps) will be at most $\epsilon_n$. We conclude that the unconditional probability is also at most $\epsilon_n$. But then we have that the probability that an edge has two different colors at its endpoints when the edge is chosen uniformly at random is at most $\epsilon_n$. Thus, no coloring can be an $\epsilon$-approximation for any $\epsilon > \epsilon_n$.

All that's left is to show that two random vertices from $V(v, i)$ have different colors with probability at most $\epsilon_n$. There are $n$ vertices in $V(v, i)$. If $a$ vertices are colored in one color, then there are $a(n-a)$ pairs with different colors. Thus, the probability of choosing two vertices with different colors is $a(n-a) / {n \choose 2}$. But the closer $a$ gets to $\frac{n}{2}$, the larger $a(n-a)$ gets. In particular, for $n$ even, $a(n-a)$ achieves a maximum value of $n^2/4 = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n}{2}$ and for $n$ odd, $a(n-a)$ achieves a maximum value (for integer $a$) of $(n^2-1)/4 = \left(\frac{n-1}{2}\times\frac{n+1}{2}\right) = \left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$ at $a = \frac{n\pm 1}{2}$. In all cases, the maximum value of $a(n-a)$ is $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right)$, so we can conclude as desired that two random vertices from $V(v, i)$ have different colors with probability at most $\left(\lceil\frac{n}{2}\rceil \times \lfloor\frac{n}{2}\rfloor\right) / {n \choose 2} = \epsilon_n$.


PAC-learning bound with epsilon-cover of hypothesis class In this video at 43:00, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:

$$\epsilon^2 < \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$

where $m$ is the number of samples, $\delta$ is the confidence parameter, and $H_\epsilon$ is the cardinality of an "$\epsilon$-cover of the hypothesis class", where he defines an $\epsilon$-cover as a set of subsets of the hypothesis class, such that the probability that two hypothesis in the same subset disagree is less than $\epsilon$.

Apart from the fact that this isn't a formal statement, I couldn't prove this myself. Has anyone heard of this version of PAC, and if so, could they point me to resources explaining it, or give some explanation here?

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


Graph coloring minimizing the number of colors in every independent set Is the following claim known?

Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.

The following claim is known to me, but may not count because it is unpublished:
Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors,
where $B(B+1)\leq 2kn$.

This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph but also on all induced subgraphs.
I am not aware of any published results, though.


Are (empirical) Rademacher complexity always positive? Rademacher complexity and empirical Rademacher complexity are used to provide upper bound on the loss of solving an learning problem.
That seems to imply that Rademacher complexity and empirical Rademacher complexity can't be negative.

But from their definitions, I can't figure out if they are indeed always nonnegative. So what is the truth? Thanks.

For their definitions, I refer to  http://www.cc.gatech.edu/~ninamf/ML11/lect1115.pdf.

Yes, the empirical Rademacher complexity is non-negative, and this follows from Jensen's inequality.

For completeness, the empirical Rademacher complexity $\hat{R}(\mathcal{F}, X)$ given a sample $X = \{x_1, \ldots, x_m\}$ and a class of real-valued functions $\mathcal{F}$ whose domain contains $X$ is
$$
\hat{R}(\mathcal{F}, X) := \mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)},
$$
where the expectation is over $m$ independent random variables $\sigma:= (\sigma_1, \ldots, \sigma_m)$ sampled uniformly from $\{-1, 1\}$.

Notice that $\sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}$ is a convex function of $\sigma$, because it is the supremum of linear functions. Then, by Jensen and linearity of expectation,
$$
\mathbb{E}_\sigma \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\sigma_i f(x_i)}
\geq \sup_{f \in \mathcal{F}}\sum_{i = 1}^m{\mathbb{E}[\sigma_i] f(x_i)}
= 0.
$$

The final equality follows because $\mathbb{E}[\sigma_i] = 0$ for all $i$.


What's the complexity of factoring over a set of generators (say in $GL_2$)? In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know the time complexity of factoring it into a product of $A$s and $B$s is (or showing that such a factorization does not exist); that is, how long would it take to exhibit the product (or show the lack of existence)

$$ABBAAAB\cdots BAAB = C?$$

I have a feeling that this falls under Ladner's theorem but I'm not sure.

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$.

Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (in which case it is the membership problem for a subgroup of a general linear group) or not (in which case it is the membership problem for a submonoid or subsemigroup of a general linear group).

I don't know a complete answer to your question, but here are some special cases and hopefully relevant references:

In general, the membership problem in linear groups over infinite fields is undecidable [Mihailova, 1968]. I do not know whether undecidability holds for the case of 2-generated subgroups.
The Tits alternative implies that the group generated by $A,B$ is either solvable-by-finite, or contains a nonabelian free group. The intro of Eick-Kirschmer-Leedham-Green contains pointers to algorithms that solve the Tits alternative for subgroup of $GL_n(\mathbb{Q})$, in the sense of deciding which of the two cases holds.
In the solvable-by-finite case, the membership problem is decidable [Kopytov, 1968].
In the free case less is known. Eick, Kirschmer, and Leedham-Green ("The constructive membership problem for discrete free subgroups of rank 2 of $SL_2(\mathbb{R})$") give an efficient-in-practice algorithm for 2-generated subgroups of $SL_2(\mathbb{R})$ that are not only free but also discrete.
If $A,B$ commute, then Cai-Lipton-Zalcstein [FOCS 1994] show how to solve even the constructive subsemigroup membership problem in P. If $A,B$ don't commute, it's not even clear to me whether your problem is in NP, as it's not obvious to me that the desired word is polynomial-length nor has a polynomial-length description.
See also the final report of a 2014 Banff workshop on algorithms for linear groups.

(PS - If by "falls under Ladner's theorem" you mean "is likely to be NP-intermediate" (in the sense of being in NP but neither being in P nor being NP-complete), that's an unusual phrase, but I know what you meant. But, in case you're not aware, essentially no natural problem is known to have this status, even under standard complexity assumptions (such as PH not collapsing). See here for a list of natural problems that are currently candidates for being NP-intermediate.)