Finding optimal parallelization from general weighted undirected graph I am solving a problem of "blending" sets of overlapping images. These sets can be represented by undirected weighted graph such as this one:

Each node represents an image. Overlapping images are connected by an edge. Edge weight represents overlap area size (blending larger overlap sooner leads to better overall quality).

The algorithm generally removes edges. It can do it sequentially or in parallel. However, when blending occurs, the nodes merge and the graph structure changes. So parallelization is possible only on connected components that are themselves not overlapping!

Such non-overlapping components are D-B and F-E-G. We can run the blending algorithm on these components safely in parallel. The result is the following graph (merged nodes are displayed in green):

Now there is no further parallelization possible because any two connected components are overlapping (they have an edge directly between them).

The parallel version of the algorithm would look like this:

1. Find connected components (no two are connected directly) and create task for each.
2. Run the tasks in parallel.
3. Update graph.
4. Until single node remains, continue with 1.

The tricky part is the first step: How to find best set of connected components?

One way would be a greedy algorithm that simply finds the largest number of components at a given iteration.
The greedy algorithm will maximize parallelization in the beginning but at the cost of many iterations later.

The optimal solution may be bringing good amount of connected components in each iteration to maximize parallelization and minimize number of iterations at the same time (so there are two variables in the optimization).

I can't think of any optimization algorithm other than backtracking, i.e. search space of all possible evolutions and choose the one with maximum parallelization.

Edge weights can be ignored, but improved version of the algorithm may take it into account as larger areas takes more time to blend (e.g. area of size 200 will take roughly twice the time to blend than two areas of size 100). Taking weights into account may lead to better strategy on selecting components (faster overall running time of the algorithm).

Do you have any clues for such optimization algorithm, that finds the best strategy of selecting parts of graph so that there is maximum parallelization and minimum number of iterations?

This is very similar to overlaps of gene sequence in genome assembly. Chapter 4 of Ananth's thesis.

In parallel you search for promising pairs and maintain a distributed union find data structure. See Tarjan and Vishkin for their hook and shortcut algorithm to collapse the connected components.

Also, you can try recent DeBrujin graph methods on 64 bit row chunks of pixels. I think this will give you the best results. To help with quantization problems I would first reduce dimension of the pixels to 16 or 8 bit black/white. You then apply a parallel sort the 64 bit chunks, and then use them to infer edges between images.


Differential Privacy and Randomized Responses for Counting Queries I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the calculations.

The randomized response mechanism works as follows:

Let's call $q(x) = \frac{1}{n} \sum_{i=1}^{n}q(x_i)$ a counting query for a database $x$ with $n$ entries $x_i$.
Each $q(x_i)$ maps into ${0,1}$.

Now define a mechanism $M$ that works as follows:

$M(x_1, \dots, x_n) = (y_1, \dots, y_n)$, where each $y_i$ is computed as follows:

$ y_i =
\begin{array}{cc}
  \{ &
    \begin{array}{cc}
      q(x_i) & \textrm{with probability } \frac{1+\epsilon}{2} \\
      \neg q(x_i) & \textrm{with probability } \frac{1-\epsilon}{2}
    \end{array}
\end{array}
$

Now we can use the value of $M$ to estimate the value of the counting query $q(x)$.

The expected value of $y_i$ is $\mathbb{E}[y_i] = \epsilon q(x_i) + \frac{1-\epsilon}{2}$.

Now the bit that I do not understand

By Chernoff bound,

$$ \left| \frac{1}{n}\sum_i\frac{1}{\epsilon} \cdot (y_i - \frac{(1-\epsilon)}{2}) - q(x) \right| \lt \mathcal{O}\left(\frac{1}{\sqrt{n}\cdot\epsilon}\right) $$

I assume they used the additive Chernoff bound $ \Pr[X \gt \mu + \epsilon] \leq e^{-2n\epsilon^2}$.

It's not clear to me how they got the last part, since it's also not exactly clear to me how they apply the Chernoff bound.
In particular how they use the expected value of $y_i$ in combination with $x_i$ and the bound.

Could somebody maybe give me a more detailed calculation of how the last statement was calculated?

Thanks in advance!

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$
for all $\lambda>0$. Multiply through by $1/\varepsilon$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x_i)\right| \geq \frac{\lambda}{\epsilon}\right] \leq 2 \cdot e^{-2\lambda^2 n}.$$
Set $\lambda=\sqrt{\log(2/\delta)/2n}$ and substitute in $q(x)=\frac{1}{n}\sum_{i=1}^n q(x_i)$ to get
$$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \geq \frac{\sqrt{\log(2/\delta)}}{\epsilon\sqrt{2n}}\right] \leq \delta.$$
Now "suppress" the $\delta$ parameter using big-O notation to get
$$\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i  - \frac{1-\epsilon}2\right)-q(x)\right| \leq O\left(\frac{1}{\epsilon\sqrt{n}}\right)$$ with high probability, as required.


Does Nisan's pseudo-random generator relativize? Nisan proved in "Psuedorandom Generators for Space-Bounded Computation",
that there exists a pseudo-random generator which "fools" space-bounded computations.
Does this construction hold for every oracle (at least for non-adaptive queries) ?

It depends on whether in your definition of the Oracle TM, the oracle query tape is also bounded to be of logarithmic size: if it is bounded then the PRG fools also L^A for any A too, if it is not bounded then A can contain the list of "pseudorandom strings" and thus L^A will not be fooled.


Relating PAC learning results and abstaining classifiers Quite a few results are available on learning miscellaneous concept classes in the PAC learning framework. I would like to know whether any of these results have been extended in the abstaining classifier setting, where the classifier is allowed to refrain from classifying certain examples under various restrictions. In particular, does abstaining improve accuracy in any way, and if so, can this improvement be quantified?

There is work on this, and abstaining can sometimes help. You might be looking for this paper: Trading Off Mistakes with Don't Know Predictions by Sayedi et al. from the last NIPS.


Literature on alias analysis I am writing my master's thesis in CS and I am working with alias analysis. The thing that I am interested in is intraprocedural, flow sensitive must- and may-alias analysis for Java-like languages.

I am searching for texts that describe the basics of this subject in a detailed way but has been unable to locate anything really suitable.

I have survived a number of text books on compilers and static analysis but not found anything there.

I have found many papers where alias analysis is used, but most of them are focused on the problem to which alias analysis is applied and do not describe the alias analysis algorithms in detail. Others focus on C which is not suitably because of the added complexity of general pointers.

The best text I have found is the paper Compositional Pointer and Escape Analysis for Java Programs by Whaley and Rinard. It is a brilliant paper and a good starting point but it doesn't discuss alias analysis specifically.

The problem seems so general so I expected there to be some canonical algorithms available to solve it.

Does anyone have any pointers to texts on this subject?

There's a very recent survey paper available on Alias Analysis for Object-Oriented Programs.

It will be published in April in the LNCS state-of-the-art volume (gratuitous advertising alert): Aliasing in Object-Oriented Programming:
Types, Analysis and Verification. Lecture Notes in Computer Science, Vol. 7850. Dave Clarke, Tobias Wrigstad, James Noble (Eds.)


Factoring Cartesian bitwise join of bit vectors (This question has been substantially revised in an attempt to word it clearly.)

I am wondering if anyone has seen this problem. Let $[n] = \{1,\ldots,n\}$ for an integer $n$. Consider two finite multisets of bitstrings, $$ A=\{a_i\}_{i\in[r]} \quad\text{and} \quad B=\{b_j\}_{j\in[s]} \;,$$ where each $a_i \in \{0, 1\}^n$ and each $b_j \in \{0, 1\}^n$. We may compute from this a "Cartesian bitwise join" $C$, which is also a multiset of bitstrings $C= \{c_{i,j}\}_{(i,j) \in [r] \times [s]}$ for size $|C| = |A| \cdot |B| = rs$, where
$$ c_{i,j} = a_i \vee b_j$$ where "$\vee$" is bitwise-OR.

Question. If you are given such a multi-set $C$, without any particular indexing, can you find multi-sets $A$ and $B$ of which $C$ is the Cartesian bit-wise join? Equivalently: given a sequence $C = (c_k)_{k\in[m]}$ consisting of bitstrings in $\{0,1\}^n$, can you find sequences $A = (a_i)_{i\in[r]}$ and $B = (b_j)_{j\in[s]}$ such that $m = rs$, and a bijection $\varphi: [r] \times [s] \to [m]$, such that $$c_{\varphi(i,j)} = a_i \vee b_j$$ for all $(i,j) \in [r] \times [s]$?

This problem is equivalent to the following problem. Consider the ring $R$ whose elements are strings in $\{0,1\}^n$, where addition is done bit-wise by the operation $x + y = x \oplus y \oplus 1$ (where $\oplus$ is parity) with $1^n$ being the identity, and multiplication is the bit-wise OR with $0^n$ being the identity. For some particular ordering of the elements of $A$, we may present $A$ as an element of $R^r$, and similarly present $B$ as an element of $R^s$.
The Cartesian bitwise join corresponds to the outer product of $A$ and $B$,
$$ C \;=\; A B^\top \;=\; \begin{bmatrix} a_1 \vee b_1 & a_1 \vee b_2 &\cdots& a_1 \vee b_s \\
a_2 \vee b_1 & a_2 \vee b_2 & \cdots & a_2 \vee b_s \\
\vdots & \vdots & & \vdots \\
a_r \vee b_1 & a_r \vee b_2 & \cdots & a_r \vee b_s
\end{bmatrix}\;,$$
except interpreted as a multiset rather than a matrix (that is, the elements of $C$ are not assigned to particular coefficients of an $r \times s$ matrix). Given a multiset $C$ with composite cardinality $m \in \mathbb N$, can its elements be mapped to coefficients of an $r \times s$ array (such that $m = rs$) which is an outer product of the above form?

(By interchanging 0s and 1s in all of the bitstrings, we may replace the bit-wise OR "$\vee$" with the bit-wise AND "$\wedge$", in which case we may take $R$ to be the ring whose elements are strings in $\{0,1\}^n$, where addition is as vectors over $\mathbb Z_2$, and multiplication is the bit-wise AND. )

One may consider additional constraints on this problem, such as minimum Hamming weight of the bitstrings in $A$ and $B$ (in the Cartesian join formulation). We certainly require that $A,B \ne \{0^n\}$ to prevent a trivial solution.

This problem arises in an EE & complexity theory context. I am looking for other cases or analysis of it.
The problem is somewhat analogous to factoring but does not seem to have a unique factorization.
Note that bitvectors can be naturally modelled as hypergraphs so maybe something from that theory is applicable. I did research hypergraph products but that theory does not seem to apply directly. The problem translates to finding two hypergraphs $H'$ and $H''$ given a hypergraph $H$, such that the $H$ can be formed by taking all pairwise unions of edges in $H'$ and $H''$.

Passing to the dual hypergraphs to look for products.

As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.

Vertices are the elements of $[n]$;
An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x_v = 1$.

(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where

The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and
A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x_e =1$;

— that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge".
This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H_C$ obtained from a multiset $C$ now has a composite number of vertices $m$:  we would like hypergraphs $H_A$ and $H_B$ such that $V(H_C)$ has some particular bijective correspondance with $V(H_A) \times V(H_B)$.

A diagonally restricted tensor product of hypergraphs.

Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.)  The Cartesian bit-wise meet condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H_A) \times V(H_B) \to V(H_C)$$ such that the edge labelled $e \in [n]$ in $H_C$ contains only the vertices $\varphi(a,b) \in V(H_C)$ such that both $a \in V(H_A)$ and $b \in V(H_B)$ are contained in the respective edges labelled by $e$ in $H_A$ and $H_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.

If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the tensor product of graphs, also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H_A) \times E(H_B)$ which contain all vertices $(a,b) \in V(H_A) \times V(H_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H_A \otimes H_B$.
To re-obtain the Cartesian bit-wise join of $H_A$ and $H_B$, we must
restrict to the diagonal edges $(e,e) \in E(H_A) \times E(H_B) =
   [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H_A$ and $H_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are searching for hypergraphs $H_A$ and $H_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.

The resulting reformualtion.

From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:

  Is an edge-labelled hypergraph $H_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (i.e. taking only the diagonally labelled edges) of the tensor product $H_A \otimes H_B$ of two labelled hypergraphs $H_A$ and $H_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?

I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.


Word length using entropy : Maximum entropy criteria The question is based on research paper  titled, Markovian language model of the DNA and its information content
In the supplementary document, the Authors show how they determine the word length of DNA sequence using entropy. A word is a consecutive occurence of DNA symbols. The optimal word length is selected as the one which produces maximum entropy out of all the different length words. But it is not quite clear to me from the plot, if they are using Shannon's entropy rate to plot the curve or just entropy. This is because in the text they mention that the plot is entropy but th formula they have used is of the entropy rate. So, my question is what is the correct way to determine word length using entropy concept.

Consider a toy example for which the implementation in Matlab is given:

A sequence of data of length $N$ can be subdivided into equal sixed blocks each of length (size) $l$. For each block, $w$, we can calculate the entropy known as the block entropy. Considering, entropy calculation by varying the size of the blocks ie., the window size is different. The entropy of the entire sequence is $H_N = 1.99$.  I then create subwords using different sized windows : Window = [1,2,4,6,8,10,12]  This gives Shannon's entropy for each sub-word (block) as

$H_w =   \{H_1 = 1.99119952705784, H_2 = 3.20880064685926, H_4= 4.97725978596446, H_6= 6.10391179247315, H_8= 6.40200948312778,H_{10}=6.44186057426463, H_{12} =  6.45326152085405\}$
 respectively.
Out of these entropy values for each block the maximum entropy value is, maxEntropy = 6.4638 for block of size blksze = 12.

General questions, not specific to topic of DNA or text sequence data : My confusion and questions are

Based on these values of block entropy, is it possible to determine what is the optimal length $l$ of the sequence ? For which value of sequence  length $l <N$ would the entropy of this sequence $H_l$ converge towards the entropy of $H_N$? Please correct me where wrong.
Can entropy of the whole sequence be less than the block size? For equiprobable occurrece of symbols, $H_N \le log2(4)= 2$ this is the theoretical value. But, when the block size 12 I got entropy for $H_{w} = H_{12} = 6.45326152085405$ which is greater than $H_N = 1.99$. I don't know if this result is correct and what I should expect theoretically.
Is my implementation correct? How to infer the plots?

Details:

Consider a source that emits codewords consisiting of adjacent symbols of length $l$. The sequence length is $N > l$. If the source is binary ($n=2$ symbols), then I have $N(w) = n^l$ possible words of length $l$. Each word is associated with a probability and I need to estimate the probability numerically since it is unknown.  Let, $n=4$ and the alphabet set is $A = {1,2,3,4}$.  Let the symbol sequence be $s =[2, 3, 4, 1, 2, 2,1, 3,2, 1, 2, 4,\ldots]' $ and $N$ denotes the number of elements in the sequence.

A block of size $l$ is defined as a segment of $l$ consecutive elements of the symbol sequence or in other words a concatenation of several symbols. If $w$ is  a symbol sequence of size $l$, then $N(w)$ denotes the number of blocks of $s$ which are identical to $w$.

$p(w)$ is the probability that a block from $b$ is identical to a symbol sequence $w$ of size $l$ i.e.
$$p(w) = \frac{N(w)}{n-|w|+1}$$

Let, a symbol sequence of length $N = 10$ be $s = \{1,3,4,1,2,1,1,3,4,2\}$, here the alphabet set is $\mathcal{A} = \{1,2,3,4\}$ and the number of symbols $|\mathcal{A}| = n = 4$. Each symbol can be represented by 4 bits.

Disclaimer: This is based on generic information theory knowledge only. Too long for a comment.

Summary: The pointwise product of your two plots should go to some limit, as the relevant blocklengths and sequence lengths increase.

I don't know if this applies to DNA but in theory if your sequence is ergodic (stationary, and time averages are the same as ensemble averages, for long enough sequences) then the two entropies are related intimately.

The whole point is, if you obtain a "block" entropy $H(X_1,\ldots,X_n)$ for a block of length $n,$ then
$$
\lim_{n\rightarrow\infty} \frac{H(X_1,\ldots,X_n)}{n}=H_0
$$
which is the entropy per symbol, i.e., the entropy rate, what you call shannon entropy as opposed to block entropy.

Now, the question of estimating these is a different question. In fact your program does this by a sliding window technique, which then means that it is averaging overlapping thus dependent samples.

Define the shorthand $X_i^j=(X_i,X_{i+1},\ldots,X_{j})$ where $j\geq i.$ I am sure that under suitable conditions an estimator of the form
$$
\frac{\sum_{k=1}^{n-\ell+1}\hat{H}(X_k^{k+\ell-1})}{n-\ell+1}
$$
where $\hat{H}(X_k^{k+\ell-1})$ is a suitable estimator for block entropy, will converge to a multiple of the entropy rate, i.e., to $\ell \times f$ where $f$ is a correction factor. However, one may need to let $\ell$ grow with $n.$


Extensions of Matrix-Tree Theorem Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a $(0,1)$-matrix with $1$'s at places corresponding to entries where the vertices are adjacent and $0$'s otherwise).

It is known that for a given connected graph $G$ with $n$ labeled vertices, let $λ_1,λ_2,...,λ_{n−1}$ be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of $G$ is $t(G)=\frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}\,$

Now I want to extend it to the steiner tree. A $T$-Steiner tree is a subgraph of $G$ that is a tree and that spans $T$. When $T=V(G)$, a $T$-Steiner tree is a spanning tree. My question is that what is the connection between general $T$-Steiner tree and the Laplacian matrix? So far I didn't find any known results about this extension. Your comments and discussion are welcome.

Let me give a side answer to your question. Consider the variant where you only care about edge-minimal spanning trees: for 2 terminals $s$ and $t$, the problem is equivalent to counting simple $s,t$-paths, which is $\# P$-complete; also, the parameterized version where you ask for paths of length $k$ is $\# W[1]$-hard. If you care about arbitrary $T$-steiner trees (i.e. not necessarily minimal), I expect that it is also $\# P$-hard though I'm not aware of any reference.
These hardness results suggest that it's unlikely to find some "nice formula" for the number of $T$-steiner trees.

The references are: "The complexity of enumeration and reliability problems" by L. G. Valiant, and "The parameterized complexity of counting problems" by J. Flum and M. Grohe.


Two valued variant of subset sum problem I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with smallest sum. This a restricted case of the $k$-way number partitioning problem, which is NP-hard. When $k=2$, one can view this as a variant of the Subset-Sum problem, which is also NP-hard in general.
I'm wondering if the additional restriction of there being only two values in the multiset can be leveraged to design an efficient algorithm, or the problem remains NP-hard even with this restriction. For instance, minimizing the makespan (distribute jobs to machines in order to minimize the largest completion time) is polynomial-time solvable when all jobs are of length 1 or 2.
I am interested in the case where $k$ is not constant. When $k$ is fixed, the problem can be solved using linear programming. Concretely, the problem is:
Given a multiset $S = \{a_1,\dots,a_m\}$, where $a_i\in\{a,b\}$ for $a,b\in\mathbb{Z}^{+}$, and $k\in\mathbb{N}$, compute a $k$-partition $S_1,\dots,S_k$ of $S$ which maximizes $\min_i \sum_{a_j\in S_i} a_j$. I am looking either for an algorithm that runs in time polynomial in $m,k,\log a,\log b$, or a proof of NP-hardness.
Any leads would be appreciated!

Your problem $P$: given a multiset $S = \{a_1, \dots, a_m\}$ of some $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $k \in \mathbb{N}$, what is the $k$-partition $S_1, \dots, S_k$ which maximizes $\min_i \sum_{a_j \in S_i} a_j$.
Definition A "disjoint collection" of subsets of $S$ is a collection of subsets of $S$ that are disjoint. A "disjoint $k$-collection" is a disjoint collection with $k$ subsets.
Consider problem $P'$: given a multiset $S$ of $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?
Claim 1 if we can solve $P'$ in poly-time we can solve $P$ in poly-time.
Proof of Claim 1: We reduce $P$ to $P'$ using binary search. Let $A'$ denote the assumed poly-time algorithm for $P'$.
So we have $S$ and some $k$ as input from $P$. Let $T^*$ denote the optimal minimum-set-sum (the value we're trying to find to answer $P$).
We will call $A'$ with the same $S$ and various $T$s as input.
Let $\tilde{T}$ be the maximal $T \in \mathbb{Z}^+$ for which $A'$ returns a collection of size at least $k$.
We claim that $\tilde{T} = T^*$.
First, let's show $\tilde{T} \le T^*$: to see this, by definition of $\tilde{T}$, note that $A'$ produces a set of at least $k$ subsets each of whom has sum $\ge \tilde{T}$; add the "leftover" elements outside to any subset in the collection; now we have a $k$-partition with each subset having sum $\ge \tilde{T}$. But $T^*$ is the maximal $T$ with this property: so $T^* \ge \tilde{T}$.
Next, let's show $\tilde{T} \ge T^*$: by definition of $T^*$, there is some $k$-partition of $S$ all of whose subsets sum to $\ge T^*$. So if we feed $S$, $T^*$ as input to $A'$, $A'$ will return a collection of size at least $k$. But $\tilde{T}$ is the maximal such $T$, so $\tilde{T} \ge T^*$.
We know that $\tilde{T} = T^*$ lies between $T=1$ and $T=\lfloor (\sum_{a_i \in S} a_i) / k \rfloor \le m_1a + m_2b$.
So to find $\tilde{T}$, we need only $O(\log(m_1a + m_2b))$ calls to $A'$ with binary search: any $T$ for which we get a collection of size $\ge k$ from $A'$ is $\le \tilde{T}$; any $T$ for which we get a collection of size $< k$ from $A'$ is $> \tilde{T}$. $\square$
Now we show (or *claim to show*) that $P'$ can be solved in poly-time:

Problem $P'$: given a multiset $S$ of $m_1$ elements equal to $a \in \mathbb{Z}^+$ and $m_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?
Claim 2 we can solve $P'$ in poly-time.
Let $\ell^*$ denote the size maximal size disjoint collection (we are looking for $\ell^*$ and a disjoint collection that achieves this maximum).
First some definitions:
Definition call multisets consisting of only $a$'s and $b$'s, "$(a, b)$-multisets". Any such multiset can be identified by an ordered pair $(i, j)$ where $i$ denotes the number of $a$'s and $j$ denotes the number of $b$'s.
Definition "$(a,b,T)$-minimal multisets" $(i, j)$ are those $(a,b)$-multisets for which removing any element would bring you to a sum below $T$: i.e. $ai + bj \ge T$, but $a(i-1) + bj < T$ and $ai + b(j-1) < T$. For example, if $a=2$ and $b=5$ and $T=20$, the minimal multisets would be $(10, 0)$, $(8, 1)$, $(5, 2)$, $(3, 3)$ and $(0, 4)$.
Observation: Without loss of generality,  we can assume that the optimal collection of $\ell^*$ subsets of $S$ consists of only $(a, b,T)$-minimal multisets. To see why this is without loss of generality, consider any collection of $\ell^*$ subsets of $S$, each with sum $\ge T$: remove as many elements as you can from each of these subsets, while maintaining the invariant that each must have sum $\ge T$. Once you cannot remove any more, you have a collection of $\ell^*$ $(a,b,T)$-minimal subsets. So indeed it is fine to look only for collections of $(a,b,T)$-minimal multisets.
Note that there are not so many "minimal" $(a,b,T)$-multisets that can be subsets of $S$: we can crudely bound by $\min(m_1, m_2)+1$ (since no two minimal multisets can have either coordinate equal).
Call the actual number of these minimal multisets that are also subsets of $S$ as $M$. Order these $M$ subsets in say lexicographically decreasing order (like we did above), and call them $(i_1, j_1), (i_2, j_2), \dots, (i_p, j_p),\dots, (i_M, j_M)$.
We claim to solve $P'$ in poly-time with a dynamic programming approach (where we'll construct the optimal $\ell^*$ minimal multisets in lexicographically decreasing order):
Our overall problem is to compute the maximum number of disjoint $(i_p, j_p)$s we can find among the base set $S = (m_1, m_2)$.
Let $F(M', m_1', m_2')$ be defined as the maximally sized disjoint collection of $(m_1', m_2')$ you can find, where all the subsets must be one of the lexicographically smallest $M'$ subsets of the $M$ $(a,b,T)$-minimal subsets we identified, i.e. $(i_{M-M'+1}, j_{M-M'+1}), (i_{M-M'+2}, j_{M-M'+2}) ..., (i_M, j_M)$.
We want to find $F(M, m_1, m_2)$.
We have the recurrence $$F(M, m_1, m_2) = 1 + \max_{p=1, 2, \dots, M} F(M-p+1, m_1-i_p, m_2-j_p)$$ and similarly $$F(M', m_1', m_2') = 1 + \max_{p=M-M'+1, \dots, M} F(M-p+1, m'_1-i_p, m'_2-j_p).$$ In each subproblem none of the 3 coordinates ever increase, and always either $m_1'$ or $m_2'$ decreases.
The running time of this dynamic programming is bounded by $O(M (Mm_1m_2)) = O((m_1+m_2)^4)$, as we wanted (strictly, the DP only gives the value of $\ell^*$ and not an achieving disjoint $\ell^*$-collection, but I think an actual optimal solution should be able to be constructed from the DP table as well). $\square$.


How to simulate sequential registers from causal ones? Background: In distributed shared memory (DSM) model, the problem of register simulations/constructions is to simulate registers with certain characteristic out of registers with weaker features. For example, we can construct the strongest multi-writer multi-reader atomic $\texttt{read/write}$ registers from the weakest single-writer multi-reader safe ones [1].

Question:

  Is it possible to simulate sequential registers from causal ones in DSM model? And how to, if possible?

I guess the answer is negative. However, I have no idea how to prove/disprove it (Googling does not help on this).

[1] The Art of Multiprocessor Programming. By Maurice Herlihy and Nir Shavit (Chapter 4)

Answer my own question: The answer is (probably; please let me know if I am wrong) negative: it is impossible to simulate sequential registers from causal registers.

Note: the following proof is indirect. And I am still interested in a direct proof.

  Theorem: It is impossible to simulate sequential registers from causal registers.

Proof: In the thesis [1], Kawash shows that causal consistency memory (with only $\texttt{read/write}$ operations) cannot solve mutual exclusion. However, Lamport's bakery algorithm (wiki), when run on sequential consistency memories, solves mutual exclusion.

[1] Limitations and Capabilities of Weak Memory Consistency Systems by Jalal Y. Kawash, PhD Thesis, 2000.


Combinatorial Independent set Algorithms for sub-classes of perfect graphs As an extension to the question posed recently by Bulatov, I wonder what are the maximal sub-classes of perfect graphs for which we know of combinatorial algorithms to compute a maximum independent set.

One springs to mind and is listed as a maximal subclass in ISGCI, which surprised me: perfect claw-free graphs (a.k.a. perfect quasi-line graphs).  This was done by Minty for all claw-free graphs around 1980.  But a couple of other algorithms for claw-free graphs, one recently in SODA 2011 that is $O(n^3)$ by Faenza, Oriolo, and Stauffer, use the Chudnovsky-Seymour structural characterization of these graphs to reduce the problem to line graphs (and therefore maximum matching) in a fairly straightforward way.  If you're only looking at perfect claw-free graphs, then the earlier characterization by Maffray and Reed is sufficient (and the reduction to line graphs is more obvious).


Newman's lemma for distributional communication complexity This may be obvious — sorry if it is.

Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be converted to one that uses only $O(\log(n/\delta^2))$ public random bits, while preserving the communication complexity and at the price of an additional $\delta$ probability of error.

Adapting the proof, this generalizes readily to $k$-party protocols $f\colon (\{0,1\}^n)^k\to\{0,1\}$, using $O(\log(kn/\delta^2))$ public random bits.

What I couldn't find is the same result for distributional communication complexity (more precisely, for public-coin randomized distributional communication complexity, which may be a rather niche notion (?)). For the worst-case setting, the $n$ factor in the number of public random bits comes from a union bound over all possible $2^{2n}$ joint inputs. In the case of distributional communication complexity, where the input $x,y)$ (or even $(x^{(1)},\dots,x^{(k)})$ comes from a distribution $\mu$ over inputs, does that mean that one can avoid this union bound, and get the conclusion of Newman's lemma with only  $O(1/\delta^2)$ public random bits?

(This seems a bit too good to be true — what am I missing?)

Here is the proof I have in mind:

Let $\mu$ a distribution over $\{0,1\}^n\times\{0,1\}^n$, and $f\colon \{0,1\}^n\times\{0,1\}^n \to \{0,1\}$ the function to compute. Let $\Pi$ be a public-coin protocol computing $f$ with probability at least $1-\varepsilon$ over $\mu$, i.e.,
$$
\mathbb{P}_{(x,y)\sim \mu, r}\{ \Pi(x,y; r) \neq f(x,y) \} \leq \varepsilon
$$
where the probability is taken over the choice of input (drawn from $\mu$) and the public randomness $r$ of $\Pi$.

As in the proof of Newman's lemma, we can assume wlog that $\Pi$ is a uniform distribution over deterministic protocols $\Pi_1,\dots,\Pi_R$ for some $R\geq 0$. Thus,
$$
\mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon
$$
and, if we select uniformly and independently $t = O(1/\delta^2)$ indices $r_1,\dots, r_t\in[R]$, we have with probability at least $9/10$ that
$$
\frac{1}{t}\sum_{i=1}^t \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_i) \neq f(x,y)} \leq \varepsilon + \delta
$$
so that in particular there exists a choice of $t$ indices $r^*_1,\dots, r^*_t\in[R]$ such that
$$
\mathbb{P}_{(x,y)\sim \mu, i\sim[t]}\{ \Pi(x,y; r) \neq f(x,y) \}
= \mathbb{E}_{i\sim [t]} \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r^\ast_i) \neq f(x,y)} \leq \varepsilon+\delta
$$
which yields a public-coin protocol $\Pi^\ast$ with same communication complexity as $\Pi$, using only $O(\log t) = O(\log(1/\delta))$ random bits.

There's nothing wrong in your proof, but you can do even better; by taking the average in

$$
\mathbb{E}_r \mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r) \neq f(x,y)} \leq \varepsilon
$$

you can conclude that there's a single $r_0$ for which

$$
\mathbb{E}_{\mu} \mathbf{1}_{\Pi(x,y; r_0) \neq f(x,y)} \leq \varepsilon.
$$

So in particular, randomized distributional communication complexity is the same as deterministic distributional communication complexity, which explains why it didn't get much attention in the literature...


Application of weak determinantal identities to GCT? In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to satisfy certain identities and therefore by reason $x,y,z$ we get lower bound on permanent or does it reduce to the symmetry characterization also (simply because determinantal identities follow from symmetries)? I am asking this because may be there are identities (I cannot think of one) that need only fewer essential symmetries (other symmetries just follow as consequence) making it easier to prove lower bounds (any superpolynomial lower bound on weaker assumptions can only be good).

Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the fact that the symmetries of the determinant characterize it). Whenever one has some determinantal identities, they can often be massaged into getting equations for the orbit closure of the determinant - the closure of the set of homogeneous polynomials that are linear projections of the determinant. The family of these orbit closures (one for each size $n$) is a natural geometric object capturing the complexity class $\mathsf{VP}_{s}$.

Some work in this direction by Landsberg & Ressayre was reported here (Section 2.2), but I don't know if the actual paper has appeared yet.

A somewhat related paper, which gives some equations that vanish on the determinant orbit closure is:

  Landsberg, Manivel, & Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory program. Comentarii Mathematici Helvetici 88(2):469-484, 2013. (arXiv version)

That paper, as with Mignon-Ressayre, uses the rank of the Hessian, rather than explicitly from a determinantal identity. However, the rank of the Hessian can be seen as closely related to Segre's identity $\det_{n^2}(Hess(\det_n(A)) = (-1)^{\binom{n+1}{2}}(n-1)\det(A)^{n(n-2)}$, which is the identity reportedly used above.

You might also be interested in the following paper, which shows that any reduction from perm to det which respects the symmetries of perm (see the paper for precise definitions) must have exponential blow-up:

  J. M. Landsberg and Nicolas Ressayre. Permanent v. determinant: an exponential lower bound assumingsymmetry and a potential path towards Valiant's conjecture. Differential Geom. Appl., in press,
   2017. (arXiv version)


Complexity of counting the number of edge covers of a graph An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: A Simple FPTAS for Counting Edge Covers and Generating Edge Covers of Path Graphs. However, unless I missed something, they do not provide a reference for this claim, or a proof. (Reference 3 of the first paper seemed promising, but I didn't find what I wanted there either.)

Where can I find a reference or proof of the fact that counting the number of edge covers of a graph is #P-complete?

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems.

EdgeCover is included in the dichotomy theorem in (1).  Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs.  To see this, the expression for EdgeCover as a Holant problem over 3-regular graphs is $\operatorname{Holant}([0,1,1,1])$ (or replace $[0,1,1,1]$ with $[0,1,\dotsc,1]$ containing $k$ 1's for the same problem over $k$-regular graphs).  This $[0,1,1,1]$ notation lists the output of a symmetric function in order of input Hamming weight.  For some subset of the set edges (which we think of as being assigned 1 and the complement set being assigned 0), the constraint at each vertex is that at least one edge is assigned 1, which is exactly what the function $[0,1,1,1]$.  For a fixed subset of edges, its weight is the product of the outputs of $[0,1,1,1]$ at each vertex.  If any vertex is not covered, it contributes a factor of $0$.  If all vertices are covered, then all vertices contribute a factor of $1$, so the weight is also $1$.  Then the Holant is to sum over every possible subset of edges and add the weight corresponding to each subset.  This Holant value is exactly the same if we subdivide every edge and impose the constraint that both incident edges to these new vertices must be equal.  Using the symmetric function notation, this binary equality function is $[1,0,1]$.  This graph is bipartite.  The vertices in one part have the $[0,1,1,1]$ constraint while the vertices in the other part have the $[1,0,1]$ constraint.  The expression for this as a Holant problem is $\operatorname{Holant}([0,1,1,1]|[1,0,1])$.  Then you can check for yourself that row "$[0,1,1,1]$" and column "$[1,0,1]$" of the table near the theorem cited above contains "H", which means the problem is #P-hard even the input graph must be planar.

Side note: Note that Pinyan Lu is an author of both this paper and the first paper you cite.  I am guessing that when their paper says "counting edge covers is
a #P-complete problem even when we restrict the input to 3 regular graphs", they were implicitly citing (1).  They probably didn't mention that the hardness also holds when further restricted to planar graphs since their FPTAS does not need this restriction.

Later Holant dichotomy theorems, such as those in (2,3)---conference and journal versions of the same work---proved more.  Theorem 1 (in both versions) says that EdgeCover is #P-hard over planar $k$-regular graphs for $k \ge 3$.  To see this, we need to apply a holographic transformation.  As described above, the expression for EdgeCover as a Holant problem over $k$-regular graphs is $\operatorname{Holant}([0,1,\dotsc,1])$, where $[0,1,\dotsc,1]$ contains $k$ 1's.  And furthermore, this is equivalent to $\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$.  Now we apply a Holographic transformation by $T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$ (or its inverse, depending on your perspective).  By Valiant's Holant Theorem (4,5), this does not change the complexity of the problem (in fact, both problems are actually the same problem because they agree on the output of every input...only the expression of the problem has changed).  The alternate expression for this problem is

$$
\operatorname{Holant}([1,0,1] T^{\otimes 2}|(T^{-1})^{\otimes k} [0,1,\dotsc,1])
= \operatorname{Holant}([2, e^{\pi i / k}, e^{2 \pi i / k}]|=_k),
$$
where $=_k$ is the equality function on $k$ inputs. To apply Theorem 1, we have to normalize $[2, e^{\pi i / k}, e^{2 \pi i / k}]$ to $[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$ by dividing the original function by $e^{\pi i / k}$, which doesn't change the complexity of the problem since this value is nonzero.  Then the values $X$ and $Y$ in the statement of the theorem are $X = 2$ and $Y = -2^k - 1$.  For $k \ge 3$, one can check that this problem, so thus EdgeCover as well, is #P-hard over planar $k$-regular graphs for $k \ge 3$.

Side note: One can also see this theorem and proof in Michael Kowalczyk's thesis.

I will continue my literature search to see EdgeCover was shown to be #P-hard before (1).

(1) Holographic Reduction, Interpolation and Hardness by Jin-Yi Cai, Pinyan Lu, and Mingji Xia (journal, preprint).

(2) A Dichotomy for $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(3) Partition functions on $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(4) Holographic Algorithms by Leslie G. Valiant

(5) Valiant’s Holant Theorem and matchgate tensors by Jin-Yi Cai and Vinay Choudhary


How good can a halting detector be? Is there a Turing Machine that can decide whether almost all other Turing Machines halt?

Suppose we have some enumeration  $\mathbb{N} \rightarrow \{M_i\}$ of Turing machines, and some notion of "size" of a set of natural numbers $\| \cdot \|$, and we define:

$$f(i) = \|\{n: M_i \text{ can't decide whether }M_n \text{ halts} \}\|.$$

What characterizations of the minimum value of $f$ exist for different $\| \cdot \|$? For instance, suppose $\| S \|$ is the limsup of the proportion of numbers up to $k$ that are in $S$. Is there an $i$ for which $f(i) = 0$?

This isn't a "nice" property, because whether it's true or false depends upon the encoding.

See David et al's Asymptotically almost all $\lambda$-terms are strongly normalizing, which proves what it says in the title. However, this paper also shows that the opposite holds for SKI-combinators (into which lambda-terms can be compositionally embedded).

In the lambda calculus, a reduction is the equivalent of a step of a Turing machine, and strong normalization is the property that every reduction sequence eventually reaches a normal form -- ie, no further reductions are possible. (Since a given lambda-term may have many valid reductions, strong normalization is a bit like saying a given nondeterministic Turing machine always halts.) So the fact that asymptotically almost all $\lambda$-terms are strongly normalizing means that with probability approaching 1, reducing a large lambda terms will always reach a normal form.

However, lambda-terms can be translated in a meaning-preserving way into a combinatory calculus such as the SKI combinators (and vice-versa), and in combinator calculi asymptotically all terms loop.


Check the match of the maximum of each subset Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number.

Question: determine whether, for all subset $I\subseteq \{1, \cdots, n\}$, there is some $T_j$ ($1\leq j\leq m$) such that $\max\{a_i\mid i\in I\}=\max\{b_i^j\mid i\in I\}$.

Obviously there is an exponential time algorithm to do this (one can just enumerate all $I$), but can we do better to have a polynomial-time algorithm? or is it NP-hard?

Example: $S=(1,2,0)$, $T_1=(2,1,0)$, $T_2=(2,0,1)$, $T_3=(1,0,2)$, $T_4=(0,2,1)$ gives an affirmtive answer.

Motivation: this question is from database research, the background of which is a bit hard to describe precisely here.

You can do the following. For every $i\in\{1,\dotsc,n\}$, start with the set $I=\{k\,:\,a_k\leqslant a_i\}$. Let $K=\{k\,:\,\exists j\ b_k^j=\max\{b^j_\ell\,:\,\ell\in I\}=a_i\}$. If $K=\emptyset$, then $I$ is a counterexample. If $i\in K$ then there is no counterexample with $i\in I$ and $a_i=\max\{a_k\,:\,k\in I\}$. If $K\neq\emptyset$ and $i\not\in K$ then any counterexample $J$ with $i\in J$ and $a_i=\max\{a_k\,:\,k\in J\}$ will be a subset of $I\setminus K$. So we can replace $I$ by $I\setminus K$, and iterate.

It is necessary and sufficient that for every $i$ we end up with $i\in K$.


Does $NP=PP$ collapse the counting hierarchy? Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is

Theorem If $NP=PP$ then $PH^{PP}=NP$.

Proof $PP$ is closed under complement (due to Gill), so $NP=coNP=PH$. Take any level of $PH^{PP}$: then $\Sigma_i^{P^{PP}}=\Sigma_i^{P^{NP}}=\Sigma_{i+1}^{P}=NP$. $\square$

One plausible-looking way to get to the desired consequence is by observing that in this world, the interactive proof protocol for the $\textsf{Permanent}$ has been derandomized and de-Merlinized to the point where one message to Arthur has perfect completeness and soundness (as $NP=P^{\#P}$ under the hypothesis). If you can exploit this fact and compute the Permanent in some class that's low for $PP$, such as $UP$ or $BQP$ or $SPP$, we're done. That would give us $NP=PP\implies PP=UP$ (for example), which would immediately give $PP^{PP}=PP^{UP}=PP=NP$.

(This came up in my thesis, where I investigate the hypothesis $QMA=PP$, and it also came up when trying to fix Scott Aaronson's broken theorem $PP\subset BQP_{/qpoly}\implies CH=PP=QMA$, Theorem 5 in Oracles are Subtle but not Malicious).

We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP closed under complement. This implies $\mathrm{CH=NP}$.


$\mathcal{MA}$ in terms of $\mathcal{PCP}$ The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of the proof certificate sent by Merlin (see, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP).

However,  In 1990 Babai, Fortnow, and Lund proved that $\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$, so its not exactly a restriction. What are the parameters ($f(n),g(n)$) for which $\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$?

If you want to restate the definition of MA in terms of PCP, you need another parameter for PCP, namely the proof length.  MA is clearly the same as PCP with polynomial randomness, polynomial queries, and polynomial-length proofs.  Usually the proof length in PCP is not restricted (that is, it is bounded only implicitly by randomness and queries), but this is insufficient to restate the definition of MA.

If you are looking for some characterization of the form MA = PCP(q(n), r(n)), which is not just the restatement of the definition of MA, then I do not think that any such characterization is known.


Fast Reduction from RSA to SAT Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention:

  Build a public library of 3SAT instances, with as few variables and clauses as possible, that would have noteworthy consequences if solved.  (For example, instances encoding the RSA factoring challenges.)  Investigate the performance of the best current SAT-solvers on this library.

This triggered my question: What's the standard technique for reducing RSA/factoring problems to SAT, and how fast is it? Is there such a standard reduction?

Just to be clear, by "fast" I don't mean polynomial time. I'm wondering whether we have tighter upper bounds on the reduction's complexity. For example, is there a known cubic reduction?

One approach to encode Factoring (RSA) to SAT is to use multiplicator circuits (every circuit can be encoded as CNF).
Let's assume we are given an integer $C$ with $2n$ bits, $C=(c_1,c_2,\cdots,c_{2n})_2$. We are interested in finding two $n$-bit integers $A=(a_1,\cdots,a_n)$ and $B=(b_1,\cdots,b_n)$ whose product is $C=A*B$.
The most naive encoding can be something like this; we know that:
$$c_{2n}= a_n \land b_n$$
$$c_{2n-1}= (a_n\land b_{n-1}) xor (a_{n-1}\land b_n)$$
$$Carry:d_{2n-1}= (a_n\land b_{n-1}) \land (a_{n-1}\land b_n)$$
$$c_{2n-2}= (a_n\land b_{n-2}) xor (a_{n-1}\land b_{n-1}) xor (a_{n-2}\land b_{n}) xor d_{2n-1}$$
...
Then using Tseitin transformation, the above encoding can be translated into CNF.
This approach produces a relatively small CNF. But this encoding does not support "Unit Propagation" and so, the performance of SAT Solvers are really bad.
There are other circuit for multiplication which can be used for this purpose, but they produce a larger CNF.


Complexity class of phase information in Gauss sum Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?

Actually I was looking for something more than the answers given. It is known Gauss sums have a random walk behavior than is exploited in designing low-correlation sequences. Also Montogomery's conjecture provides a tighter bound than the Weil bounds of Deligne under the assumption of random behavior (deeper exposition in the book by Katz and Sarnak - the material of which I am not familiar). I was actually curious whether such randomness has been utilized in computer science. It seems very possible there are uses.

See Efficient Quantum Algorithms for Estimating Gauss Sums by Wim van Dam and Gadiel Seroussi.

They have a nice introduction to the computational problem of estimating Gauss sums over finite fields and finite rings. They carefully explain how the computational problem is specified, how the characters are specified in the input and what the input size is.

They show how to estimate the phase of a Gauss sum to inverse polynomial accuracy in polynomial time on a quantum computer. They then show that this problem is classically hard assuming discrete log is hard.


Vertex-disjoint paths in sparse graphs I'm looking for a graph $G$ on $n$ vertices with the following properties

G doesn't have too many edges, $O(nlog(n))$ or $O(n)$ would be perfect
For random k disjoint pairs of vertices $(s_i,t_i)$ there is a path that links $s_i$ to $t_i$ for each $i$ such that all of these paths are vertex-disjoint. This statement should be true with high probability p.

The goal is to find $G$ such that $k$ is maximal. I'm not very precise on $k$ and the number of edges as well as on p (but let's say large constant p is fine or even better something that goes to 0 with n) because I don't know what is possible.

EDIT: I rephrased the question in terms of average case instead of worst case since worst case won't give many vertex-independent paths as pointed out by Chandra Chekuri.

Thanks,
André.

A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log_2 n+1}{2}$:

S. Madhavapeddy, and I. H. Sudborough, "A topological property of hypercubes: node disjoint paths", Proc. IEEE SPDP, 532-539, 1990.


What does one mean by heuristic statistical physics arguments? I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a simple toy example of such a phenomenon?

It would be good if the answer assumed little background in statistical physics and could explain what these mysterious heuristics are and how they can be informally justified.  Also, perhaps someone can indicate the broad picture of how much of these heuristics can be rigorously justified and how the program of Lawler, Schramm and Werner fits into this.

The second paragraph of RJK's response deserves more detail.

Let $\phi$ be a formula in conjunctive normal form, with m clauses, n variables, and at most k variables per clause. Suppose we want to determine if $\phi$ has a satisfying assignment.  Formula $\phi$ is an instance of the k-SAT decision problem.

When there are few clauses (so m is quite small compared to n), then it is almost always possible to find a solution.  A simple algorithm will find a solution in roughly linear time in the size of the formula.

When there are many clauses (so m is quite large compared to n), then it is almost always the case that there is no solution.  This can be shown by a counting argument.  However, during search it is almost always possible to prune large parts of the search space by means of consistency techniques, because the many clauses interact so extensively.  Establishing unsatisfiability can then usually be done efficiently.

V. Chvátal and B. Reed. Mick gets some (the odds are on his side), FOCS 1992. doi: 10.1109/SFCS.1992.267789

In 1986 Fu and Anderson conjectured a relationship between optimisation problems and statistical physics, based on spin glass systems.  Although they used sentences like

  Intuitively, the system must be sufficiently large, but it is difficult to be more specific.

they do actually give specific predictions.

Y Fu and P W Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A. 19 1605, 1986. doi: 10.1088/0305-4470/19/9/033

Based on arguments from statistical physics, Zecchina and collaborators conjectured that k-SAT should become hard when $\alpha = m/n$ is near a critical value.  The precise critical value depends on k, but is in the region of 3.5 to 4.5 for 3-SAT.

Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky.  Determining computational complexity from characteristic `phase transitions', Nature 400 133–137, 1999.  (doi: 10.1038/22055 , free version)

Friedgut provided a rigorous proof of these heuristic arguments.  For every fixed value of k, there are two thresholds $\alpha_1 < \alpha_2$.  For $\alpha$ below $\alpha_1$, there is a satisfying assignment with high probability.  For a value of $\alpha$ above $\alpha_2$, formula $\phi$ is unsatisfiable with high probability.

Ehud Friedgut (with an appendix by Jean Bourgain), Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 1017–1054, 1999. (PDF)

Dimitris Achlioptas worked on many of the remaining issues, and showed that the above argument holds for constraint satisfaction problems, too.  These are allowed to use more than just two values for each variable.  One key paper shows rigorously why the Survey Propagation algorithm works so well to solve random k-SAT instances.

A. Braunstein, M. Mézard, R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms 27 201–226, 2005. doi: 10.1002/rsa.20057
D. Achlioptas and F. Ricci-Tersenghi, On the Solution-Space Geometry of Random Constraint Satisfaction Problems,
STOC 2006, 130–139. (preprint)


Reference needed for lower bound on number of guards in three-dimensional art gallery guarding During my research (writing my master's thesis) I've stumbled across the book Art Gallery Theorems and Algorithms by O’Rourke.
In chapter 10 (pdf available on the above site), section 10.2.2. he shows a lower bound of $\Omega\left(n^{3/2}\right)$ on the number of guards needed in three-dimensional art gallery guarding. He says (bold marking is by myself):

  In fact, we describe in this section a polyhedron constructed by Seidel that has these two properties.

I believe that the construction, as presented in the book, is not fully correct and thus I tried to find the original work by Seidel.
Sadly there is no reference in this section and the only reference in the book with Seidel is Constructing Arrangements of Lines and Hyperplanes with Applications by H. Edelsbrunner, J. O’Rourke, and R. Seidel which does not include the construction.

I have looked through Seidels Google Scholar page but there seems to be nothing relevant.

Do you have a source or know anything more about this construction?
What could be a good and accepted way for me to obtain information? Contacting either of the two?

To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else.

In one of his papers, Seidel even refers to O'Rourke's book for a description of his own construction. He writes on top of page 253 of his joint paper with Jim Ruppert:
"In his book [9, p. 255] O'Rourke describes n-vertex three-dimensional polyhedra that require $\Omega(n^{3/2})$ guards."

  Jim Ruppert, Raimund Seidel: On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete & Computational Geometry 7: 227-253 (1992)


Applicability of Church-Turing thesis to interactive models of computation Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere.  That is, it is presented as encompassing all computation when in fact it applies only to computation of functions, which is a very small subset of all computation.  Instead they suggest we should seek to model interactive computation, where communication with the outside world happens during the computation.

The only critique I have seen of this work is in the Lambda the Ultimate forum, where somebody lamented these authors for continually publishing what is obviously known.  My question then is, is there any more critique into this line of thinking, and in particular their Persistent Turing Machines.  And if not, why then is it seemingly studied very little (I could be mistaken).  Lastly, how does the notion of universality translate to an interactive domain.

Here's my favorite analogy.  Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread.  Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.

You might say: sure, I have a "point", but it's a totally uninteresting one.  No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals.  If you want a TM to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster's internal logic (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!).  In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer.  In neither case are we saying anything that wouldn't have been obvious to Turing himself.

So, I'd say the reason why there's been no "followup" to Wegner and Goldin's diatribes is that TCS has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.

Update (8/30): A related point is as follows.  Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing's notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?

Another Update: To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question.  What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code?  Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?  To clarify, the Church-Turing Thesis is not the claim that "TURING MACHINEZ RULE!!"  Rather, it's the claim that any reasonable programming language will be equivalent in expressive power to Turing machines -- and as a consequence, that you might as well think in terms of the higher-level languages if it's more convenient to do so.  This, of course, was a radical new insight 60-75 years ago.

Final Update: I've created a blog post for further discussion of this answer.


Multiple-sources dominator trees: compact representation and fast algorithm? I recently learnt about the concept of dominator trees and was fascinated by it.

I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in the graph as sources: can all-sources dominators be represented more compactly than in O(n^2) space and computed more efficiently than running the classic dominator tree algorithm from every vertex?

I tried searching for keywords like "multiple sources dominators" etc, but only found about "multiple-vertex dominators", which are a different thing (dominating sets of size > 1)

Does any of this become simpler if the graph is acyclic? (in fact, I work at Google and I think it'd be fun to apply this to the huge dependency graph of Google's build targets)

I think it's really hard to do that. First of all, for one source dominator tree, there are several dominator points for a vertex. If we want to use "Lengauer-Tarjan algorithm", we can't avoid using tree structure. But how can we save a tree with less than $o(n)$ space? It means that for $n$ source dominator tree, we have to use at least $o(n^2)$ space unless we create a new structure which can represent dominator's information more effective.

For a dag, I remember there is a another algorithm to find whether two vertices share the same dominator for one source. Maybe it will help, you may search uva12671 for more information. (Actually, I am thinking a developing problem about this recently.)

Finally, I am also fascinated by it. If anybody has a new idea, please contact me anytime.


"Almost all objects have property P" vs. "It is easy to test whether an object has property P" I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".

My guess is that they are completely separate (that is, one doesn't imply the other). Am I missing something?

(Note: Almost all in the sense of probability)

PS: I am not sure whether the tag probability is appropriate here, sorry.

They are separate (assuming $P \ne NP$).  Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT.  It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.


Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST The paper in question is "On the Usefulness of Predicates", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]).

On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an additional accepting predicate of all $1$'s. The claim is that this predicate can be shown approximation resistant with Theorem 8.3, which requires that $P$ accept all strings $x_1 x_2 x_3 x_4$ such that $\prod_1 ^3 x_i = -1$ and $x_3 = -x_4$.

In particular, $P$ should accept $(1,1,-1,1)$ but the definition of $GLST$ provided requires that $x_2 \ne x_4$.

Following Emil's suggestion and using trial and error, define $P'(x_1, x_2, x_3, x_4) \equiv P(-x_1, x_2, x_3, x_4)$

Instances of $\text{CSP}(P')$ are isomorphic to instances of $\text{CSP}(P)$, via adding a negation in every constraint where $x_1$ appears. Then we apply the theorem on $P'$ after checking that the $\{3,4\}$ fourier coefficient is still positive. We can conclude $P'$ is resistant and therefore $P$ is as well.


Maximum number of geometrically disjoint paths - is the complexity known? Let $G$ be an undirected  graph, given with a planar drawing.
We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct point in the plane, and each edge is represented by a continuous planar curve between its endpoints. Assume that no other vertex can lie on such a curve, but we allow unlimited intersections among these edge-curves.

Let $s,t$ be two distinguished vertices in $G$. We say that two $s-t$ paths are geometrically disjoint, (with respect to the given drawing), if their geometric representations  do not share any point, other than $s$ and $t$. Note that it is a stronger requirement than being (internally) vertex disjoint in the graph theoretic sense, because they may be vertex disjoint, yet they may share some intersection point of the curves that represent the edges, when we follow through the paths as geometric curves.

Questions:

What is the complexity of finding the maximum number of geometrically disjoint $s-t$ paths?
How about the special case when the edges are restricted to be straight lines?

Remark: Finding the max number of vertex- or edge-disjoint paths is well known to be solvable by network flow techniques in polynomial time. Does the geometric requirement make the problem harder?

Edit: Let us assume that the vertices have polynomially bounded integer coordinates, in terms of the number of vertices. Furthermore, assume an oracle is available that can determine for any two edge-curves whether they intersect or not. When the edges are represented by straight lines, this is straightforward, but in the general case it may be hard to decide whether two curves intersect.

The following paper establishes NP-hardness of essentially all non-trivial questions in this direction:

  Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril:
  Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math. 4(2): 223-244 (1991)


The cozy neighborhoods of "P" and of "NP-hard" Let $X$ be an algorithmic task. (It can be a decision problem or an optimization problem or any other task.) Let us call $X$ "on the polynomial side" if assuming that $X$ is NP-hard is known to imply that the polynomial hieararchy collapses. Let us call $X$ "on the NP-side" if assuming that $X$ admits a polynomial algorithm is known to imply that the polynomial hierarchy collapses.

Of course, every problem in P is on the polynomial side and every problem which is NP-hard is in the NP-side. Also, for example, factoring (or anything in NP intersection coNP) is on the polynomial side. Graph isomorphism is on the polynomial side. QUANTUM-SAMPLING is in the NP-side.

1) I am interested in more examples (as natural as possible) of algoritmic tasks in the polynomial side and (especially) in more examples in the NP side.

2) Naively it looks that the NP side is a sort of a "neighborhood" of the NP-hard problems, and the P-side is a "neighborhood of P".  Is it a correct insight to regard problems in the NP side as "considerably harder" compared to problems in the P side. Or even to regard problems in the NP side as "morally NP-hard?"

3) (This might be obvious but I don't see it) Is there an $X$ on both sides or are there theoretical reasons to believe that such an $X$ is unlikely. Update The answer is YES; see Yuval Filmus' answer below.

(If these "sides" are related to actual complexity classes and if I miss some relevant cc jargon or relevant results please let me know.)

Update: There are by now several very good answers to the question. As noted first by Yuval Filmus and mentioned again the question is not formal and some restriction on the argument showing that X is on the P-side/NP-side is needed. (Otherwise, you can have X to be the task of presenting a proof for 0=1 which is on both sides.) Putting this aside, it may be the case that problems X (genuinly) on the NP-side capture somehow the hardness of SAT, although this may also be the case for some problems on the P-side where the hardness of SAT is weakened (even slightly) in a provable way. Yuval Filmus gave a weakened version of SAT which is on both sides. Andy Drucker gave (in two answers) five interesting examples including a reference to Schöning's Low and High hierarchies, and Scott Aaronson gave further interesting examples, mentioned the question of inverting a one-way function which is close to capture NP hardness and yet on the P-side,  and his answer also discusses the interesting case of QUANTUMSAMPLING. I metioned an old result of this kind by Feige and Lund.

The very terms "on the P-side" and "on the NP-side," and of course the question title, encourage us to imagine a "cozy neighborhood" surrounding P and another "cozy neighborhood" surrounding the NP-hard problems.  However, I'd like to argue that these two neighborhoods are not so "cozy" at all!

As a first observation, there are problems "on the P-side" that seem "morally" much closer to NP-hard than to P.  One example, anticipated by Gil of course, is the general problem of inverting one-way functions (depending on exactly what type of reductions are allowed; see Bogdanov-Trevisan or Akavia et al.).

Conversely, there are also problems "on the NP-side" that seem "arbitrarily far" from being NP-hard.  One silly example is a random language L, with probability 1 over L!  For if such an L is in P, then 0=1 and math is inconsistent, and therefore PH collapses also. ;-D

(Note that a random language L is also "on the P-side," with probability 1 over L.  For almost all such L's have the property that if they're NP-hard, then NP⊆BPP and PH collapses.  And this gives a proof, much simpler than the appeal to Ladner's Theorem, that there exist languages on both "sides."  Indeed, it shows that of the uncountable infinity of languages, "almost all" of them -- in fact, 100% -- are on both sides!)

This sounds like juvenile game-playing, but there's a serious lesson I'd like to draw from it.  I'd argue that, even though QUANTUM SAMPLING is formally "on the NP-side," that problem is barely any closer to being "morally NP-hard" than the random language L was.  Arkhipov and I (and independently, Bremner-Jozsa-Shepherd) showed that, if QUANTUM SAMPLING is in P (or rather, in SampBPP, the class of polynomially-solvable sampling problems), then P#P = BPPNP, and therefore the polynomial hierarchy collapses.  Yet if you're a BPP machine, an oracle for BosonSampling would, as far as we know, bring you no closer to solving NP-complete problems than a random oracle would.  Only if you already have the ability to solve NP-complete problems -- say, if you're a BPPNP machine -- do you "notice" that the BosonSampling oracle boosts your capabilities even further, to #P.  But the property of boosting NP up to #P seems different than, and maybe even "orthogonal to," the property of being NP-hard on one's own.

Incidentally, a wonderful open problem suggested by Gil's question is whether BosonSampling is also "on the P-side."  That is, can we show that if NP reduces to BosonSampling then PH collapses?  While I might be missing something obvious, at first glance I have no clue how to prove such a thing, any more than I know how to prove the stronger implication that if NP ⊆ BQP then PH collapses.


Problems of similar complexity for different measures It is a common belief that $\mathbf{P}\subsetneq\mathbf{PSPACE}$, thus (most likely) there are problems that are "harder" for time than for space. But is there a problem in $\mathbf{P}$ with a poly-space lower bound (say for multi tape TM), i.e. is there a space-hard problem in $\mathbf{P}$?

Similarly, is there a problem in $\mathbf{P}$ with a good non-deterministic time lower bound? Is there a problem in $\mathbf{NP}$ with poly-space lower bound? ...

The answer to the first question is that we don't know, because we don't know whether $\mathbf P=\mathbf L$, so it could be that all $\mathbf P$ problems use only logarithmic space.

For the second one, most reasonable problems need at least linear time to read the input, even for non-deterministic machines, so it does not make a lot of sense to say "polynomial non-deterministic lower bound", or you need to make your question more precise.

Finally, the last question is like the first one: it could be that $\mathbf{NL}=\mathbf{NP}$, in which case such a problem wouldn't exist, we don't know...


Which randomized algorithms have exponentially small error probability? Suppose that a randomized algorithm uses $r$ random bits. The lowest error probability one can expect (falling short of a deterministic algorithm with 0 error) is $2^{-\Omega(r)}$. Which randomized algorithms achieve such minimal error probability?

A couple of examples that come to mind are:

Sampling algorithms, e.g., where one wants to estimate the size of a
set for which one can check membership. If one samples uniformly at
random the elements to check, the Chernoff bound guarantees an
exponentially small error probability.
The Karger-Klein-Tarjan algorithm for computing minimum spanning tree. The algorithm picks each edge with probability 1/2, and recursively finds the MST in the sample. One can use Chernoff to argue that it's exponentially unlikely there'll be 2n+0.1m of the edges that are better than the tree (i.e., one would prefer to take them over one of the tree edges).

Can you think of other examples?

Following Andras' answer below: Indeed, every polynomial time algorithm can be converted to a slower polynomial time algorithm with exponentially small error probability. My focus is on algorithms that are as efficient as possible. In particular, for the two examples I gave there are deterministic polynomial time algorithms that solve the problems. The interest in the randomized algorithms is due to their efficiency.

Impagliazzo and Zuckerman proved (FOCS'89, see here) that if a BPP algorithm uses $r$ random bits to achieve a correctness probability of at least 2/3, then, applying random walks on expander graphs, this can be improved to a correctness probability of $1-2^{-k}$, using $O(r+k)$ random bits. (Note: while the authors use the specific constant 2/3 in the abstract, it can be replaced with any other constant greater than 1/2.)

If we take $k=r$, this means  that any BPP algorithm that achieves a constant error probability $< 1/2$, using $r$ random bits,  can be (non-trivially) improved to have error probability $2^{-\Omega(r)}$. Thus, (unless I misunderstood something), the error probability of $\leq 2^{-\Omega(r)}$ is achievable for every problem in BPP.


What is the difference between arrows and exponential objects in a cartesian closed category? In a Cartesian Closed Category (CCC), there exist the so-called exponential objects, written $B^A$.  When a CCC is considered as a model of the simply-typed $\lambda$-calculus, an exponential object like $B^A$ characterizes the function space from type $A$ to type $B$.  An exponential object is introduced by an arrow called $curry : (A \times B \rightarrow C) \rightarrow (A \rightarrow C^B)$ and eliminated by an arrow called $apply : C^B \times B \rightarrow C$ (which unfortunately called $eval$ in most texts on category theory).  My questions here is: is there any difference between the exponential object $C^B$, and the arrow $B \rightarrow C$?

One is internal and the other is external.

A category $\mathcal{C}$ consists of objects and morphisms. When we write $f : A \to B$ we mean that $f$ is a morphism from object $A$ to object $B$. We may collect all morphisms from $A$ to $B$ into a set of morphisms $\mathrm{Hom}_{\mathcal{C}}(A,B)$, called the "hom-set". This set is not an object of $\mathcal{C}$, but rather an object of the category of sets.

In contrast, an exponential $B^A$ is an object in $\mathcal{C}$. It is how "$\mathcal{C}$ thinks of its hom-sets". Thus, $B^A$ must be equipped with whatever structure the objects of $\mathcal{C}$ have.

As an example, let us consider the category of topological spaces. Then $f : X \to Y$ is a continuous map from $X$ to $Y$, and $\mathrm{Hom}_{\mathsf{Top}}(X,Y)$ is the set of all such continuous maps. But $Y^X$, if it exists, is a topological space! You can prove that the points of $Y^X$ are (in bijective correspondence with) the continuous maps from $X$ to $Y$. In fact, this holds in general: the morphisms $1 \to B^A$ (which are "the global points of $B^A$") are in bijective correspondence with morphisms $A \to B$, because
$$\mathrm{Hom}(1, B^A) \cong
\mathrm{Hom}(1 \times A, B) \cong
\mathrm{Hom}(A, B).
$$

Sometimes we get sloppy about writing $B^A$ as opposed to $A \to B$. In fact, often these two are synonyms, with the understanding that $f : A \to B$ might mean "oh by the way here I meant the other notation, so this means $f$ is a morphism from $A$ to $B$." For example, when you wrote down the currying morphism
$$\textit{curry}: (A \times B \to C) \to (A \to C^B)$$
you really should have written
$$\textit{curry}: C^{A \times B} \to {(C^B)}^A.$$
So we cannot really blame anyone for getting confused here. The inner $\to$ is used in the internal sense, and the outer in the external.

If we work in simply typed $\lambda$-calculus then everything is internal, so to speak. We have just a basic typing judgment "$t$ has type $B$", written as $t : B$. Because here $B$ is a type, and types correspond to objects, then we clearly have to interpet any exponentials and arrows in $B$ in the internal sense. So then, if we understand
$$\textit{curry}: (A \times B \to C) \to (A \to C^B)$$
as a typing judgment in the $\lambda$-calculus, all arrows are internal, so this is the same as
$$\textit{curry}: ((C^B)^A)^{C^{A \times B}}.$$
I hope by now it is clear why people use $B^A$ and $A \to B$ as synonyms.


Epsilon-closure and DFA minimization algorithms for probabilistic NFA Are there any algorithms performing e-closures and DFA minimizations for probabilistic Finite Automata? Given that probabilistic NFAs might have multiple accepting paths for generating equivalent strings with different probabilities, do current minimization algorithms allow to reduce such amount of complexity to generating just one string with given fixed probability?
I am aware of e-closure and DFA minimization for standard Finite Automata, but I was able to find no paper/algorithm for automata with probabilities.

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


Pre order traversal of an array I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?

I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.

I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.

By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.

With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).


NP-hardness of a graph partition problem? I'm interested in this problem: Given an undirected graph $G(E, V)$, Is there a partition of $G$ into graphs $G_1(E_1, V_1)$ and $G_2(E_2, V_2)$ such that $G_1$ and $G_2$ are isomorphic?

Here $E$ is partitioned into two disjoint sets $E_1$ and $E_2$. Sets $V_1$ and $V_2$ are not necessarily disjoint. $E1∪E2=E$ and $V1∪V2=V$.

This problem is at least as hard as Graph Isomorphism Problem. I guess it is harder than Graph Isomorphism but not NP-hard.

  Is this partition problem $NP$-hard?

EDIT 3-3-2012: Posted on MathOverflow.

EDIT 3-5-2012: It turns out that the reference in Diego's answer is one of the unpublished results. After some digging, I found a reference to it in The NP-Completeness Column: An Ongoing Guide by David JOHNSON (page 8). I found other papers  that cite the NP-completeness result of Graham and Robinson as unpublished.

I've found that this problem is NP-hard, even restricted to trees.
The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.


How are new probabilities computed when simulating measurement on a set of qubits? Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure:

|000> -> a
|001> -> b
|010> -> c
|011> -> d
|100> -> e
|101> -> f
|110> -> g
|111> -> h

With it holding that a^2 + b^2 ... h^2 = 1.

a) Now suppose I wanted to measure the third qubit. Would it be valid to generally take the probability of the measurement being 0 as a^2 + c^2 + e^2 + g^2?

b) Assume I had measured the third qubit as 0. How would I construct a new probability distribution across my remaining 2 qubits:

|00> -> w
|01> -> x
|10> -> y
|11> -> z

Where w, x, y and z are computed from a, b ... h

Thank you in advance for any guidance you can give me!

Let
$$P(0) = |a|^2 + |c|^2 + |e|^3 + |g|^2.$$
This is the probability of observing $0$.

Then
\begin{eqnarray*}
w &=& a \big/ \sqrt{P(0)}, \\
x &=& c \big/ \sqrt{P(0)}, \\
y &=& e \big/ \sqrt{P(0)}, \\
z &=& g \big/ \sqrt{P(0)}.
\end{eqnarray*}


Reynolds: "the basic laws of variable binding" I recently came across this passage in an article by John Reynolds (emphasis added):

  ...from designers innocent of the principles of programming language design, we have been given a nearly endless succession of “input formats” that seem to be designed to encourage error. (Flawed macro facilities that violate the basic laws of variable binding are particularly prominent examples.)

I was happy to come across the phrase in italics because for some time now I've been aware of having precisely this deficiency, but not knowing what to call it, and therefore failing repeatedly at finding a way to remedy it.

Can someone point me to where I can learn about these "basic laws of variable binding"?

See chapter 1 of Robert Harper's book Practical Foundations of Programming Languages. He formalizes syntax with binding operators using the notion of "abstract binding trees", which IIRC were originally introduced in the Nuprl proof assistant. The main keyword you need to find further information is "alpha-equivalence".


Language and automata textbook, free or low cost? I'll be teaching a standard undergraduate class on languages and automata next semester, and would prefer to use a legitimate free or low-cost text. Any suggestions?

I love the Sipser text but the latest edition costs $196, which is hard to say with a straight face in the age of free courses.

Maheshwari and Smid's Introduction to Theory of Computation is free, with a Creative Commons license. It has some computability and complexity theory as well but seems to be primarily on languages and automata.


Reference request: Skeptics of classical threshold theorem Early classical computing had skeptics, or at least cautious researchers, that were skeptical reliable computing results were possible. Scott Aaronson references this in a page on his site:

A: The only reason we don't need fault-tolerance machinery for classical computers is that the components are so reliable, but we haven't been able to build reliable quantum computer components yet. Presumably, if we could build extremely reliable components, we wouldn't need error correction and fault-tolerance technology.
Scott: Yes, that's what I would say. In the early days of classical computing, it wasn't clear at all that reliable components would exist. Von Neumann actually proved a classical analog of the Threshold Theorem, then later, it was found that we didn't need it. He did this to answer skeptics [emphasis mine] who said there was always going to be something making a nest in your JOHNNIAC, insects would always fly into the machine, and that these things would impose a physical limit on classical computation. Sort of feels like history's repeating itself.

source (And here is a related question about where that paper first appeared).
My request is for published research article (references) that are skeptical classical fault tolerant computing is possible, or names of individuals advocating for skepticism at the time.

It has been a while since I read von Neumann's paper, but I don't recall having the same impression that Scott Aaronson had. It seemed to me that von Neumann was addressing an argument that human brains must be qualitatively different from computers, because while human brains' individual components, neurons, are unreliable, human brains on a whole are much more reliable than electronic computers are.

While Claude Shannon does not actually make this argument explicitly in his 1953 paper "Computers and Automata" (it's quite possible other people did), he certainly brings up the question of reliability and brains. I have extracted a few sentences below:

  The brain has often been compared, perhaps overenthusiastically,
  with computing machines.
  ...
  Comparisons of this sort should be taken well salted—our understanding of brain functioning is still, in spite
  of a great deal of important and illuminating research,
  very primitive.
  ...
  The similarities between the brain and computers
  have often been pointed out. The differences are perhaps
  more illuminating, for they may suggest the important
  features missing from our best current brain
  models. Among the most important of these are:
  ...
  3. Differences in reliability organization. The brain
  can operate reliably for decades without really serious
  malfunctioning (comparable to the meaningless
  gibberish produced by a computer in trouble
  conditions) even though the components are probably
  individually no more reliable than those used
  in computers.


Hyperdoctrines and Monadic Second Order Logic This question is essentially the question I asked on Mathoverflow.

Monadic Second Order (MSO) logic is second order logic with quantification over unary predicates. That is, quantification over sets. There are several MSO logics that are fundamental to structures studied in computer science.

Question 1. Is there a categorical semantics for Monadic Second Order Logics?

Question 2. Treatments of categorical logic often talk about "higher order intuitionistic logic." Am I right to assume that they are referring to higher order functions, rather than quantification over second order predicates?

Question 3. (Added, 08 Nov 2013, after Neel's answer) My understanding of first-order quantification (in terms of the presentation of Pitts mentioned below) is that it is defined with respect to the pullback $\pi^*$ of a projection morphism $\pi$. Specifically, universal quantification is interpreted as the right adjoint of $\pi^*$ and existential quantification is interpreted as the left adjoint of $\pi^*$. These adjoints have to satisfy some conditions, which I have sometimes seen referred to as Beck-Chevalley and Frobenius-Reciprocity conditions.

Now if we want to quantify over predicates I assume I'm in a Cartesian closed category, the picture is nearly the same, except that $X$ below has a different structure from before.

$$  \exists_{I,X}, \forall_{I,X}: P_C(I\times X) \to P_C(I) $$

Is that right?

I believe my mental block was because I was previously dealing with first-order hyperdoctrines and did not need the category to be Cartesian closed and did not consider it later.

Background and Context.
I have been working with the presentation of categorical logic by Andy Pitts in his Handbook of Logic in Computer Science article, but I'm also familiar with the treatment of Tripos theory in his doctoral dissertation, as well as the notes of Awodey and Bauer. I started out studying Crole's Categories for Types and the book by Lambek and Scott but it's been a while since I consulted the last two texts.

For motivation, I am interested in the kind of MSO logics appearing in the theorems below. I do not want to deal with a logic that is expressively equivalent to one of these. Meaning, I do not want to encode monadic predicates in terms of higher order functions and then deal with another logic, but I'm happy to study a semantics that includes such an encoding under the hood.

(Buechi and Elgot Theorem) When the universe of structures is finite words over a finite alphabet, a language is regular exactly if it is definable in MSO with an interpreted predicate for expressing consecutive positions.
(Buechi's Theorem) When the universe of structures is $\omega$-words over a finite alphabet, a language is $\omega$-regular exactly if it is definable in MSO with an appropriate interpreted predicate.
(Thatcher and Wright Theorem) A set of finite trees is recognizable by a bottom-up finite tree automaton exactly if it is definable in MSO with an interpreted predicate.
WS1S is the Weak Monadic Second order theory of One Successor. Formulae define sets of natural numbers and second order variables can only be interpreted as finite sets. WS1S can be decided by finite automata by encoding tuples of natural numbers as finite words.
(Rabin's Theorem) S2S is the Second order theory of Two Successors. S2S can be decided by Rabin automata.

I don't know!
No, your assumption is not right. You can quantify over higher-order functions and predicates in IHOL (in fact, predicates are just functions into a type of propositions). The setup looks a bit like this:

$$
\begin{array}{llcl}
\mbox{Sort} & \omega & ::= &  \omega \to \omega \;\; | \;\; \omega \times \omega \;\; | \;\; 1  \;\;|\;\; \mathrm{prop}  \;\;|\;\; \iota\\
\mbox{Term} & t & ::= & x \;\;|\;\; \lambda x.t \;\;|\;\; t\;t' \;\;|\;\; (t,t) \;\; | \;\; \pi_1(t) \;\;|\;\; \pi_2(t) \;\;|\;\; () \\
&            &  |  &
     p \Rightarrow q \;\;|\;\; \top \;\;|\;\; p \wedge q \;\;|\;\; \bot \;\;|\;\; p \vee q  \\
& & | & \forall x:\omega.p \;\;|\;\; \exists x:\omega.p  \;\;|\;\; t =_\omega t' \\
& & | & f(\vec{t})
\end{array}
$$

You give the usual typing rules to judge the well-formedness of a term. The first line of terms are the usual simply-typed lambda calculus, the second two lines are the propositions of higher-order logic (typed as elements of $\mathrm{prop}$), and the third line are whatever constants you use to form individuals (elements of $\iota$).

Then the idea is that you want to extend the Kripke semantics for first-order intuitionistic logic to higher-order logic, by extending the hyperdoctrine semantics with additional structure. A first-order hyperdoctrine is a functor $P : C^\mathrm{op} \to \mathrm{Poset}$ between a category $C$ with products (used to interpret the terms in context), and a category of posets (the truth value lattices), satisfying some conditions to make substitution work right.

To get to IHOL, you additionally assert that

$C$ is cartesian closed (to model the ability to quantify over function types), and
$C$ has an internal Heyting algebra $H$ satisfying the property that for every $\Gamma \in C$, $\mathit{Obj}(P(\Gamma)) \simeq C(\Gamma, H)$. You use $H$ to model $\mathrm{prop}$, and the isomorphism tells you that terms of type $\mathrm{prop}$ really do correspond to truth values.

This structure is almost an "elementary topos". If you additionally require that $P(\Gamma)$ is a poset of subojects of $\Gamma$, then you're there. (This essentially says that you can add a comprehension principle to your logic.)


Find Shortest Pairwise Distance of Points in o(n log n)? The following exercise has been handed out to students I supervise:

  Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of points. The algorithm should run in time $o(n^2)$.

There is a (relatively) simple divide and conquer algorithm that solves the task in time $\Theta(n \log n)$.

Question 1: Is there an algorithm that solves the given problem exactly in worst-case time $\mathcal{o}(n \log n)$?

What made me suspect  that this might be possible is a result I remember to have seen in some talk (reference appreciated). It stated something along the lines of that not more than a constant number $c \in \mathbb{N}$ of points can be arranged in the plane around some point $p$ inside a circle of radius $r \in \mathbb{R}$, with $r$ the minimal distance between any two of the involved points. I think $c=7$, the points forming a equilateral hexagon with $p$ in the center (in the extreme case).

In that case, the following algorithm should solve them problem in $n$ steps.

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Note that this is (claimed to be) in linear time because only a constant number of points in r can be no farer away than m from p (assuming above statement); only these points have to be investigated for finding a new minimum. There is a catch, of course; how do you implement nextNeighbour (maybe with preprocessing in linear time)?

Question 2: Let a set of points $R$ and a point $p \notin R$. Let $m \in \mathbb{R}$ with

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

and

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$.

Assume $R_{p,m}$ is finite. Is it possible to find $p' \in R_{p,m}$ with minimal distance from $p$ in (amortised) time $\mathcal{O}(1)$? (You may assume $R$ to be constructed by adding investigated points $p$ one by one.)

There is a randomized linear expected time algorithm by Rabin; see e.g. Rabin Flips a Coin on Lipton's blog.


Chernoff-type inequality for random variable with 3 outcomes Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following inequality (from Cover & Thomas) applies in this case.

  Theorem 12.4.1 (Sanov's theorem): Let $X_1, X_2, \ldots, X_n$ be i.i.d. $\sim Q(x)$.
  Let $E \subseteq \mathscr{P}$ be a set of probability distributions.
  Then
  $$Q^n(E) = Q^n(E \cap \mathscr{P}_n) \leq (n+1)^{|\mathcal{X}|}2^{-nD(P^*||Q)},$$
  where $$P^* = \arg\min_{P \in E} D(P||Q),$$
  is the distribution in $E$ that is closest to $Q$ in relative entropy.

This inequality is quite loose for small $n$. For binary outcomes, $|\mathcal{X}|=2$, and Chernoff-Hoeffding bound is much tighter.

Is there a similarly tight bound for for $|\mathcal{X}|=3$?

You can get fairly good bounds by considering the random variable $Y_{ij}$ which is 1 if $X_i = j$ and zero otherwise (for $1 \le i \le n$ ranging over trials and $1 \le j \le 3$ ranging over categories). For any fixed $j$ the $Y_{ij}$ are independent and therefore $\sum_i Y_{ij}$ can be analyzed using Chernoff bounds. Then do a union bound over $j$.

If the above isn't enough I suggest that you look at the balls and bins model e.g. in Upfal and Mitzenmacher's textbook. That model is the same as yours except that some of your bins may be more likely than others to have balls land in them, right? There are some more sophisticated techniques involving Poisson approximations in that model that would likely be extendable to your setting with non-uniform bin probabilities.


Network / Social network analysis visualization tools? I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network / social network analysis and visualization.

FLARE produces rather beautiful graphs and visualisations, and in fact I have used it for just this purpose with a small private social network. In particular you may want to look at "layouts" in the demo as it gives an excellent demonstration of transforming between different ways of drawing the graph.