Hardness of an extended maximum set packing problem (Edited)

The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$.

The requirement in this problem is that the sets in the solution will be pair-wise disjoint. In other words, one have to find as many as possible sets taken from the sets in the problem (each containing $k$ elements) such that no two sets share one element or more.

Let us now consider a modified version of the $k$-set packing, which we will call Problem A. Instead of finding the maximum number of pair-wise disjoint sets, we have to find the maximum number of subsets of the original sets, such that each subset contains at least $l$ elements not shared by any other subset. For $l=k$, we get the maximum $k$-set packing. Is Problem A NP-hard for $l<k$?

Formally:

Input: A collection $A_1,A_2,...,A_n$ of sets of size $k$ each and an integer $l$, $1 \le l \le k$.

Output: The maximum number of subsets $A'_i \subseteq A_i$ such that $\left| {A{'_i}} \right| \ge l$ and $\left| {A{'_i} \cap A{'_j}} \right| = \emptyset$.

Note that for $l=1$ (for any $k$ such that $l \le k$), we can transform our problem to the maximum bipartite matching problem, so in this case Problem A is solvable in polynomial time. Thus, I ask about the NP-hardness of Problem A in the case $1 < l < k$.

Examples:

${A_1} = \left\{ {1,2,3} \right\}, {A_2} = \left\{ {1,2,3} \right\}$ ($k=3$) and $l=1$. Then $A'_1={1}, A'_2={2}$ is a valid solution. This can be achieved by considering $A_i$ as one group of nodes in a bipartite graph, and the elements as the other group, and then looking for maximum matching. Note that for $l=2, l=3$ only one set can be obtained as a solution.
${A_1} = \left\{ {1,2,3} \right\},{A_2} = \left\{ {2,4,5} \right\},{A_3} = \left\{ {3,4,5} \right\}$ (again, $k=3$). For $l=1$, one possible solution is $A{'_1} = \left\{ 1 \right\},A{'_2} = \left\{ 2 \right\},A{'_3} = \left\{ 3 \right\}$. For $l=2$, only $2$ sets can be chosen: $A'{'_1} = \left\{ {1,2} \right\},A'{'_2} = \left\{ {4,5} \right\}$. For $l=3$, one of the original sets can serve as a valid solution. That is, for $l=1$ we get a solution of cardinality (number of sets) $3$, for $l=2$ the cardinality is $2$ and for $l=3$ the cardinality is 1.

The previous reduction doesn't work with the current reformulation of your problem (19 July 2014); however I leave it below, because it is correct for that particular maximum k-set packing problem variant (which is defined in the reduction). Here it is a fix for the current version:

CURRENT VERSION

Again your problem is NP-hard for $l \geq 3$. NOTE that  $l$ should not be part of the input otherwise it is simply a generalization of the MAXIMUM $k$-SET PACKING problem (MSP): given an instance of MSP, feed it to your algorithm setting $l = k$; so the NP-hardness proof is immediate.

If $l,k$ are not part of the input, I give you the idea of the reduction for the case $l = k-1$, but it can be easily extended to arbitrary $3 \leq l < k$. Given an instance of MAXIMUM $l$-SET PACKING PROBLEM (MSP), i.e. a collection of sets $A_1, A_2, ..., A_n$ and an integer $p$ that represents the minimum number of sets required for the solution, build an instance of your problem in the following way:

if $A = \{x_1,...,x_m\} = A_1 \cup ... \cup A_n$ are the elements in the $A_i$, "clone" them: $B = \{y_1,...,y_m\}$ using $m$ new elements and build the corresponding $B_i$: $x_j \in A_i \Leftrightarrow y_j \in B_i$;
add to the $A_1,...,A_n,B_1,...,B_n$ a (new) shared element $z$;
the sets $A_1 \cup \{z\},...,A_n\cup \{z\},B_1 \cup \{z\},...,B_n \cup \{z\}$ represent the input of your problem;
sets to $2p$ the minimum number of subsets required for the solution of your problem (each one must contain $l$ unique elements).

Suppose that a solution exists for your problem. Then we can have the following cases:

exactly $p$ subsets of $A'_i \subseteq A_i \cup \{z\}$ and $p$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; but, by construction, the element $z$ can only be contained in one of them - suppose one of the $A_i$ - but in that case the $p$ sets $B'_i$ (that don't contain $z$) also represent a valid solution for the original MSP problem (because each one of them contains $l$ unique elements);
or $q > p$ subsets $A'_i \subseteq A_i\cup \{z\}$ and $2p - q$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; again the element $z$ can be included in only one of the $A'_i$, but nevertheless we have at least $p$ of them (because $q > p$) that don't include it, so those $p$ subsets $A'_i \subseteq A_i$ represent a valid solution for the original MSP problem;
or $q > p$ subsets $B'_i \subseteq B_i\cup \{z\}$ and $2p - q$ subsets $A'_i \subseteq A_i\cup \{z\}$ are included in the solution; this case is similar to the previous one.

In the opposite direction, if a valid solution to the original MSP exists, it also represent a valid solution to your problem: just pick $A'_i = A_i \subseteq A_i \cup \{z\}, B'_i= B_i \subseteq B_i \cup \{z\}$.

PREVIOUS VERSION

The decision version of your problem MAXIMUM $l$-DISJOINT $k$-SET PACKING PROBLEM is:

Input: an integer $q \geq 0$ and a collection $D$ of finite sets, each set contains $k$ elements; an integer $0 < l < k$
Output: a set packing of $q$ or more sets, i.e. a collection of partially overlapping sets $D' \subseteq D$ with $|D'| >= q$ and foreach $A_i, A_j \in D', | A_i \cap A_j | \leq k - l$ (the last contraint means that two subsets must contain at least $l$ distinct elements)

When $l \geq 3$ the above problem remains NP-hard and this is a reduction from the decision version of MAXIMUM $l$-SET PACKING PROBLEM which is NP-hard because $l \geq 3$ ($k=l$):

Input: an integer $p \geq 0$ and a collection $C$ of finite sets, each set contains $l \geq 3$ elements;
Output: a set packing of $p$ or more sets, i.e. a collection of disjoint sets $C' \subseteq C$ with $|C'| >= p$

Reduction: simply pick $q=p$, and add $k - l$ new shared elements $Y = \{y_1,...,y_{k-l}\}$ to every original set $A_i \in C$; i.e. $D \ni A'_i = A_i \cup Y$

Suppose that $A'_i, A'_j \in D'$ (where a D' is a valid solution to your problem), then by construction they already share $k-l$ elements (the $y_i$s); so they cannot share more elements, otherwise the number of disjoint elements would be less than $l$: $(A'_i \setminus Y) \cap (A'_j \setminus Y) = \emptyset$.

But $A'_i \setminus Y$ contains exactly the elements of the original $A_i \in C$, and  $A'_j \setminus Y$ contains exactly the elements of the original $A_j \in C$, so $A_i \cap A_j = \emptyset$ and we can conclude that the solution $D'$ corresponds to a valid solution $C'$ of the original problem.

The opposite direction (if there exists a valid solution $C'$ for the $l$-SET PACKING PROBLEM then there is also a valid solution $D'$ to your problem) is immediate.


#P-complete problem whose decision version is in P 1) Is it possible to have a parsimonious reduction from a #P-complete problem #A to a counting problem #B when (the decision version) A is NP-complete and the B is in P?

For example, can there be a parsimonious reduction from #SAT to #B, when B is in P?

2) If B is in P, what are the different possibilities for the complexity of #B?

If you insist on parsimonious reductions (where the number of solutions is preserved) you cannot have such a reduction unless P = NP because the decision algorithm for non-emptyness of solutions for B will give you a decision algorithm for non-emptyness of solutions for A. On the other hand, if you allow other kind of reductions you can have such a case. For example, Valiant showed that #SAT reduces to the problem of counting perfect matchings in a bipartite graph: the reduction starts with a CNF-formula $F$ and builds a bipartite graph $G$ whose number of perfect matchings mod $2^{8m}+1$ is $4^m$ times the number of satisfying assignments of $F$, where $m$ is the number of literal occurrences in $F$. Note how this is not a parsimonious reduction, but a reduction nonetheless since you can recover the number of satisfying assignments of $F$ from the number of perfect matchings of $G$.

See Chapter 18 in Papadimitriou's "Computational Complexity" book for a clear exposition of this.


Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$.

The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in $\sigma$.
That is if I locate all neighbours of $v$ in $\sigma$ I find all the neighbours present in chunks in $\sigma$, where number of such chunks is $O(\sqrt{m})$.

Clearly any vertex with degree $<\sqrt{m}$ does not voilate any vertex ordering as even if all its neighbours are separated in $\sigma$ the number of sequences/chunks cannot exceed $degree$ of the vertex.

Does such an ordering always exists?Can I find such an ordering efficiently?

Best case would be to find such an ordering in $O(m)$ time. Also is it possible for find such an ordering for smaller number of chunks/sequences?

So if I understand it correctly you want the neighbors of each vertex to form a small number of contiguous blocks of the ordering? Then no, you need a larger number of blocks than that.

Let's suppose we have a bipartite graph with a small number $k$ of (labeled) vertices on one side and $n$ on the other. Each edge from one side to the other can be present or absent independently of the others, so there are $kn$ bits of information required to specify the whole graph.

On the other hand, suppose you could find an ordering with the neighbors of each vertex forming at most $b$ blocks. Then you could specify the same graph by listing the ordering of the big side of the bipartition (representable in $\le n\log_2 n$ bits of information) and the positions and lengths of the blocks for each of the $k$ vertices on the small side of the bipartition ($\le 2bk\log_2 n$ bits). So to have enough information to specify the whole graph we need
$$
n\log_2 n+2bk\log_2 n\ge kn
$$
or equivalently
$$
b\ge\frac{kn-n\log_2 n}{2k\log_2 n}
$$
Setting $k=2\log_2 n$ gives $b=\Omega(n/\log n)$, significantly greater than $\sqrt m=\Theta((n\log n)^{1/2})$.


Weapon target assignment problem Does anybody know a NP-hardness proof of Weapon-target assignment problem (http://en.wikipedia.org/wiki/Weapon_target_assignment_problem)? Lloyd and Witsenhausen produced a reduction from 3-EXACT-COVER, but it seems that there is no chance to get their paper titled "Weapons allocation is NP-complete".

I don't have access to the original paper, but this is an alternate reduction from SUBSET PRODUCT. The decision version of the WEAPON TARGET ASSIGNMENT (WTA) problem is:

Input: Given an integer $k$, $W_i$ weapons of type $i = 1,...,m$, $n$ targets $j=1,...,n$ having values $V_j$; each weapon type has a certain probability of destroying each target, given by $p_{i,j}$.
Question: Does there exist an assignment of the available weapons such that:

$$D = \sum_{j=1}^n V_j \prod_{i=1}^m q_{i,j}^{x_{i,j}} \leq k  $$

where $x_{i,j} = 1$  if weapon $i$ is assigned to target $j$ ($x_{i,j} = 0$ otherwise), and $q_{i,j} = 1 - p_{i,j}$ (survival probability of target $j$ when hit by weapon $i$).

Given a set of positive integers $A= \{a_1, a_2, ..., a_m\}$, and a target product $b$; the SUBSET PRODUCT problems asks for a subset $X \subseteq \{1,2,...,m\}$ such that $\prod_{i \in X} a_i = b$. Let $P = \prod a_i$, note that if $b \nmid P$ then the subset product problem doesn't have a solution.

We can build a WTA instance with two targets ($n=2$) having the same value $V_1 = V_2= P$ and $m+2$ weapons $W_1,W_2,...,W_m,W_{\alpha},W_{\beta}$:

    weapons $W_1,W_2,...,W_m$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 - \frac{1}{a_i}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{1}{a_i}$);
    weapon $W_{\alpha}$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 - \frac{b}{2P}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{b}{2P}$);
    weapon $W_{\beta}$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 - \frac{1}{2b}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{1}{2b})$

We set $k = 1$.

($\Rightarrow$) Suppose that the original subset sum problem has a solution $X$; let $Y=\{1,\ldots,m\} \setminus X$.
Then
$$\prod_{i \in X} \frac{1}{a_i}=\frac{1}{b},\quad \prod_{y \in Y} \frac{1}{a_y} = \frac{b}{P}$$

If we assign weapons $W_x, x \in X$ and $W_{\alpha}$ to target 1; weapons $W_y, y \in Y$ and $W_{\beta}$ to target 2 we get:

$$ D= V_1 * \frac{b}{2P}* \frac{1}{b}  + V_2 * \frac{1}{2b}* \frac{b}{P} = P * \frac{b}{2P}* \frac{1}{b}  + P * \frac{1}{2b}* \frac{b}{P}  = 1$$

($\Leftarrow$) Suppose that the WTA instance has a solution and let $X',Y'$ be the indices of the weapons assigned to target 1 and 2 respectively ($X',Y'\subseteq \{1,\ldots,m,\alpha,\beta\}$). We must have:

$$ D = P \prod_{x \in X'} q_{x,1} + P \prod_{y \in Y'} q_{y,2} \leq 1$$

$W_{\alpha}$ and $W_{\beta}$ cannot both belong to $X'$ (or $Y'$), otherwise:

$$P \frac{1}{2b}*\frac{b}{2P}*\frac{1}{ \prod_{x \in X'\setminus \{\alpha,\beta\}} a_x} + \frac{P}{ \prod_{y \in Y'} a_y} \geq \frac{1}{4 \prod_{x \in X'\setminus \{\alpha,\beta\}} a_x}+1 > 1$$

So suppose that weapon $W_{\alpha}$ is assigned to target 1 and $W_{\beta}$ to target 2; let $X = X' \setminus \{ \alpha \}, Y = Y' \setminus \{ \beta \}$; we must have:

$$ P \frac{b}{2P} \prod_{x \in X} \frac{1}{a_x} + P\frac{1}{2b} \prod_{y \in Y} \frac{1}{a_y} \leq 1$$

$$\mbox{if } z = \prod_{x \in X} a_x, \quad \frac{b}{2z} + \frac{z}{2b} \leq 1$$

Multiplying both sides by the positive quantity $2bz$ we get:

$$ b^2 + z^2 \leq 2bz$$

$$(b - z)^2 \leq 0$$

So we must have $b = z = \prod_{x \in X} a_x$, so $X$ is a valid solution for the original SUBSET PRODUCT problem.

(P.S. Unfortunately, despite the hardness of this problem, the war between peoples seems to be a lot easier to start ..."The day the power of love overrules the love of power, the world will know peace." [Mahatma Gandhi] ):


Problems not known to be PSPACE-complete What are problems with the following properties:

1) they are restriction of (possibly well known) problems that are PSPACE-complete;

2) the restricted versions are in PSPACE, but it is an open problem if they are PSPACE-complete (or even if they are NP-hard).

Four examples from "puzzles & C.":

The complexity of 1x1 Rush Hour [1] (PSPACE-complete for blocks of size 2x1 );
[SOLVED] The complexity of planar Subway Shuffle [1] (PSPACE-complete even for planar graphs, a draft of the paper can be downloaded here );
The complexity of Lunar-Lockout without fixed blocks [1] (PSPACE-complete with fixed blocks);
(not so famous) The complexity of (my) Switch-network problem (it is a restriction of the PSPACE-complete Sokoban, NP-hard in the non-planar case, see this Q&A on cstheory).

If you have many, group them by topic.

[1] Robert A. Hearn, Erik D. Demaine: Games, puzzles and computation. A K Peters 2009, ISBN 978-1-56881-322-6, pp. I-IX, 1-237

Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known that there are positions that require exponential moves, but the problem is only known to be $NP$-hard.

http://arxiv.org/abs/1409.1530

https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach


Complexity analysis on a parameterized recurrence relation In order to analyse the complexity of our algorithm, we try to solve this recurrence:

$T(n)=3T(n-1)-T(n-2)+T(n-k)+3^k$ ; in which $k$ is a parameter to be fixed.

We know that this kind of recurrence means $T(n)=O(\alpha^n)$, where $\alpha$ is the zero root of the equation $f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-k}-3^k$.

The term $3^k$ expects a small value of $k$, while the rest terms want a big value of $k$, therefore we believe that there should be a best choice of $k$.

So the question is how to choose $k$, $(k=g(n))$ in order to minimize $\alpha$?

Thank you in advance for any idea.

UPDATE 1:

The recurrence has been corrected, and yes, $\alpha$ should be between 2 and 3.
Please note that $k$ is a dynamic value, which changes during the recursion. So it's better to consider the recurrence as $T(n)=3T(n-1)-T(n-2)+T(n-g(n))+3^{g(n)}$

UPDATE 2:

To somewhat simply the problem, we may consider $g(n)=\beta n$ and try to find the $\beta$ ?

First, if $k(n)$ and $T(n)$ are non-negative functions satisfying
$$T(n)=3T(n-1)-T(n-2)+T(n-k(n))+3^{k(n)}\tag{$*$}$$
for all sufficiently large $n$, it is easy to see that $T(n)$ cannot have a finite limit, and in particular, it cannot be decreasing. But if $T(n_0+1)\ge T(n_0)$, then $T(n+1)>T(n)$ for all $n>n_0$ by induction on $n$. Thus, $T$ is eventually increasing.

Second, proving bounds on $T(n)$ is inconvenienced by the presence of a negative term in $(*)$. We can fix this by defining a new function
$$S(n)=\begin{cases}T(\tfrac n2)&\text{$n$ even,}\\T(\tfrac{n+1}2)-T(\tfrac{n-1}2)&\text{$n$ odd,}\end{cases}$$
which (as we just proved) is also eventually nonnegative, and satisfies the recurrence
$$S(n)=\begin{cases}S(n-1)+S(n-2)&\text{$n$ even,}\\
S(n-1)+S(n-2)+S(n-k'(n))+3^{(k'(n)+1)/2}&\text{$n$ odd,}\end{cases}\tag{${*}{*}$}$$
where $k'(n)=2k((n+1)/2)-1$.

This makes it obvious that
$$S(n)\ge S(n-1)+S(n-2),\qquad n\gg0,$$
hence
$$S(n)=\Omega(\phi^n)\quad\text{and}\quad T(n)=\Omega(\phi^{2n}),$$
where $\phi=(1+\sqrt5)/2\approx1{.}618$ is the golden ratio.

I claim that a suitable choice of $k(n)$ gives a matching upper bound. The right choice is to make the two terms involving $k'$ approximately equal; since we are shooting for $S(n)\approx\phi^n$, this means
$$\phi^{n-k'(n)}\approx3^{k'(n)/2},$$
thus
$$k'(n)\sim\beta n,\qquad\beta=\frac{2\log\phi}{2\log\phi+\log3}\approx0{.}467$$
and $k(n)\sim\beta n$ as well. So, let us assume
$$\beta n+c\le k'(n)\le\beta n+d$$
for some constants $c,d$ (with some conditions on $c$ below). I claim that with this setting, any nonnegative solution of $({*}{*})$ satisfies
$$S(n)\le a\phi^n-b\psi^n\tag{${*}{*}{*}$}$$
for some constants $a,b>0$, where
$$\psi=3^{\beta/2}=\phi^{1-\beta}\approx1{.}29,$$
and consequently
$$T(n)=O(\phi^{2n}).$$

Pick $n_0>2$, $a,b>0$ such that $({*}{*})$ holds for $n\ge n_0$, and $({*}{*}{*})$ holds for $n\le n_0$ (there will be one more condition below). We want to show $({*}{*}{*})$ for all $n$ by induction. The induction step goes as follows:
$$\begin{align*}
S(n)&\le a(\phi^{n-1}+\phi^{n-2})-b(\psi^{n-1}+\psi^{n-2})+a\phi^{(1-\beta)n-c}+3^{(\beta n+d+1)/2}\\
&=a\phi^n-b(\psi^{-2}+\psi^{-1})\psi^n+(a\phi^{-c}+3^{(d+1)/2})\psi^n\\
&\le a\phi^n-b\psi^n.
\end{align*}$$
The last step is valid if
$$b(\psi^{-2}+\psi^{-1}-1)\ge a\phi^{-c}+3^{(d+1)/2}.\tag{${*}{*}{*}{*}$}$$
We can arrange this condition by observing that the other requirements on $a,b$ continue to hold if we increase both by the same amount; this will eventually make $({*}{*}{*}{*})$ true if $c$ is sufficiently large so that
$$\psi^{-2}+\psi^{-1}-1>\phi^{-c}.$$


Maximizing sum edge weights I am wondering if the following problem has a name, or any results related to it.

Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,v \in V$, $w(u,v) \in [-1,1]$. The problem is to find a subset of vertices that maximizes the sum of the weights of the edges adjacent to them:
$$\max_{S \subseteq V} \sum_{(u,v) : u \in S\ \textrm{or}\ v\in S} w(u,v)$$
 Note that I am counting edges both that are inside the subset and that are outside the subset, which is what distinguishes this problem from max-cut. However, even if both $u$ and $v$ are in $S$, I only want to count the edge $(u,v)$ once (rather than twice), which is what distinguishes the objective from merely being the sum of the degrees.

Note that the problem is trivial if all edge weights are non-negative -- simply take the whole graph!

FWIW, your problem is hard to approximate within a multiplicative factor of $n^{1-\epsilon}$ for any $\epsilon>0$.

We show that below by giving an approximation-preserving reduction from Independent Set, for which the hardness of approximation is known.

Reduction from Independent Set

Let undirected graph $G=(V,E)$ be an instance of Independent Set.
Let $d_v$ denote the degree of vertex $v$ in $G$.
Let $n$ be the number of vertices in $G$.

Construct edge-weighted graph $G'=(V',E')$ from $G$ as follows.
Give each edge in $E$ weight 1.
For each non-isolated vertex $v\in V$,
add $d_v-1$ new edges, each with weight $-1$,
to $d_v-1$ new vertices.
For each isolated vertex $v\in V$,
add one new edge of weight 1 to a new vertex.

(Note: each new vertex (in $G'$ but not $G$) has exactly one neighbor,
which is in $G$.)

Lemma. $G$ has an independent set of size $k$ iff
$G'$ (as an instance of your problem) has a solution of value at least $k$.

Proof.  Let $S$ be any independent set in $G$.
Then, since the vertices in $S$ are independent in $G'$,
the value of $S$ in $G'$ (by your objective)
is
$$\sum_{v\in S} d_v - (d_v-1) ~=~ |S|.$$

Conversely, let $S$ be a solution for $G'$ of value at least $k$.
Without loss of generality, assume $S$ contains no new vertices.
(Each new vertex $v'$ is on a single edge $(v',v)$.
If $v$ was not isolated in $G$, then the weight of the edge
is $-1$, so removing $v'$ from $S$ increases the value of $S$.
If $v$ was isolated, then the weight of the edge is 1,
so removing $v'$ from $S$ and adding $v$ maintains the value of $S$.)

Without loss of generality, assume that $S$ is an independent set in $G$.
(Otherwise, let $(u,v)$ be an edge such that $u$ and $v$ are in $S$.
The total weight of $v$'s incident
edges in $G'$ is $d_v - (d_v-1) = 1$, so the total weight of $v$'s incident
edges other than $(u,v)$ is at most zero.
Thus, removing $v$ from $S$ would not increase the value of $S$.)

Now, by the same calculation as at the start of the proof,
the value of $S$ is $|S|$.  It follows that $|S| \ge k$. QED

As an aside, you might ask instead for an additive approximation,
of, say, $O(n)$ or $\epsilon m$.

It seems possible to me that for your problem even deciding whether
there is a positive-value solution could be NP-hard.


Deciding between different PhD programs Edited Version

What are the main characteristics and qualities that you would consider if you were going to choose a PhD program in theoretical computer science (or related areas) today (based on your experience) and why would you consider them important?
What are the credible sources that I can get information about those characteristics of PhD programs?

Especially I would like to hear your opinion about the following two issues:

If you had to choose between a program with a global and better brand name and another one with a strong research focus, which one would you choose? why?
Which of the following two is more important in your opinion: availability of specialization one wants vs general teaching/research quality of faculty?

Thanks.

What are the parameters that one should look for?
Number and quality of the faculty working in your area of choice or related areas, ease of finding an advisor, opportunities to collaborate with different people in the program, how well funded the program is, quality of the students, how successful are graduates in finding jobs/positions that you would be interested in after graduating, etc.
What are credible sources other than institute website/provided materials to get information about the course or program?
Other students in the program are one of the best sources of information. Most schools should have an Open House for admitted students. Highly recommend you go to them.
Do brand names really matter? (As in if you had to choose between one with a global and better brand name and other with a strong research focus)
The story I've heard is that brand names matter in the sense that you'll likely find an excellent and diverse faculty body making it easier to find an advisor and do good work in your field. In addition, on average, the quality of students at such universities is likely to be higher which can be important as at least in my experience, I tend to learn a lot from my peers and work harder if people around me are working hard too.
You'll also have an easier time getting a good CS job and can also help when looking for a postdoc/faculty position if only because it would be easier to collaborate with a well known faculty member who could write you a great rec.


Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time? Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression  operations (Kleene star, concatenation, reverse, set operations, etc). I was unsure about the worst case performance of my package.

A DFA has the same expressive power as an NDFA, because an n-state NDFA can be trivially converted to a DFA having 2^n states. However, are there any lower upper bound guarantees for such a conversion that do not require an exponential explosion in state?

I was unable to come up with examples mal-behaving regular expressions or NDFAs, but I didn't spend much time thinking about it. I am guessing a regular expression like ((((e|A|B|C)*(e|D|E|F))*(e|G|H|I))*(e|J|K|L|M))* which mixes a lot of alternations and Kleene stars would have a linearly sized NDFA but an expansive DFA.

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

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

Abstract of the paper:

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

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


Latest word on cross validation? It's a standard result leave-one-out cross-validation is an unbiased estimator of the risk (see, e.g., Lemma 4.1 in Mohri, Rostamizadeh, Talwalkar). Are there any "better" results? Such as, say, with high probability rather than just in expectation?

It is not hard to see that without additional stability assumptions one won't be able to get high probability bounds. For example consider predicting unbiased coin using majority label in the sample. With probability $~1/\sqrt{n}$ we get that majority of leave-one-out is exactly the opposite of the excluded point so LOO will give error of 1. Note that the true error is always 1/2.

If one assumes stability then the bounds will depend on the notion of stability being used. Uniform stability will give high probability bounds for both empirical mean and LOO estimator (e.g. https://arxiv.org/abs/1902.10710).
Weaker notions will give you weaker bounds. I guess the latest on variance of the estimator is this paper http://www.satyenkale.com/papers/crossvalidation.pdf


Correspondence between Computability & Learnability Theory Could someone give a brief explanation of the computability & learnability theory & the correspondence betwwen them if any? (pointers to good sources of info. on this other than wikipedia are welcome) Thank You.

Let's stick to the classical PAC (supervised learning) setting.
The short answer is that if computability is not an issue, then any class of functions with finite VC-dimension is PAC learnable via the Empirical Risk Minimization algorithm (just pick the hypothesis with the minimal sample error).

Of course, in many cases of interest ERM is computationally hard (e.g., if your class of functions is 3-term DNFs; see book by Kearns and Vazirani.

As Suresh commented above, the question is too vague and open-ended to give a comprehensive answer, but hopefully the above is a start...


polytime transformation from a graph to a set of binary strings $d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows.
Given any undirected graph $(V, A)$, does there always exist a one-to-one correspondence $f : V \mapsto \Omega$, $f$ computable in polynomial time,
where $\Omega$ is a set of binary strings of the same size and such that $\exists \alpha > 0$, $\forall v_i, v_j \in V$,
$$d_H(f(v_i), f(v_j)) = \left\lbrace\begin{array}{ll}
\alpha & \mbox{ if } (v_i, v_j) \in A,\\
\mbox{some value strictly greater than $\alpha$,}& \mbox{otherwise.}
\end{array}\right.$$

For instance, if $(V, A)$ is a clique of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = V \times V$, then such a function $f$ can be defined as follows:
$f(v_1) = 100$, $f(v_2) = 010$, $f(v_3) = 001$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = d_H(v_1, v_3) = 2$.

As another example, consider a line $(V, A)$ of size $3$, i.e., $V = \{v_1, v_2, v_3\}$ and $A = \{(v_1, v_2), (v_2, v_1), (v_2, v_3), (v_3, v_2)\}$, then such a function $f$ can be defined as follows:
$f(v_1) = 00$, $f(v_2) = 10$, $f(v_3) = 11$. We have $d_H(v_1, v_2) = d_H(v_2, v_3) = 1$ and $d_H(v_1, v_3) = 2$.

Yes. If the graph is regular there is a trivial scheme. Fix some ordering of the edges, and define $f(v)$ to be $0$ at the corresponding position of a particular edge if $v$ is not incident to that edge, and $1$ is $v$ is incident to the edge.

If the graph is $k$-regular, then $d_H(f(v),f(u))$ is $2k-2$ if $u$ and $v$ are adjacent, and $2k$ if they are not.

If the graph is not regular, then we may pad the graph with additional degree $1$ vertices such that all of the original vertices have the same degree. Then the above scheme will work.


Obfuscation transformation and code maintainability This is more a software engineering question, but my interest is in the mathematical modeling of the problem.

While there seems to be some literature on the modeling of obfuscation transformation, I'm finding it difficult to locate papers that relates it to code maintenance - guess because they are inherently orthogonal. But its hard to imagine no study has been done by modeling this as an optimization problem. Can anybody point me to any thing that is helpful to get some insight into this?

From comments ...

Do you mean relation between code obfuscation and code maintenance?

Obviously good obfuscation means poor maintainability, so an alternate question is: how can a small part of the source code be reobfuscated without having to obfuscate the whole source code again? This leads to: "how can I build an efficient incremental obfuscator?" ... unfortunately obfuscators heavily depend on the target programming languages, so I don't think there are many academic papers on that subject.

However, if you need a more theoretical approach then you can start with a survey on the subject: for example: Code Obfuscation Literature Survey (with good references at the end). Or look for papers which cite the negative result of Barak et al.: On the (Im)possibility of Obfuscating Programs .

Otherwise - if you are more "code-oriented" - you can search for information (and source code) on how real incremental obfuscators work (.NET obfuscator, ProGuard obfuscator, ...). Some years ago I used ProGuard to obfuscate a Java application (in Netbeans environment); it is an open source project, so you can download the full source code (http://proguard.sourceforge.net/). Incremental obfuscation is obtained keeping a mapping file that allows to mantain classes/variables/methods/etc.etc. names consistent across subsequent builds.


Statistical query model with Gaussian noise? Kearns' statistical query model is a well-known learning model with noise tolerance. The statistical query oracle takes as input a statistical query of the form $\{\chi, \tau\}$. Here $\chi$ is any mapping of a labeled example to $\{0, 1\}$ and $\tau \in [0, 1]$ is called the noise tolerance. The oracle returns an estimate for the expectation $\mathbf{E}\chi$, that is, the probability that $\chi = 1$. The additive error of this estimate is at most $\tau$.

The statistical query oracle only guarantees an upper bound of the noise and Kearns' model mentions nothing about the noise distribution. Is there any query oracle in computational learning theory that can answer a statistical query with normal distributed noise? That is, the oracle takes as input a statistical query of the form $\{\chi, \sigma^2\}$ and returns the estimate of $\mathbf{E}\chi$ with additive error of Gaussian distribution $\mathcal{N}(0, \sigma^2)$.

I think this model is reasonable because Gaussian noise is a common assumption in many problems. Also, for central limit theorem, the estimate will converge to a Gaussian distribution (but we are not able to control the variance).

We know something close to what you want.

If you look at Ke Yang's "Honest Statistical Queries" -- there is no noise at all, but only "sampling error".   In this model, you pass in a parameter $t$, and the Oracle takes $t$ samples, honestly evaluates the passed-in function (onto {0,1}), and returns the average value of the function on the samples.

In effect, this estimates the expected value of the function.  It is easy to see that this Oracle samples from the Binomial distribution $B(t, E_{x \sim D}(f(x))$.  For small skew and large $t$, this is approximated by the Normal.  We extended this to explicitly consider variance here.

The punchline, basically, is that SQ lower bounds still hold in this non-adversarial noise setting.  Actually the SQ lower bounds are even harsher because they work for sample sizes $t=1$, where the algorithm sees the result of its function evaluation on every random sample (and can average or do anything by itself).


Results/concepts that also proved useful outside of their "home areas" There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used in many papers that are not about complexity theory. This is an indication of the general usefulness and importance of the concept.

Similarly, network flow algorithms, shortest path algorithms etc.,  have combinatorial optimization as their home area, but are also used in many papers that are not specifically about combinatorial optimization. Graphs have graph theory as their home area, but are used in many other fields, as well.

Question: What are some other, not so obvious or not so well known examples of methods/concepts that also proved useful outside of their home areas?

One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).


Algebraically Compact Categories I read Freyd's paper "Algebraically Complete Categories" in the famous Como90 and I have two questions about the notion of algebraic compactness he defined in that paper. (If you are not familiar with the definition, here it is: A category is called algebraically compact if every endofunctor has an initial algebra and a final co-algebra which are canonically isomorphic.)

What are some examples of algebraically compact categories? Freyd mentions an example but strictly speaking the condition in the definition holds only for certain endofunctors of interest. From reading other papers (such as "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire") I guess that category of cpo's, omega-cpo's or categories enriched over (omega-) cpo's are algebraically compact. What is the standard reference for this fact?
Freyd says that the definition is motivated by the "principal of versality" and, being a nonnative speaker of English, I am confused. First of all, I think it should be principle, not principal. Also what is versality? Does he mean versatility? Is this a game on words like (uni)versality?

I found the reference for CPO-like categories.
Scott's paper Continuous Lattices in the book Toposes, Algebraic Geometry and Logic. It is explained in the comments right after corollary 4.3.
A more general theorem can be found in Smyth's and Plotkin's paper Category-Theoretic Solution of Recursive Domain Equations. It is lemma 2.

However, again, the functors are not arbitrary. One needs some sort of a continuity assumption.


Computing Functions with Dynamical Systems I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes all initial conditions - The initial tape content, starting state, initial head position) "evolves" to a specific configuration after a finite number of steps and if the function is computable, it halts with the output of the function on the tape. I am trying to draw an analogy of Turing Machines with other "time-evolving" systems and the most intuitive of all is a Dynamical System as a set of differential equations. As an attempt, I formulated a dynamical system which could compute asymptotically the square of a number.

Suppose I want to find the functions $f(x,y,t)$ and $g(x,y,t)$ such that the following dynamical system:

$\frac{dx}{dt}=f(x,y,t)$

$\frac{dy}{dt}=g(x,y,t)$

is such that:

In the phase plane (with $x$ on X axis and $y$ on Y axis), every point on the X axis is a fixed point.
Any initial point on the line y=$\alpha$ (with $\alpha\neq0 $) with coordinates $(x(0),\alpha)$ goes towards the fixed point $(x(0)^2,0)$ for $t\rightarrow\infty$

The functions $f$ and $g$ may contain the $\alpha$ term

With such a dynamical system at hand, if we wanted to compute the square of a number $a$, all we have to do is to start off with initial conditions $x(0)=a$ and $y(0)=\alpha$ (Just like we place the initial input on the Turing Machine's tape,set the initial state to the starting state and correctly position the head; In this case we place the input $a$ as the x coordinate of the initial point of the phase trajectory) and "let the Dynamical System evolve" (Just like we let the Turing Machine evolve after placing the inputs), the phase trajectory will converge to $a^2$ for $t\rightarrow\infty$ (Assuming the function to be computable, the turing machine stops in finite time and it prints the output on tape; the given dynamical system doesn't stop in finite time but it also "prints the output" as the x coordinate of the evolved phase trajectory for $t\rightarrow\infty$). In other words if we had a "machine M" following the given dynamical system, we could say that: M computes the "square" function asymptotically. (Just like the way the turing machine computes the "square" function in finite time) The computations in this case happens over reals as opposed to that over members of a countable alphabet.

But I cant really think of such functions $f$ and $g$ for computing the "square" function and I need help finding these. Furthermore if I start taking up more complicated functions to compute, finding the corresponding $f$ and $g$ will not be a trivial task. Can someone guide me on what possible difficulties I may face and how I can overcome them?

If I can formulate computation using Dynamical Systems the way I described above, is there a possibility to prove some theorems in computability (and complexity?) using these formulations?

Thankyou!

Brockett [1] studied a closely related idea, and showed how to construct dynamical systems that solve any linear programming problem in (I believe) the same manner you suggest, as well as dynamical systems to sort a list of numbers and to diagonalize a matrix. You may be able to use this to directly get the dynamics you need to compute the squaring function.

(At some point I saw a cool video of the trajectory of a dynamical system for sorting, but I can't seem to find it...)

I won't venture a guess as to whether such dynamical systems formulations could be used to prove something interesting in computability/complexity, but can offer some further references that may be relevant.

In quantum computing, Nielsen, Dowling, Gu, and Doherty show that QC can be realized as (if I understand correctly) geodesic flow on a certain manifold - a particular example of the kind of dynamical system you're talking about. See [2] and references therein for a discussion of some complexity issues related to this.

Finally, although I don't think it's exactly what you're talking about, it would probably also be worth checking out Bernard Chazelle's work on "influence systems" which are a type of dynamical system that is at least as powerful as Markov chains and Turing machines, but can exhibit all kinds of dynamic behavior (including chaos, etc). See [3] and references therein.

[1] Roger W. Brockett, Dynamical Systems that Sort Lists, Diagonalize Matrices and Solve Linear Programming Problems, Proc. 27th IEEE Conf. Dec. and Control, Austin, TX, pp. 799-803, Dec. 1988.

[2] Mark R. Dowling, Michael A. Nielsen. The geometry of quantum computation, arXiv:quant-ph/0701004, 2007.

[3] B. Chazelle, Natural Algorithms and Influence Systems, Comm. ACM 55 (2012), 101-110.


How can I rank paths through an HMM? I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path that generates that long sequence of symbols, and it all works very well to identify the user's pattern. But I'm now interested in extending this, and identifying the k-most probable paths through my model that would generate some long sequence. Is there an existing algorithm to do this? I've come across something called the "1-best" or "k-best" algorithm, but I can't find much of anything describing it.

I've also considered what I'm sure would be a heuristic, by finding the most probable path and then returning the neighbourhood around it. This would be found by iterating over each move between states in the most probable path, setting that particular step to 0, and resolving using Viterbi. This would obviously increase the run-time by a factor of (length of the path ~= length of pattern), which I suspect will be reasonable for my purposes.

Has anybody come across something like this, or can anybody see anything obviously wrong in my neighbourhood idea? I'd appreciate any feedback. As a note, this has been cross-posted to the Data Science forum.

Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.


Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)? The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that:

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$
transformation must be computed in polynomial time.

Can I say that the reduction is a Karp reduction $(x,k) \mapsto (x',k')$ such that

$(x,k) \in L \Leftrightarrow  (x',k') \in L$
$|x'| \leq f(k)$ for some function $f$
$k' \leq g(k)$ for some function $g$

I am confused because the language is a binary language.
Perhaps, this is a naive question, but I am not sure if I can call it Karp reduction. It seems that the Karp reduction is not used in parameterized complexity.

Clearly there are similarities - both kernelization algorithms and Karp reductions need to work in polynomial time and produce an output instances that is equivalent to the input instance (in the sense that both are “yes”-instances or both are “no”-instances).
But they are not the same concept, nor is one a special case of the other. First, they operate on different objects: Karp reductions deal with languages (subsets of $\Sigma^*$), while parameterized reductions deal with parameterized problems (subsets of $\Sigma^* \times \mathbb{N}$). Karp reductions (typically) go between different languages, while kernelization algorithms for a single (parameterized) problem. There are more differences, but I guess you get my drift.


Is it possible to have a 4-coloring for a non-planar graph ? I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.

The question is whether this is a necessary condition as well, i.e. whether having a proof that a graph is not planar implies it is not four colorable ?

Obviously not. A graph is bipartite if and only if it is 2-colorable, but not every bipartite graph is planar ($K_{3,3}$ comes to mind).


Graph transformation according to some utility function Consider an undirected graph that models a social network. Each vertex is a person, each arch represents a friendship relation between two persons.
Each arc is decorated by its average 'usage': how much, on average, the arc is used to read/send some information (ie: send my status update to my friends).

By default, the graph structure models the friendship relationship between people; but as we all know not all friends are the same: some are more important than others, and we want to receive news more reliable/faster than from others (ie: on facebook, some friends can be ignored).
An arc would be more 'used' if we receive more often news by the person associated with it.

So, from the social graph made by the 'who-knows-who' relationship, we can infer a subgraph of the 'who-ignores-who' with its dual 'who-cares_about-who'.

The problem that I'd like to solve is how to split/transform the original 'who-knows-who' graph into the two described sub-graphs as clusters, such as the arcs between these 2 clusters is minimal.

Is this problem tractable ?
Can it be reduced to the 'min-bisection' (or similar NP-hard) problems ?

thanks,
valerio

I assume that the edge weights express how much the users interact to one another, rather than the amount of communication , i.e. the communication is always mutual and  not in risk of being just one-sided. This is more an issue of modeling and not of the problem itself.

The sets in general are not disjoint, as a cut would require them to be, unless you are referring to the subgraph of a certain person's friends (the adjacent vertices). In the social network graph, complex relations can be formed. For example, think of a triangle graph of 3 friends: You (A) might care for a friend B who also cares for your mutual friend C, however you ignore C. It is unclear in which subgraph C belongs. Experimenting with graphs allows you to find a lot of examples where the two sets are not disjoint.

Even if the subgraphs were disjoint and you wanted to know how communities, i.e.  groups of people that care for each other, appear in the graph, this is the min-k-cut problem , which is NP-complete, unless you know the number of communities (which in general you don't).

However, you can easily obtain the two subgraphs you want, by selecting a threshold and then on one graph include all edges (and their adjacent vertices) that pass that threshold, constructing the "who-cares_about-who"
 subgraph and in the other one include the edges that do not and also invert the weights, so that the bigger the weight, the higher the lack of interest between two friends. The problem with this approach is that deciding the value of the threshold is an optimization problem which seems to be reduced to the previous NP-complete problem. Still, you can use a number of techniques from statistics and experimental data to have a fixed threshold, perhaps associated with a level of confidence. Furthermore, you can use fuzzy logic so that the threshold is an interval instead of a fixed point, increasing the accuracy but risking false positives.


What is the difference between meaning and denotation? In programming language semantics, it is often heard that people talking about meaning and denotation.  They seem not to be the same.  What is the difference?  Is the former associated with operational semantics while the latter with denotational semantics?  Thanks.

"Meaning" is used in a broader way than denotation is.

The original dichotomy, inherited from logic and philosophy, is between "sense" and "denotation" (which philosophers call "reference").

This distinction can be illustrated by Frege's original example. He noted that phrases "the morning star" and "the evening star" referred to the same object --- the planet Venus --- but that the sentence "the morning star and the evening star are the same planet" actually conveys some information to a reader. He suggested that the meaning of a noun phrase can go beyond the actual object it denotes, including something about how it presents the object it denotes.

Similarly, in a programming language, the expression $8 \times 7$ is not the same as the expression $56$, even though they may be (ought to be!) completely indistinguishable by any client program. But even though they are indistinguishable, they are not the same -- when evaluating the two programs, your machine does a multiplication in the first case, and doesn't in the second.

When building a denotational semantics, we try to build a model of a language in which indistinguishable programs denote --- refer to --- the same mathematical object.  The goal is to simplify reasoning about the behavior of programs, since we can reason about the denotations, the mathematical objects, without having to worry about the details of how the program is presented. This lets us avoid having to deal with aspects of the meaning of programs that are not of interest to us.

The way sense and denotation relate to operational semantics is more complicated, and different. I may extend my answer later to cover this, but I have to run now. :)

EDIT: Okay, I'm extending this answer now.

The connection between "denotation" and "reference" is pretty much exact, and it's exact because the people who invented denotational semantics (e.g., Scott and Strachey) were quite consciously appropriating ideas from philosophical logic as part of their project.

To understand how meaning and operational semantics relate, it's helpful to recall the philosopher Michael Dummett's notion of a "meaning theory" and how it differs from a "semantic theory".

In Dummett's terminology, a semantic theory is a compositional way of relating  sentences to determinate mathematical objects. In logic, the meaning of a sentence is its truth-value, and it is determined from the truth-values of its constituents. Denotational semantics of programming languages uses a much wider variety of mathematical objects, but it works the same way -- we give the meaning of a program term in terms of the meaning of its subterms. So in Dummett's terminology, denotational semantics offer semantic theories of programming languages.

A meaning-theory is also a compositional way of relating sentences to mathematical objects, but in addition it contains an account of what justifies the relationship between the sentence and the mathematical object. He developed this idea in order to understand how intuitionistic mathematicians understood the notion of truth. In particular, they had a compositional account of the meaning of logical connectives, but did not give them semantic values in the same way that classical logicians do. For example, in the Brouwer-Heyting-Kolmogorov account of intuitionistic logic, truth is defined in the following way:

A canonical proof of $A \land B$ is a pair $(p_1, p_2)$, where $p_1$ is a canonical proof of $A$ and $p_2$ is a canonical proof of $B$.
A canonical proof of $A \vee B$ is a pair $(i, p)$, where $i$ is either $0$ or $1$, and if $i$ is $0$, then $p$ is a canonical proof of $A$, and if $i$ is $1$, then $p$ is a canonical proof of $B$.
A canonical proof of $A \to B$ is an effective procedure, that takes any canonical proof of $A$ and computes a canonical proof of $B$.
A canonical proof of $\forall x.\;A(x)$ is an effective procedure which takes a numeral $n$, and computes a canonical proof of $A(n)$.
A canonical proof of $\exists x.\;A(x)$ is a pair $(n, p)$, where $n$ is a numeral and $p$ is a proof of $A(n)$.

A proposition $A$ is said to be true when it is possible to give a canonical proof of $A$.

Now, note that this definition connects propositions and truth values, but the connection must be justified by the possibility of giving a canonical proofs.

Operational semantics enters the picture via this notion of justification. An operational semantics is just a description of what an abstract machine does. After we give a denotational semantics, we generally want to show that the denotational semantics is faithful to the operational semantics. This property is called adequacy (along with its big brother full abstraction), and it exactly amounts to giving a meaning-theory that connects abstract machine states with denotational objects, which is closed under the reduction of the abstract machine.

This is actually not the whole story, since what I've laid out here is how to connect operational and denotational approaches via a realizability model. Type theories can also have proof-theoretic semantics (indeed, this prospect was what Dummett was most interested in), but I have not explained that connection in this post.


What do stronger circuit lower bounds give in terms of derandomization? We have $EXP\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

This is essentially $DTIME(2^{O(n)})\not\subseteq P/poly\implies BPP\subseteq io-DTIME(2^{n^\epsilon})$ at every $\epsilon>0$.

Is there any consequence of a stronger derandomization?

Let $a(n)$ be any time constructible superpolynomial.

What does $NTIME(a(n))\not\subseteq P/poly$ give?
What does $DTIME(a(n))\not\subseteq P/poly$ give?

Do these give $BPP\subseteq io-DTIME(poly(n))$ or some thing weaker?

It is known that if $E = DTIME(2^{O(n)})$ is not contained in $SIZE(2^{\varepsilon \cdot n})$ for some $\varepsilon>0$  then $BPP = P$ (https://dl.acm.org/citation.cfm?id=258590).

(Actually, a slightly stronger assumption is needed, namely, the separation between $E$ and $SIZE(2^{\varepsilon \cdot n})$ should hold for almost all input lengths - thanks to Ryan O'Donnel for pointing it out.)

More generally, this paper gives a direct optimal translation of any circuit lower bound into a corresponding derandomization result:
http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf


How long does it take at most for $k$ boolean variables to map back to themselves with a positive disjunctive update rule? I have a vector of boolean variables $v=(x_1,\dots,x_k)$. In each step each variable is updated according to a positive disjunction like so:

$x_1 \leftarrow x_i \vee \dots \vee x_j$
$\dots$
$x_k \leftarrow x_m \vee \dots \vee x_n$

This produces a sequence of vectors $\underline{v} = v_1,v_2\dots$. My question is, how long does it take for $\underline{v}$ to reach a cycle, in terms of $k$, for arbitrary $v_1$, that is:
Let $v$ be a $k$-ary boolean vector. Then $f(v)$ denotes the update function for  according to those rules. We say $v'$ is in a cycle from $v$ if there is an $n>0$ and $m \geq 0$ such that $f^{(m)}=f^{(m+n)}$. We define the smallest time to reach a cycle as the smallest sum $m+n$ for which the equality holds.
The question is: What is an upper bound for the smallest time to reach a cycle in terms of $k$ that holds for all possible starting vectors $v_1$ and all possible update functions $f$.

My idea was to represent the update rules as a dependency graph and look at cycles to form rules such as if $x_i$ is true in $v_y$  and is in a cycle of length $n$, then it will also be true in $v_{y+n}$.
But the best lower bound I could do so far is to construct an example where for even $k=2l$ I construct two cycles of length $l$ and $l+1$ with one common node and start with $v_1$ having exactly one true node. The common node is true every $l$ or $l+1$ steps (depending on in which cycle the first true node was). Since $gcd(l,l+1)=1$, eventually all nodes in the other cycle will be true as well. For this, the common nude must be true $l+1$ or $l$ times, respectively. This yields $O(k^2)$ steps until all nodes are true (and then $\underline{v}$ is trivially cyclic).
Unfortunately, I did not get any upper bound except for the obvious $2^k+1$ since each $v_i$ can only assume one of $2^k$ values.

I am not necessarily looking for an exact upper bound if that turns out to be hard, it'd also be sufficient for me to give the upper bound in $O$-notation, or even just show whether the upper bound is polynomial or exponential.
Further, I'm also interested in and extension to the 3-valued case (with 3-valued Kleene disjunction).

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


One way randomised communication complexity of disjointness I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a universe of size $U$ and Bob wants to determine if the intersection of their sets is empty or not.  I would like prob of error $<1/3$, say.

I can find the standard $\Omega(m)$ bit lower bound and some work on two-way communication complexity, but is there a reference for something tighter for one-way?

EDIT: I should have specified that I am interested in the private  randomness (not public coin) model.

The answer is $\Theta(m\log m + \log\log |U|)$.  In the public coins model, we have (as described above) $\Theta(m\log m)$.  As Yuval suggested above, for the upper bound in the private coins model we need only an additive $O(\log n)=O(\log m + \log\log |U|)$ bits (see theorem 3.14 in the K&N book), where $n$ is the length of the encoding of the input ($n=m\log|U|$).  For the additional lower bound of $\Omega(\log\log |U|)$ in the private coin model, it is enough to concentrate on the case $m=1$ (as the other items can be fixed to be all different), which is just the equality function on $\log |U|$-bit strings, whose private coin complexity is logarithmic in that (example 3.9 in K&N).


Reference for fast algorithm for bottleneck shortest paths I am looking for a good reference for bottleneck shortest paths.  Specifically, given vertices s and t in an undirected graph with edge weights, you want the shortest path from s to t, where the length of a path is the maximum edge on that path.  This can be solved in O(n+m) time by finding the median edge weight and (carefully) recursively deleting half the edges.

  Does anyone know a reference for
  this?

P. M. Camerini (1978), The min-max spanning tree problem and some extensions, Information Processing Letters 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3


Outer part of Voronoi diagram in 3D Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any other point in $V$ is exactly a part of the diagram. See also Wikipedia.

It is well known that for $d=2$, its complexity is $\Theta(n)$ and it can be computed in $O(n \log n)$ time. For $d=3$ however, there are families of pointsets for which the Voronoi diagram has complexity $\Theta(n^2)$, and for $d > 3$ there are even worse cases.

However, from what I've seen, all these bad cases seem to occur 'inside' the pointset, and for the purpose I have in mind, this inside is irrelevant.

Let $m = \max \{ |uv| \mid u, v \in V \}$. Suppose therefore we take a bounding box around our pointset $V$ and increase its size by some constant factor $c$ so that any point in $V$ is at least $m (c-1)/2$ away from this larger box. We take the Voronoi diagram for $V$ and remove the part that is inside the box. We name this new diagram the outer Voronoi diagram.

  What is the worst-case complexity of the outer Voronoi diagram for $d=3$? What if $d>3$? If this complexity is smaller than the normal Voronoi diagram, can we also compute it faster?

I think it's still quadratic, for arbitrarily large choice of $c$.

Let $\epsilon$ be small, and place two line segments $s_1$ and $s_2$ of length $\epsilon^2$, each tangent to the unit sphere at their midpoints, at distance roughly $\epsilon$ apart from each other. Because the line segments are so short, the Voronoi diagram of the two line segments approximates the Voronoi diagram of the two midpoints, which is just a plane $P$ bisecting the sphere. At the center of the sphere, the two equal closest sites are the midpoints of the segments.

Now, place equally spaced points on each segment. This will cause the Voronoi diagram of the points of a single segment $s_i$ to consist of two halfplanes separated by many thin slabs bounded by parallel planes, that all pass near the center of the sphere. These slabs intersect $P$ in thin parallel two-dimensional stripes, whose slope can be controlled by the angle at which $s_i$ is placed relative to the sphere. By choosing the angles of $s_1$ and $s_2$ so that they are skew to each other, the stripes for $s_1$ on $P$ can be made to cross the stripes for $s_2$ on $P$, near the center of the sphere. This in turn means that for each pair of a Voronoi region from $s_1$ and a Voronoi region from $s_2$, there is a boundary between the two regions near the center of the sphere. Thus, the Voronoi diagram has quadratic complexity in a region of space (the center of the sphere) that is far from a bounding box of the generating sites.


How to automatically generate indexes and preaggregations from queries This question might be a little ill-specified, but the idea I want to explore is:

User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-only database table)
The schema for the data is specified

Using this input, what data structures need to be generated to "efficiently" query the table? The program would read the input data and then generate a bunch of indexess/pre-aggregations so that the queries will be ultra fast.

For a really simple example, say I have a table of logs:

(URL, IP address, user agent, response code)

And I input a queries like:

select * where URL = http://foo

Then it should know to automatically generate an index on the URL field.

If I also specify:

select count(*) from table group by IP_address desc limit 20

or however you specify the 20 most common IP addresses, then it should also generate some pre-aggregation that is efficient (think of having 100 million rows).

I'm sure I am not specifying the problem completely, but I found some papers that seem related, i.e. http://scholar.google.com/scholar?cluster=1230153639822613926&hl=en&as_sdt=0,5

Looking for more references in this area. This is a computer science/algorithm question; I'm not looking for ways implement to implement this with MySQL or anything like that. Thanks.

Hmm...

You could use undirected multigraphs or alternative graph structures stacks (epicly space inefficient).


Learnability of constraint satisfaction problems CSPs? This may sound more like a soft question but I am struggling to find an answer for it.

While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of machine learning and learning theory, there is almost nothing on learning CSPs. Given that CSP is a well known constraint formalism, I found this very weird. Am I missing something here?

You are probably looking for this paper:

Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003.  doi:10.1016/S0304-3975(03)00342-6

In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms.  This includes CSPs as a special case of more general quantified formulas (since a CSP instance is just an existentially quantified conjunctive formula).

For the Boolean case and also for two broad classes of non-Boolean formulas, there is a dichotomy between polynomially learnable (via the Generating Set algorithm, if the clone contains a "nice" operation) and not, subject to the hypothesis that there exists a public key cryptosystem secure against chosen ciphertext attacks.


When does automaton stay unchanged after string homomorphism? Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$.
Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to expand each $\varphi(\Sigma)$, but leave them in this abstract form, e.g., $\varphi(a)\varphi(b)\varphi(a)$ would be a word.
So in fact for any language $L$, the language $\varphi(L)$ is the same as $L$, over a different alphabet.
If $M$ was an automaton over $\Sigma$, then there is a natural automaton, $\varphi(M)$, over $\varphi(\Sigma)$ with the same number of states: from any given state after reading $\varphi(a)$, $\varphi(M)$ goes to whatever state $M$ would go after reading all letters of $\varphi(a)$.

For example, suppose that $M$ was counting the parity of $b$'s, that is, from state 0 it goes to state 1 iff the read letter is $b$, and vica versa.
Let $\varphi$ map $a$ to $\varphi(a)=ab$ and $b$ to $\varphi(b)=bab$.
Then $\varphi(M)$ goes from state 0 to state 1 iff the read letter is $\varphi(a)$.
Therefore, $M$ and $\varphi(M)$ are isomorphic.
In fact, for the above $M$, we get an isomorphic automaton if and only if exactly one of $\varphi(a)$ and $\varphi(b)$ have an odd number of $b$'s.

  In general, for what $M$ and $\varphi$ will be $\varphi(M)$ isomorphic to $M$?

If it makes the question simpler, we can ignore which states are accepting and which is the start state.
I am interested in any type of conditions, as I could not find anything on the subject.
I am also curious when $\varphi(M)$ will be minimal for the language it recognizes.

Let $\mathcal{A} = (Q, A, \cdot, q_0, F)$ be the minimal DFA of your language $L$. If I understand correctly, you would like to have a permutation $\sigma$ on $A$ such that
$$
q \cdot \varphi(a) = q \cdot \sigma(a)
$$
for every state $q$ and letter $a$. This will happen if and only if, there exists $\sigma \in \mathfrak{S}(A)$ such that, for each letter $a$,
$$
\varphi(a) \in \bigcap_{q \in Q} L(q, q \cdot \sigma(a))
$$
where, given two states $p$ and $q$, $L(p, q) = \{u \in A^* \mid p \cdot u = q\}$.

For instance, in your example, you get the following conditions when $\sigma$ is the identity
\begin{align}
 \varphi(a) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
 \varphi(b) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\
\end{align}
and the following conditions when $\sigma$ is the transposition $(1\ 0)$
\begin{align}
 \varphi(a) \in L(0,1) \cap L(1,0) &= \{ u \in A^* \mid |u|_b \text{ is odd }\} \\
 \varphi(b) \in L(0,0) \cap L(1,1) &= \{ u \in A^* \mid |u|_b \text{ is even }\} \\
\end{align}
which, altogether, gives your condition.


A category of NP-complete problems? Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, where can I find it?

The area you want to look at is called "implicit complexity theory". A random and incomplete fistful of names to Google for are Martin Hofmann, Patrick Baillot, Ugo Dal Lago, Simona Ronchi Della Rocca, and Kazushige Terui.

The basic technique is to relate complexity classes to subsystems of linear logic (the so-called "light linear logics"), with the idea that the cut-elimination for the logical system should be complete for the given complexity class (such as LOGSPACE, PTIME, etc). Then via Curry-Howard you get out a programming language in which precisely the programs in the given class are expressible. As you might expect from the mention of linear logic, these all these systems then give rise to monoidal closed categories of various flavors, which leaves you with a purely algebraic and machine-independent characterization of various complexity classes.

One of the things that make this area interesting is that neither traditional complexity nor logical/PL methods are entirely appropriate.

Since the categories involved typically have closed structure, the combinatoric methods favored by complexity theorists often break down (since higher-order programs tend to resist combinatorial characterizations). A typical example of this is the failure of syntactic methods to handle contextual equivalence. Similarly, the methods of semantics also have trouble, since they are often too extensional (since traditionally semanticists have wanted to hide the internal structure of functions). The simplest example I know here is the closure of LOGSPACE under composition: this is AFAIK only possible due to dovetailing and selective recomputation, and you can't treat the problems as pure black boxes.

You will likely also want to have some familiarity with game semantics and Girard's Geometry of Interaction (and their precursor, Kahn-Plotkin-Berry's concrete data structures) if you get seriously into this area -- the ideas of token-passing representations of higher-order computations used in this work supply a lot of the intuitions for ICC.

Since I've pointed out the central role of monoidal categories in this work, you might reasonably wonder about the connections to Mulmuley's GCT. Unfortunately, I can't help you here, since I simply don't know enough. Paul-André Melliès might be a good person to ask, though.


Is partitioning a multiset into two multisets with equal averages NP-complete? The subset sum problem of partitioning a multiset of integers into two multisets with equal sums is NP-complete. Is the seemingly related problem of partitioning a multiset of integers into two multisets with equal averages also known to be NP-complete? Does the problem have a received name? I have found no formal analysis of the problem online, only an occasional speculation that the problem may be “hard.”

One NP-hard variant of the PARTITION problem is as follows:

  INSTANCE: $2k$ positive integers $a_1,\ldots,a_{2k}$ with $\sum_{i=1}^{2k}a_i=2A$
  QUESTION: Does there exist an index set $I\subseteq\{1,\ldots,2k\}$ with $|I|=k$ so that $\sum_{i\in I}a_i=A$?

Take the integers $a_1,\ldots,a_{2k}$ together with two copies of the integer $100kA$. It is straightforward to see that these $2k+2$ numbers allow a partition into two sets with equal averages, if and only if the original instance of PARTITION has answer yes.


Randomized Polynomial Hierarchy? I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$?

It seems, we could still build a hierarchy, the same way as $PH$ is built, just using $RP$ everywhere instead of $NP$, and $coRP$ instead of $coNP$. Let us call it Randomized Polynomial Hierarchy ($RPH$).

My first guess is that $RPH\subseteq BPP$, or maybe $RPH=BPP$. It is based on the known  fact that $NP=RP$ implies $PH=BPP$. Nevertheless, if $P\neq RP$, then $RPH$ could still be a proper, infinite hierarchy within $BPP$.

Of course, the edge of the issue is blunted by the fact that $P=RP$ is conjectured (even $P=BPP$), which would flatten $RPH$ into $P$.  However, $P=RP$  is not known at this time, and it has resisted all proof attempts so far. Therefore,  $RPH$ still has at least some chance to be a proper hierarchy.

While $RPH$, admittedly, has a good chance to be "flat," could the concept still be useful for something nontrivial? Here is an example: if one can prove $RPH=BPP$, then it would yield that $P=RP$ implies $P=BPP$, which, I think,  would be an interesting result.

Is anything known about this?

Clearly, $\mathrm{RPH}\subseteq\mathrm{BPP}$. On the other hand, $\mathrm{BPP}=\mathrm{ZPP^{promiseRP}}$ (Buhrman&Fortnow, pdf), so the only way the hierarchy didn’t collapse to (at most) the second level and didn’t exhaust $\mathrm{BPP}$ would be for the  unlikely reason that $\mathrm{RP}$ oracles were significantly weaker than $\mathrm{promiseRP}$ oracles.


A square with entries whose adjacencies never repeat Suppose we have an $n \times n$ square, and an alphabet $\Gamma$.  We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location.  The constraint is that a pair $a,b$ of neighbors (either east-west of each other, or north-south of each other) can only appear in that configuration once.

Example of a prohibited square:

a b c
d e f
g d e

Since "de" appears on both the second and the third row, the entries of the square are not acceptable. The same problem would arise if, say, a appeared above d anywhere except the top left corner.

  Given $n$, the width of the square as a parameter, what is a lower bound on the size of the alphabet $\Gamma$?

I would love (suggestions toward) a direct proof, but also, has this type of square-filling problem been studied?  I can't connect it to either a Latin square, or a block design.  Does this map onto any already-named combinatorial object?

(Note: this is related to a previous question of mine about avoiding partial words, but that question only required avoidance east-west, so to speak, whereas here I need to avoid north-south repetitions also.)

An extended version of my comment:

Let $p = n+1$ be a prime number. Then we can construct an $n \times n$ square from the multiplication table of integers modulo $p$. For example, if $p = 5$, we have

1234
2413
3142
4321

Now each pair $ab$ with $a \ne b$ occurs exactly once. Similarly, each pair $a$-above-$b$ with $a \ne b$ occurs exactly once.

Hence this is a valid construction; alphabet size $n$ and an $n \times n$ square.

Moreover, it is optimal. In an $n \times n$ square there are $n(n-1)$ horizontal pairs, and each of them must be different. If we had an alphabet of size $n-1$, we could only construct $(n-1)^2 < n(n-1)$ different horizontal pairs.


Oracle Construction for Grover's Algorithm In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's algorithm, there seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. Specifically, my question is this: given some f(x) such that for some x value, f(x)=1, but for all others, f(x)=0, how does one construct an oracle that will get us from our initial, arbitrary state |x>|y> to |x>|y+f(x)>? As much explicit detail as possible (perhaps an example?) would be greatly appreciated. If such a construction for any arbitrary function is possible with Hadamard, Pauli, or other standard quantum gates, a method for construction with these would be appreciated.

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.

For example, suppose you have a 3-sat problem:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Now make a circuit that computes whether the input is a solution, like this:

Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):

That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.

Iterate diffusion steps with oracle steps, and you've got yourself a grover search:

... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).


Nearly-Eulerian Tours The Eulerian Tour problem is of course a well-studied classical problem in graph theory (Wikipedia article). This question concerns non-Eulerian graphs; i.e., graphs that contain one or more odd-degree vertices. In a nutshell, I wonder what is the best "Eulerian-like" way of traversing non-Eulerian graphs.

Given an undirected connected graph, let an Eulerian "semi-tour" be defined as a "cycle" that passes each edge at least once and can visit any vertex or edge multiple times. Consider the following costs for a given semi-tour:

Total cost: The total number of edges visited by the semi-tour, counting multiplicities.
Width cost: The number of times the most-visited edge is visited.

I'm interested in optimization problems that aim to find a semi-tour that minimizes the total cost or the width cost on a given graph. Of course, if a graph is Eulerian, an Eulerian tour would be optimal, for which the total cost is the number of edges and the width cost is zero. For graphs containing odd degree vertices, the optimal cost in both senses must be larger.

I suspect these optimization problems (if not trivial) must have been well studied in the literature. What are the relevant references, if any, and what is known about these problems (both algorithmically and combinatorially)?

For total cost, see http://en.wikipedia.org/wiki/Route_inspection_problem (also called the Chinese postman problem). The optimal solutions to this problem visit each edge at most twice, so they also optimize your width cost.


Complexity of counting products of commuting operators drawn from a specific set. I have run into the following problem in the course of trying to solve another problem, and have been unable to come up with a decent answer. This may reduce trivially to a known problem, but if so I am not seeing it, and would be extremely thankful if someone could point me in the right direction.

Given a set of unique $n \times n$ matrices $\{\lambda^{i}\}$ of the form $\lambda^{i}_{jk} = \delta_{jk} (1-2\delta_{x_i j}-2\delta_{y_i j})$, where $1\leq x_i < y_i \leq n$, is there an efficient way to calculate $N_D$, the number of operators of the form $C_b = \prod_i \left(\lambda^i \right)^{b_i}$ which satisfy $\mbox{Tr}(C_b) = D$? Here $b_i \in \{0,1\}$. I would be interested to know if there is any polynomial time algorithm, or even if it is in P/poly, or alternatively, if this reduces to some more studied open problem.

As things stand, I can currently obtain $\sum_D N_D$ and $\sum_D N_D D$, but not enough other linearly independent equations to be able to solve individually for each $N_D$.

For $D$ unrestricted, computing $N_D$ exactly is equivalent to evaluating the Tutte polynomial of a graph: the values $N_D$ determine the weight enumerator of a linear code, also known as the Tutte polynomial of a binary matroid, and your restriction on the $\lambda^i$ corresponds to the linear code being given by a basis of vectors of Hamming weight 2, which is the just the usual cycle matroid of a graph.

On the other hand, we can calculate $N_{n-2k}$ if $k$ is constant in polynomial time as follows. There are $O(n^k)$ diagonal matrices $C$ with $n-k$ ones and $k$ minus-ones. These can be enumerated in polynomial time for fixed $k$. $C$ can be considered as a point in $\mathbb{F}_2^n$ and each $b$ can be considered as a point in $\mathbb{F}_2^m$ where $m$ is the number of $\lambda^i$s. This turns multiplication into addition, so the definition of $C_b$ becomes $C_{b_j}=\sum \lambda^i_{jj} b_i$. In Diestel's book on graph theory the values $b$ such that $\sum \lambda^i_{jj} b_i=0$ are called the cycle space of the graph.


Counting complexity of a scheduling problem. Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\pi$, such that $\sum_{i=1}^k p_{\pi(i)} \le d_{\pi(i)}$ for all $k=1,\ldots,n$.

Does there exist a pseudo-polynomial time algorithm for computing the total number of feasible schedules?

A pseudo-polynomial time algorithm is an algorithm whose running time is bounded by a polynomial on the size of the input, given that the input is written in unary notation (2 = II, 3 = III). (e.g., the size of a number n in unary notation is $O(n)$, and not $O(\log(n)))$.

Edit: It seems that the questioner knew that this was an open problem: https://mathoverflow.net/questions/33796/existence-of-a-pseudo-polynomial-time-algorithm-for-a-counting-problem.  For what it is worth, it took me some time to find the paper, and I think that the time was wasted.

This question is stated as an open problem in [Ber09], where the same problem except that the numbers in the input are written in binary is shown to be #P-complete by a reduction from the counting version of the Subset Sum problem.

References

[Ber09] Gerardo Berbeglia.  The counting complexity of a simple scheduling problem.  Operations Research Letters, 37(5):365–367, Sept. 2009.  http://dx.doi.org/10.1016/j.orl.2009.05.004


Distinguishing semantics vs syntactic techniques and the syntax of your semantic domains Consider a denotational semantics from simply-typed $\lambda$-calculus into dependent type theory. Is that actually a (trivial) term transformation into that dependent type theory? After all, type theory has a syntax.

In fact, even set theory has a syntax*! So how do we distinguish a denotational semantics from a compositional term transformation?

Now, let's generalize to less trivial program transformations — say, transformation to continuation-passing style (or store-passing style, environment passing style, ...). You can show the same idea through a non-standard semantics (here, a continuation-passing semantics) or a term transformation into a continuation-passing term, and they're distinguished by a binding-time shift. Again, isn't the non-standard semantics also a term transformation?

This is a concrete confusion which I've observed at least twice:

In my work (on incremental computation) I've used a non-standard denotational semantics into type theory (a "change-passing" semantics). After a presentation of that, Gabriel Scherer remarked (kindly) that for him, that was a term transformation into a dependently typed language.
"F-ing modules" preempts this confusion — they defend their presentation of the syntax of semantic objects.

  Semantic signatures. The syntax of semantic signatures is given in Figure 9. (And no, this is not an oxymoron, for in our setting the “semantic objects” we are using to model modules are merely pieces of Fω syntax.) [Emphasis added.]

*Apparently, some (non-formalists) claim that set theory is not "just syntax", but something ontologically different. I'll ignore this subtle philosophical issue; the only reference I know on it is Raymond Turner's Understanding Programming Languages.

I think I understand your difficulties, indeed if you consider just a programming language both a denotational semantics and a term transformation (into another language) are nothing but mappings of syntactic elements of the given language in mathematical objects (elements of a domain in the first case, terms of the language in the second case).

Notheless differences between these two semantics start to arise if you put an operational semantics in your programming language and so you want that the denotational semantics and term transformations are compatible with this operational semantic.

In the first case you would like that denotation of terms/programs that compute the same results have the same denotation, hence the denotational semantics should associates to operational convertible terms the same denotation.

In the second case you would simply like that the term transformation maps terms/programs in such a way to preserve the derivations (if you reguard terms and reduction/derivations respectively as objects and morphisms of a category you can say that a term transformation should be a functor).
In the first case we lost information about the reduction between terms in the second case we preserve it.

In the first case semantically equivalent terms are mapped in the same denotation in the second they are mapped just in operationally equivalent terms but the term translation does not guaratee that equivalent terms are mapped in the same term (and usually that's not the case).

Denotational semantics  allows to easily find different terms, supposing that the denotation-mapping is easily computable, in order to distinguish two programs we just need to compute the denotation an see if they are different values.
Nonetheless in this way we lost information about the reductions (computations of our operational semantics) which are instead preserved by the term transformations.

I hope this helps.


Uniform way of quantifying "branching" in nondeterministic, probabilistic, and quantum computation? The computation of a nondeterministic Turing machine (NTM) is well known to be representable as a tree of configurations, rooted at the starting configuration. Any transition in the program is represented by a father-child link in this tree.

Similar trees can also be constructed for visualising the computations of probabilistic and quantum machines as well. (Note that it is better for some purposes not to view the related graph for quantum computations as a tree, since two nodes representing identical configurations at the same level of the tree can "cancel" each other out, due to quantum interference, but this doesn't have anything to do with the present question.)

Of course, deterministic computations are not like that; there is a single "branch" in the corresponding "tree" for any run of a deterministic machine.

In all the three cases mentioned above, what sometimes makes these computations "difficult" for deterministic computers is not really that there is branching going on, rather, it is a matter of how much branching is present in the tree. For instance, a polynomial-time nondeterministic Turing machine which is guaranteed to produce computation trees whose "widths" (i.e. number of nodes in the most crowded level) are also bounded above by a polynomial function of the input size can be simulated by a polynomial-time deterministic TM. (Note that this "polynomial width" condition is equivalent to restricting the NTM to make at most a logarithmically bounded number of nondeterministic guesses.) The same thing is true when we put similar width bounds on probabilistic and quantum computations.

I know that this issue has been examined in detail for nondeterministic computations. See, for example, the survey "Limited Nondeterminism" by Goldsmith, Levy, and Mundhenk. My question is, has this phenomenon of "limited branching" or "limited width" been studied in a common framework encompassing all of the nondeterministic, probabilistic, and quantum models? If so, what is the standard name for it? Any links to resources will be appreciated.

Nondeterministic computations can also be viewed as verification of claims using short proofs. That is, the class NTIME(t) can also be viewed as the class of languages $L$ such that a claim of the form $x \in L$ can be verified in time $t(|x|)$ by reading a short proofs. In this model, "quantifying the braching" is analogous to studying how short the proofs can be. While I don't know of papers that studied this question, this could give you a direction of where to look for them.
One paper that studied a related question in the context of interactive proofs is "On Interactive Proofs with Laconic prover", by Goldreich, Vadhan, and Wigderson:
http://www.wisdom.weizmann.ac.il/~oded/p_laconic.html

Regarding probabilistic computation: The amount of "branching" used in the computation is exactly the number of random bits/coin tosses that the algorithm uses. Quantifying this number and minimizing it is studied extensively in the area of "Derandomization". You can read about it in Chapters 20 and 21 of the Arora-Barak book (http://www.cs.princeton.edu/theory/index.php/Compbook/Draft) or in Chapter 8 of Goldreich's book (http://www.wisdom.weizmann.ac.il/~oded/cc-book.html).
It should also be mentioned that the common belief in this area is that $P=BPP$. If this is true, then the number of random bits a computation uses does not affect its power, as long as this number is polynomial.


Complexity of counting weighted cycles in planar graphs? Assume G is a weighted planar graph, nodes and edges in G are weighted, and K is a given constant.
A is a decision problem with following description:

  Does G contain a cycle with total
  weight K ?

What is the complexity of the counting version of A (#A)? (i.e the complexity of counting all cycles with total weight K)

If you allow repetition of vertices, but not edges, within a cycle, then the problem is $\text{#P}$-complete.  This paper shows that the problem of counting Eulerian tours is $\text{#P}$-complete for 4-regular planar graphs.  Therefore the problem I just described (call it $\text{#}A^\prime$) is $\text{#P}$-hard, because it is at least that difficult: in the special case where all edges have weight 1 and all nodes have weight 0, the Eulerian tours are just those cycles with total weight equal to the number of edges in the graph.  On the other hand, $\text{#}A^\prime\in\text{#P}$, because the corresponding decision problem $A^\prime \in \text{NP}$.


One-way randomized communication complexity of Greater-Than Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the positive integer whose binary representation is $y$.
It is well-known that the randomized communication complexity of $\mathrm{GT}_n$ is $\Theta(\log n)$. Several references claim that the randomized one-way communication complexity of $\mathrm{GT}_n$ is $\Theta(n)$, but I am unable to find a reference that actually contains a proof. It is easy to show a $\Omega(n/\log n)$ lower bound by a reduction from INDEX, and this is done in a paper by Kremer, Nisan, and Ron. They also claim that the proof of the $\Omega(n)$ lower bound appears in a paper by Miltersen, Nisan, Safra, and Wigderson. The latter paper uses a round-elimination lemma to show a $\frac{n^{1/k}}{120^k}$ lower bound on the $k$-round communication complexity of $\mathrm{GT}_n$ but never gets around to proving the base case somehow (see Theorem 14), and the base case is all I am asking for. They also claim this is an unpublished result of Yao, but as far as I know that result may never have been written down.
Surely at some point someone wrote down a proof of this lower bound? The closest I could find (with help from Clément Canonne) is this paper showing a lower bound on the quantum one-way communication complexity of $\mathrm{GT}_n$ and that just seems like an overkill.

If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}_n$ with $n = 1$ requires one bit of communication.
If the goal is simply to convince oneself from first principles that $\textrm{R}^\to(\textrm{GT}_n) = \Omega(n)$, this is immediate by reduction from the AUGMENTED-INDEX problem. An $\Omega(n)$ one-way lower bound for AUG-INDEX boils down to the chain rule for mutual information. For a discussion of AUG-INDEX, see, e.g., Section 3.4 of Jelani Nelson's PhD thesis (https://people.eecs.berkeley.edu/~minilek/publications/papers/phd_thesis.pdf).


Do any quantum algorithms improve on classical SAT? Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )

For comparison, using Grover's algorithm on a quantum computer would look for and provide a solution in $1.414^n$, randomized. (This may still require some knowledge of how many solutions there may or may not be, I'm not sure how necessary those bounds still are.) This is clearly significantly worse. Are there are any quantum algorithms that do better than the best classical algorithms (or at least -- almost as good?)

Of course the classical algorithms could be used on a quantum computer assuming sufficient working space; I'm wondering about inherently quantum algorithms.

Indeed, as wwjohnsmith1 said, you can get a square root speed-up over Schöning's algorithm for 3-SAT, but also more generally for Schöning's algorithm for k-SAT. In fact, many randomized algorithms for k-SAT can be implemented quadratically faster on a quantum computer.

The reason for this general phenomenon is the following. Many randomized algorithms for k-SAT that run in time $O(T(n) \mathrm{poly}(n))$ (where $T(n)$ is some exponentially growing function of $n$) actually do something stronger. At their core, there is a polynomial-time algorithm that outputs a satisfying assignment, if one exists, with probability at least $1/T(n)$. From this it is clear that if you repeat this poly-time algorithm $O(T(n))$ many times and accept if any of the runs returns a solution, you will get a randomized algorithm for k-SAT that runs in time $O(T(n) \mathrm{poly}(n))$.

Now instead of running this algorithm $O(T(n))$ times, you can run amplitude amplification on this poly-time algorithm. Amplitude amplification is a general quantum algorithm that can decide if another algorithm accepts with probability 0 or with probability $1/T$ using only $O(\sqrt{T})$ uses of this algorithm. Applying amplitude amplification to such a k-SAT solver will immediately yield a quantum algorithm for k-SAT with running time $O(\sqrt{T(n)}\mathrm{poly}(n))$, which is quadratically faster (ignoring the poly(n) term).


Linear Function Representation of Neural Network I have trained a neural network using MATLAB and am ready to deploy it into my software. Right now, I include it in my software by programming the structure of the neural network and the connection weights and doing some matrix multiplication.

But there has to be a better way to do this: neural networks are basically linear separators. This means that it should be possible to model the outputs as some linear function of the inputs.

So here's the question: given the structure of a neural network and the connection weights after training, how would I come up with the correct linear function of the inputs that models the functionality of the network?

It would seem to depend on the complexity of your neural network. A single perceptron is a linear separator. On the other hand, it is known that multilayer feed-forward neural networks are universal approximators (see here: http://dl.acm.org/citation.cfm?id=70408 ): i.e. they can approximate any function to arbitrary accuracy. Obviously for such a network, you should not expect to be able to express its outputs as a linear function of its inputs.


Issue with inequalities involving probablities I'm reading this paper http://eccc.hpi-web.de/report/2016/044/download/, at page 7 you can see this equation:

$$ \sum_t \mathbb{E}_{w \in W} [|p_t - p_{t|w,w}|] = 2 \sum_t \mathbb{E}_{w \in W} [\max(0,p_t - p_{t|w,w})]$$

I think what we're using here is this:
$$a+b+|a-b| = 2 \max(a,b)$$

but with $a=0$ and $b=p_t-p_{t|w,w}$ we get:
$$p_t - p_{t|w,w} + |p_t - p_{t|w,w}| = 2\max(0,p_t - p_{t|w,w})$$
I know it's a bit of a silly question but I just can't figure it out, maybe I'm missing some fact about probabilities?

This uses the fact that the L1-norm between two probability distributions is equal to twice their total variation distance.

See https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures

To prove the equality you take the subset A in the definition to be the set of points where $$p_t > p_{t|w,w}.$$


Balanced Max-2-SAT NP-Hardness The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ times in the clauses, and exactly $k$ times negative in the clauses.

I'm looking for a published proof of NP-Hardness for this problem, for references.

It is implied NP-Hard by [this paper],
but I can't find the original NP-Hardness proof.

Is it a consequence of the hardness of Max-2-SAT ?

Also as a bonus, Balanced Max-2-SAT($k$) is the subcase in which every variable appears exactly $k$ times positive, exactly $k$ times negative.
Is there some known $k$ for which NP-Hardness is published?
I know that Balanced Max-3-SAT(2) is hard, but found nothing for the $2$ case.

I think it is possible to reduce Max Cut to this problem: given a graph $G(V,E)$, make a variable for each vertex, and for each edge $(u,v)\in E$ make the two clauses $(x_u\lor x_v)$ and $(\neg x_u\lor\neg x_v)$. In the resulting instance, $x_u$ appears $d(x_u)$ times positive and the same number of times negative. Since Max Cut is still NP-hard on regular graphs, this proves that the version for which $k$ is the same for all variables is also hard.


VC-dimension of infinite set of triangle wave I am searching for the VC-dimension of the following:
What is the VC-dimension of the infinite set of triangle wave functions with
amplitude 1 and period parameter p on points on the line?
2πarcsin(sin(2πx⁄p))

First of all, presumably you want the VC-dimension of your class of composed with the sign function, which yields a class of Boolean functions (otherwise, VC-dim is not defined). With that out of the way, the answer is: It's infinite. That will be the answer for any periodic function class that contains all possible frequencies and crosses the x-axis. For a concrete proof for this sine wave, see Theorem 9 here:
https://www.cs.bgu.ac.il/~karyeh/fat-add.pdf