What is "distributed computing" as a field of computer science? I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. Algorithms and computational techniques are should be discussed in High-performance computing sub-area.

Am I wrong ? Where I can read strong thesis about distributed computing and it hierarchy ?

Thanks.

This is a TCS site, not a general computer science site, so I will only give the TCS answer.

In TCS, the following things are more or less equal:

"distributed computing"
"distributed algorithms"
the study of computational aspects of distributed systems (computability, computational complexity, algorithm design and analysis, etc.)
topics of conferences such as PODC and DISC
topics covered in textbooks such as Lynch (1996): Distributed Algorithms
topics covered in courses such as this.

(Outside TCS, "distributed computing" can mean anything: SETI@home, grids, clusters, clouds, HPC, Internet, web services, P2P, IPC, you name it.)


Finding smallest context free grammar that generates a set of sets Are there any results known about the size of smallest context free grammar that generates a set of sets?

That is, I am given an alphabet $\Sigma$ as well as a set $S \subseteq \mathbb{P}(\Sigma)$ and I want to find the smallest context free grammar $G$ whose language $L$ has the property that $A \in S \Leftrightarrow (\exists x \in L~\forall l \in \Sigma~[l \in x \Leftrightarrow l \in A])$.

For instance, if $\Sigma =\{a,b,c,d\}$ and $S=\{\{d,a,c,b\},\{b,c,a\},\{a,b\},\{a\},\{\}\}$, I can have following grammar $G$ of size 14 which corresponds to the given $S$:
$$
\begin{array}{l}
G \rightarrow ``dacb"\\
G \rightarrow ``bca"\\
G \rightarrow ``ab"\\
G \rightarrow ``a"\\
G \rightarrow \lambda
\end{array}
$$

However, I can also use the fact that $S$ is a set and have the following smaller grammar $G'$ of size 13 which corresponds to representing $S$ as $``\{\{a,b,c,d\},\{a,b,c\},\{a,b\},\{a\}\}"$
$$
\begin{array}{l}
G' \rightarrow aA\\
A \rightarrow bB\\
A \rightarrow \lambda\\
B \rightarrow cd\\
B \rightarrow c\\
B \rightarrow \lambda
\end{array}
$$

I am interested in the following questions:

Has this problem been studied somewhere? In this regard, do we know the complexity of this problem? If it happens to be computationally complex, are there any approximation algorithms? What about good heuristics?
Has problems similar to this been studied before? For example, instead of using context free grammars, use set theoretic operations such as union and intersection or maybe use some other type of grammar (maybe more restricted than CFGs?).

I am interested in all results that use the underlying assumption of wanting to represent a set (i.e., order is irrelevant). I know that, in the compression literature, there are works on optimal arithmetical encodings of sets. However, I cannot see any direct translation from those results to this domain where we are interested in finding a short grammar.

Define a language $L$ to be nicely-ordered if $L \subseteq a^*b^*c^*d^*\cdots$, i.e., in every word of $L$, the letters appear solely in lexicographic order.

Conjecture: the optimum is always obtained by some nicely-ordered language, i.e., if $G$ is the smallest such grammar that generates $S$, then there exists a grammar $G'$ of the same size that also generates $S$ and such that $L(G')$ is nicely-ordered.

If this conjecture is true, then your problem reduces to a kind of grammar induction.  In particular, we are given a finite language, and the goal is to find the minimal context-free grammar that generates that language.

There are heuristics for this problem.  For instance, see the Sequitur, Lempel-Ziv-Welch, and byte pair encoding algorithms, as well as others.

In the general case (given an arbitrary finite language, find the smallest context-free language that generates it), the problem is NP-hard; I don't know if it remains NP-hard when restricted to nicely-ordered finite languages.  You could take a look at the standard proof of NP-hardness and see if it can be adjusted to apply to nicely-ordered languages.  See also Lower bounds on the size of CFGs for specific finite languages for other results in this space.

So, back to the conjecture.  One angle of attack on the problem might to try to prove or disprove this conjecture.  For instance, you might try writing a program to search for counterexamples (generate small random sets, look for the optimal grammar, check whether the conjecture holds, and repeat millions of times).  If the conjecture is true, it might make your problem much easier to solve.  If it's false, it might shed light on what makes the problem challenging.


A practical multi-word compare-and-swap operation In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the double-compare-single-swap operation - RDCSS, as follows:

word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

where the RDCSSDescriptor_t is a structure with the following fields:

a1 - address of the first condition
o1 - value expected at the first address
a2 - address of the second condition
o2 - value expected at the second address
n2 - the new value to be written at the second address

This descriptor is created and initialized once in a thread which initiates the RDCSS operation - no other thread has a reference to it until the first CAS1 in the function RDCSS succeeds, making the descriptor reachable (or active in the terminology of the paper).

The idea behind the algorithm is the following - replace the second memory location with a descriptor saying what you want to do. Then, given that the descriptor is present, check the first memory location to see if its value changed. If it hasn't, replace the descriptor at the second memory location with the new value. Otherwise, set the second memory location back to the old value.

The authors do not explain why the line with the !! comment is necessary within the paper. It seems to me that the CAS1 instructions in the Complete function will always fail after this check, provided that there is no concurrent modification. And if there was a concurrent modification between the check and the CAS in Complete, then the thread doing the check should still fail with its CAS in Complete, since the concurrent modification should not use the same descriptor d.

My question is: Can the check in the function RDCSSS, if (r == d->o2)... be omitted, with RDCSS still maintaining the semantics of a double compare, single swap instruction which is linearizable and lock-free?  (line with !! comment)

If not, can you describe the scenario where this line is actually necessary to ensure correctness?

Thank you.

In a concurrent runtime environment simple things can seem weird ... hope this can help.

We have a BUILT-IN ATOMIC CAS1 having this semantic:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

We need to define an ATOMIC RDCSS function using CAS1 and having the following semantic:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuitively: we need to CONCURRENTLY change the value at addr2 only if *addr1 == oldval1 ... if another thread is changing it we can help the other thread to complete the operation, then we can retry.

RDCSS function will be used (see article) to define CASN. Now, we define a RDCSS Descriptor in the following way:

RDCSSDESCRI
int *addr1
int oldval1
int *addr2
int oldval2
int newval2

Then we implement RDCSS in the following way:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);
}

STEP1: first we try to change the value of *addr2 to our (own) descriptor d, if CAS1 succeeds then res == d->oldval2 (i.e. res is NOT a descriptor)
STEP2: check if res is a descriptor i.e. STEP1 failed (another thread changed addr2) ... help another thread completing the operation
STEP3: retry the STEP1 if we didn't succeed in storing our descriptor d
STEP4: if we fetched our expected value from addr2 then we succeeded in storing our descriptor (pointer) in addr2 and we can complete our task storing newval2 to *addr2 iif *addr1 == oldval1

ANSWER TO YOUR QUESTION

If we omit STEP4 then the if(... && *addr1==oldval1) *addr2=newval2 part of the RDCSS semantic will never be executed (... or better: it can be executed in an umpredictable way by other threads helping the current one).

As pointed out by you in your comment the condition if(res == d1->oldval2) at STEP4 is unnecessary: even if we omit it, both CAS1 in Complete() will fail because *(d->addr2)!=d. Its only purpouse is avoid a function call.

Example T1=thread1, T2=thread2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)


Generating set of a group and relation to diameter? Is there an efficient algorithm to test if a given subset of symmetric group generates the symmetric group?
Drawing the Cayley graph and testing for all pairs reachability is one way however that scales in the size of the group.
Is there a relation between maximum distance between generating elements where distance betwee two elements of generating elements is with respect to transpositions and diameter of Cayley graph of the group with respect to the generating set?

The answer to the first part of your question is yes.

Given a permutation group $G = \langle S \rangle$, there is a polynomial time algorithm (clearly more efficient than the brute force approach which has factorial complexity), the Schreier-Sims algorithm (https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm) which computes a base and strong generating set (BSGS) that can be used to compute the order of the group (hence decide if $G=S_n$).
A good reference seems to be Seress' Permutation Group Algorithms and especially chapter 4.

Also, this question can be solved in practice by using GAP $\texttt{IsSymmetricGroup}$ (https://www.gap-system.org/Manuals/doc/ref/chap43.html), which implements this method.


Languages that we cannot (dis)prove to be Context-Free I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques.

  Is there a recent survey on the subject or an open problem section from a recent conference ?

  Probably there are not many languages which are not known to be CF, so if you know one you can also post it as an answer.

The examples I found are:

the well known language of Primitive words $Q = \{ w \mid w \neq u^i (|u| > 1) \}$ (there's a whole nice recent book on it: Context-Free Languages and Primitive Words)
the Base-k representations of the co-domain of a polynomial (see question "Base-k representations of the co-domain of a polynomial - is it context-free?" on cstheory, which perhaps has been solved by domotorp, see his preprint)

Note: as showed by Aryeh in his answer you can build a whole class of such languages if you "link" a language to an unknown conjecture about the (non)finiteness or (non)emptiness of some sets (e.g. $L_{Goldbach} = \{ 1^{2n} \mid 2n$  cannot be expressed as a sum of two primes$\}$). I'm not quite interested in such examples.

Another good one is the complement of the set $S$ of contiguous subwords (aka "factors") of the Thue-Morse sequence ${\bf t} = 0110100110010110 \cdots $.  To give some context, Jean Berstel proved that the complement of the set $T$ of prefixes of the Thue-Morse word is context-free (and actually something more general than that).  But the corresponding result for subwords is still open.


Can we design our own `if` clause in Normal Order evaluation I have been reading SICP and have been thinking over a thing for quite some time related to evaluation using Substitution with Applicative-order vs Normal-Order.

Suppose, I have defined my own if-new clause which is supposed to behave exactly as if

(define (if-new predicate a b)
        (cond (predicate a)(else b)))

This is not same as if in a runtime that evaluates in Applicative-Order. Example:

(define (p) (p))
(if (= 0 0) 0 (p)) ; This evaluates to 0.

; In case of 'if-new`
(if-new (= 0 0) 0 (p)) ; Infinite self-recursive iterative loop

But say it was evaluated in Normal-order then it will evaluate to 0.

So can I say, for a runtime which evaluates in Normal-Order, is if-new same as if?

PS: I could not think of any counter examples. I tried to solve it mathematically by proof of contradiction but I am not sure of its correctness.

Proof by Contradiction: Hypothesis: A runtime which evaluates in Normal-Order, (if-new p a b) is not same as (if p a b)
               where p,a,b are deterministic expressions and pure procedures. (i.e. when evaluated they return the same value always)

Then ∃(p a b) such that (if-new p a b) => x1 and (if p a b) => x2. And x1 != x2 (=> represents evaluation)

a' represents that a has been evaluated.

Case-1: p whenever evaluated, returns true

   (if-new p a b) => (cond (p a)(else b)) => (cond (p' a)(else b)) => a'

   (if p a b) => p' => a'

Case-2: p whenever evaluated, returns false

   (if-new p a b) => (cond (p a)(else b)) => (cond (p' a)(else b)) => b'

   (if p a b) => p' => b'

In each of the case, both the expressions provide the same result. This is a contradiction as our assumption suggests they are different. Hence proved

To answer your question we need some machinery and concepts from the theory of programming languages, so that we can actually make your question well posed, and then answer it.

You are asking whether two pieces of code are observationally equivalent.

It is usually quite hard to determine observational equivalence with direct methods (and the sort of arguments you attempted will not work). A common one is to use adequate denotational semantics. Adequacy means: "If $p$ and $q$ have the same denotation then they are observationally equivalent".

In your case, the traditional domain-theoretic denotational semantics, for instance using $\omega$-cpos, will do the job. In the denotational semantics the difference between the two evaluation orders is manifested by the fact that in the applicative order (also known as call-by-value) every function is strict (it maps the bottom element to the bottom element), while under the normal order evaluation (also known as call-by-name) one may define non-strict function.

First method

A simple calculation shows that for the call-by-name semantics the denotation of if is a map $f : \{0,1,\bot\} \times D \times D \to D$, where $D$ is a domain, defined by
$$f(b,x,y) =
\begin{cases}
\bot & \text{if $b = \bot$}\\
x & \text{if $b = 0$}\\
y & \text{if $b = 1$}
\end{cases}
$$
while the denotation of if-new is exactly the same. Because denotational semantics is adequate, we may conclude that if and if-new are observationally equivalent.

It is instructive to see what the denotation is for the strict semantics (applicative order). The semantics of if remains the same, while the semantics of if-new is a map $g : \{0,1,\bot\} \times D \times D \to D$, where $D$ is a domain, defined by
$$g(b,x,y) =
\begin{cases}
\bot & \text{if $b = \bot$ or $x = \bot$ or $y = \bot$}\\
x & \text{if $b = 0$}\\
y & \text{if $b = 1$}
\end{cases}
$$
This is not sufficient to conclude that if and if-new are observationally inequivalent (because the denotational semantics is not fully abstract), but you already gave a specific example which shows that they are different under applicative order.

Second method

The first method is an application of the general rule that denotationally equal programs are observationally equal. It requires us to always deal with domain theory. Another method is to derive useful general laws that we can then use to argue about observational equivalence. In your case we need the law of $\beta$-equivalence, which says that
((lambda (x) e1) e2) is observationally equal to e1 with e2 substituted for x. This law does not hold under applicative order, but it does for normal order. So we may calculate:

(if-new p a b) is observationally equivalent to
((lambda (x y z) (if x y z)) p a b) is observationally equivalent to
((lambda (y z) (if p y z)) a b) is observationally equivalent to
((lambda (z) (if p a z)) b) is observationally equivalent to
(if p a b)

Caveat: I am doing all this under the assumption that we are working in a fragment of Scheme which is purely functional (no side effects other than divergence).


Free books (or course materials) on undergraduate algorithms What free books (or course materials) are there that cover undergraduate algorithms material?  I added "course materials" in case there exist comprehensive sets of lecture notes/video/other that are not quite organized in a book format but that are at least as effective as a book.

A similar question about Language and Automata.

Jeff Erickson's lecture notes on Algorithms are free, with a Creative Commons license. Other than Algorithms, this site also contains lecture notes for Models of Computation, which are also with a CC license.


Cases of Linear programming known to be in $NC$? Linear programming is $P$-complete.

However are there special situations where we know an $NC$ algorithm?

Fixed dimensional linear programming (for any constant dimension $d$) is known to be in $\mathsf{NC}$; in fact, it can be done work-efficiently (in the same amount of work as the fastest sequential algorithm). The more recent paper by Blelloch et al. shows that the randomized-incremental approach for constant-dimensional LP can actually be parallelized efficiently.

Alon and Meggido (1994): Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Blelloch et al. (2016): Parallelism in Randomized Incremental Algorithms


Complete problems and universal simulator machines I'm trying to get straight in my mind the relation between complete problems and universal simulator machines.  Some notions of computability have universal machines (Turing-computability) and some don't (FDAs).

When we say that there are $\mathsf{NP}$-complete problems (to take an example) is this the same as saying that a polynomially hampered universal Turing machine is universal for the notion of polytime-computability?

My colleague Ashley Montanaro here (who kindly told me about this site) told me once that the class of $\mathsf{DSPACE}(o(\log\log n))$ problems is the same as the class of regular languages.   Does this mean that there is no universal machine for the $\mathsf{DSPACE}(o(\log\log n))$ problems?

There is a universal simulator for $\mathsf{DSPACE}(o(\log \log n)) = \mathsf{DSPACE}(O(1))=\mathsf{REG}$. Namely, $U_{REG}(p,x)$ treats the first input $p$ as the description of a DFA, and then runs that DFA on input $x$. The universal simulator, however, is not itself in $\mathsf{DSPACE}(o(\log \log n))$---the $U_{REG}$ I just described uses space essentially $O(p)$---so I don't know about complete languages in this case.

More generally, complete problems and universal simulators are related, but not equivalent. For one, a universal simulator for a class $\mathcal{C}$ need not be (and in general won't be) in the class $\mathcal{C}$ itself, as in the above example. Your example of "polynomially-hampered universal TMs" for $\mathsf{P}$ exhibits this distinction even better: let $M_1, M_2, \dotsc$ be an enumeration of poly-time TMs, where $M_i$ is hampered to use time at most, say, $n^i + i$. Then let $U(i,x) = M_i(x)$. $U$ is a universal simulator for $\mathsf{P}$, but there is no single polynomial that bounds the runtime of $U$, so $U$ itself is not in $\mathsf{P}$ and hence not complete.

Furthermore, there cannot be a single polynomial that bounds the runtime of a universal simulator for $\mathsf{P}$: if the universal simulator ran in time $n^k$, it would never be able to decide a language which required more time, say, $n^{k+1}$. We know that such languages exist by the Time Hierarchy Theorem.

However, the other direction usually holds. That is, if a class has a complete language under essentially any of the natural types of reductions, then it has a universal simulator. As an example, consider $\mathsf{NP}$ and its standard complete language SAT. Then we construct a universal machine for $\mathsf{NP}$ as follows (we knew how to do this for $\mathsf{NP}$ already using polynomially-hampered nondeterministic machines, but you'll see how this construction generalizes to any class with a complete language). $U(i,x) = SAT(M_i(x))$ where $M_i$ is the $i$-th poly-time deterministic TM, as above. Here we are using the $M_i$ to list out the possible reductions to the complete language, rather than the deciders of languages themselves.


Data Structure isomorphisms Disclaimer: I am not a CS theorist.

Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data structures. I first thought that straight up set theoretical bijective morphisms would suffice, but I ran into a wall quite rapidly - those are just encodings and do not capture the computational essence of the data structure.

Is there a more restrictive (but more useful) definition? (Or if not, why?) Is there a canonical definition of category of "constructed data structures"?

There is not a canonical such category, for the same reason there is no canonical category of computations. However, there are large and useful algebraic structures on data structures.

One of the more general such structures, which is still nevertheless useful, is the theory of combinatorial species. A species is a functor $F : B \to B$, where $B$ is the category of finite sets and bijections between them. You can think of  species as being families of structures indexed by abstract sets of locations. This explains the functoriality over $B$ -- such families have to be invariant with respect to renaming the abstract labels. Then, the calculus of species basically replays generating function methods at the functorial level, to generate sets of data structures instead of counts.

To see this theory implemented in a programming language, you can read Brent Yorgey's Haskell Symposium paper, Species and functors and types, oh my!. I think Sage also has a species package, though of course it's oriented towards computer algebra rather than programming.


$NP$ completeness of Hamiltonicity of cubic polyhedral plane graphs with bounded face degree? Let $\mathscr{C}_d$ be the class of cubic 3-connected simple plane graphs, with face degree bounded by $d$.

Is there any $d$ such that Hamiltonian cycle is $NP$ complete on $\mathscr{C}_d$? If so, what is the smallest (known) $\mathscr{C}_d$ ?

My thoughts:

I know $\mathscr{C}_3$ consists only of graphs isomorphic to $K_4$, by an Euler's formula argument. So necessarily $d > 4$.

$\mathscr{C}_4$ is already infinite, and the number of isomorphism types of size $\leq k$ grow exponentially fast: once you have a triangle, you can subdivide two of its edges and connect them with an edge. You can also subdivide four sided faces by connecting opposite edges with a new edge. You can then subdivide a triangle into an m level pyramid, and subdivide the levels with vertical lines, which gives $2^m$ choices based on the next subdivision point being 'right' or 'left' of the previous one. So $\mathscr{C}_4$ is (to me) a plausible candidate.

I know the following two closely related theorems:

1) Hamiltonian cycle is NP-complete on the class of cubic, 3-connected simple plane graphs ( $\mathscr{C}_{\infty}$ in my notation): http://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/the%20planar%20hamiltonian.pdf

In addition, they show that they can force the girth to be at least 5. This is opposite from the spirit of my question.

2) Hamiltonian cycle is NP-complete on the class of 3-connected plane graphs with face degree $3$ (i.e. maximal plane graphs): http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W82a/tech298.pdf

In the first paper which you link to (Garey-Johnson-Tarjan) they show how to construct a 3-input OR on Figure 6. This gadget has the property that it can link 3 edges with the only requirement that at least one of them needs to be used. So start from your original cubic 3-connected graph and suppose that it has a face larger than $d$. Then insert this gadget into this face onto edges $e,f,g$, where $e$ and $f$ are adjacent, and $g$ is opposite to them. Since $e$ and $f$ are adjacent, anyhow one of them had to be used in the original cubic graph, so the gadget will do nothing. On the other hand, since $g$ is on the opposite side of the face, the size $d$ will be almost halved. Here 'almost' means that this inserted gadget also has some size $c$, so the new faces will have size at most $d/2+c$. Repeating this gets rid of all faces whose size is more than $2c$.


A simple approximation algorithm for the TSP Consider the following extremely simple approximation algorithm for the TSP.

Input: A complete weighted graph $G=(V,E).$

Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$
While there are vertices in V that are not in H:

Take one of them, say $v.$ Let $H=(v_1,v_2,...,v_k,v_1),$ where $k$ is the number of distinct vertices currently contained in $H.$
Take as new $H$ the shortest of all the Hamiltonian cycles $(v,v_1,v_2,\ldots,v_k,v),$ $(v_1,v,v_2,\ldots,v_k,v_1),$ $(v_1,v_2,v,\ldots,v_k,v_1),$ $\dots,$ $(v_1,v_2,\ldots,v,v_k,v_1),$ i.e., insert $v$ before every vertex in $H$ and find the shortest Hamiltonian cycle among all those.

Output: $H.$

Obviously, this algorithm has runtime $O(n^2).$

Can anyone give me a lower (or upper) bound on the approximation ratio of this algorithm? Or a worst-case example, for that matter?

This is called an insertion heuristic. The general TSP cannot be approximated unless $P=NP$. The question is more interesting for the metric TSP. In that case, Rosenkrantz et al. (1974) show that your heuristic gives an $O(\log n)$ approximation.

You can also try to choose a good vertex $v$ to be inserted in each step, instead of just taking an arbitrary one. One variant is farthest insertion in which $v$ is chosen such that is has maximum distance from the current $H$. Another variant is nearest insertion in which $v$ is chosen such that it has minimum distance from the current $H$. Yet another possibility is cheapest insertion in which $v$ is chosen such that the new $H$ has minimum length. Rosenkrantz et al. show that both nearest and cheapest insertion give a $2-2/n$ approximation and this is tight.

The full reference is:
D. Rosenkrantz, R. Stearns, and P. Lewis II. An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563-581, 1977.


Knot Recognition as a Proof of Work Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.

Is it possible to use a Decision problem in Knot Theory such as Knot recognition and make it into a proof of work function? Also has anyone done this before? Also, when we have this Proof of Work function will it be more useful than what is being currently computed?

If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic.

In more detail, as is well known in the Graph Non Isomorphism protocol of [GMW85], Peggy the prover wishes to prove to Vicky the verifier that two (rigid) graphs $G_0$ and $G_1$ on $V$ vertices are not isomorphic.  Vicky may secretly toss a random coin $i\in\{0,1\}$, along with other coins to generate a permutation $\pi\in\ S_V$, and may present to Peggy a new graph $\pi(G_i)$.  Peggy must deduce $i$.  Clearly Peggy is only able to do this if the two graphs are not isomorphic.

Similarly, and more relevant for the purposes of a proof-of-work, as taught by [GS86] an Arthur-Merlin version of the same protocol includes Arthur agreeing with Merlin on $G_0$, $G_1$, given as for example adjacency matrices. Arthur randomly picks a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^k$, along with an image $y$.  Arthur provides $H$ and $y$ to Merlin.  Merlin must find a $(i,\pi)$ such that $H(\pi(G_i))=y$.

That is, Merlin looks for a preimage of the hash $H$, the preimage being a permutation of one of the two given adjacency matrices.  As long as $k$ is chosen correctly, if the two graphs $G_0$ and $G_1$ are not isomorphic then there will be a higher chance that a preimage will be found, because the number of adjacency matrices in $G_0 \cup G_1$ may be twice as large than if $G_0\cong G_1$.

In order to convert the above [GS86] protocol to a proof-of-work, identify miners as Merlin, and identify other nodes as Arthur.  Agree on a hash $H$, which, for all purposes, may be the $\mathsf{SHA256}$ hash used in Bitcoin.  Similarly, agree that $y$ will always be $0$, similar to the Bitcoin requirement that the hash begins with a certain number of leading $0$’s.

The network agrees to prove that two rigid graphs $G_0$ and $G_1$ are not isomorphic.  The graphs may be given by their adjacency matrices
A miner uses the link back to the previous block, along with her own Merkle root of financial transactions, call it $B$, along with her own nonce $c$, to generate a random number $Z=H(c\Vert B)$
The miner calculates $W= Z\:mod\: 2V!$ to pick $(i,\pi)$
The miner confirms that  $\pi(G_i)\neq G_{1-i}$ - that is, to confirm that the randomly chosen $\pi$ is not a proof that the graphs are isomorphic
If not, the miner calculates a hash $W=H(\pi(G_i))$
If $W$ begins with the appropriate number of $0$’s, then the miner “wins” by publishing $(c,B)$
Other nodes can verify that $Z=H(c\Vert B)$ to deduce $(i,\pi)$, and can verify that $W=H(\pi(G_i))$ begins with the appropriate difficulty of $0$’s

The above protocol is not perfect, some kinks I think would need to be worked out.  For example, it's not clear how to generate two random graphs $G_0$ and $G_1$ that satisfy good properties of rigidity, for example, nor is it clear how to adjust the difficulty other than by testing for graphs with more or less vertices.  However, I think these are probably surmountable.

But for a similar protocol on knottedness, replace random permutations on the adjacency matrix of one of the two graphs $G_1$ and $G_2$ with some other random operations on knot diagrams or grid diagrams... or something.  I don’t think random Reidemeister moves work, because the space becomes too unwieldy too quickly.

[HTY05] proposed an Arthur-Merlin protocol for knottedness, but unfortunately there was an error and they withdrew their claim.

[Kup11] showed that, assuming the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$, and mentions that this also puts knottedness in $\mathsf{AM}$, but I’ll be honest I don’t know how to translate this into the above framework; the $\mathsf{AM}$ protocol of [Kup11] I think involves finding a rare prime $p$ modulo which a system of polynomial equations is $0$.  The prime $p$ is rare in that $H(p)=0$, and the system of polynomial equations corresponds to a representation of the knot complement group.

Of note, see this answer to a similar question on a sister site, which also addresses the utility of such "useful" proofs-of-work.

References:

[GMW85] Oded Goldreich, Silvio Micali, and Avi Wigderson.  Proofs that Yield Nothing but their Validity, 1985.

[GS86] Shafi Goldwasser, Michael Sipser.  Private Coins versus Public Coins in Interactive Proof Systems, 1986.

[HTY05]  Masao Hara, Seiichi Tani, and Makoto Yamamoto.  UNKNOTTING is in $\mathsf{AM} \cap \mathsf{coAM}$, 2005.

[Kup11] Greg Kuperberg.  Knottedness is in $\mathsf{NP}$, modulo GRH,  2011.


Characterization of integral polyhedra A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if for any $c \in \mathbb{R}^n$, the program $\max\{cx : x \in P\}$ has an integer optimizer.
Now according to the theorems, to show that $P$ is integral, it merely suffices to show that for any $c \in \mathbb{Z}^n$, the program $\max\{cx : x \in P\}$ has an integer optimal value (whenever the optimum is finite).
Why should having an integer optimal value imply that there is an integer optimal solution? The proofs that I read for this use duality and give me no intuition.
Is there a better explanation of why this is true, or some kind of intuition?

Here's a proof (sketch) that doesn't explicitly use duality.  More precisely, it replaces duality by a seemingly weaker (and hopefully easily believable) geometric fact, in Step 3 below.
EDIT: But, per the comment, the proof applies only to polytopes, not (unbounded) polyhedra!
Let $P\subset \mathbb R^n$ be any polyhedron polytope such that, for all $c\in \mathbb Z^n$, the (optimal) value of the LP $\max\{cx : x\in P\}$ is an integer.
Lemma 1. $P$ is integral.  That is, every extreme point (vertex) of $P$ has integer coordinates.
Proof sketch.

Suppose otherwise for contradiction.  That is, there exists a vertex $x'$ of $P$ with a coordinate $x'_k$ that is not an integer.

Given any cost vector $c\in \mathbb R^n$ such that $x'$ is an optimal solution to the linear program $\max\{c\cdot x : x\in P\}$, say that ``$c\cdot x$ is maximized by $x'$.''

We will use the following, hopefully intuitive, geometric fact: the set of vectors $c$ such that $c\cdot x$ is maximized by $x'$ contains a ball of positive volume in $\mathbb R^n$. (Draw some pictures for intuition.)

Equivalently, there is a vector $c'\in \mathbb R^n$ and an $\epsilon>0$ such that, for all $d\in \mathbb R^n$, if $\max_i |d_i - c'_i| \le \epsilon$, then $d\cdot x$ is maximized by $x'$.

Now define $d' = c'/\epsilon$ (scaling up $c'$ by $1/\epsilon$).

Then, for all $d\in \mathbb R^n$, if $\max_i |d_i - d'_i| \le 1$, then $d\cdot x$ is maximized by $x'$. (Here we use Line 4 above, and that $d\cdot x$ is maximized by $x'$ iff $(\alpha d)\cdot x$ is, provided $\alpha > 0$.  We take $\alpha=1/\epsilon$.)

Define $b$ and $b'$ in $\mathbb Z^n$
by taking $b_i = \lfloor d'_i \rfloor$ for all $i$,
and obtaining $b'$ from $b$ by increasing $b_k$ by 1.  (Recall that $k$ is such that $x'_k$ is not an integer.)

Then $b\cdot x$ is maximized by $x'$ (using $\max_i |b_i-d'_i| \le 1$),
and $b\in\mathbb Z^n$, so (by our assumption on $P$) $b\cdot x'$ is an integer.

By the same reasoning, $b'\cdot x'$ is an integer.  So $(b'-b)\cdot x'$ is an integer.

But $(b'-b)\cdot x'$ equals $x'_k$, which is not an integer. $~~~\Box$


Transitive closure of an affine relation I am looking for work on computing the transitive closure
of an affine relation in the following sense:

Let $R(x_1,\dots,x_n,x'_1,\dots,x'_n)$
be the relation defined by a system of linear inequalities over real variables
$x_1,\dots,x_n,x'_1,\dots,x'_n$,
i.e.

$R(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff
$A x_1\dots x_n x'_1\dots x'_n \leq b$

where $A$ is an $m\times 2n$ matrix and $b$ an $m$-vector.

I am looking for a symbolic representation of $R^k$,
where

$R^k(x_1,\dots,x_n,x'_1,\dots,x'_n)$ iff
there exists $y_1,\dots,y_n$ such that
$R^{k-1}(x_1,\dots,x_n,y_1,\dots,y_n)$
and
$R(y_1,\dots,y_n,x'_1,\dots,x'_n)$.

As a very simple example, consider

$R(x,x')$ iff $x'\leq x+1$ and $x'\geq \frac{1}{2} x$

In this case, $R^k(x,x')$ iff $x'\leq x+k$ and $x'\geq \frac{1}{2^k} x$

There is an easy special case where all constraints are equalities:
then we can apply Gauss elimination to find the affine transformation
that maps the $x_i$ to the (dependent) $x'_j$ and compute its $k$th power.
But of course in general, $R$ will not be functional.

The problem also seems to be easier when $R$ describes an open polytope  a convex cone, but I can not assume this.

Edit: I'm looking for a parametric form independent of the concrete value of $k$ (as in the toy example). For a given value of $k$, a representation of $R^k$ can always be obtained from $R^{k-1}$ and $R$ by variable elimination.

An answer in case the monoid generated by $A$ for matrix multiplication is finite: Alain Finkel and Jérôme Leroux, How to Compose Presburger-accelerations: Applications to Broadcast Protocols, in FSTTCS 2002 (Foundations of Software Technology and Theoretical Computer Science)
Lecture Notes in Computer Science 2556, pages 145--156, DOI: 10.1007/3-540-36206-1_14, 2002 (see also the many references there).  The relation $R^k$ is represented by an effectively computable Presburger formula.

A more recent reference on the subject of actually computing the transitive closure is Marius Bozga, Radu Iosif and Filip Konečný, Fast Acceleration of Ultimately Periodic Relations, in CAV 2010 (Computer Aided Verification), Lecture Notes in Computer Science 6174, pages 227--242, DOI: 10.1007/978-3-642-14295-6_23, 2010.


Where can you find job postings for faculty positions in CS theory? What are the best resources for finding job postings for faculty positions in CS theory?  Is there one website or mailing list in particular that is fairly comprehensive?  I currently have the impression that one has to use a variety of resources to get a comprehensive, worldwide list of job postings.  Is this the case?

This question is related to how to get a job, though the question I'm asking here is, how do you find out about a job?

The CRA jobs site is still the best place, although it's not theory-centric. Given the proliferation of postdocs in theoryCS, I think it would be nice to have a dedicated place for theory job postings.


Is it NP-hard to _play_ minesweeper perfectly? This paper shows that it is NP-hard "to determine if there is some pattern of mines in the blank squares that give rise to the numbers seen."

If there is a way to "lead a perfect player into" such positions, then it would easily follow that it is also NP-hard to play minesweeper perfectly. However, I do not see any way to rule out the possibility of an algorithm that plays minesweeper perfectly by never going into the sort of positions that would be produced by applying that paper's reduction to hard instances of SAT.

Is playing minesweeper perfectly known to be NP-hard?

Just an extended comment; in

Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper May Not Be NP-Complete but Is Hard Nonetheless

the authors face the problem I mentioned in my comment above.

From the abstract:

In volume 22 of The Mathematical Intelligencer, Richard
Kaye published an article entitled "Minesweeper is NP-Complete."
We point out an oversight in Kaye's analysis
of this well-known game. As a consequence, his
NP-completeness proof does not prove the game to be hard.
We present here an improved model of the game,
which we use to show that the game is indeed a hard problem;
in fact, we show that it is co-NP-complete.
....In this article, we investigate the complexity of the
deterministic part of playing Minesweeper. In our
analysis, we assume that the player is given a
consistent Minesweeper board configuration.
That is, when completely revealed,
the board presented has in each square either
a mine or a numeber corresponding to the correct number
of neighboring mines.
Further, we assume an ideal player who makes no
mistakes in reasoning. Note that these assumptions imply
that the player can only lose (try to open a square containing a mine) when forced
to guess. Therefore, our optimal player who follows
the strategy described previously will avoid guessing whenever possible.
However, to do so he must be able to decide
whether it is possible to make progress on the board
without guessing. This problem is what we call the
Minesweeper Inference problem.
...

There is also a recent paper on arXiv that seems relevant (I just found it now):

Michiel de Bondt, The computational complexity of Minesweeper

Abstract: We show that the Minesweeper game is PP-hard, when the object is to locate all mines with the highest probability. When the probability of locating all mines may be infinitesimal, the Minesweeper game is even PSPACE-complete. In our construction, the player can reveal a boolean circuit in polynomial time, after guessing an initial square with no surrounding mines, a guess that has 99 percent probability of success. Subsequently, the mines must be located with a maximum probability of success.
Furthermore, we show that determining the solvability of a partially uncovered Minesweeper board is NP-complete with hexagonal and triangular grids as well as a square grid, extending a similar result for square grids only by R. Kaye. Actually finding the mines with a maximum probability of success is again PP-hard or PSPACE-complete respectively.
Our constructions are in such a way that the number of mines can be computed in polynomial time and hence a possible mine counter does not provide additional information. The results are obtained by replacing the dyadic gates in [3] by two primitives which makes life more easy in this context.


Hypersequents: proof term assigments or translations to hybrid logic I've been looking at a modal logic with the axiom

$$
(\Diamond A \land \Diamond B) \to \Diamond((A \land \Diamond B) \vee (A \land B) \vee (A \land \Diamond B))
$$

Roughly, this says that the accessibility relation is linear.

It seems like you can give a proof theory for this language using hypersequents (see Andrzej Indrzejczak's Cut-Free Hypersequent Calculus for S4.3), and I was wondering if anyone has investigated giving proof term assignments to hypersequent calculi.

Alternatively, I'd be just as happy if someone had shown how to translate hypersequent calculi into hybrid logics.

Any pointers?

I know this is a bit late, but perhaps it is still of interest.

While not exactly the logic you are interested in, Gödel-Dummett logic, the intermediate logic characterised by linear Kripke-frames, is closely related to S4.3, and for this logic people have looked into similar questions:

The paper A Lambda Calculus for Goedel-Dummett Logic Capturing Watifreedom by Yoichi Hirai gives a lambda calculus based on a hypersequent calculus for that logic.
The paper A Natural Deduction System for Intuitionistic Fuzzy Logic by Matthias Baaz, Agata Ciabattoni and Christian Fermüller gives a natural deduction system for the same logic, which might be used to give proof term assignments.

Also, you might be interested in the paper From Frame Properties to Hypersequent Rules in Modal Logics by Ori Lahav, which includes an alternative hypersequent calculus for S4.3.


Communication complexity of Independent Set game? Consider the following communication game.

Independent Set game

Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$.
Alice receives a set $X$ of edges, each edge being a pair of distinct vertices from $[n]$, and Bob receives a set $Y$ of edges.
Alice and Bob must communicate to determine whether the graph $([n],X \cup Y)$ contains an independent set with $r$ vertices.
Let IS$_{n,r}(X,Y) = 1$ if there is such a set, and IS$_{n,r}(X,Y) = 0$ otherwise.

There is a simple nondeterministic protocol to confirm that IS$_{n,r}(X,Y) = 1$; Alice nondeterministically chooses an $r$-vertex set $I$ that forms an independent set in her graph $([n],X)$ and sends Bob a description of this set using at most $r(1+\log n)$ bits.
Bob responds with 1 if $I$ is an independent set in $([n],Y)$ also; otherwise he responds with 0.
On the other hand, there is a fooling set of pairs of sets $(V,V)$ such that $([n],V)$ is a graph formed by $r$ disconnected vertices adjoined to a complete graph with $n-r$ vertices.
This 1-fooling set contains $\binom{n}{r}$ such fooling pairs, so the nondeterministic communication complexity of $\text{IS}_{n,r}$ is at least $\Omega(r\log n)$.
It follows that the simple protocol is optimal up to a small constant factor.

My question is:

  Is there a large 0-fooling set for IS$_{n,r}$?

If not, is there an efficient deterministic protocol?

I would also be interested in pointers to the literature if this problem is known.
The closest I have found is the Clique vs. Independent Set game of Yannakakis but this did not seem useful here.

Yes, there is a large 0-fooling set.
It is enough to prove this for $r=2$, as we can add (the same) $r-2$ independent vertices to all graphs in our construction.
For $r=2$, take every graph that has exactly ${n\choose 2}/2$ edges.
Everyone will fool around with its complement.


Why Ramanujan graphs are named after Ramanujan? I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?

To add some content to the answers here, I'll explain briefly what Ramanujan's conjecture is.

First of all, Ramanujan's conjecture is actually a theorem, proved by Eichler and Igusa.  Here is one way to state it.  Let $r_m(n)$ denote the number of integral solutions to the quadratic equation $x_1^2 + m^2 x_2^2 + m^2 x_3^2 + m^2 x_4^2 = n$.  If $m=1$, that $r_m(n) > 0$ was of course proved by Legendre, but Jacobi gave the exact count: $r_1(n) = 8 \sum_{d \mid n, 4 \not \mid d} d$.  Nothing similarly exact is known for larger $m$ but Ramanujan conjectured the bound: $r_m(n) = c_m \sum_{d \mid n} d + O(n^{1/2 + \epsilon})$ for every $\epsilon > 0$, where $c_m$ is a constant dependent only on $m$.

Lubtozky, Phillips and Sarnak constructed their expanders based on this result.  I'm not familiar with the details of their analysis but the basic idea, I believe, is to construct a Cayley graph of $PSL(2,Z_q)$ for a prime $q$ that $1 \bmod 4$, using generators determined by every sum-of-four-squares decomposition of $p$, where $p$ is a quadratic residue modulo $q$.  Then, they relate the eigenvalues of this Cayley graph to $r_{2q}(p^k)$ for integer powers $k$.

A reference, other than the Lubotzky-Phillips-Sarnak paper itself, is Noga Alon's brief description in Tools from Higher Algebra.


Determining how n-tuples are sorted as you search them? I have a sorted list of $N$ n-tuples, but I do not know exactly how they were sorted. The person who sorted them did so by lexicographically ordering some permutation least-to-greatest. For example, if I see the list [(53,10),(10,53)], I can conclude that they must have been swapping the elements before comparing them. If I see the list [(1,2,3),(10,20,0),(2,30,20)], I can conclude that they must have permuted the tuples so that the second element was first.

It takes $\log_2 n! \approx n \log_2 n$ bits to describe the permutation, and I would expect to discover one bit with every comparison. If that's true, then it seems like there could be a manageable algorithm for searching lists that have been sorted in an unknown way. What is the complexity of searching this kind of list? What algorithm might be able to achieve it?

The problem can be slightly generalized as follows: given a set $I\subseteq\{1,\dots,n\}$ and a set $S$ of lists of $n$-tuples, find a permutation $\sigma:\{1,\dots,|I|\}\to I$  such that each $l\in S$ is sorted according to the lexicographical preorder that compares the $\sigma(1)^\text{th}$ component, and then the $\sigma(2)^\text{th}$ component, ..., and finally the $\sigma(|I|)^\text{th}$. I'll write $<_\sigma$ for this lexicographical order.

This new problem is easily solvable by recursion: If $I=\emptyset$, there is nothing to do. Otherwise, find some $i_0\in I$ such that in each $l\in S$, the $i_0^\text{th}$ component are increasing (and if no such $i_0$ exist, return an error). Define $I':=I\setminus\{i_0\}$ and $S'$ the set of lists you get by splitting each list every time the $i_0^\text{th}$ component changes. A recursive call with $I'$ and $S'$ gives you a bijection $\sigma':\{1,\dots,|I|-1\}\to I'$ and you can then simply return $\sigma$ defined by $\sigma(1)=i_0$ and $\sigma(i+1)=\sigma'(i)$.

This algorithm runs in $O(|I|^2 |S|)$ (where $|I|$ is the cardinal of $I$, and $|S|=\sum\limits_{l\in S}\operatorname{length}(l)$). In your case and with your notations, that would be $O(n^2N)$.

I think that a slight variation of this algorithm runs in $O(|I||S|+|I|^2)$. It is described at the end of this answers. The proofs concern the $O(|I|^2 |S|)$ version but should be (relatively) easy to adapt to the faster version.

Correctness

The invariant is that if the algorithm returns a permutation $\sigma$, then all the lists in $S$ are sorted according to $<_\sigma$.

The proof is by induction on $I$. The base case is trivial because all lists are sorted according to the neutral element for the lexicographical product: equality.

In the inductive case, take any $l\in S$ we know that the sublists $l_1,\dots,l_r$ that resulted from splitting $l$ at the points where the $i_0^\text{th}$ component changed (i.e. $l=l_1@\dots@l_r$ where $@$ is concatenation, for each $k\in\{1,\dots,r\}$ all elements of $l_k$ have the same $i_0^\text{th}$ component, and for any $k\in\{1,\dots,r-1\}$ $(l_k.last)[i_0]\not=(l_{k+1}.first)[i_0]$. Since we chose $i_0$ such that $l$ (and therefore $l_k$ for all $k\in\{1,\dots,r\}$) is sorted with respect to $<_{i_0}$, this induces that (A) $a<_{i_0}b$ iff $a\in l_k$ and $b\in l_{k'}$ with $k<k'$. By the induction hypothesis, (B) each $l_k$ is sorted with respect to $<_{\sigma'}$.

Let $a,b\in l$ such that $a$ appears before $b$ in $l$.

If $a$ and $b$ appear in the same $l_k$, by (A), $a~_{i_0}b$ (i.e. $a\le_{i_0}b$ and $b\le_{i_0}a$) and $a$ appears before $b$ in $l_k$ so that by (B) $a<_{\sigma'}b$. We therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.
If $a$ appears in $l_k$ and $b$ appears in $l_{k'}$ with $k<k'$, then by (A), $a<_{i_0}b$ and we therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.

We are done because $(<_{i_0}\times_\text{lex}<_{\sigma'})={<_\sigma}$.

Completeness

The invariant is that if every $l\in S$ is sorted according to some $<_{\tilde\sigma}$ then the algorithm will return $\sigma$ such that for any $l\in S$ and $a,b\in l$, $a<_\sigma b$ iff $a<_{\tilde\sigma}b$. This implies that a list in $S$ being sorted with respect to $<_\sigma$ is equivalent it being sorted with respect to $<_{\tilde\sigma}$. We prove this invariant by induction in $I$. The base case is trivial.

In the inductive case, suppose that $l\in S$ is sorted according to some $<_{\tilde\sigma}$. Defined $\tilde\sigma':\{1,\dots,|I'|\}\to I'$ by $\tilde\sigma'(i)=\tilde\sigma(i)$ if $i<i_0$ and $\tilde\sigma'(i)=\tilde\sigma(i-1)$ if $i>i_0$. Since each $l_k\in S'$ is sorted with respect to $\tilde\sigma$, it is also sorted with respect to $\tilde\sigma'$. By the induction hypothesis, we therefore have that for all $a,b\in l_k$, $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$.

Let $a,b \in l$.

If $a,b\in l_k$, $a<_{\tilde\sigma} b$ iff $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$ iff $a<_{\sigma}$.
If $a\in l_k$ and $b\in l_{k'}$ with $k<k'$, by (A), $a<_{i_0} b$ and we therefore have $a<_{\sigma}b$. Since $l$ is sorted with respect to $<_{\tilde\sigma}$, $a<_{\tilde\sigma}b$. So we indeed have $a<_{\tilde\sigma}b$ iff $a<_{\sigma}b$ (because both are true).

We can boost it a bit by keeping keeping $S$ as a list (such that $L:=\operatorname{flatten}(S)$ is an invariant) instead of a set. You also keep a list $J$ of integers such that $\forall k\in\{1,\dots,|I|\}$, the sublist $L[1\dots J[k]]$ is sorted according to $<_k$. Then, to test a candidate $i_0$, you only check that $L[J[i_0]\dots |L|]$ is sorted with respect to $<_{i_0}$ (where you would previously test that $L[1\dots |L|]$ is), and if it fails at some point, you update $J[i_0]$ to the greatest $j$ such that $L[1\dots j]$ is sorted according to $<_{i_0}$. The number of comparisons is then bounded by $O(|I||S|+|I|^2)$ because:

You only get a positive answer for a test once (because then, you remember it was positive with $J$ and never test it again) which amounts for $O(|I||S|)$ because $\sum\limits_{1\le k \le |J|}J[k]$ starts at $0$, increases by one after every positive test (if we update it after every comparison instead of just after a comparison with a negative answer), and is bounded by $\sum\limits_{1\le k \le |J|}|S|=|J||S|=|I||S|$.
There are at most $O(|I|^2)$ negative answers, because $|I|$ strictly decreases at each iteration of the outer loop, and in the worst case, the right $i_0$ is the last you try.

You could probably further optimize it by trying all possible $i_0$ in parallel, and picking one as soon as it's the only one left (instead of checking that the rest of the list is indeed sorted with respect to that index).


What is the grammar of network protocols and file formats? For network protocols and/or file formats with fixed length fields, the grammar is fairly simple, and can be explained with a regular expression.

However, for protocols with varying data lenghts, there is almost always a fixed-length field preceding the data that gives the length of that data.

Without going into details of protocol/format specifications, we can talk about its equivalents in grammar notation. For example, consider the following production rule:

A -> anb^n

where 'a' is some fixed-length symbol, 'n' is a non-negative integer, and b^n is b repeated n times.

I'm having trouble understanding how such a rule can capture the fact that the value of 'n' is somehow related to how many b's are present in the sentence.

Where in the Chomsky hierarchy do such grammars lie? Also is it possible to automatically generate parsers for such grammars?

There is an international agreed notation for describing protocols and format specifications
(well actually there are several), which is ASN.1. It is a form of Context_free grammar notation.

I used to teach formal notations for networking at one time, but these things have dropped out of the curriculum in favour of security ; which is interesting when a better understanding of the formalism might help enhance security.

It is possible to generate code for handling protocols; and some is done that way. Using state machines for the protocol and notations like ASN.1 for the packet descriptions much can be automated, and has been in the past.


Open problems related to Graph isomorphism Presently I am doing literature survey on Graph isomorphism (GI) problem.

I would like to know some open questions related to the following

What are the graph parameters for which fixed parameter tractability of GI is an open problem.
What are the graph parameters, by fixing them polynomial time solvability of GI is not known.
Complexity of GI when restricted to many graph classes is equivalent to general GI (GI-Completeness). What are the graph classes for which GI-completeness is not known.

Thank you.

For the first question: Graph Isomorphism has been considered for at least the following parameters for which fixed-parameter tractability is still open.

pathwidth / treewidth (see [2], has been asked here), maybe solved: http://arxiv.org/abs/1404.0818
cutwidth / bandwidth [1]
treewidth-k vertex deletion set size (feedback vertex set number in [7])
tree / path distance width (see [1]), connected tree distance width (see [3], however you can get quite close to the last one, see section 6.4. of my diploma thesis ) : solved by Y. Otachi  and P. Schweitzer : http://arxiv.org/abs/1403.7238
clique-width / shrub-depth (or SC-depth) (see [4])
maximum degree [5]
genus [6] / crossing number [8]

Note that there is active ongoing research for some them.

[1] : K. Yamazaki, H. L. Bodlaender, B. de Fluiter and D. M. Thilikos. Isomorphism
for graphs of bounded distance width. Algorithmica 24.2 (1999)

[2] : H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chro-
matic index on partialk-trees. Journal of Algorithms 11.4 (1990)

[3] : Y. Otachi. Isomorphism for Graphs of Bounded Connected-Path-Distance-
Width. Algorithms and Computation. Springer, 2012

[4] : http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5] : L. Babai and E. M. Luks. Canonical labeling of graphs. STOC '83.

[6] : I. S. Filotti and J. N. Mayer. A polynomial-time algorithm for determining the
isomorphism of graphs of fixed genus. STOC '80 /
G. Miller. Isomorphism testing for graphs of bounded genus. STOC '80

[7] : S. Kratsch and P. Schweitzer. Isomorphism for graphs of bounded feedback vertex set number. SWAT 2010

[8] : http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf


Strong normalization property of CoC inside CoC Wikipedia says that

  The CoC is strongly normalizing, although, by Gödel's incompleteness
  theorem, it is impossible to prove this property within the CoC since
  it implies inconsistency.

Why is it impossible to prove within CoC that it is strongly normalizing?

Probably strong normalization property within CoC implies proof of consistency within CoC.  Then we can use the second Gödel's incompleteness theorem.  If so,

How does strong normalization property within CoC imply proof of consistency within Coc?

UPDATE:

In other words, why there can not exist a term of CoC that is a proof of CoC's proposition that CoC has normalization property. My guess is that such a term could be used to construct a term that proves a proposition of CoC that expresses consistency of CoC which is impossible by the second Gödel's incompleteness theorem.  How to construct a proof of consistency within CoC given a proof of normalization property?

I'll summarize the comments from chi, and sketch the proof that

There can be no proof of $\mathrm{False}:=\forall X:*.X$ in the CoC in head normal form. Furthermore, this fact can be proven in a weak theory, say Peano Arithmetic (though the excluded middle is not required).
This fact implies that if the CoC is normalizing, then it is consistent, and furthermore this implication does not use classical logic.

for 1., you proceed by induction on the term structure of a hypothetical closed term $t$ of type $\mathrm{False}$. Actually terms in normal form must be in the form:
 $$ \lambda x_1:T_1\ldots\lambda x_n:T_n.y\ t_1\ldots t_m$$

where $n$ and $m$ may be $0$. If $n$ is zero, then $t=y\ t_1\ldots t_m$, which is not possible since $t$ is closed (typed in the empty context).

Otherwise, we may apply inversion and conclude that $T_1=*$ (and $x_1=X$), and we get
$$ X:*\vdash\lambda x_2\ldots\lambda x_n.y\ t_1\ldots t_m\ :\ X$$
to be derivable in the CoC. Now since $X$ is not a $\Pi$, we can apply inversion again to conclude that $n=1$ and in fact the above term is simply
$$ X:*\vdash y\ t_1\ldots t_m\ :\ X$$
Inversion yet again shows that
$$X:*\vdash y\ :\ \Pi y_1:U_1\ldots\Pi y_m:U_m.X $$
but $y$ must be $X$, since it is the only variable around! Therefore $m=0$, and $X=*$, which is impossible, contradiction.

Now all this reasoning is intuitionistic, as I've proven a negative (there can be no proof of...) and proofs of negations are always constructive. I do rely heavily on inversion, and you'll just have to take it on faith that this also can be proven in arithmetic, without the excluded middle, which is non-trivial.

Now for 2. we define consistency to mean "does not prove $\mathrm{False}$"! Again a negative statement. Now if the CoC is normalizing, one can take any normal form of a proof of $\mathrm{False}$ and use the above argument to get a contradiction. Again a constructive argument!

Finally to tie it all together. Now suppose you had enough arithmetic to carry out the above arguments in CoC. Note that this is almost possible: you actually need to add the axiom $0\neq 1$ to get anything off the ground. You can then prove that normalization implies consistency within the CoC, and you also have enough arithmetic for the second incompleteness theorem to apply. Therefore you cannot (if CoC is consistent!) prove normalization, as then you would have a full proof of consistency within CoC.


Complexity of universal computation on random input This post is a refinement of a previous question which turned out to be trivial
It is also related to another previous question
Motivation: A property commonly ascribed to artificial intelligence is the ability to solve generic problems. In my opinion, this must be supplemented by a requirement of efficiency, otherwise any solvable problem can be solved by brute force which would hardly count for intelligence. Therefore it seems natural to explore the complexity bounds of universal problem solvers. Also, rather than treating all problems "equally", it makes sense to focus on problems with low Kolmogorov complexity which is elegantly achieved by generating random programs for a prefix-free universal Turing machine. The significance of these random programs in the context of artificial intelligence was acknowledged in the context of Solomonoff induction, the intelligence measure introduced by Legg and Hutter and other works on universal intelligence
Formal statement of question: Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Suppose further we have an infinite sequence $A_1, A_2, A_3...$ of such algorithms, each generated randomly and independently of the others. Denote $t_1, t_2, t_3...$ the execution times of these algorithms. We can then define
$$\nu(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t_i}<t}\right\})$$
Here $E_{halt}$ is conditional expectation value, the condition being that all algorithms halt. In other words, $\nu(t)$ is the average number of algorithms that can be executed during time $t$, assuming the algorithms are sampled randomly from our ensemble, but avoiding algorithms which don't halt. If the conditional expectation value of the execution time of $A$ had a finite value $\tau$, $\nu(t)$ would behave asymptotically as $t / \tau$. However $\tau$ is infinite since the busy beaver function grows (much) faster than exponentially, as pointed out by Artem Kaznatcheev in response to my previous question. Hence $\nu(t)$ grows much slower than linearly.
Now consider $U$ a universal computer i.e. an algorithm taking an input-less algorithm $B$ for input and producing $B$'s output for output. My point of view is that $B$ is a "problem" and $U$ is a "universal problem solver". It seems reasonable to assume that if $U$ represents an intelligent agent it should in some sense perform better than simple execution of $B$. One is reminded of the anecdote about Gauss when his school teacher gave the class an assignment to sum all numbers from 1 to 100. Instead of doing it head-on, like the teacher intended, Gauss discovered the formula
$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$
Denote $t^U_1, t^U_2, t^U_3...$ the execution times of $U$ given the input $A_1, A_2, A_3...$. Define
$$\nu_U(t):=E_{halt}(\max\left\{{n:\sum_{i=1}^n{t^U_i}<t}\right\})$$
$$T:=\inf_U \limsup_{t \to \infty} \frac{\nu(t)}{\nu_U(t)}$$
Obviously $T < \infty$. Finally, the questions:

Is T > 0?
Is T achieved for a specific $U$ i.e. is it a minimum?

Yes, T>0. I am not sure I correctly get all your conditions, so I suppose that each $A_i$ is an algorithm and each of them contains an upper bound for its running time. A constant fraction of the algorithms will be the following type: "Run U on ``This'' program and if it stops in less then k steps, then output something different from its output, otherwise stop after k steps". obviously U cannot run faster than such an algorithm. (Here faster means more than a constant factor faster.)

For your other question, you gotto be more specific about what kind of Turing-machines you allow. Probably the answer is no, see http://en.wikipedia.org/wiki/Linear_speedup_theorem.

Update 7/7 to Squark's comment: I see, you are right, I have proved that for every U the limsup >0. But if you take inf for all U, then you can take a U that knows the answer for the first many A_i and need not spend any time on them, and with high probability many of our random A_i will be from the first many, so T will go to 0. (Here I suppose that $t_i^U\le t_i$ which is not necessary, as programs can have never needed parts, but without this I cannot even prove $T<\infty$.)


Time complexity for a variant of edit distance This question is about the following variant of edit distance.  Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter x for a letter y only costs 1 the first time.  Any further substitutions of x for y cost 0.
As simple examples:
A = apppple
B = attttle

cost 1 (not 4) to transform A into B. This is because we change p for a t four times but we only charge for the first one.
A = apxpxple
B = atxyxtle

cost 2 (not 3) as the p to t substitution only costs 1 even though we do it twice.
A = apppple
B = altttte

cost 2. p -> l give allllle and then l -> t gives altttte.
If we assume the total length of the input is n, what is the best time complexity?
I suspect the problem is NP-hard so I am not expecting a poly time solution.
Question previously asked at https://codegolf.stackexchange.com/questions/215148/edit-distance-where-a-substitution-only-costs-the-first-time

Computing this type of edit distance is NP-complete, which I will prove below by reducing from the NP-complete problem Vertex Cover (given a graph $G$ and a number $k$, determine whether there exists a set of vertices $C$ with $|C|\le k$ such that each edge in $G$ has at least one vertex in $C$, aka a vertex cover of size at most $k$).
Helpful subproblem
Consider any sequence of edits between two strings (insertions/deletions/substitutions). This sequence of edits can be re-ordered so that the new sequence of edits has the same cost, but the substitutions happen after the insertions and deletions. We can separate the cost of the edits into two parts: an insertion/deletion cost and a substitution cost.
If you have already made a choice of what insertions/deletions to do starting at the source string, the insertion/deletion cost is already fixed, but there might be multiple different substitution strategies to get from that intermediate state to the target string. So one reasonable question is to ask what the optimal substitution strategy is at that point, and therefore what the optimal substitution cost is. Equivalently, this is asking for the edit distance using your distance metric but with only substitutions allowed.
So let's say we want to get from string $A = a_1a_2\ldots a_n$ to string $B = b_1b_2\ldots b_n$. Construct the directed graph $T_{A\to B}$, whose vertices are the characters used in these strings, and whose edges are the pairs $(u, v)$ such that $a_i = u \ne v = b_i$ for some $i$. In other words, $T_{A\to B}$ is the graph of the desired substitutions.
Then we have the following key fact: The optimal substitution cost is equal to the number of vertices in $T_{A\to B}$ minus the number of acyclic weakly connected components of that graph. This fact will be used in the analysis of the reduction. The rest of this section will prove it. If you are just interested in the NP-hardness proof, feel free to skip to the next section.
We want to know what substitutions to do, but each substitution has cost 1 no matter how many times we do it. In other words, we can look at every pair of characters $(u,v)$, and ask the question of whether we want to do the substitution of $u \to v$ at least once or not. This choice of which substitutions to do can be expressed as a directed graph, where we include edge $(u,v)$ if we plan to do the substitution of $u \to v$ at least once. Thus, the problem can be thought of as an optimization problem where we are looking for an optimal graph. What are we optimizing and what are our constraints? Well we are trying to minimize the substitution cost, so we are trying to choose a graph with a minimum possible number of edges. As for the constraints, each edge $(u,v)$ of $T_{A\to B}$ is a constraint saying that character $u$ must be converted into $v$ via a sequence of substitutions. In other words, the presence of edge $(u,v)$ in $T_{A\to B}$ means that we have the constraint that there must be a path from $u$ to $v$ in our graph.
Consider any weakly connected component of a candidate graph for this graph optimization problem. If the component is acyclic, then there must be at least $n-1$ edges where $n$ is the number of vertices in that component. On the other hand, if the component is cyclic, there must be at least $n$ edges. Therefore, the overall number of edges in a candidate graph has as a lower bound the number of vertices (which is fixed) minus the number of acyclic weakly connected components (which can vary among candidate graphs). If we could get an upper bound on the number of acyclic weakly connected components, we would have an overall lower bound on the number of edges (aka the substitution cost).
Now consider a weakly connected component of $T_{A\to B}$. If two vertices are in the same weakly connected component of $T_{A\to B}$, then they must also be in the same connected component of any candidate graph in our graph optimization problem (because edges in $T_{A\to B}$ correspond to paths in the candidate graph, thereby retaining connectivity). Therefore, each weakly connected component of our candidate graph must be a union of weakly connected components of $T_{A\to B}$. Thus, we see that the number of acyclic weakly connected components in $T_{A\to B}$ is an upper bound on the number of acyclic weakly connected components in our candidate graphs, which is exactly what we wanted. We have our lower bound on the substitution cost: it is at least the number of vertices in $T_{A\to B}$ minus the number of acyclic weakly connected components.
This is exactly the value that the key fact says is the optimal substitution cost, so all that's left is to demonstrate that this value can be achieved. We will do this as follows. Consider every acyclic weakly connected component of $T_{A\to B}$, one at a time. That component is a DAG, so we can find a topological sort. Then, we can include that topological sort as a path in our graph of substitutions (i.e. earliest element in the sort points to second earliest, etc...). This uses one fewer edge than the number of vertices in that component. It also satisfies the constraints for that component: if $u$ needs to be converted into $v$, then $(u,v)$ is an edge in the component; as a result $u$ must be before $v$ in the topological sort, and so the path of substitutions has as a subpath a path from $u$ to $v$. After doing this for all the acyclic weakly connected components, take all the other vertices, and arrange them in a cycle. This uses a number of edges equal to the number of vertices and satisfies the requirement since any of these vertices has a path to any other (by following the cycle). This graph satisfies all the requirements and has a total number of edges equal to the number of vertices minus the number of acyclic weakly connected components.
This concludes the proof of the key fact.
NP-hardness reduction
We wish to prove that computing the edit distance is NP-hard by reducing from Vertex Cover. That means our reduction starts with a given Vertex Cover instance: a graph $G$ and a number $k$. The reduction will output a pair of strings $(A, B)$ and a number $k'$ using polynomial time to compute these outputs. We will prove that the edit distance between $A$ and $B$ is at most $k'$ if and only if $G$ has a vertex cover of size at most $k$.
In particular, $k'$ will be $k + 4m$ where $m$ is the number of edges in $G$.
As for the strings $A$ and $B$, we will construct them out of several pieces $A = A_1A_2\ldots A_t, B = B_1B_2\ldots B_t$, where each pair $(A_i, B_i)$ is a gadget built for a specific purpose. The rest of this section will go over what kinds of gadgets we will use, how these gadgets will be combined together (i.e. how many of which gadget we will use and what characters will be used for the gadgets), and then a correctness proof showing that this reduction is correct (i.e. the edit distance between $A$ and $B$ is at most $k'$ if and only if $G$ has a vertex cover of size at most $k$).
Gadgets
The first kind of gadget we will use is an alignment gadget. This gadget consists of pair $(A_i, B_i)$ where $A_i$ consists of a large number of different characters that are not used anywhere else in $A$ or $B$ and $B_i = A_i$. The purpose of this gadget is to force alignment of these two sections of strings $A$ and $B$ via insertions/deletions. If these two sections don't align, then in the substitution step, there would need to be a number of different substitutions roughly equal to the number of characters in $A_i$. By making the number of characters large (much larger than $k'$), we can make it prohibitively expensive, in terms of substitution cost, to not align these sections of $A$ and $B$ during the insertion/deletion stage of the edits.
We will use alignment gadgets as separators between the other gadgets, which allows us to reason about each other gadget $(A_i, B_i)$ in isolation. That is, we will be forced, due to separator gadgets $(A_{i-1},B_{i-1})$ and $(A_{i+1},B_{i+1})$, to edit $A_i$ directly into $B_i$ (rather than possibly converting $A_i$ into some other part of string $B$ and converting some other part of $A$ into $B_i$).
The second gadget is a forced substitution gadget. This gadget simply consists of $(A_i, B_i)$ where $A_i$ and $B_i$ have the same (very large) length, $A_i$ consists entirely of copies of one character $u$ and $B_i$ consists of entirely copies of another character $v$. The duplication of these characters many times makes it so that even after using an insertion/deletion cost of up to $k'$, there is still at least one character $u$ that must be converted into a $v$. Since that conversion needs to happen anyway, the simplest way to solve this gadget is to just use a substitution cost of 1 to convert all the copies of $u$ into copies of $v$. However, it is possible to use some other substitution strategy to convert these characters (i.e. by converting to some third character before converting to $u$). All we really need to know here is that the insertion/deletion cost within this gadget can be as low as 0 and that the desired substitution $u \to v$ is forced, either directly or indirectly, by this gadget.
The final gadget is a choice gadget. Here $A_i = x_1ax_2$ and $B_i = bc$, where $x_1$ and $x_2$ are characters unique to this gadget (not used anywhere else), while $a$, $b$, and $c$ are characters potentially used elsewhere. Assuming this gadget is placed between two alignment gadgets, we need to convert $A_i$ into $B_i$. If this is done with an insertion/deletion cost of $1$, then we are left trying to convert either $x_1a$, $x_1x_2$, or $ax_2$ into $bc$. This can be accomplished with two substitutions, though the substitution cost can be anywhere between $0$ and $2$ depending on whether these substitutions can also be used elsewhere. Therefore, if using an insertion/deletion cost of $1$, the total cost in this gadget is at most $3$. On the other hand, the next smallest possible insertion/deletion cost in this gadget is $3$, which is already at least the cost of the three solutions listed above. Therefore, there is always an efficient solution of this gadget with only one deletion followed by substitutions. If we chose to delete $a$ and substitute $x_1x_2$ into $bc$, then both substitutions have cost $1$ since neither $x_1$ nor $x_2$ appear elsewhere in the strings; therefore, if we were to instead choose one of the other two possible deletions, the cost would be no worse. That is why this is a choice gadget: the remaining two choices involve either substituting $a$ into $b$ (when $ax_2 \to bc$) or into $c$ (when $x_1a \to bc$).
Arrangement of gadgets
As previously mentioned, we will use alignment gadgets as separators for all the other gadgets. In other words, every second gadget will be an alignment gadget. This leaves the question of which other gadgets should be used.
Consider every edge $e$ in $G$. We will use two characters $p_e$ and $q_e$ for this edge. For each such edge $e$, we will include two forced substitution gadgets forcing the substitution of $p_e$ into $q_e$ and the substitution of $q_e$ into $p_e$.
Next consider the vertices of $G$. If $v$ is a vertex, we will use $r_v$ as a character. For every edge $e = (u, v)$, we will create a choice gadget in which character $p_e$ must be substituted into either $r_u$ or $r_v$ (i.e. the choice gadget where $A_i = x_1p_ex_2$ and $B_i = r_ur_v$).
That concludes the actual construction of the reduction. Notably, these strings $A$ and $B$ and the value $k$ can easily be constructed from the vertex cover instance in polynomial time. What's left is to prove the correctness.
Correctness
Suppose first that we have a vertex cover $C$ of $G$ with $|C| \le k$. Then we will prove that the edit distance between $A$ and $B$ will be less than $k' = k + 4m$.
$A$ can be edited into $B$ as follows:

First, in the insertion/deletion step, delete one character from each choice gadget, for an insertion/deletion cost of $m$. In particular, for each edge $e = (u,v)$, we have the gadget $(A_i, B_i) = (x_1p_ex_2, r_ur_v)$ and we will delete either $x_1$ or $x_2$ as follows. Either $u$ or $v$ is in the vertex cover $C$. We will delete $x_1$ (thus requiring the substitution $p_e \to r_u$) if $u \in C$, and will delete $x_2$ (thus requiring the substitution $p_e \to r_v$) otherwise (in which case $v \in C$).
In the substitution step, we will do two things. First, we will look at each choice gadget, and we will convert either $x_1$ or $x_2$, whichever is still there, into the character it needs to turn into. This has a substitution cost of $m$. Second, we will take the characters $p_e$ and $q_e$ for every edge $e$ in $G$ and the characters $r_v$ for every vertex $v$ in $C$, and we will arrange these characters in a cycle, substituting each character for the next in the cycle. This has a substitution cost of $2m + |C|$, and allows any of these characters to turn into any other (by simply substituting along the cycle repeatedly).

This converts $A$ into $B$ with a total cost of $m+m+2m+|C| = 4m + |C| \le 4m + k = k'$. To confirm that this actually converts $A$ into $B$, lets consider every gadget. The alignment gadgets are successfully converted as long as the other gadgets are. The forced substitution gadgets are successfully converted since both $p_e$ and $q_e$ are in the cycle of substitutions. As for the choice gadgets, the necessary substitutions are either $x_1p_e \to r_ur_v$ (in a case where $v \in C$) or $p_ex_2 \to r_ur_v$ (when $u \in C$). The substitutions of $x_1$ or $x_2$ are explicitly handled. Therefore, we're left needing to substitute either $p_e \to r_v$ (when $v \in C$) or $p_e \to r_u$ (when $u \in C$). Note that in both cases, the character that $p_e$ needs to be converted into is in the cycle of substitutions, meaning that the above instructions successfully convert the choice gadgets as well.
This shows that if the answer to the vertex cover instance is "yes", then the edit distance between $A$ and $B$ is at most $k'$.
What about the reverse direction?
Let's say there is a way to edit $A$ into $B$ using at most cost $k'$. Suppose we have the solution with the least cost. When we analyzed the choice gadget, we saw that there is always an efficient (least cost) solution involving one deletion in that choice gadget, specifically deleting either $x_1$ or $x_2$ in the gadget. Thus we can assume WLOG that our least-cost solution has no insertions and exactly one deletion in each choice gadget and that the deletion is one of the two intended deletions. That's an insertion/deletion cost of $m$ in the choice gadgets alone. Therefore, the substitution cost must be at most $k' - m = 3m + k$.
Due to the alignment gadgets we know that the choice gadgets must be solved entirely by substitution after the one deletion in that gadget. Therefore, for each edge $e = (u,v)$, we either have a substitution of $x_1p_e \to r_ur_v$ or $p_ex_2 \to r_ur_v$. Define a set of vertices $C$ such that $v \in C$ if and only if there is a substitution $p_e \to r_v$ that needs to happen in some edge gadget. By the above, we see that $C$ must be a vertex cover (since each edge gadget contributes one of the endpoints of the edge to $C$).
We also know from the forced substitution gadgets that $p_e \to q_e$ and $q_e \to p_e$ are forced substitutions.
Let $A'$ be the state of the string after the insertion/deletion step and before the substitution step. At this point we will use the key fact from the first section to determine what the substitution cost must be. We know that there is a directed graph $T_{A'\to B}$ whose edges are the substitutions that are required to convert $A'$ into $B$. We know from the above that this graph includes the following edges:

$(p_e, q_e)$ and $(q_e, p_e)$ for every edge $e$ in $G$
Either $(x_1, r_u)$ and $(p_e, r_v)$, or $(x_2, r_v)$ and $(p_e, r_u)$ for each edge $e = (u,v)$ (where the $x_1$ and $x_2$ vertices are unique per edge $e$)

According to the key fact from the previous section, the substitution cost is equal to the number of vertices in this graph minus the number of acyclic weakly connected components. This value can never decrease if we add more vertices or edges, so computing this value for only those edges listed above is a lower bound on the substitution cost of our edit solution.
There are exactly $3m+n$ vertices listed above, where $n$ is the number of vertices in $G$ (one $p_e$ vertex per edge of $G$, one $q_e$ vertex per edge of $G$, one $x_1$ or $x_2$ per choice gadget--of which there are $m$, and one $r_v$ per vertex of $G$). What about the number of acyclic weakly connected components? Due to the cycle $p_e, q_e, p_e$, the connected components of vertices $p_e$ are never acyclic. As for each $r_v$, it either connects to some $p_e$, in the case that $v \in C$, or it does not connect to any $p_e$ if $v \not\in C$. In the former case, this vertex is not in an acyclic weakly connected component. In the latter case, the entire weakly connected component of $r_v$ is that vertex with some number of $x_1$ or $x_2$ vertices neighboring it. That is acyclic. As for the $x_1$ or $x_2$ vertices, each one neighbors an $r_v$ vertex, and its weakly connected component has therefore already been addressed one way or the other above. Thus, we see that each acyclic weakly connected component contains exactly one $r_v$ vertex and furthermore one where $v \not\in C$. Thus, the number acyclic weakly connected components is equal to the number of vertices $v$ not in $C$. This equals $n - |C|$.
The substitution cost therefore has a lower bound of $(3m+n) - (n-|C|) = 3m+|C|$. But we saw before that the substitution cost must be at most $k' - m = 3m + k$. Therefore, we see that it must be the case that $|C| \le k$. Then $C$ is a vertex cover of size at most $k$, proving that the answer to the vertex cover instance is "yes".
We have shown via the two directions that $G$ has a vertex cover of size at most $k$ if and only if $A$ and $B$ have an edit distance of at most $k'$. This proves that the reduction is correct. Since we previously noted that it runs in polynomial time, this concludes the proof that computing edit distance (as you defined it) is NP-hard.


Can any Steiner Tree Problem be converted to Node-Weighted Steiner Tree Problem? Steiner Tree Problem:
Given a weighted graph G(V,E,w) where w is the weight function on edges and a subset of vertices S⊆Q called terminals, a Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Steiner Tree Problem.

Node-weighted Steiner Tree Problem
Given a weighted graph G(V,E,w) where w is the weight function on nodes and a subset of vertices S⊆Q called terminals, a Node-Weighted Steiner Tree is a connected subgraph which connects all vertices in S. Finding minimum weight Steiner Tree is called Node-Weighed Steiner Tree Problem.

My question is: can any Steiner Tree Problem be converted to Node-weighted Steiner Tree Problem? I have the following approach and need to verify whether it is correct:

Lets assume we have a Steiner Tree problem with weighted edges. Consider an edge (u, v) with weight w assigned to it. Lets place a vertex X on this edge, so that the edge splits in two edges: (u, X) and (X, v). Assign zero weight to each of those edges, and assign weight w to vertex X. Repeat this for every edge of the initial graph.

The obtained graph will be node weighted and any solution to the node-weighted problem can be easily converted to match initial Steiner Tree Problem.

Basically, I need someone to verify all above is valid. I would also greatly appreciate any references from reliable sources, regarding this issue.

Sounds right. Denote by $G$ the original graph, and by $G'$ the graph after introducing the new vertices.

The first direction is trivial - every Steiner tree in $G$ corresponds to a Steiner tree in $G'$, with the same weight (by splitting each edge with its new vertex).

The second direction is less trivial. Still, consider a minimal Steiner tree $T$ in $G'$. We can assume w.l.o.g that $T$ does not contain any leaf that corresponds to a new edge-vertex. Indeed, this vertex is not in $S$, so if it is a leaf, it can be removed from the tree, keeping it a Steiner tree with minimal weight (unless you allow negative weights, which I assume you don't).

Now that we have a Steiner tree without edge-vertex leafs, we can convert it to a Steiner tree in $G$: root the tree by some vertex that is not an edge-vertex, then by the construction, all the edge-vertices have a single child in this tree. So you can replace each pair of edges $(u,X),(X,v)$ by $(u,v)$ in the original graph, obtaining a Steiner tree with the same weight.

I don't see any bugs here, but maybe I missed something.


Powerful Algorithms too complex to implement What are some algorithms of legitimate utility that are simply too complex to implement?

Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications.

Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.

Chazelle gave a linear time algorithm for triangulating a simple polygon. Skiena wrote (p.575, Algorithm Design Manual) that it's "sufficiently hopeless to implement that it qualifies more as an existence proof"


Rigorous security proof for Wiesner's quantum money? In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank has access to a giant table of random numbers, and that banknotes can be brought back to the bank for verification.  In Wiesner's scheme, each banknote consists of a classical "serial number" $s$, together with a quantum money state $|\psi_s\rangle$ consisting of $n$ unentangled qubits, each one either

$$|0\rangle,\ |1\rangle,\ |+\rangle=(|0\rangle+|1\rangle)/\sqrt{2},\ \text{or}\ |-\rangle=(|0\rangle-|1\rangle)/\sqrt{2}.$$

The bank remembers a classical description of $|\psi_s\rangle$ for every $s$.  And therefore, when $|\psi_s\rangle$ is brought back to the bank for verification, the bank can measure each qubit of $|\psi_s\rangle$ in the correct basis (either $\{|0\rangle,|1\rangle\}$ or ${|+\rangle,|-\rangle}$), and check that it gets the correct outcomes.

On the other hand, because of the uncertainty relation (or alternatively, the No-Cloning Theorem), it's "intuitively obvious" that, if a counterfeiter who doesn't know the correct bases tries to copy $|\psi_s\rangle$, then the probability that both of the counterfeiter's output states pass the bank's verification test can be at most $c^n$, for some constant $c<1$.  Furthermore, this should be true regardless of what strategy the counterfeiter uses, consistent with quantum mechanics (e.g., even if the counterfeiter uses fancy entangled measurements on $|\psi_s\rangle$).

However, while writing a paper about other quantum money schemes, my coauthor and I realized that we'd never seen a rigorous proof of the above claim anywhere, or an explicit upper bound on $c$: neither in Wiesner's original paper nor in any later one.

So, has such a proof (with an upper bound on $c$) been published?  If not, then can one derive such a proof in a more-or-less straightforward way from (say) approximate versions of the No-Cloning Theorem, or results about the security of the BB84 quantum key distribution scheme?

Update: In light of the discussion with Joe Fitzsimons below, I should clarify that I'm looking for more than just a reduction from the security of BB84.  Rather, I'm looking for an explicit upper bound on the probability of successful counterfeiting (i.e., on $c$)---and ideally, also some understanding of what the optimal counterfeiting strategy looks like.  I.e., does the optimal strategy simply measure each qubit of $|\psi_s\rangle$ independently, say in the basis

$$\{ \cos(\pi/8)|0\rangle+\sin(\pi/8)|1\rangle, \sin(\pi/8)|0\rangle-\cos(\pi/8)|1\rangle \}?$$

Or is there an entangled counterfeiting strategy that does better?

Update 2: Right now, the best counterfeiting strategies that I know are (a) the strategy above, and (b) the strategy that simply measures each qubit in the $\{|0\rangle,|1\rangle\}$ basis and "hopes for the best."  Interestingly, both of these strategies turn out to achieve a success probability of (5/8)n.  So, my conjecture of the moment is that (5/8)n might be the right answer.  In any case, the fact that 5/8 is a lower bound on c rules out any security argument for Wiesner's scheme that's "too" simple (for example, any argument to the effect that there's nothing nontrivial that a counterfeiter can do, and therefore the right answer is c=1/2).

Update 3: Nope, the right answer is (3/4)n!  See the discussion thread below Abel Molina's answer.

It seems like this interaction can be modeled in the following way:

Alice prepares one of the states $|000\rangle$, $|101\rangle$,$(|0\rangle+|1\rangle)|10\rangle/\sqrt{2}$, $(|0\rangle-|1\rangle)|11\rangle/\sqrt{2}$, according to a certain probability distribution, and sends the first qubit to Bob.
Bob performs an arbitrary quantum channel that sends his qubit to two qubits, which are then returned to Alice.
Alice performs a projective measurement on the four qubit on her possession.

If I am not wrong about this (and sorry if I am), this falls within the formalism from Gutoski and Watrous presented here and here, which implies that:

From Theorem 4.9 in the second of those, it is optimal to Bob to act independently  when Alice repeats this process with several qubits in an independent way, if the objective of Bob is to always fool Alice.
It is possible to obtain the value of c from a small semidefinite program. You can find more details of how to obtain this program in Section 3 here. See the comments for the cvx code for the program and its value.


$k$-clique in $k$-partite graph Is the decision whether a $k$-clique exists in a $k$-partite graph NP-hard?

I have found only a very limited number of references on this problem, and they seem to be concerned with heuristics to enumerate the cliques (in particular k-cliques in k-partite graphs). On complexity, they only comment that the max-clique problem is generally hard, but nothing on the specific case.

Note: This is an edit of my earlier question: whether the max-clique problem in a $k$-partite graph is NP-hard, with $k$ being part of the input? As Austin pointed out in the comments, it is easy to see that the answer is trivially yes by a reduction from the general max-clique problem; any graph $G$ on $n$ vertices can be considered $n$-partite.
The new question, however, is more specific and a reduction does not seem so obvious. For example, (and contrary to the original question) for $k=n$ one can easily check if an $n$-partite graph contains/is an $n$-clique. What about general $k$?

This should be indeed NP-hard. And the construction is very similar to one that already worked for a similar question: Many-one reduction from inequality problem to equality problem.

From a graph $G=(V,E)$ and $k$ construct the graph $G'$ with vertex set $V \times \{1,\dots,k\}$ and edges between $(v,i)$ and $(w,j)$ if $(i \ne j)$ and $(v \ne w)$ and $(v,w) \in E$. It is easy to see that $G'$ is $k$-partite and it has a $k$-clique if and only if $G$ has.


Handbook of advanced data structures I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be used for teaching a graduate level course on advanced data structures like Erik Demaine and André Schulz's Advanced Data Structures course at MIT.
An encyclopedic handbook of data structures would be even nicer.

I wish I had a good answer for you. I use Book:Fundamental Data Structures (a collection of relevant Wikipedia articles) for my course on this subject but it's not really a complete textbook (for one thing, it has no exercises). CLRS is, I think, at a good level of detail for this sort of class but is missing too many of the important structures.


Extension of a partial order to a total of partitions of a weak alternating automaton My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order?

The partitions of weak alternating automaton are defined as follows: Let $A(\Sigma,Q,q_0,\delta,\alpha)$ where $\alpha$ represents the acceptance condition, $Q$ is the set of states, and $q_0$ is the initial state. A weak alternating automaton is an alternating Buchi tree automaton in which exists a partition of the set $Q$ into disjoint sets $Q_1,\dotsc,Q_n$, such that for each set $Q_i$, either $Q_i\subseteq\alpha$ (in which case $Q_i$ is an accepting set) or $Q_i\cap\alpha=\varnothing$ (in which case $Q_i$ is a rejecting set). In addition exists a partial order $\leq$ on the collection of $Q_i$, such that for every $s \in Q_i$ and $s' \in Q_j$ for which $s'\in\delta(s,a)$ we have $Q_j \leq Q_i$. Thus, transition from the state in $Q_i$ lead to states in either the same $Q_i$ or lower one.Hence , given the partial order defined above, how to turn this order in a total order $Q_1 \leq Q_2 \leq ... \leq Q_n$

If I understand you correctly, you are asking for a linear extension of the partial order induced by the partitioning of the weak alternating automaton into its maximal strictly connected components and the transitions between the states.

Note that the "extension of the partial order" to a total order is not unique. The process of obtaining any such total order is called topologic sorting.

See the following wikipedia page for details and a link to an algorithm: http://en.wikipedia.org/wiki/Partially_ordered_set


Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for example, in Paz and Moran, Non Deterministic Polynomial Optimization Problems and Their Approximations, 1981).

I've seen several claims (for example, Lund and Yannakakis, On the Hardness of Approximating Minimization Problems, 1994) that this reduction means the approximation factor bound of $c \log m$ for some $c > 0$ (proven in Raz and Safra, A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, 1997 and cited in the mentioned Wikipedia article) gives a similar bound of $c \log n$ for MINIMUM DOMINATING SET.

But $m$ in the MINIMUM SET COVER bound is the cardinality of the universe of the sets, while the size $n = |V|$ of the graph obtained by the reduction is bigger by the number of the subsets provided for covering. When the number of subsets gets as large as $2^m$, $\log n = \log (m + 2^m)$ becomes $\Theta(m)$. How do we prove the $c \log m$ approximation factor for SET COVER when the DOMINATING SET approximation differs from the optimum only by a factor of $c m$ in the worst case?

One might argue that subsets contained in other subsets are redundant - but this still leaves $m \choose {\lfloor m/2\rfloor}$ subsets due to the Sperner's theorem, which is yet of the order of $2^m$.

Note: this page in A compendium of NP optimization problems also cites Raz and Safra's result on SET COVER inapproximability as sufficient for ($c \log |V|$)-inapproximability for DOMINATING SET.

I didn't at first understand that the question Inapproximability of set cover: can I assume m=poly(n)? contains the answer to my own question. (Thanks to @Tsuyoshi Ito for pointing out.)

In short, the proof by Raz and Safra (and any other PCP-based proof) builds an instance of SET COVER where the number of subsets is a polynomial of the universe cardinality.