Efficient enumeration of the reachable leaves of nodes in a polytree

It turns out that it is possible to do what I want with linear preprocessing and constant delay, by an argument suggested by my friend Louis. Here is my summary of his idea.

Edit: The scheme below, in a much more concise and understandable form, appears as Theorem C.1 in our recent preprint. I'm leaving the messy sketch below in case it's useful, but you should probably look at the preprint instead (the theorem and proof are independent from the surrounding material). The proof is generalized to multitrees and also refines the scheme slightly to show a logarithmic bound on memory usage.

Let's consider a polytree $P$. The linear preprocessing can insert
intermediate nodes and collapse nodes with
only one child to get a polytree which we can use to answer queries on the original polytree, so that we can assume
without loss of generality that all internal nodes of $P$ have degree exactly
2.

We will do the linear-time preprocessing bottom-up following any
topological order. For every node of $P$ that we process (whose children have
all already been processed), we will construct an index structure for
the node, which we call an "infix tree", and which may also include
pointers to other previously defined such structures (but not modify
them, of course: one can think of this as a purely functional
data structure supporting constant-delay enumeration and constant-time
union.)

The construction will work in linear time, and for any node we will be
able to enumerate its descendants in constant delay by considering its
infix tree.

There are three kinds of nodes in infix trees:

leaves, which are labeled with an explicit set of at least one and at
most four elements (which are leaves of the original polytree);
small internal nodes, which are labeled with one explicit element
and with pointers to one or two infix tree nodes;
large internal nodes, which are labeled with two explicit elements and
with pointers to one or two infix tree nodes.

We further require that there are no duplicate elements in the infix
tree, i.e., for every node $x$ of the infix tree, each leaf of $P$ appears
at most once in the labels of $x$ and its descendants. A node $x$ in
an infix tree codes a set $S(x)$ of leaves of $P$,
namely, those which appear in the node's label and its descendants (and
as we just assumed it is always duplicate-free). The idea of the infix
tree is that, by keeping around some explicit elements, we can both use
them when enumerating to make progress when visiting the nodes, and use
them when unioning two sets of descendants to have sufficiently many
elements to annotate the newly created nodes in the infix tree.

Our indexing data structure will map each node $n$ of the polytree to an
infix tree node $N(n)$ capturing exactly its reachable leaves, i.e.,
$S(N(n))$ is the set of leaves that are reachable from $n$ in $P$.
There are two claims:

we can actually do this in linear time;
when we have done this, we can enumerate in constant delay.

Let's first see why claim 2 is true. From the infix tree $N(n)$ of a node $n$ of
$P$, we can enumerate its contents in constant delay with the
following algorithm. Maintain a working list $W$ of nodes of the infix
tree to be enumerated, initially it is $\{N(n)\}$. Now, until $W$ is empty,
take its first element $x$ and do the following:

if $x$ is a leaf of the infix tree, enumerate its elements and
discard $x$
if $x$ is an internal node (small or large), enumerate its explicit
elements and add its child nodes to $W$.

It is clear that this correctly enumerates $S(N(n))$, and that it is constant
delay because at each step we enumerate something

So now let's turn to the proof of claim 1. To do this, we will proceed
bottom-up as I pointed out above, further maintaining the following
invariant: for any node $n$ of $P$, $N(n)$ is never a small internal node, so it is
either a large internal node or a leaf. In other words, small internal
nodes will only be used as an intermediate tool in the construction, but
no node of $P$ directly points to such a node in the result of the indexing.

The base case is for a leaf $n$ of $P$, where we set $N(n)$ to be a
fresh leaf node of the infix tree whose contents are $\{n\}$.

The inductive case is for an internal node $n$ of $P$ with
children $n_1$ and $n_2$, for which $N_1 := N(n_1)$ and $N_2 := N(n_2)$ have
already been prepared (and are not small internal nodes). We set $N(n)$ as
follows depending on the types of $N_1$ and $N_2$. Note that, by design, in
the nodes that we add, we will be pointing to $N_1$ and $N_2$ (and also to
their children in some cases), but that's fine provided that we don't
modify them.

If $N_1$ and $N_2$ are leaves and their explicit lists contain at most
four elements total, set $N(n)$ to be a fresh leaf node with an
explicit list which is the union of the labels of $N_1$ and $N_2$.
If $N_1$ and $N_2$ are leaves and their explicit lists contain five or
more elements total, set $N(n)$ to be a fresh large internal node
labeled with the first two elements of the union of the labels, and
whose two children are two fresh leaves with the missing elements
(the two lists can be made non-empty because there are at least two
elements left).
If $N_1$ is a large internal node and $N_2$ is a leaf, we make $N$ a fresh
large internal node labeled with the elements of $N_1$, and having one
child which is a fresh small internal node labeled with the first
element of $N_2$ and whose children are (pointers to) the children of
$N_1$. If $N_2$ has strictly more than one element, we create a fresh leaf
node containing the remaining elements of $N_2$, that we add as a second
child of $N$.
The case where $N_1$ is a leaf and $N_2$ is a large internal node is
symmetric to the case above.
If $N_1$ and $N_2$ are large internal nodes, we create a fresh large
internal node $N$ containing the elements of $N_1$, and whose children are
two fresh small internal nodes, the first one containing the first
element of $N_2$ and pointers to the children of $N_1$, the second one
containing the second element of $N_2$ and pointers to the children of
$N_2$.

This is clearly in constant time, and one can verify that the semantics
is correct, i.e., $S(N)$ is the set of reachable leaves, with no dupes:
this is obvious for leaves and proved in the inductive case from the
contents of $N_1$, $N_2$ and their children. This concludes the proof of claim 2 and the proof of the overall scheme.


Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

In the standard $\epsilon$-free PDA definition the transition function is:

$\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$

$(q_i, a, A, q_j, \alpha) \in \sigma$ means that the PDA on state $q_i$, with head on input $a$ and $A \in \Gamma$ on top of the stack, enters state $q_j$ and replace $A$ with $\alpha \in \Gamma^*$

According to this definition, if $|\alpha| \leq 1$ there is no way to increase the stack and the resulting automata is a DFA.

But letting $|\alpha| \leq 2$ is enough to recognize all CFLs; and this is a direct consequence of the following theorem:

Theorem [D.J. Rosenkrantz. Matrix equations and normal forms for context-free grammars] Given a proper context-free grammar $G$, an equivalent context free grammar in quadratic Greibach normal form can effectively be constructed from $G$

A grammar $G$ in quadratic Greibach normal form if every right side of the rules is in the form $A V^*,\; |V| \leq 2$ ($A$ is the terminal alphabet, $V$ is the set of non-terminals):

$X \to a\, B C$ or
$X \to a\, B$ or
$X \to a$

$B, C \in V$

***ADDENDUM

This is an idea to prove that even with the constraint required by domotorp in the question (at each step 1 POP or 1 PUSH or NO CHANGES ) we can recognize all CFLs.

The above theorem says that a PDA $P$ that can "look" at the top symbol $X$ of the stack and according to it and the current input symbol can (i) POP it, (ii) REPLACE it with $B$ or (iii) REPLACE it with $B$ and PUSH $C$ is as powerful as a PDA.

In order to build an equivalent $P'$, we expand the set of non-terminals $\Gamma$ of $P$ to $\Gamma' = \Gamma \times (\Gamma \cup \{ = \})$; we also expand the set of states $Q$ to $Q' = Q \times (\Gamma \cup \{*\})$

The double symbols in each "register" $r$ of the stack are used to store both the symbol at $r$ (left element) and to "override" the symbol at $r-1$ (right element):

      <A,B>  in P' is equivalent in P to  A
      <C,.>                               B
      ....                               ....

      <A,=>  in P' is equivalent in P to  A
      <C,.>                               C
      ....                               ....

If $P'$ is in state $\langle q_j,*\rangle$ it means that the "logic" top of the stack symbol that it should use is effectively the top of the stack; if it is in state $\langle q_j, A \rangle$ then the "logic" top of the stack is $A$ (and the real top should be ignored).

So the replace (ii) operation of $P$ can simply be stored in the internal state of $P'$:

$q_i, a, A \to q_j, B$ becomes

$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, B \rangle, \langle A,\cdot\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j,  B \rangle, \langle \cdot,\cdot\rangle $

As soon as $P$ needs to PUSH $BC$ (iii), it can store $B$ in the right part of the pushed symbol (the "override" part):

$q_i, a, A \to q_j, BC$ becomes

$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, * \rangle, \langle A,\cdot\rangle \langle C,B\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j, * \rangle, \langle \cdot,\cdot\rangle \langle C,B\rangle $

The $P$ POP operation (i) can be simulated popping the current top and if it "overrides" the previous element, store it in the state:

$q_i, a, A \to q_j, \epsilon$ becomes

$\langle q_i, * \rangle, a, \langle A,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, * \rangle, a, \langle A,B \rangle \to \langle q_j, B \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,B \rangle \to \langle q_j, B \rangle, \epsilon$

***ADDENDUM 2

The above proof could be highly simplified, because:

the PDA derived from the quadratic Greibach Normal form needs only one state (provided that the acceptance condition is the empty stack at the end of the input);
$P'$ could simply store the TOP of the stack in its internal state (there is no need to use $\Gamma' = \Gamma \times Gamma$

as soon as I have some free time I'll update the answer.


Where can I seek help when I cannot understand a research paper?

There are a couple options within this site alone, and a couple other options that I’ve heard people having success with.

First of all, there have been several excellent answers on different stack exchanges about how to read papers in general, such as how to read a mathematics paper, how to take notes on research papers, how to remember what you read, and how to choose what to read.

Second of all, the stack exchange network is a great place to get answers to specific questions that you have about a paper or about reading papers.

If you have a general question about reading an academic paper that can be answered without reference to the paper, that will be on-topic on Academia SE.

If you have a specific question about the content of a paper about theoretical computer science, that can be on-topic here, at Math Overflow, and at Math SE depending on precisely what the question is. math.stackexchange is notably the only one on this list that accepts non-research level questions, so if you have a question that comes up in you’re reading that’s more foundational than research level, that’s a better place to ask it. There’s also CS SE  Which doesn’t have the “research-level” requirement but I’m not sure how strong their theory participation is.

The best sorts of questions for these SEs would be a question that can be answered in one go, rather than a question that starts a conversation. For example, questions along the lines of “I don’t understand the motivation/proof/concept in [passage],” would be on-topic. If you’re ever unsure if a question is appropriate, you can ask if you can ask that question on the corresponding meta site. To access the meta, click the meta button or add go to meta.[name].stackexchange.com

All of the aforementioned sites also have a chat that you can check out, and maybe find someone who is willing to sit down and talk about a paper with you for a bit.

Finally, if your question requires significant back-and-forth then a forum is potentially a better site. There are subreddits dedicated to mathematics and computer science, and there are a number of CS-oriented blogs or blogs with substantial CS readership that have open threads that invite people to raise questions that interest them. Slatestarcodex has such threads every other week, and I believe Scott Aaronson’s blog  has them occasionally too. I’m not an avid reader of the later, but it’s quite common for people tor raise papers that interest or confuse them for discussion and explanation on SSC. You used to be able to do this on lesswrong.com as well, though that community is largely defunct now from what I understand. I’m sure there are other blogs or communities that support such activities, and you can probably find them via simply asking around at those two blogs.


3-colourability of Eulerian maximal planar graph

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then propagate information around the cycle you come back to something different.
If you have a dual cycle that surrounds only a single primal vertex, then it's a wheel, and it's inconsistent if and only if it's an odd wheel.
If you have a dual cycle that surrounds more than one primal vertex, you can draw a dual path inside it that splits it into two dual cycles that each surround fewer primal vertices (this is where we use the fact that the triangulation is on the plane and not on a higher-genus surface). If both smaller cycles are consistent you could glue together consistent colorings of both to get a consistent coloring of the whole thing. So by induction on number of primal vertices contained, when the graph is Eulerian, all dual cycles are consistent.


Is there a succinct representation for all problems?

Any language $L$ consisting of strings of length $2^k$ for nonnegative integers k has a succinct version: given a binary circuit $C$ that takes $k$ inputs and outputs a single bit, is the truth table (seen as a binary string of length $2^k$) a string of the language $L$. You can restrict any language to strings whose length is a power of two, or you can try other encoding tricks.


Closure Properties of Locally Testable Language

A language is $k$-locally testable if it is a Boolean combination of languages of the form $\{u\}$, $vA^*$, $A^*v$ or $A^*wA^*$, with $|u| < k - 1$, $|v| = k - 1$ and $|w| = k$. Thus, yes, $k$-locally testable languages are closed under complementation.

But the link you gave to Wikipedia gives the definition of local languages, which is not the same thing as locally testable languages.
And indeed, local languages are not closed under complementation.

Finally, a local automaton recognizing a language $L$ might be incomplete. Therefore, you first need to complete it to compute the complement of $L$ by exchanging final and non final states. But this completed automaton is no longer local...


What are theoretical computer science jobs?

I have a CS Theory background and work in industry doing research at a consulting firm. We get hired by people who want to use various types of computer models and don't have the expertise to create them themselves. This is (partially) a research job because our clients typically have interests usually unaddressed in the academic literature, and so our contracts usually result in us creating new models and techniques that work in their context. I'm currently working on a poster presentation for an academic conference, though one in political science methodology rather than CS.

My group specializes in machine learning and social network analysis, also known as applied linear algebra and graph theory. Our clients tend to be interested in applying this to topics like international relations, logistics, international trade, and cyber security. My coworkers have backgrounds such as a PhD in applied math, a PhD in computational social science, and a masters in computational linguistics. I'm the theoretician in my group and was specifically hired for my pure mathematics knowledge. I primarily work on model design and validation, especially on leveraging graph theoretic structures in the phenomena being modeled to inform model design. I am also the point person for investigating new research and evaluating how it fits into what we are currently working.

I would strongly second Peter Shor's list of recommended skills. The key to being a successful theoretician in industry is to be able to be the bridge between engineers, data analysts, and developers on the one hand and academics on the other.


Minimum length walk from s to t covering a subset of vertices

So you are given a weighted undirected graph $G$. You want to find a shortest walk from $s$ to $t$ such that you visit all the vertices of the set $S$. You may choose to visit vertices in $V \setminus S$. You may visit vertices multiple times. You may use the edges multiple times. Let's call this problem $stSWALK$.

  $stSWALK$ is equivalent to metric Traveling Salesman Path problem ($MTSPP$).

It is easy to see that, when $S = V$ then $stSWALK$ is same as $MTSPP$.

You can convert an instance of $stSWALK$ into an instance of $MTSPP$ by simply computing the shortest paths between every pair of vertices in $S$ (and adding the corresponding "new" edges with the weights equal to the lengths of these shortest paths) and then solving $MTSPP$ on the graph induced by $S \cup \{s,t\}$ (lets call this graph $H$). To get a solution to $stSWALK$, we simply expand these newly added edges into their corresponding shortest paths in $G$.

Note that If $G$ is planar then $H$ is not necessarily a planar graph.


Laying paths on a network using minimum number of links/edges

The problem you are asking is called capacitated network design. Typically each edge e also has a cost/weight w(e) and you want to minimize the weight/cost of the chosen edges such that the resulting graph supports the demands given by $T_{ij}$. The weighted version can be reduced to the unweighted version by replacing an edge of weight w(e) by a path of w(e) edges (this reduction is pseudo-polynomial). The problem is NP-Hard even when $T_{ij}$ is non-zero for a single pair and even here we don't quite understand the approximability.

See the following recent papers for more on this:

Minimum-Cost Network Design with (Dis)economies of Scale. IEEE FOCS 2010.
Approximability of Capacitated Network Design. IPCO 2011.


Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

This problem is strongly reminiscent of "Optimal stopping" of stochastic processes.  These are frequently solved by dynamic programming.  References even to this specialized literature are extensive, due to its applications in decision theory and finance.


Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

There is no such problem.  If it's hard to sample, it's hard to integrate.

Here is a sketch of the reason why.  Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$.  If you can integrate over the set of all solutions, here is an algorithm to sample from all solutions:

Count the number of solutions; call it $N_0$.  (As you say, this can be done efficiently, as it is just an integral.)  Count the number of solutions $x$ such that $x_1=1$; call it $N'_0$.  (This is an integral of the function $f(x)$ over all solutions, where $f(x_1,\dots,x_n) = x_1$, so it can be computed efficiently.)  With probability $N'_0/N_0$, set $y_1 = 1$, else set $y_1 = 0$.
Count the number of solutions $x$ such that $x_1=y_1$; call it $N_1$.  (This is another integral.)  Count the number of solutions $x$ such that $x_1=y_1$ and $x_2=1$; call it $N'_1$.  With probability $N'_1/N_1$, set $y_2 = 1$, else set $y_2 = 0$.
Count the number $N_2$ of solutions $x$ such that $x_1=y_1$ and $x_2=y_2$, and the number $N'_2$ of solutions $x$ such that $x_1=y_1$ and $x_2=y_2$ and $x_3=1$.  With probability $N'_2/N_2$, set $y_3=1$, else set $y_3=0$.
And so on.  When this procedure finishes, output $y_1,y_2,\dots,y_n$.  This will be a valid solution, sampled uniformly at random from the set of all solutions.

It's easy to see that if you have a way to compute the exact integral, you'll obtain a way to sample exactly uniformly at random.  I expect it will follow that if you can approximate the integral, you can sample approximately uniformly at random; I'll let you compute the parameters and relation between the two approximations.

You can also implement this algorithm using expectations.  Let $X$ be a r.v. that is uniformly distributed on the set of all solutions.  Set $y_1=1$ with probability $\mathbb{E}[X_1]$; set $y_2=1$ with probability $\mathbb{E}[\mathbf{1}_{X_1 = y_1} \cdot X_2] / \mathbb{E}[\mathbf{1}_{X_1 = y_1}]$; and so on.  Here I use $\mathbf{1}_{e(X)}$ to represent a function that is 1 if $e(X)$ holds, and 0 otherwise.  Why does this work?  Well, $\Pr[X_1=1] = \mathbb{E}[X_1]$, and

$$\Pr[X_2=1|X_1=y_1] = {\Pr[X_1 = y_1 \land X_2=1] \over \Pr[X_1=y_1]}
= {\mathbb{E}[\mathbf{1}_{X_1 = y_1} \cdot X_2] \over \mathbb{E}[\mathbf{1}_{X_1 = y_1}]}.$$


PiSigma: why does 'unfold' bind a variable?

I don't think there's any magic/necessary reason. IMO, it's written that way to make it more straightforwardly obvious that unfold is an analytic/checking elimination rule; just like why split is written the way it is rather than being written as first and second projections, and why case is written the way it is rather than being written like uneither in Haskell.

Re the "analytic" bit, note how the other elimination rules are either synthetic/inferring (beta) or bidirectional (bang)


Can two strings be matched as disjoint subsequences of a string?

Case k=2

Perhaps you can use the following polynomial time dynamic approach:

Keep a table $T_i$ of $(|S_1|+1)(|S_2|+1)$ pairs, in which element $(x,y)=1$ if and only if after scanning $i$ elements of the reference string $S$, $x$ characters of $S_1$ have been found, and $y$ characters of $S_2$ have been found (without overlaps).

Every pair of the table $T_0 (i=0)$ is zero except for the pair $(0,0)=1$.
Copy $T_i$ to $T_{i+1}$ and read the next character $c=S[i+1]$  from $S$; if in $T_i$ there is an entry $(x,y)=1$ such that $S[x+1]=c$ then in $T_{i+1}$ set $(x+1,y)=1$; if in $T_i$ there is an entry $(x',y')=1$ such that $S[y'+1]=c$ then in $T_{i+1}$ set $(x',y'+1)=1$.

At the end of the scan, $S$ contains the merged distinct copies of $S_1$ and $S_2$ if and only if $(|S_1|,|S_2|)=1$.

Simple example:

S  =  a b a a c
S1 =  a a c
S2 =  b a

S    0,0  0,1  0,2 1,0 1,1 1,2 2,0 2,1 2,2 3,0 3,1 3,2
     1    0    0   0   0   0   0   0   0   0   0   0  < T0
a    1    0    0   1   0   0   0   0   0   0   0   0  < T1
b    1    1    0   1   1   0   0   0   0   0   0   0  < T2
a    1    1    1   1   1   1   1   1   0   0   0   0  < T3
a    1    1    1   1   1   1   1   1   1   0   0   0  < T4
c    1    1    1   1   1   1   1   1   1   1   1  [1] < T5

Case k fixed

The same approach above can be used for any fixed $k >2$ (the table size grows polynomially).

Case k not fixed

If $k$ strings are given as input, and $k$ is NOT FIXED: in that case there is a quick reduction from the 3-PARTITION problem which is strongly NP-complete, so it remains NPC even when the input numbers are represented in unary.

Given a set of $A = \{x_1,x_2,...,x_{3m}\}$ of $3m$ positive integers (that can be specified in unary), and a target sum $B$ we must find $m$ disjoint subsets $A_1,A_2,...,A_m \subseteq A$ of $3$ elements ($|A_i|=3$), and the sum of the elements of each subset must be $B$.

Over alphabet $\{a,b,c\}$, set:

"reference" string $S = a^3 \; b^B\; c^3 \; a^3 \; b^B\; c^3 \; ... a^3 \; b^B\; c^3 \;$ ($a^3 b^B c^3$ repeated $m$ times)
for $i = 1,...,3m$ set string $S_i = a \; b^{x_i} \; c$

Informally: the $a^3$ parts of $S$ force to match $3$ of the $S_i$s (otherwise some $S_i$ will not be included); the $c^3$ parts force to "close" $3$ of the $S_i$s. And the  $b^B$ blocks (there are $m$ of them) must be filled exactly with the $b^{x_i}$ substrings of $3$ distinct $S_i$.

Small example:

3-PARTITION instance: $A = \{ 3,  2, 1, 5, 4, 3\}, B=9, (m=2)$

S  = aaa bbbbbbbbb ccc aaa bbbbbbbbb ccc
S1 = a bbb c
S2 = a bb c
S3 = a b c
S4 = a bbbbb c
S5 = a bbbb c
S6 = a bbb c


Complexity of "destroying" the graph's minimum spanning tree weight

EDIT

As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited in my original answer. However, the asker poses instead the question of whether or not removing $k$ edges could increase the MST weight of $G$ by any amount. Let's call this problem "$k$ Any Vital Edges" or $k$-AVE. We will show that $k$-AVE is in P.

Let $G=(V,E)$ be an edge-weighted graph with weight function $w:E\rightarrow \mathbb{N}$. The goal of $k$-AVE is to find a subset of edges $S \subseteq E$ of size $k$ such that the MST weight of $G$ is strictly less than the MST weight of $G\setminus S \triangleq (V, E\setminus S)$. We'll call such an $S$ a valid $k$-AVE set. We will proceed by outlining necessary and sufficient conditions for $S$ to be a valid $k$-AVE set.

Let $T$ be a MST of $G$. For every edge $e \in T$, we may associate a partition of $V$ into two parts (i.e.: a cut) based on how $e$ splits $T$ (i.e.: each partition consists of the vertices reachable from either endpoint of $e$ using only edges in $T \setminus \{e\}$). In particular, we will denote by $C_e$ the cut-set of this associated partition (i.e.: set of edges in $G$ that straddle this partition, including $e$ itself).

Now, by the Cut Property of MSTs, we know that each $e$ has minimum weight among all edges in $C_e$; there may be more than one edge in $C_e$ with that same minimum weight. Let these sets be denoted $M_e \triangleq \{e' \in C_e | w(e') = w(e)\}$. Suppose that, for some $e$, $M_e\subseteq S$. Then, we conclude that $G\setminus S$ has larger MST weight than $G$. Otherwise, we would have some MST $T'$ in $G$ that did not use any of the minimum weight edges across the cut-set $C_e$, a contradiction of the Cut Property. This shows that a sufficient condition for $S$ to be a valid $k$-AVE set is for it to contain $M_e$ for some $e$.

Next, we will show that this is condition is also necessary. Suppose to the contrary that, for all $e\in T$, $S$ excludes some $e' \in M_e$ (of course allowing that $e'$ may equal $e$). In general, removing $S$ from $G$ splits $T$ into a forest. We will reconstruct a new minimum spanning tree $T'$ from $T\setminus S$ by using the edges spared by $S$, as follows:

  Let $T' = T\setminus S$
  For each $e$ in $T$ do
  $\qquad$If no edge in $T'$ spans $C_e$ then let $T' = T' \cup \{e'\}$
  Return $T'$

We leave as an exercise to the reader to prove that this procedure reconstructs a spanning tree $T'$ with the same weight as $T$. (Outline: each edge added in step 3 preserves acyclicity and no components of $T\setminus S$ can remain separated).

These necessary and sufficient criteria naturally suggest a poly-time algorithm for determining if $G$ has a valid $k$-AVE set. First, construct a MST $T$. For each $e\in T$, we compute the cut-set $C_e$ and the set of minimum weight edges in $C_e$, $M_e$. If for some $e$, $|M_e| \leq k$, then we can simply take any $S \supseteq M_e$ as our valid $k$-AVE set. Otherwise, if all $M_e$ sets are larger than size $k$, we conclude that $G$ has no $k$-AVE set.

Original Answer Below

Shen, Hong. "Finding the k most vital edges with respect to minimum spanning tree." Acta Informatica 36.5 (1999): 405-424.

  For a connected, undirected and weighted graph $G = (V,E)$, the problem of finding the $k$ most vital edges of $G$ with respect to minimum spanning tree is to find $k$ edges in $G$ whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary $k$.


While this is not a direct answer, the following discussion on MO (Mathoverflow) relates to finding convolution operations that admit fast FFT-like operations on other algebraic structures.


Finding a set which dominates the Minimum Dominating Set

The algorithm previously proposed in the post (before the current edit), does not work.

Here are the problem and algorithm proposed in that version of the post:

input: graph $G=(V,E)$ and the minimum size $k$ of any dominating set in $G$

output: a set of $k$ nodes that dominates a dominating set of size $k$

  algorithm$(G,k)$:

  At the start, all nodes are unmarked.

  1) Pick an unmarked node $v$ as a center and mark everything within 2
  hops of $v$.  [This step was edited and differs in the current post.]

  2) Repeat step 1 until all nodes are marked. (Note, this will never
  place more than $k$ centers)

  3) If we have picked less than $k$ centers, keep placing centers on
  undominated nodes until we have placed $k$ centers.

  Lemma. The algorithm above doesn't work.

Proof. Consider the counter-example $G=(V,E)$ where

$V=\{a, b, c, d, e, f\}$
$E=\{(a, b), (a, c), (a, d), (b, e), (c, f), (d, f)\}.$

The (unique) minimum dominating set is $\{b, f\}$, with size $k=2$.

The algorithm can place a center on $v=a$ in Step 1 (marking all nodes), then place a center on $e$ in Step 3.  This returns a set $\{a, e\}$ of two centers, neither of which dominates $f$ (which is in the only dominating set of size $2$). $~~~\Box$


Importance of ACM/IEEE in TCS conference

One thing ACM brings to a conference is name recognition: if I see that a conference is ACM-sponsored, even if it's one that I haven't heard of before, I can be confident that it's reasonably high quality and well organized, rather than being one of those scam conferences that accepts everything and profits off the registration fees. (I'm less sure of that with IEEE after the Schlangemann scandal.) Of course, there are also good conferences that are not sponsored by these societies. And I wouldn't want to rely on this halo effect for making decisions about tenure or anything important like that — better to solicit opinions from people who know that area better — but it can be useful when deciding where to send a paper.


This question is related to the so called insertion systems.

An insertion system is a special type of rewriting system whose rules are of the form $1 \rightarrow r$ for all $r$ in a given language $R$. Let us write $u \rightarrow_R v$ if $u = u'u''$ and $v = u'ru''$ for some $r \in R$. Let us denote by $\buildrel{*}\over\rightarrow_R$ the reflexive transitive closure of the relation $\rightarrow_R$. The closure of a language $L$ of $A^*$ under $\buildrel{*}\over\rightarrow_R$ is the language
$$
[L]_{\buildrel{*}\over\rightarrow_R} = \{ v \in A^* \mid \text{ there exists $u \in L$ such that $u \buildrel{*}\over\rightarrow_R v$} \}
$$
Recall that a well quasi-order on a set $E$ is a reflexive and
transitive relation $\leqslant$ such that for any infinite sequence $x_0,
x_1, \ldots$ of elements of $E$, there are two integers $i < j$ such
that $x_i \leqslant x_j$. The following theorem is proved in [1]:

  If $H$ is a finite set of words such that the language $A^* \setminus
A^*HA^*$ is finite, then the relation $\buildrel{*}\over\rightarrow_R$ is a well quasi-order on $A^*$ and $[L]_{\buildrel{*}\over\rightarrow_R}$ is regular.

[1] W. Bucher, A. Ehrenfeucht and D. Haussler, On total regulators generated by derivation relations, Theor. Comput. Sci. 40, 2-3 (1985), 131– 148.


Question about Mapping Reductions (Clarify Example)

If M does not accept w, then the only case in which M' accepts is if its input is of the form 0^n 1^n.


Rounding to minimise the sum of errors in pairwise distances

OK. The DP algorithm seems to be unnecessarily complicated. After reading comments I think this might solve the Monotonic version of the problem (but I have not checked every detail).

First, assume each $x_i = \lfloor x_i\rfloor +\{x_i\}$, where $\lfloor x_i\rfloor$ is the integral part, $\{x_i\}$ is the fractional part. Assume $x_i$ is rounded to $\lfloor x_i \rfloor + v_i$, where $v_i$ is a nonnegative integer (of course in general $v_i$ can be negative, but we can always shift so that the smallest $v_i$ is 0).

Now, consider the cost for a pair $x_i$, $x_j$ when doing this rounding. The cost should be

$$
||v_i-v_j+ \lfloor x_i\rfloor -  \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||
$$

The expression is complicated because of the absolute values. However, notice that we have monotonicity, so the things inside the two inner absolute values should have the SAME sign. Since we have an outer absolute value, it really doesn't matter what that sign is, the expression just simplifies to

$$
|v_i-v_j - (\{x_i\} - \{x_j\})|
$$

From now on we do not assume the solution is monotonic, but instead, we change the objective to minimize the sum of the above term for all pairs. If the solution to this problem happens to be monotonic, then of course it is also the optimal solution for the monotonic version. (Think of this as: original problem has an infinite penalty when the solution is not monotonic, the new problem has smaller penalty, if a monotonic solution wins even in the new version, it must be the solution to the monotonic version)

Now we would like to prove, if $\{x_i\} > \{x_j\}$, in the optimal solution we must have $v_i \ge v_j$.

Assume this is not true, that we have a pair $\{x_i\} > \{x_j\}$ but $v_i < v_j$. We shall show that if we swap $v_i$ $v_j$ the solution gets strictly better.

First we compare the term between $i$ and $j$, here it is really clear that swapping is strictly  better because in the non-swap version, $v_i-v_j$ and $\{x_j\}-\{x_i\}$ has the same sign, the absolute value will be the sum of the two absolute values.

Now for any $k$, we compare the sum of pairs $(i,k)$ and $(j,k)$. That is, we need to compare

$|v_i-v_k-(\{x_i\}-\{x_k\})|+|v_j-v_k-(\{x_j\}-\{x_k\})|$ and $|v_j-v_k-(\{x_i\}-\{x_k\})|+|v_i-v_k-(\{x_j\}-\{x_k\})|$.

Use $A$, $B$, $C$, $D$ to denote the four terms inside the absolute value, it is clear that $A+B = C+D$. Also it is clear that $|A-B| \ge |C-D|$. By convexity of the absolute value, we know $|A|+|B| \ge |C|+|D|$. Take the sum over all $x_k$'s, we know swapping can only be better.

Notice that now we already have a solution for the Monotonic floor/ceil version: there must be a threshold, when $\{x_i\}$ is bigger always round up, when it is smaller always round down, when it is equal round some up and some down, while the solution quality only depends on the number. We enumerate all these solutions and pick the one with smallest objective function. (All these solutions are necessarily monotonic).

Finally we would like to go to the monotonic integer version of the problem. We can actually prove the optimal solution is the same as Monotonic floor/ceil version.

As we assumed, the smallest $v_i$ is 0. Group all the $x_i$'s according to their $v_i$'s, and call them group $0,1,2,...,\max\{v_i\}$. We shall first prove that there are no empty groups, but this is simple, if the $k$-th group is empty, for any $v_i > k$ just let $v_i = v_i-1$. It is easy to see the objective function always improves (basically because $|\{x_i\}-\{x_j\}| < 1$).

Now we shall prove, the average of $\{x_i\}$ in group $k+1$ is at least the average of $\{x_i\}$ in group $k$ plus $1/2$. If this is not true, simply let $v_i = v_i-1$ for all $v_i > k$, computation again shows the objective function improves.

Since the average of $\{x_i\}$ is in range $[0,1)$, there are really at most two groups, which corresponds to the floor/ceil version.


Decidability of membership in the fixed point of a rational relation

The answer to (1) is no, even for deterministic transducers. The reason is that we can encode configurations (tape contents + head position + machine state) of Turing machines into words such that the configuration changes made by any machine $M$ can be represented by a transducer $T_M$, and then decidability of (1) would imply decidability of the halting problem. In some more detail, this is how it works:

For simplicity, I assume that our Turing machines move left or right in each step, i.e. for any machine state $q\in Q$ and tape symbol $a\in \Sigma$, the action $\delta(q,a)$ performed in $q$ upon reading $a$ is either $(q',a',L)$ or $(q',a',R)$ for some $q',a'$. The alphabet $\Sigma$ contains the blank $\_$, and $\Pi:=\Sigma\setminus\{\_\}$. I also assume that the machine erases the tape before halting, and doesn't write any blanks otherwise - this is a straightforward modification to any given machine, and ensures that all halting configurations are encoded as the same word.

The encoding of a configuration is a word in $(\Sigma\cup Q)^*$ of the form $\_uqav\_$, delimited by blanks, where $q\in Q$ is the current state, $a\in\Sigma$ is the content of the cell under the head, and $u,v\in\Pi^*$ are the contents to the left and to the right, respectively. Due to the above restriction, a halting configuration is encoded as $\_q_e\_\_$, where $q_e$ is the halting state.

The transducer $T_M$ operates in several phases, using its state to temporarily store a symbol $b\in\Sigma$:

It reads the leading $\_$ and sets $b:=\_$;
It reads $v = v_1\dots v_k$, in each step outputting $b$ and setting $b$ to the current $v_j$ (if $v$ is empty, then $b$ is still $\_$ after this);
It reads $q$ and $a$. Then if $\delta(q,a) = (q',a',L)$, it outputs $q'ba'$, otherwise ($\delta(q,a) = (q',a',R)$), it outputs $ba'q'$. It also remembers the move direction.
It reads and outputs $w\_$, unless we moved left, $w$ is empty, and $a'=\_$ (to avoid extra trailing $\_$).

Then $T_M^k(\_q_0w\_)$ encodes the configuration of $M$ after $k$ steps on input $w$, and $\_q_e\_\_\in\mu Z.\{\_q_0w\_\}\cup T_M(Z)$ iff $M$ halts on $w$.


Trakhtman has a bibliography on the problem, which is apparently kept up to date; so I suppose Černý's question remains unresolved until today. The same is stated in Volkov's recent survey (LATA 2008) linked from the wikipedia article cited in the question. There you find pointers to some partial results, for example, for which subclasses of regular languages the conjecture is known to be true. Even more recent is a research paper by Ananichev, Gusev & Volkov (MFCS 2010) on a related topic, where they confirm that Černý's conjecture is still open now (at least as of May 2010).


Graph families which have polynomial time algorithms for computing the chromatic number

As you observe, all perfect graphs can be colored in polynomial time, but I think the proof involves ellipsoid algorithms for linear programming (see the book by Grötschel, Lovász, and Schrijver) rather than anything direct and combinatorial. There are a lot of different classes of graphs that are subclasses of perfect graphs and have easier coloring algorithms; chordal graphs, for instance, can be colored greedily using a perfect elimination ordering.

All locally connected graphs (graphs in which every vertex has a connected neighborhood) can be 3-colored in polynomial time, when a coloring exists: just extend the coloring triangle by triangle.

Graphs of maximum degree three can be colored in polynomial time: it's easy to test whether they're bipartite, and if not then either they require only three colors or they have K4 as a connected component and require four colors (Brooks' theorem).

Triangle-free planar graphs can be colored in polynomial time, for the same reason: they are at most 3-chromatic (Grötzsch's theorem).


Are there non trivial 2-basis of a 2-connected planar graph?

The cycles of a 2-basis (and the one leftover cycle formed from the symmetric difference of all these cycles) necessarily form the faces of a planar embedding of the graph. First, all edges of the graph belong to some cycle by 2-connectivity. Second, the edges appearing only once in the basis cycles must form a single cycle, else their subgraph would have multiple cycles not all of which could be represented by the basis. So adding the leftover cycle produces a set of cycles that cover every edge exactly twice. Third, one can form an embedding of the graph onto a topological surface by making a polygon for each cycle and gluing these polygons together. One can use 2-connectivity again to show that the surface is actually a manifold: if multiple patches of surface touched each other locally at a single vertex, one could find a cycle passing from one patch to another through that vertex which could not be represented by the basis, because any basis representation would produce evenly many edges into that vertex within each patch of surface. And fourth, every cycle in the graph must be a boundary of a subset of the surface (it is the boundary the union of the basis cycle polygons whose symmetric difference is the given surface cycle). But this can be true only of a topological sphere, so the embedding is planar.
However, a planar graph that is 2-connected but not 3-connected can have multiple embeddings and when it does, the cycles of any given 2-basis may not be faces of a different embedding. As an example, $K_{2,4}$ has three combinatorially-distinct embeddings, for the three ways of choosing which pairs of degree-two vertices are non-co-facial, and for any particular embedding it is possible to find a cycle basis using one or both of the two non-facial cycles. (The degree-two vertices of this example can be replaced by two triangles connected edge-to-edge to make an example where all degrees are greater than two.)


How do you actually construct the sets of types and terms (more) formally
  in set theory, and convince me that these actually do form a set?

It's essentially the same argument that BNF grammars define sets.

Start with the set of untyped terms (conventionally dubbed the preterms), and the set of untyped contexts (sequences $x_1:A_1, \ldots, x_n:A_n$ where the $x_i$ are variables and $A_i$ are preterms).
Think of each judgement form as a predicate. Think of $\Gamma \vdash e : A$ as a three-argument predicate on precontexts, preterms, and preterms, $\Gamma \vdash A \mbox{ type}$ as a two-argument predicate on preterms, $\Gamma \vdash e \equiv e' : A$ as a four-place predicate and so on.
Interpret each rule of MLTT as a predicate transformer.
So a rule like
$$
  \frac{\displaystyle \Gamma \vdash e : \Sigma x:A.B}
       {\displaystyle \Gamma \vdash \pi_1 e : A}
  $$
is defining a new predicate $\vdash'(\_, \_, \_)$ from the old predicate $\vdash(\_, \_, \_)$ such that $\vdash'(\Gamma, \pi_1 e, A)$ holds when  $\vdash(\Gamma, e, \Sigma x:A.B)$ holds.
Observe that every rule is a Horn clause without negation.
As a result, the predicate transformer induced by the interpretation of a rule is monotone on the inclusion order on the lattice of sets of terms (or tuples of contexts and terms; or tuples of contexts, terms and terms; and so on).
Furthermore, the pointwise union of monotone predicate transformers is also monotone. So we can interpret all of the rules as jointly defining a monotone predicate transformer.
By the Knaster-Tarski theorem, there is a least fixed point to the this lattice.
That fixed point gives you the set of well-typed terms, contexts, etc.


Expected length of longest construction path in Barabási–Albert Model

(Answer-in-progress, according to comments.)

I will look at a special case, and then discuss how it relates to the general case. The special case is $m=1$ and $V(G)=\{0\}$ with no edge. The added vertices, in order, are $1,2,\ldots,n$, starting from $1$.

Let $d_{i,n}$ be the degree of vertex $i$ divided by $2n$. So $\sum_{i=0}^n d_{i,n}=1$. Let $l_i$ be the length of the longest path from $i$ to $0$ that visits vertices in decreasing order. (Vertices added after $i$ do not affect decreasing paths starting from $i$, so there is no need for $l_{i,n}$.) Both $d_{i,n-1}$ and $l_i$ are random variables. The generating model for these variables is how you'd expect: Once we fixed their values for $n-1$, we pick a number $k_n$ from $\{0,\ldots,n-1\}$ according to the probabilities $d_{i,n-1}$, and compute $d_{i,n}$ and $l_n$ as if we added edge $nk_n$.

We have that $l_n=1+l_{k_n}$, where $k_n$ is a random variable drawn from $\{0,\ldots,n-1\}$ according to the distribution given by $d_{k,n-1}$. In other words, $l_n=1+\sum_{i\lt n}[k_n=i]l_i$ and $\mathbb{E}[l_n]=1+\sum_{i\lt n}d_{i,n}\mathbb{E}[l_i]$. (The independence here is a bit tricky. In the comment on the post I said it does not hold, but I think it does. The trick is to think of this as a stratified generative model, such that the choice of $k_n$ is independent from $l_i$, but drawn from a certain distribution.)

Let's assume, without proof for now, that $d_{i,n}$ depends on $i$ as $\Theta(i^c)$ for some constant $c$.

Now, let's assume $\mathbb{E}[l_n]=O(f(n))$, and see what properties should $f(n)$ have. According to the recurrence on $\mathbb{E}[l_n]$, we should have that
$$
\sum_{i=0}^{n-1} i^c f(i) \Big/ \sum_{i=0}^{n-1} i^c = O(f(n))
$$
In the continuous approximation, this is
$$
\int_1^n x^c f(x) \,dx = O(n^{c+1}\cdot f(n))
$$
One function that has this property is $f(n)=\log n$.

But, does $d_{i,n}$ grow like $i^c$ (for fixed $n$)?

When $m=1$, we can write a recurrence on vertex degrees. The arc $ni$ occurs with probability $d_{i,n-1}$, so $$d_{i,n}=d_{i,n-1}\frac{2(n-1)d_{i,n-1}+1}{2n}+(1-d_{i,n-1})\frac{2(n-1)d_{i,n-1}}{2n}=d_{i,n-1}\Bigl(1-\frac{1}{2n}\Bigr)$$ The border conditions are $d_{n,n}=1/2n$ and $d_{0,1}=d_{1,1}=1$. Now apply linearity of expectation and approximate $\sum_k\log\Bigl(1-\frac{1}{2k}\Bigr)$ with an integral. Alternatively, note that $d_{i,n}/d_{i-1,n}=d_{i,i}/d_{i-1,i}=(i-1)/(i-1/2)$, so $d_{i,n}$ is roughly $\Gamma(n)/\Gamma(n+1/2)$.

Both approaches lead to $\mathbb{E}[d_{i,n}]=\Theta(i^{-(1/2)})$.

For $m=2$, you draw two variables $k_n$ and $k'_n$ from $\{0,\ldots,n-1\}$ according to $d_{i,n}$, and we keep just the maximum. This is like picking just one variable, $\max\{k_n,k'_n\}$, but from a different distribution. The question is if this distribution is still $\Theta(i^c)$ for some (other) $c$. Let $d^{(2)}_{i,n}$ be this distribution. We have, dropping the $n$ subscript, $d^{(2)}_i=2\sum_{j=0}^i d_i d_j + d_i^2$. So, $d^{(2)}_i=\Theta(1/i)$. In fact, $d^{(2m)}_i=2\sum_{j=0}^i d^{(m)}_i d^{(m)}_j + {d^{(m)}_i}^2$. Again based only on some quick-and-dirty calculations, I believe that for $m\gt 2$ we have $d^{(m)}_i=\Theta((\log i)^{cm}/i)$, which would seem to say that the $O(\log n)$ bound on $\mathbb{E}[l_n]$ doesn't work anymore.

The only thing that matters about the seed graph is how many edges it has. I didn't look at how this affects the answer, but, again, it cannot increase the expected length.


Paradigms for complexity analysis of algorithms

There are natural variants of worst-case analysis that are also useful. Perhaps the most famous one is parametrized complexity. Here, we consider a "two-dimensional" measure: the usual input length $n$ and some additional non-negative integer $k$, the parameter. Even though an algorithm may run horribly in the worst case (for all values of $n$ and $k$), it could be that all the cases in one's application that needs to be solved, this parameter $k$ happens to be low, so the algorithm runs well on those instances.

For example, suppose you want to solve Maximum Independent Set on some class of graphs, and develop an interesting algorithm that is surprisingly fast. Investigating further into the class of graphs themselves, you find that all the graphs you examine just happen to have treewidth at most $10$. Well, Bodlaender (cf. Neidermeier [1]) showed that when the treewidth is k, Max Independent Set is fixed parameter tractable: it can be solved in $O(2^k (|E|+|V|))$ time. This gives some explanation as to why your algorithm works well.

[1] R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.


Yes, a general solution to this problem has recently been given by
Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman,
see Pseudorandom Generators for Combinatorial Shapes.

That paper handles an even more general setting, where the generator outputs $n$ $\log m$-bit blocks, which are then fed to arbitrary boolean functions, whose $n$ outputs are then fed to a boolean symmetric function.

A variety of sub-cases were already known; see for example Pseudorandom Bit Generators That Fool Modular Sums, Bounded Independence Fools Halfspaces, and Pseudorandom Generators for Polynomial Threshold Functions. The first handles sums modulo $p$. The second and the third handle precisely the threshold tests you mention, however the error is not good enough to apply your reasoning to obtain a result for every symmetric function.


How to do organize papers, urls and other TCS related resources?

I am old school and just use files and folders to organize everything. I have it in Dropbox and I share it with my professors or other students. I think using files and folders although it isn't very fancy but it works well. I have tried special organizers but never used them.


Do people look at loop nestness in boolean circuits?

You should have a look at PhD thesis (later published as a monograph) of Tomás Feder: Stable Networks and Product Graphs, where he studied the complexity of finding stable configurations of networks, which are exactly circuits with "loops" like  you mentioned.


If I am not mistaken, a simpler CS grammar is possible.  Here it is:

$S \rightarrow ABSc$
$S \rightarrow Abc$
$BA \rightarrow XA$
$XA \rightarrow XY$
$XY \rightarrow AY$
$AY \rightarrow AB$
$A \rightarrow a$
$Bb \rightarrow bb$.

A derivation for the string $aaabbbccc$ is

$\Rightarrow_1 ABSc\\\Rightarrow_1 AB\textbf{ABSc}c\\\Rightarrow_2 ABAB\textbf{Abc}cc\\\Rightarrow_3 A\textbf{XA}BAbccc\\\Rightarrow_4 A\textbf{XY}BAbccc\\\Rightarrow_5 A\textbf{AY}BAbccc\\\Rightarrow_6 A\textbf{AB}BAbccc\\\dots\\\Rightarrow_{3-6}AAB\textbf{AB}bccc\\\Rightarrow_{3-6}AA\textbf{AB}Bbccc\\\Rightarrow_{7...}\textbf{aaa}BBbccc\\\Rightarrow_8 aaaB\textbf{bb}ccc\\\Rightarrow_8 aaa\textbf{bb}bccc$


Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules)

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

A summary of the proof given in the link. First, it is shown that proving $L \cap R$ is CFL reduces to proving that $L \cap R'$ is CFL, where $R'$ is a regular language recognized by a DFA with exactly one final state. Then from the grammar for L (in Chomsky normal form) and DFA for R' a new grammar for $L \cap R'$ is constructed using a few straightforward rules.


Is there any connection between the diamond norm and the distance of the associated states?

For a quantum channel $\Phi$, let us write $J(\Phi)$ to denote the associated state:
$$
J(\Phi) = \frac{1}{n} \sum_{1\leq i,j \leq n} \Phi(|i \rangle \langle j|) \otimes |i \rangle \langle j|.
$$
Here we are assuming that the channel maps $M_n(\mathbb{C})$ (i.e., $n\times n$ complex matrices) to $M_m(\mathbb{C})$ for whatever choice of positive integers $n$ and $m$ you like.  The matrix $J(\Phi)$ is sometimes called the Choi matrix or Choi-Jamiolkowski representation of $\Phi$, but it is more frequent that those terms are used when the $\frac{1}{n}$ normalization is omitted.

Now, suppose that $\Phi_0$ and $\Phi_1$ are quantum channels.  We may define the "diamond norm distance" between them as
$$
\| \Phi_0 - \Phi_1 \|_{\Diamond} =
\sup_{\rho} \: \| (\Phi_0 \otimes \operatorname{Id}_k)(\rho) - (\Phi_1 \otimes \operatorname{Id}_k)(\rho) \|_1
$$
where $\operatorname{Id}_k$ denotes the identity channel from $M_k(\mathbb{C})$ to itself, $\| \cdot \|_1$ denotes the trace norm, and the supremum is taken over all $k \geq 1$ and all density matrices $\rho$ chosen from $M_{nk}(\mathbb{C}) = M_n(\mathbb{C}) \otimes M_{k}(\mathbb{C})$.  The supremum always happens to be achieved for some choice of $k\leq n$ and some rank 1 density matrix $\rho$.

(Note that the above definition does not work for arbitrary mappings, only those of the form $\Phi = \Phi_0 - \Phi_1$ for completely positive maps $\Phi_0$ and $\Phi_1$.  For general mappings, the supremum is taken over all matrices with trace norm 1, as opposed to just density matrices.)

If you don't have any additional assumptions on the channels, you cannot say too much about how these norms relate aside from these coarse bounds:
$$
\frac{1}{n} \| \Phi_0 - \Phi_1 \|_{\Diamond} \leq
\| J(\Phi_0) - J(\Phi_1) \|_1 \leq \| \Phi_0 - \Phi_1 \|_{\Diamond}.
$$
For the second inequality, one is essentially settling for the specific choice
$$
\rho =
\frac{1}{n} \sum_{1\leq i,j \leq n} |i \rangle \langle j| \otimes |i \rangle \langle j|
$$
rather than taking the supremum over all $\rho$.  The first inequality is a bid tougher, but it would be a reasonable assignment question for a graduate course on quantum information.  (At this point I should thank you for your question, because I fully intend to use this question in the Fall offering of my quantum information theory course.)

You can achieve either inequality for an appropriate choice of channels $\Phi_0$ and $\Phi_1$, even under the additional assumption that the channels are perfectly distinguishable (meaning $\| \Phi_0 - \Phi_1 \|_{\Diamond} = 2$).


Practical/heuristic algorithm for multi set-cover

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M.

See also

The documentation of algorithm D, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;
the latest preprint of fascicle 5c of The Art of Computer Programming, which at some point will get as far as explaining the algorithm, but already has a number of exercises that will give you an idea of the problems that Knuth has solved with it.


Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?

Ogden's lemma should work:

For a given $p$ choose $a^i b^p c^k$ and mark all the $b$'s (and nothing else).

$i$ and $k$ are chosen such that for every choice of how many $b$'s are actually pumped there is one pumping exponent such that the number of $b$'s is equal to $i$ and one where it is equal to $k$.

That is $i$ and $k$ have to be from the set $\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$.

I am quite sure but too lazy to formally prove that this set is infinite.


From the comment above: there are two interpretations to your question:

1) The Cook-Levin theorem does not relativize in this sense: there exists a language $L$ and an oracle $A$ such that $L \in NP^A$ but $L$ is not polynomial-time many-one reducible to $3SAT$ even if the polynomial time Turing machine that performs the reduction is allowed to access the same oracle $A$ (i.e. $L \nleq_m^A 3SAT$). The proof is a standard exercise (see for example Arora and Barak, Computational Complexity); hint: play a little bit with the oracle that separates P from NP, the only difference here is that you must "fool" polynomial-time oracle Turing machines that output 3SAT formulas instead of deciders that output yes/no (let me know if you need the full proof);

2) The Cook-Levin theorem does relativize in this sense: you  can extend the circuit model with oracle gates, i.e. $k$-inputs gates in which the inputs are ordered and the output bit is the result of the associated oracle on the query formed by the ordered input bits (there is also a variant in which every bit of the query is represented by two input bits, in order to allow queries shorter than $k$). With this extended oracle circuit model you can build in polynomial time a polynomial-size oracle circuit $C^A$ that "simulates" - in a similar way of the Cook-Levin theorem - the computation of an oracle polynomial time machine $M^A$ and on input $x$ evaluates to 1 if and only if $M^A(x)=1$. So, if

$\text{Circuit-}SAT^A = \{ C \mid C $ is a boolean circuit equipped with oracle gates for $A$ and for which there exists $x$ such that $C(x)=1 \}$ you say that:

for every oracle $A$, $\text{Circuit-}SAT^A$ is $NP^A$-complete.

3) Finally with a TQBF oracle we have $P^{TQBF} = NP^{TQBF}$, so if we add a TQBF oracle to the polynomial time Turing machine that performs the reduction (interpretation 1) we give to it the power to solve the original problem directly, so we have: $NP^{TQBF} \leq_m^{TQBF} \{1\}$ i.e. every trivial set is $NP^{TQBF}$-complete under polynomial time many-one TQBF-oracle reductions (except $\emptyset$ and $\Sigma^*$ :-), so Cook-Levin theorem does relativize for the TQBF oracle (solve the source instance and output $(x_1 \lor x_2 \lor x_3)$ if it belongs to the language, output an unsatisfiable 3SAT formula otherwise).

Addendum: related to your question, it is interesting how the (old but great) Computational Complexity by C. Papadimitriou explicitly faces the problem of the relativization of another well known thereom, the Ladner's theorem, in this way (probably the oracle gates were introduced later):

[From Chapter 14]: ... "If $P^A \neq NP^A$, then there is a language in $NP^A - P^A$
which is not $NP^A$-complete". But when we say "$NP^A$-complete", do
we also allow the use of oracle in our reductions?
With a little reflection we may decide that the
right way to state the result is in terms of ordinary reductions...
..... There seems to be no reasonable definition of $SAT^A$.
To get around this difficulty, we must replace the usage of SAT
with an $NP^A$-complete problem. Such problem exist; for example:

$C^A = \{ (M^A,x) \mid $ nondeterministic  oracle machine $M^A$ accepts $x$ in time $|x|\}$


complexity of greatest common divisor (gcd)

This is a major open question in complexity theory: it is not known if GCDs can be computed in NC, and it is not known if computing GCDs is P-complete.  The best parallel algorithms do have sub-linear parallel running time, one such algorithm being due to Sorenson:

  J. Sorenson.  Two fast GCD algorithms.  Journal of Algorithms, 1994.

If I am not mistaken, it is not even known if one can decide whether two integers are relatively prime in NC.


Optimizing multiplication in a partly commutative semigroup

Okay, I've given it a bit of thought and I see that the algorithm is very easy.

Example: Let % denote "commutes". Let A % B, A % C, B % C, B % X.

Compute ABAAXCBA:

Let us keep a "result", an "active multiset" and a "remaining suffix". Let us append a special "$" symbol that commutes with noone onto the string.

Invariant: the product of "result", active multiset and the remaining suffix equals the product of original string.

Invariant: all items in the active multiset commute.

At each new element of the suffix, drop elements from the active multiset that don't commute with it into the product, and insert the element into the multiset.

(1, {}, ABAAXCBA$) ->
(1, {A:1}, BAAXCBA$) ->
(1, {A:1, B:1}, AAXCBA$) ->
(1, {A:2, B:1}, AXCBA$) ->
(1, {A:3, B:1}, XCBA$) -> (drop A^3)
(A^3, {B:1, X:1}, CBA$) ->
(A^3 X, {B:1, C:1}, BA$) ->
(A^3 X, {B:2, C:1}, A$) ->
(A^3 X, {B:2, C:1, A:1}, $) ->
(A^3 X B^2 C A, {$}, )

This version has at most O(|A|) (size of alphabet) overhead per input symbol and it does an optimal number of multiplications.


Calculus of Constructions: compress expression to its smallest form

There's a bit of freedom in what we considre "the same value". Let me show that there is no such algorithm if "the same value" means "observationally equivalent". I will use a fragment of the Calculus of constructions, namely Gödel's System T (simply typed $\lambda$-calculus, natural numbers, and primitive recursion on them), so the argument applies to a much weaker calculus already.

Given a number $n$, let $\overline{n}$ be the corresponding numeral representing it, i.e., $n$ applications of $\mathtt{succ}$ to $0$.
Given a Turing mahcine $M$, let $\lceil M \rceil$ be the numeral encoding $M$ in some reasonable way.

Say that two closed terms $t, u : \mathtt{nat} \to \mathtt{nat}$ are equivalent, written $t \simeq u$, when for all $n \in \mathbb{N}$, $t \, \overline{n}$ and $s \, \overline{n}$ both normalize to the same numeral (they normalize to a numeral because we're in a strongly normalizing claculus).

Suppose we had an algorithm, which given any closed term of type $\mathtt{nat} \to \mathtt{nat}$ calculates a minimal equivalent term.
Then we can solve the Halting oracle as follows.

There is a term $S : \mathtt{nat} \times \mathtt{nat} \to \mathtt{nat}$ such that, for all $n \in \mathbb{N}$ and all Turing machines $M$,
$S (\lceil M \rceil, \overline{n})$ normalizes to $\overline{1}$ if $T$ halts within $n$ steps, and it normalizes to $\overline{0}$ otherwise. This is well known, since simulation of a Turing machine for a fixed number of steps $n$ is primitive recursive.

There are finitely many closed terms $Z_1, \ldots, Z_k$ which are minimal terms equivalent to $\lambda x : \mathtt{nat} .\, 0$. Our minimization algorithm returns one of them when we give it $\lambda x : \mathtt{nat} .\, 0$, and it may even be the case that $\lambda x : \mathtt{nat} .\, 0$ is in fact the only such minimal term. All this does not matter, the only thing that matters is that there are finitely many minimal terms that are equivalent to $\lambda x : \mathtt{nat} .\, 0$.

Now, given any machine $M$, consider the term
$$u \mathbin{{:}{=}} \lambda x : \mathtt{nat} .\, S (\lceil M \rceil, x)$$
If $M$ runs forever then $u \overline{n}$ normalizes to $\overline{0}$ for every $n$ and is equivalent to $\lambda x : \mathtt{nat} .\, 0$. To decide whether $M$ runs forever, we feed $u$ into our minimzation algorithm and check whether the algorithm returned one of $Z_1, \ldots, Z_k$. If it did, then $M$ runs forever. If it did not, then it halts. (Note: the algorithm need not calculate the $Z_1, \ldots, Z_k$ by itself, these can be hard-coded into the algorithm.)

It would be nice to know an argument that works with a weaker notion of equivalence, for instance just $\beta$-reducibility.


The logic is EXP-complete. One way to prove the lower bound is to note that the logic KTB augmented with universal modality, or even just the global consequence relation of KTB, is EXP-complete (Chen and Lin [1]; note that they denote KTB as B).

Note that a connected IK5-frame $(W,R,R^{-1})$ is either a single irreflexive point, or it consists of a reflexive cluster $C$ together with a (possibly empty) set $I$ of irreflexive points, each of which sees (in $R$) a nonempty subset of $C$. Thus,
$$R_s:=\{(x,y)\in C^2:\exists z\in I\,(R(z,x)\land R(z,y))\}$$
is a symmetric relation on $C$; if every element of $C$ is seen by an element of $I$, $R_s$ is also reflexive. Conversely, it is easy to see that every reflexive symmetric frame can be obtained in this way. It follows that

$${}\vdash_{\mathrm{KTB}^U}\phi\iff{}\vdash_{\mathrm{IK5}}\Diamond^-\top\land\Box^+\Diamond^-\Box^-\bot\to\phi^*,$$

where the translation $\phi^*$ commutes with propositional connectives, and is defined for modal operators by

\begin{align*}
(\Box\phi)^*&=\Box^-(\Box^-\bot\to\Box^+\phi^*),\\
(A\phi)^*&=\Box^+\phi^*.
\end{align*}

Here, $A$ denotes the universal modality of $\mathrm{KTB}^U$, and $\Box^+$ and $\Box^-$ respectively denote the forward and backward modalities of IK5.

Reference:

[1] Cheng-Chia Chen and I-Peng Lin, The complexity of propositional modal theories and the complexity of consistency of propositional modal theories, in: Proc. LFCS 1994 (Anil Nerode and Yu. V. Matiyasevich, eds.), LNCS 813, Springer, pp. 69–80, doi 10.1007/3-540-58140-5_8.


Does P/poly $\neq$ NP/poly have any interesting implications?

Emil Jeřábek' comment answers the question:

  P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly

Note the corollary

  P/poly $\neq$ NP/poly implies P $\neq$ NP.

Proof of corollary:

P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\ $ (Emil's comment)
NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\ $ (implied by 1.)
P/poly $\neq$ NP/poly implies NP $\not\subseteq$ P/poly $\ $ (equivalent to 2.)
NP $\not\subseteq$ P/poly implies P $\neq$ NP $\ $ (P $\subseteq$ P/poly)
P/poly $\neq$ NP/poly implies P $\neq$ NP $\ $ (implied by 3. and 4.)

Proof of Emil's comment:
It is sufficient to show that NP $\subseteq$ P/poly implies P/poly $=$ NP/poly.

So let's assume NP $\subseteq$ P/poly.
Because SAT $\in$ NP there exists $p_{SAT}\geq k_{SAT}>0$ and a sequence of advice strings $s_n$ with $\left|s_n\right|\leq n^{k_{SAT}}$, a deterministic algorithm that can decide SAT instances of size $n$ in time $\leq n^{p_{SAT}}$, if it has access to $s_n$. WLOG, that algorithm can also decide SAT instances of size $\leq n$, because we can define a modified sequence $s'_n=s'_{n-1}s_n$ with $\left|s'_n\right|\leq n^{k_{SAT}+1}$, where all previous advice strings are included in $s'_n$.
Now let $L\in$ NP/poly be an arbitrary language, for which we need to show $L\in$ P/poly. There exists $p_L\geq k_L>0$ and a sequence of advice strings $l_n$ with $\left|l_n\right|\leq n^{k_L}$ and a nondeterministic algorithm that can decide $L$ instances of size $n$ in time $\leq n^{p_L}$, if it has access to $l_n$.
For each $w$ with $|w|=n$, a SAT instance of size $\leq c\cdot n^{p_L}$ can be computed (in time $O(n^{p_L})$) that is satisfiable exactly if $w\in L$.
So for the sequence of advice strings $t_n=l_ns_{c\cdot n^{p_L}}$ with $|t_n|\leq n^{k_L}+(c\cdot n^{p_L})^{k_{SAT}}$, the combination of the deterministic algorithms from 2. and 4. gives a deterministic algorithm that can decide $L$ instances of size $n$ in time $O((c\cdot n^{p_L})^{p_{SAT}})$, if it has access to $t_n$.
Because $L\in$ NP/poly was an arbitrary language, this shows NP/poly $\subseteq$ P/poly, under the assumption that NP $\subseteq$ P/poly.

All the above proofs relativize, because the existence of NP-complete problems is also true in relativized worlds. This suggests that it is fruitless to search for a proof that P/poly $\neq$ NP/poly. However let's summarize the removed motivation section from the question as "The advice string could be a formal axiomatic system (automatically guaranteed to be consistent, evil grin) whose strength is quickly increasing with input length, and NP is extermely good at exploiting this advice." If one is not very careful that "existence of a sequence of advice stings" only has "formal" meaning relative to a fixed formal system, that setup is likely to allow the construction of apparent paradoxes. But the construction of such paradoxes might be fun nevertheless, and perhaps they might even suggests ways how to construct independence proofs (for sufficiently weak formal systems).


Bounded-cardinality bounded-frequency set cover: hardness of approximation

Using the more common parameter notation $(\Delta,k)$ instead of $(k,f)$, this is equivalent to (and I think more commonly known as) the Vertex Cover problem in $k$-uniform hypergraphs of maximum degree $\Delta$.  To emphasize, for consistency with the literature I'm using $k$ where you use $f$, and $\Delta$ where you use $k$.

For any constant $\varepsilon > 0$, results ignoring $\Delta$ include

$\sup_\Delta\{ a(\Delta,k) \}\leq k$ from general set cover.
$\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ (Dinur et al., 2004), as noted by Lev.
If the unique games conjecture is true, then $\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$, which is tight (Khot & Regev, 2008).

Ignoring $k$,

$\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
$\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)

The only result I know that combines the two parameters is

$a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ for fixed $k$, or $k$ growing slowly with $\Delta$ (Halperin, 2002)

There is a connection between this problem and the (Weak) Independent Set problem, but I'm not exactly sure how they're related in terms of approximability.  I would recommend investigating this, perhaps starting here: [PDF].


Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3?

Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.


The Overfull conjecture in graph theory and $coNP$

For the possible reduction you are mentioning, if you find such a reduction from SAT to this particular edge-coloring problem, and additionnally you assume OC, then it would indeed mean  NP $=$ co-NP. However, it would be very surprising:   it would mean that basically, up to encoding, you found a way to always provide a short certificate that a formula is not satisfiable.
This seems quite unlikely to reach with a simple construction.


Finding a minimal DFA whose language has a desired intersection with another

$M_C$ must accept every word of $S^+ = B$ and reject every word of $S^- = A \setminus B$.

Let $A$ and $B$ be finite and such that both $S^+$ and $S^-$ are non-empty. Then exact computation of $M_C$ is NP-hard. [1]

[1] E.M. Gold. Complexity of Automaton Identification from Given Data. Information and Control, 37, 302-320 (1978)


Does coNP-complete problem have subexponential size certificate?

This is the topic of proof complexity, i.e. the size of certificates for the $\mathbf{co\text{-}NP}\text{-}complete$ problem $TAUT$ ($= coSAT$).

The short answer is: it is open.

On the negative side, we cannot even show that there are not polysize $Frege$ refutations for unsatisfiable formulas (let alone the general question of showing this for an arbitrary proof system, a propositional proof system can be thought as a nondeterministic algorithm for $TAUT$).

The question is also equivalent to $\mathbf{coNP} \subseteq NTime(2^{o(n)})$.


Is a CEK machine an implementation of a CESK machine?

The store in a CESK machine is the "heap", where mutable pointer-based data structures live.

If your language is purely functional, then its operational  semantics don't need a store. Take it out, and you get the CEK machine.
If your language does not have control operators (such as call/cc or exceptions), then you can get away with the K (the continuation).
If you don't want to model environments and closures explicitly -- that is, you don't mind a substitution-based semantics -- then you don't need the E (the environment). Calculi for classical logic (which have control operators but no state) often end up looking like CK machines.
If you have a purely functional language without control effects, then you can use the program itself as the abstract machine state, and the reduction rules will be the small-step operational semantics for that language.


On reducing the hardness of CNF-SAT to k-Clique

I don't know the answer to your specific question (it seems related to the question of whether W1=W[2]).

But the algorithm you give in your question is subsumed by several other results. Using your definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the paper by Wahlstrom (link goes to a google scholar page of papers that cite it). In particular, Wahlstrom shows that if $d$ is the average number of occurrences of a variable in the CNF, and no variable appears at most once, then CNF-SAT can be solved in $O(1.1279^{n(d - 2)})$ time. (There are other references with similarly strong running times.)

Update: Another reference is:

Hirsch, E.A.: New worst-case upper bounds for SAT. J. Autom.
Reason. 24(4), 397–420 (2000)

This gives faster algorithms in terms of $m$ and your $N$ (which is typically called $\ell$). Namely, Hirsch gets $2^{0.30897m}$ and $2^{0.10299\ell}$ time.


Flynn's taxonomy, and "task parallelism and data parallelism"

Task/Data parallelism is a simple classification that lies at the algorithm-level of a computation.

Flynn's taxonomy describes low-level machine architectures or models.

Trying to draw lines between both completely ignores the vast sea of complexity that lies between those two levels.  Using an example; You can do task, data and pipeline parallelism perfectly on a SISD for example. Stating that you cannot ignores the vast complexity of today's operating systems.


Total flow using minimum number of edges on a bipartite network

Your problem is NP-hard.
Consider a partition problem instance with input $a_1,\ldots,a_n$.
We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n a_i$, and $n$ sink vertices, where the $i$th vertex has capacity $a_i$. Each edge has infinite capacity.

It's easy to verify there is a partition with equal sum if and only if the solution to your problem on $G$ has $n$ edges.


Edit: the original problem is $n^{1-\epsilon}$-hard to approximate when $k=1$ where $n$ denotes the number of sets.

The dual of a hypergraph is obtained by exchanging vertices with edges, and preserving incidences. It is easier to understand the problem when we note that a hypergraph has VC-dimension 1 iff its dual is cross-free (for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty).

By duality the original problem (for $k=1$) is equivalent to, given a hypergraph $(V, \mathcal{S})$, find a max-size $U \subseteq V$ with $(U, \{S \cap U \mid S \in \mathcal{S}\})$ cross-free.

In fact, this (dual) problem is very hard even when all sets in $\mathcal{S}$ have size 2: then it is a graph and we are looking for a max-size vertex size whose induced subgraph which does not contain any two-edge path (it's not hard to see this is the only way a crossing pair can arise, assuming the graph has at least 4 vertices). But this property is hereditary and nontrivial and thus we can use a result of Feige and Kogan to show hardness.

Original reply

The dual problem for $k=1$ (find a maximum-size $S$ such that the dual VC-dimension of $S$ is at most 1) is hard to approximate within $n^{1-\epsilon}$ (in a family with $\Theta(n)$ sets).

The reason for this is that the dual VC-dimension of a family $A$ is 1 iff the following holds: for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty. (I.e. VC-dim=1 is the dual of what is often called crossing-freeness.)

We reduce from independent set to computing the maximum-size cross-free subfamily. Given a graph $G=(V, E)$ construct a hypergraph $H=(X, S)$ where $X = V \uplus E \uplus \{0\}$ for some dummy element $0$. For each vertex $v$ of $G$, we add the following set $T_v$ to $S$: $$\{v\} \cup \{e \mid e \textrm{ is an edge incident to }v\}.$$

It's not hard to show a family $\{T_v\}_{v \in U}$ is crossing-free iff $U$ is independent in $G$.

But for the original (primal) problem, it seems some more thought is required... looks interesting!


Intuition behind nested positivity and counterexamples

Here is an example exploiting positivity of an index to prove false:
module Whatever where

open import Level using (Level)
open import Relation.Binary.PropositionalEquality
open import Data.Empty

variable
  ℓ : Level
  A B : Set ℓ

data _≅_ (A : Set ℓ) : Set ℓ → Set ℓ where
  trefl : A ≅ A

Subst : (P : Set ℓ → Set ℓ) → A ≅ B → P A → P B
Subst P trefl PA = PA

data U : Set where
  d : U

El : U → Set
data D : Set

El d = D

{-# NO_POSITIVITY_CHECK #-}
data D where
  neg : ∀(c : U) → El c ≅ D → (El c → ⊥) → D

¬D : D → ⊥
¬D v@(neg c eq f) = Subst (λ D → D → ⊥) eq f v

spin : ⊥
spin = ¬D (neg d trefl ¬D)

Technically it also makes use of the fact that induction-recursion can create small universes, and that type equality can be smaller than general equality applied to the universe, but those are otherwise not really problematic to my knowledge (Coq has impredicative equality anyway, I believe). It's possible the simultaneous definition could be eliminated, too, but it's not straight forward, at least.

Edit: I asked around about your first bullet point. It was pointed out to me that there is essentially nothing special about a nested type that is nested in itself. This article shows how to use a non-native translation of nested types into indexed types of equivalent size. When you do that, as long as nesting is strictly positive, it's not difficult to apply the translation to a strictly positive indexed type.
Or for instance, the example translation I was shown uses a nested $ℕ$ parameter instead of self-nesting:
data D' (A : Set) (n : ℕ) : Set where
  c : D' A (suc n) → D' A n
  t : (case n of λ where
         zero → A
         (suc m) → D' A m
      ) → D' A n

Where I added the t constructor to make something actually use A, and D A is meant to be equivalent to D' A 0. I think another way to write this would be:
data D' (A : Set) : ℕ → Set where
  c : D' A (suc n) → D' A n
  t : D' A n → D' A (suc n)
  t' : A → D' A zero

Essentially, the $ℕ$ is a tree tracking how much nesting we need to unfold.


Universities for Quantum Computing / Information?

There are two quantum wikis which provide reasonably good list of research groups in QIP: Quantiki and Qwiki. Quantiki has better European coverage, while Qwiki has better US coverage.

The geographic area I know best is the UK. In the UK there are large theory groups in Oxford, Cambridge, Bristol, University College London and Imperial College, among other places.

In Oxford, where I have spent the last 5 years, QIP research is spread across a number of departments: Physics, Computer Science, Materials Science and Maths. There isn't much of a presence in Maths, although it is Artur Ekert's official affiliation. Computer Science has a growing group that mostly looks at category theory and quantum foundations.  Physics has quite a number of different groups ranging from experiments to theory. Materials science is weirdly the department where I have been based (although I know little about materials) and there is both a theory group there and a fair number of experimentalists. Computer Science, Materials and Physics all have taught quantum computing courses which can be taken towards the course requirement of a DPhil.

Hope this is useful.


When to use the Johnson-Lindenstrauss lemma over SVD?

The two approaches provide very different guarantees.

The JL Lemma says essentially "you give me the error you want, and I'll give you a low dimensional space that captures the distances upto that error". It's also a worst-case pairwise guarantee: for each pair of points, etc etc

The SVD essentially promises "you tell me what dimension you want to live in, and I'll give you the best possible embedding", where "best" is defined as on average: the total error of true similarity versus projected similarity is minimum.

So from a theoretical perspective they solve very different problems. In practice, which one you want depends on your model for the problem, what parameters are more important (error or dimension), and what kind of guarantees you need.


Total orders which are the transitive closure of a set in P

Note that the conditions imply that $T$ is recursive. The construction below shows that apart from that, its complexity can be arbitrarily large.

Let $L\subseteq\mathbb N$ be an arbitrary recursive language, and $f\colon\mathbb N\to\mathbb N$ a function such that $x\in L$ is decidable in time $|f(x)|$, and the subgraph $\{(x,y):y<f(x)\}$ is polynomial-time decidable. (Here $x,y$ are assumed to be written in binary as usual.) Let $(x,y,i)$ be an efficient bijective enumeration of triples where $x,y\in\mathbb N$, and $i=0,1$. Let $S$ consist of the following pairs of these triples:

$((x,y,i),(x',y',i'))$ for $x<x'$.
$((x,y,i),(x,y',i))$ for $y<y'<f(x)$.
$((x,f(x),0),(x,0,1))$ and $((x,f(x),1),(x,f(x)+1,0))$ if $x\in L$.
$((x,f(x),1),(x,0,0))$ and $((x,f(x),0),(x,f(x)+1,0))$ if $x\notin L$.
$((x,y,i),(x,y',i'))$ if $f(x)<y$ and $2y+i<2y'+i'$.

The properties of $f$ ensure that $S$ is polynomial-time decidable, and it is easy to see that its transitive reflexive closure is a total order $T$. However, $T$ is as hard to compute as $L$, since $((x,0,0),(x,0,1))\in T$ iff $x\in L$. (Conversely, $T$ is easily seen to be reducible to $L$.)


No need to approximate, we can determine the exact value: see Kőnig's theorem. In particular, this section shows how to use any maximum bipartite matching algorithm to find a minimum vertex cover.


The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

Like Turing reductions, many-one reductions came into complexity theory from computability/recursion theory literature. Cook and Karp reductions are natural complexity theoretic versions of similar existing reductions in computability.

There is a intuitive way of explaining many-one reductions: it is a restriction of Turing reductions where we can ask only a single question from the oracle and the oracle's answer will be our answer.

Now the question is why would we need to study this (and any other kind of reductions like truth-table, weak-truth-table, etc.)?

These reductions give a finer picture than Turing reductions. Turing reductions are too powerful to distinguish between many concepts. A very large portion of computability theory is devoted to the study of c.e./r.e. degrees. The notion of an c.e. set is central. We can have TM machine that can enumerate an infinite set, we may not be able to enumerate its complement. If you want to study c.e. sets then Turing reduction is too strong since c.e. sets are not closed under it. So many-one reductions are a (and maybe the) natural way of defining reductions for this purpose.

Other types of reductions are defined for similar reasons. If you are interested I would suggest checking Piergiorgio Odifreddi's "Classical Recursion Theory". It has a quite comprehensive chapter on different reductions and their relations.

Now for complexity theory the argument is similar. If you accept that $\mathsf{NP}$ is a extremely natural class of problems and you want to study $\mathsf{NP}$, then Cook reductions are too strong. The natural choice is a weaker reduction such that $\mathsf{NP}$ is closed under it and we can prove existence of a complete problem w.r.t. to those reduction for $\mathsf{NP}$. Karp reductions are the natural choice for this purpose.


Efficient algorithms for searching a collection of trees

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.


Correspondence between Computability & Learnability Theory

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...


Question on subtyping of handlers in "An Effect System for Algebraic Effects and Handlers"

I'm surprised we don't get this question more often, for Andrej and I have considered adding this rule for quite some time and believed to have proven its correctness. But in the end, it turned out to be false, at least in a call-by-value setting (I have heard it plays out nicer in call-by-push-value).

Consider the state handler, described on top of page 24 of the same paper, which takes a stateful computation of type $B$ on state $A$ and transforms it into a pure function from $A$ to $B$. Its type is $$B!\{\mathtt{lookup},\mathtt{update}\} \Rightarrow (A \to B ! \emptyset) ! \emptyset$$ Note the two empty sets on the right hand side. The first states that the resulting function is pure, the second one that there no effects occur when producing this function.

Now assume that we apply the handler to a computation that may call some other effects $\Delta$ besides $\mathtt{lookup}$ and $\mathtt{update}$. Applying the suggested rule, you would get the type $$B!(\{\mathtt{lookup},\mathtt{update}\} \cup \Delta) \Rightarrow (A \to B ! \emptyset) ! \Delta$$
but in fact, the correct type is
$$B!(\{\mathtt{lookup},\mathtt{update}\} \cup \Delta) \Rightarrow (A \to B ! \Delta) ! \Delta$$
as the unhandled effects $\Delta$ may occur before producing the function or after calling it.


Physical realization of nonlinear operators for quantum computers.

Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations.

As far as we know, the only nonlinear operation in quantum mechanics is that of measurement, but it's of a very restricted kind: measurement only happens at the end of your computation, and it doesn't allow you to amplify exponentially small amplitudes into non-trivial ones (except with negligible probability).

On the other hand, the kinds of nonlinearities discussed by the Abrams and Lloyd paper (as well as others) are generally those that allow you to take a quantum state with exponentially small amplitude, and amplify it to something nontrivial. We don't believe that it is possible to physically realize these nonlinear operations. Why? If it were possible, then you would be able to solve #P problems efficiently! From a complexity point of view, this consequence effectively chucks out the assumption. Being able to solve NP-complete problems efficiently is laughable; to handle #P with ease is a bad joke taken a little too far. The Abrams and Lloyd paper can be understood as an argument against the possibility of nonlinear quantum mechanics.

To try to answer the last part of your question: if there existed nonlinear quantum gates like described in the Abrams and Lloyd paper, then PostBQP could certainly be simulated by their nonlinear quantum computer (because PostBQP = PP by a result of Aaronson, and their nonlinear quantum computer can solve #P-complete problems efficiently).


Understanding the Proof of Strong Normalization of the Calculus of Constructions

Unfortunately, I'm not sure there are more beginner friendly resources than Geuvers' account. You might try this note from Chris Casinghino which gives an account of several proofs in excruciating detail.

I'm not sure I understand the gist of your confusion, but I think one important thing to note, is the following lemma (Corollary 5.2.14), proven in the classic Barendregt text:

$$\Gamma \vdash M:T\ \Rightarrow\ \Gamma \vdash T:*\mbox{ or }\square $$

This means that while $[\![T]\!]_\xi$ can be some complicated function, if $\Gamma \vdash M:T$ holds, then $[\![T]\!]_\xi$ has to be a set of terms.

This is insinuated in the outline (section 3.1), where $(\!|t|\!)_\sigma\in[\![T]\!]_\xi$ only if $\Gamma \vdash t:T :*$, which lines up with our expectation, which is that the interpretation of a type must be a set of terms, i.e. ${\cal V}(*)\subseteq{\cal P}(\mathrm{Term})$ (indeed, ${\cal V}(*)=\mathrm{SAT}$!)

It's a common situation in type theory that even though we're only interested in the "base kind" (here $*$), we still have to define semantics for things at higher kinds (hence the need to introduce $\mathrm{SAT}^*$). Things then work out at the end, because only kind which inhabited by types is $*$ (and $\square$, but that's not really important).


What is the significance of nominal techniques?

Short answer. Formal reasoning about binding and $\alpha$-conversion with  nominal approaches is closer to intuitive reasoning than alternative approaches.

Longer answer. Binders arise everywhere in mathematics and computer science.
Dealing with binders has historically been done in a handwaving way (e.g. assuming Barendregt's variable convention). This works well in informal mathematics, but breaks down in formal reasoning. In implementations of programming languages, this problem was initially handled with some form of renaming using a global operation, often called gensym, that creates globally fresh variables. Already in the implementation of programming languages that has some disadvantages, but the problem comes to the fore when reasoning about formal languages with binders, in particular about certified software.

The problem is that in early formal proofs about languages with binders, a disproportional amount of effort was dedicated to proving largely uninteresting lemmas about substitutions and $\alpha$-conversion. The core of the problem is that programming language  syntax is usually defined inductively. For example

$$
  P \quad ::= \quad x = E \ |\  while\ P\ do\ P \ |\   ...
$$

Given this genesis of programming language
syntax, it is natural to prove program properties by structural induction on program syntax. This works fine for simple languages like that above, but once we add binders

$$
  P \ ::=\ ... \ |\ \lambda x.P
$$

the situation changes. $P$ is not a subterm of $\lambda x.P$. We want to identfy programs up to consistent
renaming of bound variables, for example we don't want to distinguish
$\lambda x.ax$ from $\lambda y.ay$. In other words, programs are
equivalence classes ... and structural induction goes out of the
window.

Several techniques have been proposed for a better mathematisation of  the informal handling of binding.

Higher-order abstract syntax,
De Bruijn representation of binding,
Getting rid of variables altogether by using combinators.
Nominal technique which replaces substitution by swapping. Swapping is essentially* a first-order operation and can be internalised in the ambient logic.

Of all those proposals, the reasoning about binders with nominal techniques is closest to the intuitive "handwaving" done to handle binders in informal reasoning. That is the key advantage of nominal techniques. This might be best observed in Nominal Isabelle, where most of the reasoning about binders can be hidden from the user. See Nominal Techniques in Isabelle/HOL for a discussion.

* There is a subtle issue  in that
if you want to define higher-order functions by recursion in nominal logic, the recursion operator requires some kind   of freshness. See the conclusion of Pitt's Nominal logic, a first order theory of names and binding, which points out that "Nominal Logic does not give a complete axiomatisation of the
notion of finite support that underlies the notion of freshness in FM-sets. Nevertheless, the first-order
properties of a notion of freshness of names presented in this paper seem sufficient to develop a useful
theory, independent of any particular object-level language involving binders".


For three-dimensional vectors, construct the three-dimensional convex hull of the vectors in $L'$ in time $O(n\log n)$. The maximizer for a vector $v$ in $L$ is the point of the convex hull that is most extreme in the direction of $v$, and extreme-vertex queries may be answered in logarithmic time by using a Dobkin-Kirkpatrick hierarchy for the convex hull. For this part see e.g. O'Rourke's Computational Geometry in C, pp. 272ff. So the 3d problem can be solved in total time $O(n\log n)$.

For 4-dimensional vectors, the same thing would work, but you don't want to construct the convex hull because it's too expensive. Instead, it is possible to process a set of $n$ points in time and space $\tilde O(m)$ (for any $m$ between $n$ and $n^2$) so that you can answer extreme-point queries in time $\tilde O(n/\sqrt{m})$; see Corollary 8(iii) of Agarwal and Erickson's range query survey. Choosing $m=n^{4/3}$ gives total time $\tilde O(n^{4/3})$ to set up a data structure for $L'$ and query all vectors in $L$.


Follow the Perturbed Leader for nonlinear cost functions

Here is what you are looking for. It is quite new:

https://arxiv.org/pdf/1810.07362.pdf


With only flat domains, you cannot define limits to construct
"infinite" structures, such as looping structures, for data or for
programs. Fixpoint constructions in denotational semantics (since you used that tag) use non flat domains.
Maybe you should give examples of domains that are taken as flat,
while it would be better to do differently.

Many problems we deal with are expressed with data from flat domains.
But non-flat domains are used when necessary or convenient. Infinite,
or indefinite structure such as stream are not flat. Some domains used
for program analysis, for example with abstract interpretation, are not
flat. But is pretty much because non-flat domains are more
appropriate, as information that can be obtained is expected to have
different degrees of precision.

One good example to look at (but I have no expertise) is the case of
real numbers. They are often considered in a flat domain, but they are
really limits in a non-flat domain. How much is that used, explicitly
or implicitly?

Edit after the question was restricted to base types

The nature of the question changes somewhat if you restrict it to base
types.

In many case, it would be interesting to see whether there are
alternatives to using flat domain, and what is the usefulness of such
alternatives. Is there a choice between flat and
non-flat for booleans? Is there one for integers? for characters? etc. What are the
pros and the cons.

But, to begin with, you may have to define what is a base type. This
is why I suggested looking at the real numbers. Should the domain be
considered flat or not.  Even in classical mathematics, reals can be
defined as limits. So you could ask the question whether reals are a
base type.

I have not looked at these issues for a long time, but I think the
following paper may be relevant: "Concrete Domains" by Gilles Kahn and
Gordon Plotkin.

I also found a historical introduction to it which I have not
read. And there seem to be some significant literature that followed.


Existence of certain graph gadget related to coloring odd hole free graph

One can extract an argument that this cannot work from the paper found by OP in the MO thread. Suppose $G=(V,E)$ is as required, and $c:V\to[k]$ is a $k$-coloring. By the assumption, $c(u)\neq c(v)$. Consider the (bipartite) subgraph $H$ induced by $\{x\in V\ |\ c(x)\in\{c(u),c(v)\}\}$.

If $u$ and $v$ are in the same connected component of $H$, pick any shortest path in $H$ between $u$ and $v$; it is an induced path in $G$, with colors alternating between $c(u),c(v)$, and must have an odd number of edges because the colors at its ends differ. This contradicts the assumption.

So $u,v$ are in different connected components; but then one can toggle the coloring of one of these components to obtain a coloring $c'$ with $c'(u)=c'(v)$, contradiction.


The place from which I had read the proof was Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps). As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by Mignon and Ressayre.


Minimum cut through vertices/nodes - not edges

You are looking for Minimum Vertex K-cut. Also, if you search for k-node-connectivity you will get papers related to the structural properties of such cuts.


Runtime of Tucker's algorithm for generating a Eulerian circuit

A version of Tucker's algorithm was used in B. Awerbuch, A. Israeli, and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, STOC 1984, to find Euler tours efficiently in parallel, and similar ideas can be used to make the algorithm run sequentially in linear time.

Suppose you have a connected graph $G$ in which all vertices have even degree, and start by pairing off edges at each vertex. This forms a collection of cycles that together cover the graph, and Tucker's algorithm works by joining the cycles together one at a time.

To make this repeated joining process efficient, first run a connected components algorithm (e.g. DFS) to find which edges belong to which cycles. Make a bipartite multigraph $H$, where the vertices on one side of the bipartition correspond one-for-one with the vertices of $G$, the vertices on the other side of the bipartition correspond with the cycles you've constructed, and the edges of $H$ correspond to incidences between cycles and vertices in $G$. Construct a spanning tree $T$ of $H$ (e.g. DFS again), rooted at one of the cycle vertices.

Now, for each cycle $C$ that is not the root of $T$, join $C$ to its grandparent in $T$ (by swapping the edge pairing at the common vertex of the two cycles, represented by the parent of $C$), in constant time per join.

The same technique also works for directed graphs (and that's the version that Awerbuch et al use for their main presentation); in that case, the only difference is that you want equally many incoming and outgoing edges at each vertex, and the edge-pairing at each vertex must pair incoming edges with outgoing edges.


Minimizing SubModular Function: Cardinality

It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.


Is there a natural problem on the naturals that is NP-complete?

Based on the discussion, I’ll repost this as an answer.

As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^2+by-c=0$ has a solution $x,y\in\mathbb N$.

(The original paper states the problem with $ax^2+by-c$, but it is not hard to see that one can reduce it to the case $a=1$.)