Probability of a $k$-path in a random graph Assume that $G\in G(n,p)$; if $p=\frac{\ln n +\ln \ln n +c(n)}{n}$,
the following fact is well known:

\begin{eqnarray}
Pr [G\mbox{  has a Hamiltonian cycle}]=
  \begin{cases}
    1 & (c(n)\rightarrow \infty) \\
    0 & (c(n)\rightarrow - \infty) \\
 e^{-e^{-c}} & (c(n)\rightarrow c)
  \end{cases}
\end{eqnarray}

That is, a probability $p=\ln n (1+o(1)) / n$ is enough to get an Hamiltonian cycle.

For a given parameter $k\in\{1,\ldots,n\}$, I'm wondering what is the critical probability $p$ for which it's likely that the graph will have a $k$-path.

It seems that $p=\ln k(1+o(1)) / k$ is too high, as we only need one simple path of length $k$ in an $n$-nodes graph.

When $k$ is a constant, the threshold probability for a path of length $k$ is $p \sim \dfrac{1}{n^{1+1/k}}$. The same is true for any tree with $k$ edges. The general result is that the threshold probability for the appearance of a subgraph $H$ is $max_{J \subseteq H} n^{-|V(J)|/E(J)|}$, which happens to be the same as $n^{-|V(H)|/E|(H)|}$ for balanced graphs $H$ (such as trees, complete graphs, cycles).

The situation is different when $k$ grows with $n$. I don't know what the threshold is, but looking at the Hamiltonian path case, I'd guess that an extra $\log n$ factor suffices.


Universal Approximation Theorem — Neural Networks I posted this earlier on MSE, but it was suggested that here may be a better place to ask.

Universal approximation theorem states that "the standard multilayer feed-forward network with a single hidden layer, which contains finite number of hidden neurons, is a universal approximator among continuous functions on compact subsets of Rn, under mild assumptions on the activation function."

I understand what this means, but the relevant papers are too far over my level of math understanding to grasp why it is true or how a hidden layer approximates non-linear functions.

So, in terms little more advanced than basic calculus and linear algebra, how does a feed-forward network with one hidden layer approximate non-linear functions? The answer need not necessarily be totally concrete.

Cybenko's result is fairly intuitive, as I hope to convey below; what makes things more tricky is he was aiming both for generality, as well as a minimal number of hidden layers.  Kolmogorov's result (mentioned by vzn) in fact achieves a stronger guarantee, but is somewhat less relevant to machine learning (in particular, it does not build a standard neural net, since the nodes are heterogeneous); this result in turn is daunting since on the surface it is just 3 pages  recording some limits and continuous functions, but in reality it is constructing a set of fractals.  While Cybenko's result is unusual and very interesting due to the exact techniques he uses, results of that flavor are very widely used in machine learning (and I can point you to others).

Here is a high-level summary of why Cybenko's result should hold.

A continuous function on a compact set can be approximated by a piecewise constant function.
A piecewise constant function can be represented as a neural net as follows.  For each region where the function is constant, use a neural net as an indicator function for that region.  Then build a final layer with a single node, whose input linear combination is the sum of all the indicators, with a weight equal to the constant value of the corresponding region in the original piecewise constant function.

Regarding the first point above, this can be taken as the statement "a continuous function over a compact set is uniformly continuous".  What this means to us is you can take your continuous function over $[0,1]^d$, and some target error $\epsilon>0$, then you can grid $[0,1]^d$ at scale $\tau>0$ (ending up with roughly $(1/\tau)^d$ subcubes) so that a function which is constant over each subcube is within $\epsilon$ of the target function.

Now, a neural net can not precisely represent an indicator, but you can get very close.  Suppose the "transfer function" is a sigmoid.  (Transfer function is the continuous function you apply to a linear combination of inputs in order to get the value of the neural net node.)  Then by making the weights huge, you output something close to 0 or close to 1 for more inputs.  This is consistent with Cybenko's development: notice he needs the functions involved to equal 0 or 1 in the limit: by definition of limit, you get exactly what I'm saying, meaning you push things arbitrarily close to 0 or 1.

(I ignored the transfer function in the final layer; if it's there, and it's continuous, then we can fit anything mapping to $[0,1]$ by replacing the constant weights with the something in the inverse image of that constant according to the transfer function.)

Notice that the above may seem to take a couple layers: say, 2 to build the indicators on cubes, and then a final output layer.  Cybenko was trying for two points of generality: minimal number of hidden layers, and flexibility in the choice of transfer function.  I've already described how he works out flexibility in transfer function.

To get the minimum number of layers, he avoids the construction above, and instead uses functional analysis to develop a contradiction.
Here's a sketch of the argument.

The final node computes a linear combination of the elements of the layer below it, and applies a transfer function to it.  This linear combination  is a linear combination of functions, and as such, is itself a function, a function within some subspace of functions, spanned by the possible nodes in the hidden layer.
A subspace of functions is just like an ordinary finite-dimensional subspace, with the main difference that it is potentially not a closed set; that's why cybenko's arguments all take the closure of that subspace.  We are trying to prove that this closure contains all continuous functions; that will mean we are arbitrarily close to all continuous functions.
If the function space were simple (a Hilbert space), we could argue as follows.  Pick some target continuous function which is contradictorily supposed to not lie in the subspace, and project it onto the orthogonal complement of the subspace.  This residual must be nonzero.  But since our subspace can represent things like those little cubes above, we can find some region of this residual, fit a little cube to it (as above), and thereby move closer to our target function.  This is a contradiction since projections choose minimal elements.  (Note, I am leaving something out here: Cybenko's argument doesn't build any little cubes, he handles this in generality too; this is where he uses a form of the Riesz representation theorem, and properties of the transfer functions (if I remember correctly, there is a separate lemma for this step, and it is longer than the main theorem).)
We aren't in a Hilbert space, but we can use the Hahn-Banach theorem to replace the projection step above (note, proving Hahn-Banach uses the axiom of choice).

Now I'd like to say a few things about Kolmogorov's result.  While this result does not apparently need the sort of background of Cybenko's, I personally think it is much more intimidating.

Here is why.  Cybenko's result is an approximation guarantee: it does not say we can exactly represent anything.  On the other hand, Kolmogorov's result is provides an equality.  More ridiculously, it says the size of the net: you need just $\mathcal O(d^2)$ nodes.  To achieve this strengthening, there is a catch of course, the one I mentioned above: the network is heteregeneous, by which I mean all the transfer functions are not the same.

Okay, so with all that, how can this thing possible work?!

Let's go back to our cubes above.  Notice that we had to bake in a level of precision: for every $\epsilon>0$, we have to go back and pick a more refined $\tau >0$.  Since we are working with (finite) linear combinations of indicators, we are never exactly representing anything.  (things only get worse if you include the approximating effects of sigmoids.)

So what's the solution?  Well, how about we handle all scales simultaneously?  I'm not making this up: Kolmogorov's proof is effectively constructing the hidden layer as a set of fractals.  Said another way, they are basically space filling curves which map $[0,1]$ to $[0,1]^d$; this way, even though we have a combination of univariate functions, we can fit any multivariate function.  In fact, you can heuristically reason that $\mathcal O(d^2)$ is "correct" via a ridiculous counting argument: we are writing a continuous function from $\mathbb{R}^d$ to $\mathbb R$ via univariate continuous functions, and therefore, to capture all inter-coordinate interactions, we need $\mathcal O(d^2)$ functions...

Note that Cybenko's result, due to using only one type of transfer function, is more relevant to machine learning.  Theorems of this type are very common in machine learning (vzn suggested this in his answer, however he referred to Kolmogorov's result, which is less applicable due to the custom transfer functions; this is weakened in some more fancy versions of Kolmogorov's result (produced by other authors), but those still involve fractals, and at least two transfer functions).

I have some slides on these topics, which I could post if you are interested (hopefully less rambly than the above, and have some pictures; I wrote them before I was adept with Hahn-Banach, however).  I think both proofs are very, very nice.  (Also, I have another answer here on these topics, but I wrote it before I had grokked Kolmogorov's result.)


Enumerating all (super)orientations of an undirected graph Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.

Aim:
Enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph.

What for:
Compute all kernels (absorbing independent vertex sets) in as many digraphs as possible by using polyhedral descriptions of kernels, which are essentially linear programs (hence the problem can be solved efficiently).

Current solution (for enumerating all superorientations):
Given an undirected graph $G=(V,E)$,
for each edge $uv\in E$ generate 3 different arc sets $\{(u,v)\},\{(v,u)\} $ and $\{(u,v),(v,u)\}$ first.
Then enumerate all combinations of arc sets, which yields precisely $3^{|E|}$ digraphs in the result.

Code in Mathematica:

SuperOrientation[g_Graph]:= Module[{el,tal,al},
  el=EdgeList[g];
  tal=DirectedEdge@@@el;
  al=Flatten/@Tuples[Subsets[#,{1,2}]&/@Thread[List[tal,Reverse/@tal]]];
  Graph/@al];

Problem:
Current solution gives too many isomorphic digraphs, especially for highly symmetric graphs.
I can delete isomorphic superorientations "efficiently" in Mathematica (the isomorphism test in Mathematica is implemented by NAUTY, which claims to be the fastest graph isomorphism test program in practice).
But testing graph isomorphism is still quite time consuming due to the fact that graph isomorphism problem is NP-intermediate.

Question:
Is there a way to generate as less isomorphic graphs as possible in the enumeration before the isomorphism test?
It is unlikely to have a general solution.
But how about some special classes of graphs, say highly symmetric graphs.
Complete graphs, or subgraphs of complete graphs with only a few edges missing might be good starts, as my isomorphism test for superorientations of $K_7$ never ends.

For complete graphs:

Order the possible-directed-edges as [[1,0],[2,0],...,[|V|-1,0],[0,1],[2,1],...,[|V|-1,1],[0,2],[1,2],...,[|V|-1,2],...,[0,|V|-1],[1,|V|-1]],[2,|V|-1],...,[|V|-2,|V|-1]], and imagine the perfect binary rooted tree whose levels correspond to initial segments of the possible-edges under that ordering,

and whose nodes correspond to which of those possible edges are/aren't present.

Do roughly a depth-first search on that tree without actually constructing the tree,

where you do ignore tree-edges that would make neither [u,v] nor [v,u] be present

and you can ignore tree-edges that would necessarily make [number_of_superorientation_edges_to_(i+1),number_of_superorientation_edges_from_(i+1)] lexicographically less than [number_of_superorientation_edges_to_(i),number_of_superorientation_edges_from_(i)].

Output the leaves that search reaches.  In Python:

n  =  number of vertices
possibilities = tuple([(i,j) for j in range(n) for i in range(n) if j!=i])

def might_be_valid_and_canonical_(choices):
 for v in range(n):
  for u in range(v):
   i = possibilities.index((v,u))
   if (i < len(choices)) and not choices[i]:
    j = possibilities.index((u,v))
    if (j < len(choices)) and not choices[j]:
     return False
 max_out_of,max_into,min_out_of,min_into = [0]*n,[0]*n,[0]*n,[0]*n
 for i in range(len(choices)):
  if choices[i]:
   u,v = possibilites[i]
   max_out_of[u] += 1
   max_into[v] += 1
   min_out_of[u] += 1
   min_into[v] += 1
 for (u,v) in possibilities[len(choices):]
   max_out_of[u] += 1
   max_into[v] += 1
 for i in range(n-1):
  if (max_into[i+1],max_out_of[i+1]) < (min_into[i],min_out_of[i]):
   return False
 return True

numedges = n*(n-1)

def superorientations():
 if n<2:
  raise NotImplemented
 choices,try_child = tuple(),0
 while True:
  LofC = len(choices)
  if LofC == numedges:
   yield [possibilities[i] for i in range(numedges) if choices[i]]
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]
   continue
  if try_child == 0:
   if might_be_valid_and_canonical_(choices+(False,)):
    choices += (False,)
    continue
   try_child = 1
  if try_child == 1:
   if might_be_valid_and_canonical_(choices+(True,)):
    choices += (True,)
    try_child = 0
    continue
   try_child = 2
  if try_child == 2:
   LofC = len(choices)
   if LofC == 0:
    return
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]

For nearly-complete graphs, you can do that to the subgraph consisting of the

vertices with degree |V|-1, and output the extensions of those to the whole graph.


Why does the Placid Platypus function grow faster than any computable function? I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (eventually) grow faster than any computable function, similar to the busy beaver function.

However, it is trivial to upper bound this function: consider the turing machine with $n+1$ states. It's transition function is simply (have it start in state 1):

If in state $k \leq n$, go to state $k+1$, write $1$ on the tape, then move left
If in state $n+1$, halt

This will write a string of $n$ ones, thus, $PP(n) \leq n+1$, disproving the claim that the Placid Platypus function grows faster than any computable function.

What am I missing?

The function $PP(n)$ is essentially the Kolmogorov complexity of the number $n$, and is non-computable by standard arguments, which I present below.

Suppose to the contrary that $PP$
is computable. Then so is the function $f:k\mapsto n$ that maps a number $k\in\mathbb{N}$
to the least integer $n$ such that $PP(n)>k$. (Such an $n$ always exists by simple counting arguments.)
If $PP$ is computable then so is $f$.

Now define the Turing machine $M$ as follows:
$M$ prints $f(|M|)$ ones, where $|M|$ is the number of states in $M$.
Thus, $M$ has size $\ell=|M|$,
and it prints
a string of $\ell$ ones.
By construction, $PP(\ell)>\ell$,
and so
$\ell$
ones cannot be printed by any TM with $\ell$ states or fewer.
Contradiction.


Reference request: number-theory-free proof that maximal stabilizer groups determine unique states Context.

I am writing on topics such as the Gottesman-Knill theorem, using Pauli stabilizer groups, but in the case of d-dimensional qudits — where d may have more than one prime factor. (I emphasize this because the vast majority of literature on stabilizer formalism in "higher dimensions" involves the cases of d prime or d a prime power, and makes use of finite fields; I'm considering instead the cyclic groups ℤd .)

For any dimension, I characterize a (Pauli) stabilizer group as an abelian subgroup of the Pauli group, in which every operator has a +1 eigenspace.

I'm writing about a result which is well-known for d = 2 (and easily generalized to d prime):

  A stabilizer group stabilizes a unique pure state if and only if it is maximal

where by maximality, I mean that any extension either lies outside the Pauli group, or is non-abelian, or contains operators without +1 eigenvalues.
Proofs of such results for d prime usually rely on the fact that ℤd2n is a vector space (i.e. that ℤd is a field): this does not hold for d composite. There are two recourses: generalize the existing proofs in a way that is robust to the existence of zero divisiors (e.g. using tools such as the Smith normal form), or avoid number theory altogether and use ideas such as orthogonality relations of Pauli operators.

Problem.

I actually do have a concise proof of this result already, essentially using no more than orthogonality relations of Pauli operators. But I suspect that I've seen something like it before, and I would like to refer to the prior art if I can (not to mention see if there are better techniques than the one I used, which while not onerous felt less than perfect).

Certainly Knill's papers [quant-ph/9608048] and [quant-ph/9608049] consider similar subjects and use similar techniques; but I couldn't find the result I was looking for there, or in Gottesman's [quant-ph/9802007]. I'm hoping that someone can point me to where such a proof might have been published before.

Note — the result I'm considering is not one which relates the cardinality of the group to the dimension of the stabilized space (which is nice, but trivial both to prove and to find references to); I'm concerned specifically with showing that any stabilizer group which cannot be extended stabilizes a unique state, and vice versa.
A reference to a proof that any maximal stabilizer group has the same cardinality would be fine; but again, it must not rely on d being prime or ℤd2n being a vector space.

For the sake of completeness, I'll note that my version of the proof appears in

NdB. A linearized stabilizer formalism for systems of finite dimension. Quantum Information & Computation 13 (pp. 73–115), 2013. [arXiv:1102.3354v4]

appearing as Lemma B.3 (page 38) in the published version, and Lemma 12 (page 23) in the arXiv preprint; in both cases occuring in Appendix B.

If anyone can point to an reference to a proof which is older than this question, I'll accept and reward the earliest such reference which is provided.


Matching substrings within two strings I'm currently thinking about the following problem:

Given two strings $S,T$ over an alphabet $\Sigma$, return back a list $L$ of common substrings described by their length and positions within them.

I am interested only in maximal substrings as to not have redundancy. Meaning that for a substring of length $l$ with starting positions $i$ in $S$ and $j$ in $T$,  $S_{i–1} \neq T_{j–1}$ and $S_{i+l} \neq T_{j+l}$.

I am looking for a practical $O(|S|+|T|)$ solution. I wanted a bottom-up approach using hashing (a rolling hash?) that will build up the substrings as it runs. The Reputer algorithm advised to me in my previous post which is now linked gives a solution using suffix trees. I was wondering if any similar approaches have been made using hashing and if any papers exist describing them.

The answer is no. To find the full dictionary of maximal repeated substrings in linear time is a hard problem if no one has ever introduced you to a suffix tree or equivalent.  However, if you don't like using suffix trees, you can achieve much the same result using suffix arrays which can be a little easier to handle.

EDIT: Well... actually this isn't strictly a full answer if you are happy with a slightly super-linear time solution.  You can in that case use the rather lovely result from 1972 "Rapid identification of repeated patterns in strings, trees and arrays" by Karp, Miller and Rosenberg.

Can I ask, what is your motivation? You use the word practical but there is nothing impractical about the suffix tree based methods, unless your data is too large to fit in RAM. In which case the problem becomes interesting again.


Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm? We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case.
But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is exponential, it could work very well in practice.

Are there any (deterministic) examples to this situatation other than Simplex algorithm?

The $k$-means algorithm for clustering is provably exponential even in the plane, but it works very well in practice.


Occurs check in type inference I'm reading about type inference in chapter 30 of Programming Languages: Application and Interpretation and I'm trying to understand exactly how the occurs check works in an example I came up with.

Constraints generation is presented in this table:

So, given the term λx.x x, we get the following two constraints, as far as I can see:

[λx.x x] = [x] → [x x] (from λ.x x)
[x] = [x] → [x x] (from x x)

Ok, onto the unification algorithm, described in the following manner:

Apart from the use of the word “identifier”, this looks easy enough. (Apparantly the author uses “identifier” since he first assigns a name such as 1⃣  to a term like [λx.x x] – I guess these boxed numbers are identifiers...)

Ok, so our stack of constraints is

{[λx.x x] = [x] → [x x], [x] = [x] → [x x]}

and our set of substitutions is empty. The first constraint can simply be added to the set of substitutions, which is now

{[λx.x x] ↦ [x] → [x x]}

We then replace each occurrence of [λx.x x] with [x] → [x x], but there are none, so our job in this step is done.

In the next step, the remaining constraint gets the same treatment: we simply add it to the set of substitutions, which then becomes

{[λx.x x] ↦ [x] → [x x], [x] ↦ [x] → [x x]}

But our job in this step is not done, we also need to recursively update all occurrences of [x] with [x] → [x x], so we get

{[λx.x x] ↦ [x] → [x x], [x] → [x x] ↦ [x] → [x x]}

Doing this again gives us

{[λx.x x] ↦ [x] → [x x], [x] → [x x] → [x x] ↦ [x] → [x x]}

… and so on, never terminating.

Is this understanding of the problem the “occurs check” solves correct? Is this what would have happened in a type inference algorithm such as Hindley-Milner if there wasn't an explicit occurs check?

Yes, the occurs check is there so that the algorithm is guaranteed to terminate. Without it, when we deal with an equation $X = T$ in which $X$ may occur, substituting $T$ for $X$ everywhere does not get rid of $X$, and so we can run in circles, as your example shows.

There is a way to avoid this by allowing arbitrary recursive types. If we have an equation $X = T$ then we may replace $X$ everywhere by the type $\mathsf{fix} \,X \,.\, T$, i.e., a canonical solution to the equation $X = T$. Ocaml will do this for you if you run it with -rectypes:

$ ocaml -rectypes
        OCaml version 4.01.0

# fun x -> x x ;;
- : ('a -> 'b as 'a) -> 'b = <fun>

This says that fun x -> x x has the type $A \to B$ where $A = A \to B$.

By the way, you can find an implementation of the algorithm in my PL Zoo, see solve in the language Poly.


Maximize quadratic function subject to linear constraints Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?

This paper seems to come close to answering "no."  They show it is NP-hard for target functions $x_1 - x^2_2$.  However they have $x_1$ which is not squared, and from the two pages I can access online I can't understand if that's critical or not.

Bonus question: Is there a free software that can be tried to solve these problems (possibly heuristically)?

It's NP-hard.

Here's a reduction from the feasibility version of Binary Integer Programming (BIP), which is NP-hard. The problem is to decide if there's a feasible solution to the constraints $Ax \leq b$ and $x_i \in \{0,1\}$. It's easy to convert this to a problem with the constraints $Ax \leq b$ and $x_i \in \{-1,1\}$.

Now consider the following optimization problem:
$\max \sum_i x_i^2$ subject to the constraints $Ax \leq b$ and $-1 \leq x_i \leq 1$ for all $i$.

This problem has objective value $n$ (the total number of variables $x_i$) if and only if the original BIP problem was feasible.


Algorithm for finding similar images If you go to FFFFOUND! and click on some image you will notice that on the new page, under the image, there is a section called "You may like these images." which suggests 10 images that look similar to the original.

What would be a good algorithm to achieve this functionality for a collection of images?

Any documentation, books, etc. related to such algorithms is very appreciated. Also algorithms for finding similar images that yield better results than those seen on FFFFOUND! website are also welcome.

You could take a collective intelligence approach and try to determine similarity between various users based on their tastes of other images. If I like a bunch of images and another user likes majority of the same images, then it could be said that I will most likely like pictures the other user likes.

You might want to try and find information on Collaborative Filtering, Euclidean Distance/Pearson correlation (within the context of social networks.)


Rational Functions and CFL In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and  deterministic finite state transducer $T$. I've obtained some easy results like Dyck language with two braces corresponds to CFL and Dyck language with one brace is a strict subset of CFL, now there are a few problems that are still interested to me, but I can't believe that nobody have discovered it yet. Are there any papers on this subject? Googling classification of CFL or Rational Functions (Deterministic FST) + CFL gives bad result.

In general the determinism of the transducer seems to be no real restrition. The choices that can be made by a transducer can be moved into the input language. If that is OK for you, the objects sometimes denoted ${\cal M}(L)$ are called principal trio's. Examples include families of linear, blind counter and one turn counter languages (fixed number of counters).
The Habilitation-thesis of Kluas Reinhardt (Counting as Method, Model and Task in Theoretical Computer Science, available on-line) contains a nice inclusion diagram of several families (page 64).


Algorithms for the 2 Dimensional Planar Ising Model over Directed Graphs Kastelyn in the 1960's continuing Onsanger's work on the Ising model, found combinatorial solutions to the 2 dimensional planar Ising model. This was for undirected graphs.

  Has a similar algorithm been found for planar directed graphs?

To clarify what I mean, although there are several different ways one could generalise the planar Ising model to directed graphs, I have in the mind the following:

The 2-local term in the standard Ising model is the symmetric matrix $J_{ij}$. The directed graph would be represented by unsymmetric matrix $J_{ij}$! So the sum over the partition function would be unsymmetrical. I hope this helps.

If you take the standard Ising model: min $E= -\sum_{i \neq j}J_{ij}S_iS_j$, where $S_k =\pm 1$, and replace $J_{ij}$ with a non-symmetric matrix, it remains the standard Ising model. This is because you can rewrite the terms $- J_{ij}S_i S_j -J_{ji}S_j S_i = - \frac{J_{ij} + J_{ji}}{2} (S_iS_j + S_j S_i)$.

A more interesting asymmetric generalization of the planar Ising model is planar MAX 2-SAT (the problem planar MIN 2-SAT is equivalent). This is the problem MAX 2-SAT where the clauses are on the edges of a planar graph. Planar MAX 2-SAT is NP-hard: look at this paper by Guibas, Hershberger, Mitchell and Snoeyink. Thus, it appears that there may be no interesting polynomial-time generalization of the planar Ising model algorithm.

I should note that for planar MAX 2-SAT to be a generalization of the planar Ising model, you need to restrict the Ising model to polynomial-size integers $J_{ij}$. The obvious reduction also requires a planar multigraph, but there's an easy proof that planar MAX 2-SAT on a graph and on a multigraph are equivalent problems.


Bellman principle and approximability Does anybody know if a combinatorial optimzation problem that enjoys the Bellman's optimality principle can in automatic way be approximated?

One (old but useful) reference along these lines is Woeginger's 1998 paper on the connection between DPs and approximability:

  When Does a Dynamic Programming Formulation Guarantee the Existence
  of a Fully Polynomial Time Approximation Scheme (FPTAS)?


Resource / book for recent advances in statistical learning theory I'm quite familiar with the theory behind VC-Dimension, but I'm now looking at the recent (last 10 years) advances in statistical learning theory: (local) Rademacher averages, Massart's Finite Class Lemma, Covering Numbers, Chaining, Dudley's Theorem, Pseudodimension, Fat Shattering Dimension, Packing Numbers, Rademacher Composition, and possibly other results / tools that I'm not aware of.

Is there a website, survey, collection of articles, or, best of all, a book covering these topics?

Alternatively, I'm looking at examples of how to bound the Rademacher average for simple classes, in the same way that people use axis-aligned rectangles to show how to bound VC-dimension.

Thanks in advance.

I believe you would enjoy Theory of Classification: A Survey of Recent Advances by Boucheron, Bousquet, and Lugosi.  In particular, it starts by building up basic generalization theory via Rademacher complexities, introduces some useful tools (like the contraction principle, whose proof you can track down in Shai&Shai's notes referenced in the answer by Ashwinkumar, but (I believe?) originates in the probability book by Ledoux & Talagrand, which is not free), and applies these to standard classification methods (boosting and support vector machines are discussed, both due to their popularity, and since they are trained via ERM).  This text dates from 2005, so it also has some of the other somewhat recent topics you mentioned, for instance Local Rademacher Complexities, and there's even a tiny plug to chaining.  Lastly, while the manuscript is quite short, it has copious references which I believe you would find extremely useful.

Some of the other topics you mention are old enough to be in "A probabilistic Theory of Pattern Recognition" by Devroye, Györfi, and Lugosi (in particular, it has for more on packing than any other text I know).  Although it lacks some of the newer topics you mention, this is a standard book that everyone I've met in learning theory has carried on their shelves.  Maybe try to locate a table of contents and index for the book, and thumb through it.

Some of the other topics you mention I have not seen treated thoroughly in a book, but they have appeared in a number of course notes.  For instance, if you go to Sham Kakade's page at UPenn, you will find links to two learning theory courses (one was at TTI-C, with Ambuj Tewari), and you will see the topic links match some of the things you have discussed, and have not appeared in my answers or elsewhere.  There are plenty of good courses at various schools; Avrim Blum has excellent, extremely readable notes for his learning theory course (his analysis of winnow is the shortest, cleanest, and most intuitive I've ever seen!).

Some of these are maybe a little too new, though, and you'll have to go to the source material.  But if you are really just trying to pick up a grab bag of techniques, I think the survey up top and the lectures to a couple learning theory classes will serve you a long way.

Also, you sound like you're looking for advanced texts, but I'd also like to plug two introductory texts which people enjoy very much.  One is "an introduction to computational learning theory", by Kearns and (U.) Vazirani, which while old (for instance, boosting is presented only via Robert Schapire's original construction, and the emphasis is on PAC rather than agnostic learning), is presented well and has good intuition.  Personally, I got my basics in Introduction to statistical learning theory, by the same authors as the above survey (but appearing in the order Bousquet, Boucheron, Lugosi?); it has nice exposition and was the first time that generalization theory really started to click for me.


Term for a set that is not immune At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and co-RE. However, something else defined through computability theory is the concept of an immune set. Immune sets are ones where you are unable to enumerate even an infinite subset.

My question is this: is there a complexity class of decision problems where an infinite subset of "yes" instances can be enumerated, and is there a "better" name for it than "not immune"? I ask this because complexity classes are typically named for what they are, but "immune" describes what the decision problem is not.

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$.

Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$.

(If $A$ is a set of strings then we first turn it onto a [i.e. replace it by a Turing equivalent] set of integers or equivalently an infinite binary sequence before applying the hat operation.)

For instance if $A$ is the set of prime numbers then we may write
$$A=A(0)A(1)A(2)\dots=00110101000101000101\dots$$
and then $\sigma=0011010$ is a prefix of $A$ whereas $010011$ is not.

Therefore the complexity class of sets that compute only non-immune sets is just the computable sets $\mathsf{R}$.


Maximization of Mutual Information Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\mathcal{D}'$ over $X, Y, Z$ such that:

1). The marginal of $\mathcal{D}'$ on $Y, Z$ equals $\mathcal{D}$.

2). $X$ are independent of $Z$ under $\mathcal{D}'$, i.e., $I(X;Z) = 0$.

3). $I(X; Y)$ is maximized,

where $I(\cdot;\cdot)$ denotes the mutual information. For now I don't even know what is a nontrivial upper bound of $I(X;Y)$ given that $I(X;Z) = 0$? Furthermore, is it possible we can know the optimal distribution $\mathcal{D}'$ that achieves the upper bound?

My conjecture is that the upper bound of $I(X;Y)$ should have something to do with the correlation (coupling?) between $Y$ and $Z$, so ideally it should contain something related to that.

The maximum of $I(X:Y)$ in your problem is $$H(Y) - H(Z) \cdot \bigg|\Pr[Y = 0|Z = 0] - \Pr[Y = 0|Z = 1] \bigg|. $$

Let me first demonstrate an example for which this maximum is attained. Denote $\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1]$. Sample $X$ uniformly at random from $[0, 1]$ and then sample $Z$ independently from $X$ according to the corresponding marginal distribution of $\mathcal{D}$. Next, define:
$$Y = \begin{cases} 0 & \mbox{if $X\le\alpha, Z = 0$ or $X\le \beta, Z = 1$},\\ 1 &\mbox{otherwise.}\end{cases}$$

So we have 3 jointly distributed random variables $X, Y, Z$. It is clear that $(Y, Z)\sim\mathcal{D}$ and $I(X:Z) = 0$. Let's compute $I(X:Y)$. As $I(X:Y) = H(Y) - H(Y|X)$, we only have to deal with $H(Y|X)$. Assume WLOG that $\alpha \le \beta$. Then if $X\le \alpha$ or $X > \beta$, then $Y$ is constant. If $\alpha < X \le \beta$, then $Y = 1- Z$. I.e., the conditional distribution of $Y$ given $X = r\in (\alpha, \beta]$ is equal to the conditional distrbitution of $1 - Z$ given $X = r\in(\alpha, \beta]$. But $Z$ is independent of $X$, which means that this conditional distribution is just the distribution of $Z$. In other words, $H(Y|X) = \Pr[\alpha < X \le \beta] \cdot H(Z) = (\beta - \alpha) H(Z)$, as required.

There is a technical problem that $X$ takes infinitely many values. However, we can assume that $X$ takes just $3$ values with probabilities $\alpha, \beta - \alpha, 1 - \beta$. I.e., we partition $[0, 1]$ into $3$ intervals $[0, \alpha], (\alpha, \beta], (\beta, 1]$, take a random point $P$ in $[0, 1]$ and let $X$ be the interval of the partition containing $P$. The rest of the argument works similarly.

Note that in this example $Y$ is a function of $X$ and $Z$.
First, let me show that the maximum in your problem is indeed attained when  $Y$ is a function of $X$ and $Z$.

Lemma. Assume that $X, Y, Z$ are 3 jointly distributed random variables satisfying $(Y,Z) \sim\mathcal{D}$ and $I(X:Z) = 0$.Then there are 3 jointly distributed random variables $X^\prime, Y^\prime, Z^\prime$ such that $(Y^\prime, Z^\prime)\sim\mathcal{D}$, $I(X^\prime:Z^\prime) = 0$, $I(X^\prime:Y^\prime) \ge I(X:Y)$ and $Y^\prime$ is a function of $X^\prime$ and $Z^\prime$.

Proof. Sample $(X_1, Z^\prime)$ according to the distribution of $(X, Z)$ and then sample $P$ uniformly from $[0, 1]$ and independently from $(X_1, Z^\prime)$. Set $X^\prime = (X_1, P)$. Let $x$ be the value of $X_1$ and $z$ be the value of $Z^\prime$. Define
$$Y^\prime  = \begin{cases} 0 & \mbox{if $P \le \Pr[Y = 0| X = x, Z = z]$},\\ 1 &\mbox{otherwise.}\end{cases}.$$
First of all, $X^\prime$ and $Z^\prime$ are independent and $Y^\prime$ is a function of $X^\prime$ and $Z^\prime$ by construction. Further, it is clear that the distribution of $(X_1, Y^\prime, Z^\prime)$ is identical to the distribution of $(X, Y, Z)$. In particular this means that $(Y^\prime, Z^\prime) \sim\mathcal{D}$. Moreover, this gives us the following $I(X^\prime:Y^\prime) = I(X_1, P:Y^\prime) \ge I(X_1:Y^\prime) = I(X:Y)$ and the lemma is proved. Once again, there is a technical problem with the fact that $P$ takes infinitely many values, but it is clear that $P$ can be ``discretized'' as above. $\blacksquare$

To finish the argument we have to show that for any $3$ jointly distributed random variables $X, Y, Z$ such that $(Y, Z)\sim\mathcal{D}, I(X:Z) = 0$ and $Y = f(X, Z)$ for some function $f$ it holds that:
$$I(X:Y) \le H(Y) - H(Z) \cdot |\beta - \alpha|,$$
where $\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1].$

Let $W$ be the set of values of $X$. Next, define:
$$W_0 = \{x\in W \mid f(x, 0) = 0\}, \qquad W_1 = \{x\in W \mid f(x, 1) = 0\}.$$
Note that $\alpha = \Pr[f(X, Z) = 0|Z = 0] = \Pr[f(X, 0) = 0|Z = 0] = \Pr[f(X, 0) = 0] = \Pr[X\in W_0]$ (in the third equality we use the fact that $Z$ and $X$ are independent). Similarly, $\beta = \Pr[X\in W_1]$. Now, assume WLOG that $\alpha \le \beta$. Note that $\Pr[X\in W_1\setminus W_0] \ge \beta - \alpha$. On the other hand, $X\in W_1\setminus W_0$ implies that $Y = 1 - Z$. Hence $H(Y|X) \ge (\beta - \alpha) H(Z)$ and
$$I(X:Y) = H(Y) - H(Y|X) \le H(Y) - H(Z) (\beta - \alpha).$$


Are there any natural hard problems where it is required that the number of solutions are always more than one? If there are no accepting paths or only one accepting path, it outputs zero. And If there are more than one accepting paths it outputs Yes. I am looking for a natural problem that requires this.

In a cubic graph, the number of Hamiltonian cycles containing a given edge is even.  Therefore, if a cubic graph has any Hamiltonian cycles, it has at least two.  (The same has been conjectured to be true for $k$-regular graphs with $k \ge 4$ as well; I don't know the status of that conjecture.)  So deciding whether a cubic graph contains a Hamiltonian cycle (which is still NP-hard) seems to meet the criteria.

However, showing that this (or any other) problem is not in UP seems difficult, since you would have to show that the multiplicity of solutions can't be eliminated by some clever non-parsimonious reduction.  It's not enough to show that the obvious NP machine that solves the problem has multiple accepting paths.


Representing OR with polynomials I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$,
which is of degree $n$.

But how could I show, what seems obvious, that if $p$ is a polynomial that represents the OR function exactly (so $\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$), then $\deg(p) \ge n$?

Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials.

Claim: The polynomials $\{ \prod_{i \in S} x_i : S \subseteq [n] \}$, as functions $\{0,1\}^n \to \mathbb{R}$ form a basis of for the space of all functions $\{0,1\}^n \to \mathbb{R}$.

Proof: We first show that the polynomials are linearly independent. Suppose that $f = \sum_S c_S \prod_{i \in S} x_i = 0$ for all $(x_1,\ldots,x_n) \in \{0,1\}^n$. We prove by (strong) induction on $|S|$ that $c_S = 0$. Suppose that $c_T = 0$ for all $|T| < k$, and let us be given a set $S$ of cardinality $k$. For all $T \subset S$ we know by induction that $c_T = 0$, and so $0 = f(1_S) = c_S$, where $1_S$ is the input which is $1$ on the coordinates of $S$. $~\qquad\square$

The claim shows that the multilinear representation of a function $f\colon \{0,1\}^n \to \{0,1\}$ is unique (indeed, $f$ doesn't even have to be $0/1$-valued). The unique multilinear representation of OR is $1-\prod_i(1-x_i)$, which has degree $n$.


Complexity of ambiguous parsing? Consider the following problem. We are given a set of words $W \subseteq \Sigma^*$ and a set of sentences $S \subseteq W^*$. The "ambiguous parsing" problem consists, given a word $w \in \Sigma^*$, to enumerate the sentences $s \in S$ that parse to $w$ (meaning that $s$ consists of the letters $w_1,\ldots,w_k$ and $w$ is the concatenation of the corresponding words).

The problem has an interesting variant which is the search of spoonerisms: we now allow some number $M$ of letters swap, and we want to enumerate the valid sentences obtainable from $w$ with at most $M$ swaps.

So my question is: under what condition on the language $S$ can the above  problem be solved in linear time? By this I mean time $O(|W|+|S|+|w|+c)$ where $c$ is the number of solutions.

(NOTE ADDED: in response to the comments below, the vocabulary $W$ is assumed to be finite, and the set $S$ can be infinite but "finitely described" by some device $\Delta_S$. As we can report all meaningful subwords of $w$ in $O(|w|)$ time, it may be possible to reduce my question to the enumeration of the accepting paths of a non-deterministic automaton or the derivations of an ambiguous grammar. What I am looking for is restricted models that allow a linear or amortized-constant delay enumeration of the parsings.)

Here is the first part of the answer (without swapping).  I restated some of the definitions to make them clearer (I think), as I was somewhat confused by the statement of the question.

Introduction to the problem and its practical importance

I do not know the motivation for the question, as it was not given.
However this is a known problem of natural language processing (NLP),
and specifically of speech processing. The problem is that phonems are
not always clearly identifiable, nor are the boundaries between
lexical elements (words), which is a little bit more general than the
question. As a consequence, there can be several ways to cut the
spoken sentence into words of the language. In order to account for
that, the single linear stream of phonems is actually transformed into
what is called a "word lattice" which may be seen as a
directed acyclic graph or as an acyclic DFA (though even the
acyclicity is also a topic for discussion in some cases - see my
remark on whether the empty word can be in $W$). This word
lattice corresponds to all the ways the sentence can be cut into
recognizable words. This is often based on probabilities and Markov
models.

Well known examples of the need for word lattices are holorime
verses. See for example "Phonological ambiguity that changes the syntactic structure".

The word lattices are then used in various way for further linguistic
processing. One use is to do syntax analysis with respect to a
syntactic definition of the language, the identified lexical elements
(or their lexical category, called "part of speech") being used as
alphabet symbols at that syntactic level. In the question asked, the
collection $S$ or sentences plays the role of the language syntax that
defines allowed sentences. The set $W$ is the collection of acceptable
spoken language words that can be built from the phonems in $\Sigma$.
It is a bit simplified from the real speech processing situation. For
example, the set $W$ is finite, while in speech processing it is
considered open (actually finite, but so large ...). This is dealt with
by replacing all the words of a given category by that category
considered as a whole (I skip many details).

Many modern parsing techniques can be readily extended to the parsing
of word lattices, as most syntactic formalisms are closed under
intersection with regular sets. See for example "Recognition can be
Harder than Parsing".

The problem addressed by word lattices (and by this question) is lexical
ambiguity: the ambiguity resulting from the fact that the sequence of
lexical elements that can correspond to the analyzed string is not
unique. This can be opposed to syntactic ambiguity du to the fact that the
lexical sequence can be generated syntactically in two different ways,
as in ambiguous context-free grammars.

The issue of character swapping, here supposedly to detect
"spoonerisms", is part of various techniques to deal with input
ill-formedness that can be modeled by finite state tranducers.
Here again, closure properties are more than helpful.

A solution without swap, linear in each parameter

The set $W$ may be considered finite, as only a finite number of words
in $W$ can be used to form the alphabet for sentences. We assume
furthermore that the empty word is not in $W$. It is not strictly
necessary for the construction given here, but it could make the
parsing yield an arbitrarily long sequence, independently of the
length of the string $w$ being parsed, possibly giving a false idea of
the complexity.

We associate with each word $w\in W$ a unique symbol $\hat w$. Let
$\hat W=\{\hat w \mid w\in W\}$. This is not strictly necessary, but may
avoid confusion as to what is the alphabet.

Then you build a trie, as a DFA that recognizes the words in $W$. Each
final state recognizing a word $w_k\in W$ is then labeled with $\hat w_k$
(cf Moore machines). Then an $\epsilon$-transition is added from each
final state to the initial state, turning the DFA into a NFA that
recognizes sequences of words in $W$, and which can output $\hat w_k$
whenever $w_k$ has been recognized. Then you apply the powerset
construction to turn this NFA into a DFA $T_W$, such that the states of this new
DFA have all the labels of the trie final states they contain.

This construction, though expensive because of the powerset
construction, is done only once, independently of the sentence $w$,
and thus does not count in the complexity analysis. It is amortized over all string $w$ that will be parsed (as is the case for all parser construction techniques).

Given a string  $w\in\Sigma^*$
you build a DFA $L_{W,w}=(\{q_i\mid 0\leq i\leq |w|\},\hat W,q_0,q_n,\tau_{W,w})$ as follow:

$q_0$ and $q_n$ are respectively initial and final state
the number of states is $n+1$
there is a transition on input $\hat w_k$  from state $q_i$ to state
$q_j$ iff $w[i:j]=w_k$ where $w_k \in W$

The notation $w[i:j]$ denote the substring of $w$ from index $i+1$ to
index $j$, the first letter having index $1$.

This finite state automaton $L_{W,w}$, called a word lattice in speech
processing, generates or recognizes all sentences that are sequences
of words in $W$ that concatenate into the string $w$. Note that the literature often presents it as a directed acyclic graph rather than a DFA.

To build the transitions, you apply the DFA $T_W$ to the string
$w$. Whenever you enter a state that has a label $\hat w_k$ (It may
have several labels), it means
that you have just recognized the string $w_k\in W$. If you have read
$j$ letters, it means that $w[i:j]=w_k$ for $i=j-|w_k|$. Thus you add
the corresponding transition to the word lattice.

The DFA $T_W$ executes no more than $|w|$ transition steps, and at
each step adds at most $|W|$ transitions to the word lattice.
Hence the complexity is $O(|W|\times|w|)$

Now we have to find out which sentences in the language recognize by
the language of $L_{W,w}$ are also recognized by the DFA $M_S$ on alphabet
$\hat W$ recognizing $S$.

In other words we want the intersection of the two languages. This can
be obtained by the usual cross product construction of the two
automata, which are both DFA. The resulting automaton is a recognizer
for the solutions, and can be used to generate them non
deterministically.

Since the set $S$ is a regular set, potentially infinite, each
solution must be given explicitely as a word in $\hat W^*$, with
corresponding cost, rather than being named in constant time.
However, if the empty word is not in $W$, the length of each solution
is bound by the length of $w$.

The cross product construction gives a number of states that is the
product of that number for each automaton: $|Q_S|\times(|w|+1)$.
Each of the $|\tau_S|$ of the DFA $M_S$ is associated with each of the
$O(|W|\times|w|)$ transitions of the word lattice to determine the
transitions of the cross product.

Hence the cost of producing the DFA for the solutions is $O(|W|\times|w|\times|M_S|)$

The cross-product DFA is noted $F_{W,S,w}$. Its construction is such
that its mimics exactly the DFA $S$, but only for the sentences in
$\hat W^*$ accepted by the word lattice, i.e. all those corresponding
to the sentence $w$. Hence, it does give all the sentences in $S$ as
words in $\hat W^*$ that are equal letter-wise to $w$.

Enumerating the solutions

Here is how you can enumerate the solutions with the DFA $F_{W,S,w}$
to be conformant to the constraint that the enumeration should be
linear in the size of a trie of all solutions.

We suppose the symbols in $\hat T$ are totally ordered, for example by
the lexicographic order of the corresponding words in $T$.  We also
assume that the DFA $F_{W,S,w}$ has been pruned of all states that do
not have a path to an accepting state, and of transitions to and from
these states (this does not have to exceed the cost of building the
DFA). The missing transitions will be considered as virtually going to
a dead state; they are not needed here.

Let $d$ be the length of the string $w$. Since we
excluded the empty word from $T$, all solutions have a length less
than $d$. Hence the DFA $F_{W,S,w}$ is acyclic, i.e. represented by an
edge labeled DAG.

Initialize an array $\mathcal S$ of length $d$, indexed from 1 to $d$, storing
the words to be enumerated, and a cursor $c$ indexing the last
modified letter of $\mathcal S$.

Initialize a second array $\mathcal Q$ of length $d+1$, indexed from 0
to $d$, storing the states followed to produce/recognize the current
content of $\mathcal S$. The cursor $c$ indexes also the last visited
state.The array $\mathcal Q$ is initialised with the initial state of
the DFA $F_{W,S,w}$ at index 0.

Both arrays are used as pushdown stacks, the cursor $c$ pointing at
the top.

Then perform a simulation of a Depth First Search (DFS) on a virtual
version of the trie of all solutions recognized by the DFA
$F_{W,S,w}$, by updating only the top of the stacks.

When a transition of the DFA is followed, its label is pushed on
$\mathcal S$ and the next state is pushed on $\mathcal Q$.

When a state $q$ has just been pushed on the stack $\mathcal Q$:

If $q$ is an accepting state the content of stack $\mathcal S$ is a
solution;
if $q$ has transitions, follow the one with the smallest label;
if there are no transitions, then pop both stacks.

When the stacks are popped, let $\hat w$ be the symbol just popped
from $\mathcal S$, and $q$ be the new top of $\mathcal Q$.

if $q$ has transitions with a label greater than $\hat w$, follow
the one with the smallest label;
otherwise pop both stack.

When all transitions of the initial state at the bottom of stack
$\mathcal Q$ have been followed, the enumeration terminates.

This algorithm is essentially a virtual traversal of the trie of all
solutions, because the finite automation $F_{W,S,w}$ is deterministic
and pruned of unproductive states and transitions. Therefore the time
cost is linear in the size of that trie. The solutions are given in
lexicographic order with respect to $\hat V$.

However, though I have not explored the issue, I fear that the size of
that trie may far exceed the size of the DFA $F_{W,S,w}$. Even if S is
finite, it may be represented by a DFA that is much smaller than its
trie (precisely our problem).

Note:
$S$ does not have to be a regular set.

The essential ingredients for the solution presented and its
complexity are the deterministic real-time character of the automaton
and the cross product construction. Hence it should be applicable with
the same complexity result if $S$ were a real-time deterministic
context-free language.

More generally, all kinds of languages families may be considered,
with a complexity that depends on recognition complexity of the
family.
For example, if $S$ is a context-free language,
then the complexity for $|w|$ is at worst $O(|w|^3)$. But things get
then more complex: parsing with respect to a regular set for $S$ just
means recognizing $\hat W$-strings in $S$ that expand to the word $w$.
However, if S is a context-free language, one may be satisfied with a
recognizer as in the regular case, but one may also want to have some
or all parses with respect to a specific grammar which may itself be
ambiguous. The complexity analysis may then depend somewhat on what is
actually desired, on language properties or on grammar properties.
And this extend to a variety of other grammatical formalisms.

Allowing to swap letters

To come later. It can be done also with finite state techniques.


What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument? The following is not believed to be true:

  $\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Can you help me see where the argument breaks down?

The directed reachability problem is complete for $\mathsf{L}$.
I argue that it is in $\mathsf{L}$-uniform $\mathsf{NC^1}$.

The directed reachability problem over configuration graphs of
deterministic log-space Turing Machine is complete for $\mathsf{L}$.

The directed reachability problem is in $\mathsf{MSO}_2$:

  given $s$ and $t$,
  let $P$ represent the free $\mathsf{MSO}$ variable for the edges in the path.
  We need to verify that $P$ contains a directed path from $s$ to $t$
  which can be done by verifying that the in-degree and out-degree (in $P$)
  of every vertex incident on an edge in $P$ is $1$ except for $s$ and $t$
  which have in-degree,out-degree = $0,1$ and $1,0$ respectively.

Every forest is a graph of tree-width $1$.
In particular the configuration graph of
a deterministic log-space Turing Machine is a bounded tree-width structure.

From Elberfeld, Jakoby, and Tantau's
Logspace versions of the theorems of Bodlaender and Courcelle:

  $\mathsf{MSO}$ formula over bounded tree-width structures
  can be evaluated in log-space.

The proof goes something like this:
For a given structure size $n$,
a bound on the tree-width of the structures $w$, and
a $\mathsf{MSO}$ formula $\varphi$ with vocabulary $\tau$,
construct (in $\mathsf{L}$) construct a $\#\mathsf{NC}^1$ circuit $C$.

The circuit $C$ given a structure $M$ of size $n$ and tree-width at most $w$,
counts the number of "satisfying" assignments of $\varphi$ on $M$.

(The histogram tabulating
the number of assignments to the free second order variables in $\varphi$
parameterized on the sizes of the sets of values taken by the the variables).

I think the circuit $C$ only depends on the vocabulary $\tau$,
the tree-width bound $d$, and the size of structure $n$.

The proof proceeds by evaluating the circuit in $\#\mathsf{NC}^1 \subseteq \mathsf{L}$ but we don't need that part.

For us it suffices to observe that from Nondeterministic $\mathsf{NC^1}$ Computation
by Caussinus-Mackenzie-Therien-Vollmer:

  every $\#\mathsf{NC}^1$-circuit can be interpreted as
  counting the number of proof-trees of a $\mathsf{NC}^1$-circuit.

Thus the corresponding circuit outputs $1$ iff
the input structure satisfies the $\mathsf{MSO}$ formula.

From the above it seems that log-space is at least in logspace-uniform $\mathsf{NC}^1$

In fact, the circuit depends on the input structure, not only on the input structure size. We take a tree-decomposition of the graph with additional colours and turn it into a convolution tree. The evaluation of the formula on this tree is reduced to computing the value of the convolution tree. To compute the value of the tree, it is turned into an arithmetic circuit. Hence we do not get one circuit for each input size as required for $NC^1$, but rather one circuit for each single input.


Minimum amount of colors preventing an equilateral uniformly colored subtriangle In the Bundeswettberweb Infomatik 2010/2011, there was an interesting problem:

For fixed $n$, find a minimal $k$ and a map  $\varphi: \{(i,j)|i\leq j \leq n\}\rightarrow \{1,\ldots,k\}$, such that there is no triple $(i,j),(i+l,j),(i+l,j+l)$ with $\varphi(i,j)=\varphi(i+l,j)=\varphi(i+l,j+l)$.

Namely we are looking for the minimal amount of colors for a triangle, such that there is no uniformly colored equilateral subtriangle (the following picture shows an invalid coloring as the highlighted vertices form such an uniformly colored equilateral subtriangle):

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

In fact they asked for a reasonably small $k$ for $n=1000$ and in the solution (written in german) they noted that a greedy approach yields a coloring with $27$ colors for $n=1000$, which can be reduced to $15$ by randomizing colors until a valid solution is found.

I am interested into exact solutions (for smaller $n$). The solution says that backtracking yields that $2$ colors are sufficient for $n\in\{2,3,4\}$ and $3$ are sufficient for $5\leq n \leq 17$, where backtracking is already really slow for $n=17$.

First I tried to use an ILP formulation and Gurobi to get some results for $n>17$, but it was too slow (already for $n=17$). Then I used a SAT solver, because I noticed that there is a straight forward formulation as a SAT-instance.

With that approach I was able to generate a solution with $3$ colors for $n=18$ within $10$ minutes:

$\ \ \ ~~~~~~~~~~~~~~~~~~~~~~~~~~~$

But to decide if $3$ colors suffice for $n=19$ it is already too slow. Is there some different approach that gives exact solutions for $n \geq 19$? Certainly we can't expect a polynomial algorithm.

Just an extended comment:

You can take a look to the approach used by Steinbach and Posthoff to find the 4-coloring of a 18x18 (and 12x21) grid without monochromatic rectangles:

Bernd Steinbach and Christian Posthoff, Solution of the Last Open Four-Colored Rectangle-free Grid an Extremely Complex Multiple-Valued Problem. In Proceedings of the 2013 IEEE 43rd International Symposium on Multiple-Valued Logic (ISMVL '13)

As proved by Gasarch et al. given a partial $c$-coloring of an arbitrary $n \times m$ rectangle, it is NP-complete to decide if the coloring can be extended to the whole rectangle without monochromatic rectangles: Daniel Apon, William Gasarch, Kevin Lawler, An NP-Complete Problem in Grid Coloring.
So there are high chances that the problem is NP-complete even for equilateral triangles .... I think it would be a nice result to prove it.

Just a side note: I spent weeks of CPU cycles on the monochromatic rectangle-free 4-coloring problem but I started from a wrong partial result (a wrong previous analysis that restricted the number of possible 1-color sub-configurations) and I used the STP constraint solver; you can achieve great improvements if you add constraints that break symmetries (e.g. an ordering on the coloring of a side of the triangle) and try to make an analysis of the possible configurations using only 1-color.

EDIT: this is the result of an STP program for n=19 (~ 1 min.)


Matrix Coloring under Vertical and Horizontal Constraints I'm searching for the correct name of the following NP-complete problem. I  would also appreciate answers pointing to problems with similar-looking variations.

The input consists of

A set of colors $\Sigma$ with $|\Sigma|=n^{O(1)}$.
An $nxn$ square matrix $M$ where each entry $M_{ij}$ is a subset of $\Sigma$
For each $i\in [n]$ and each $j\in [n-1]$, a set $H_{ij}\subseteq \Sigma\times \Sigma$ of horizontal constraints.
For each $i\in [n-1]$ and each $j\in [n]$, a set $V_{ij}\subseteq \Sigma\times \Sigma$ of vertical constraints.

A solution for the problem is an $n\times n$ matrix $N$ where each entry $N_{ij}$ belongs to $M_{ij}$, each pair horizontally consecutive entries $(N_{ij},N_{i(j+1)})$ belongs to $H_{ij}$ and each pair of vertically consecutive entries $(N_{ij},N_{(i+1)j})$ belongs to $V_{ij}$.

A1) The problem remains NP-complete even for fixed $|\Sigma|=3$

A reduction from planar 1-3-SAT is the following; suppose $\Sigma = \{0,1,2\}$

use a sequence of $M_{ij} = \{0,1\}$ pairs of horizontal/vertical cells as "wire" gadgets to "carry" the truth values ($0=true$, $1,2 = false$) of the variables (the horizontal and vertical rules of the wires forbid switching between $true \leftrightarrow false$)
the beginning of a wire acts as "variable assignment"
the clauses are simulated using a circular pattern in which the horizontal and vertical rules force a sequence of $012\;012....$ along the circuit
each clause has 3 incoming wires; the wires are arranged to "touch" the circuit in three distinct places modulo 3; in this way only one of the three wires can have the value of true.

The following figure should be self-explanatory.

If instead of "local" horizontal/vertical rules you want to use "global" rules (a set of rules that are common to all cells) then you must add another extra "blank" color to "isolate" the wires and the reduction above still holds.

With $|\Sigma| = 2$ the problem is polynomial time solvable (each cell is represented with a binary variable, and the rules can be expressed with a 2-SAT formula).

A2) The game is also very similar to a "relaxed" version of the game Binary Puzzle: a puzzle game played on a $n \times n$ grid. Intially some of the cells contain a zero or a one; the aim of the game is to fill the empty cells according to the following rules:

Each cell should contain a zero or a one and no more than two similar numbers next to or below each other are allowed
Each row and each column should contain an equal number of zeros and ones
Each row is unique and each column is unique

Using a set of eight colors you can "simulate" the rule #1 of binary puzzle (which is NPC even without rules #2 and #3 ). This is a quick idea for a reduction.

Each one of the eight colors has 3 bits $b_0b_1b_2$;

bit 0 $b_0$ represents the $0$ or $1$ of the binary puzzle grid
bit 1 $b_1$ is $1$ if and only if the cell on the left has the same color
bit 2 $b_2$ is $1$ if and only if the cell above has the same color

If a cell $i,j$ of the initial board of binary puzzle is empty then you set $M_{ij} = \Sigma$

If a cell $i,j$ of the initial board of binary puzzle is a forced $1$ then you set $M_{ij} = \{ 1** \}$ (100,101,110,111)

If a cell $i,j$ of the initial board of binary puzzle is a forced $0$ then you set $M_{ij} = \{ 0** \}$ (000,001,010,011)

The horizontal rules are:

00* -> 01*  : allow another 0 on the right only if the previous was 1
0** -> 1**  : always allow a 0->1 transition
10* -> 11*  : allow another 1 on the right only if the previous was 0
1** -> 0**  : always allow a 1->0 transition

The vertical rules are:

0*0 -> 0*1  : allow another 0 below only if the above one was 1
0** -> 1**  : always allow a 0->1 transition
1*0 -> 1*1  : allow another 1 below only if the above one was 0
1** -> 0**  : always allow a 1->0 transition

You can find the proof of NP-completeness of binary puzzle on my blog (soon or later I'll find the time to submit it somewhere).

A3) Furthermore if you add the constraint that each color can be used only once, then the problem is still NPC even on $n \times 1$ grids with only horizontal constraints.

The reduction is from 3-PARTITION which is strongly NPC: given a set $X = \{x_1, ..., x_{3q}\}$ and a target sum $B = (\sum x_i)/3$; use (new) colors $c^i_1,...,c^i_i$ for each $x_i$. Start with a grid $G$ of length $Bq+q + 1$ with  the following sets of allowed colors:

$S E^B T_1 E^B T...E^B T_q$

Where

$S$ (the set $M_1$) represents the starting color $\{ c_S \}$
$T_i$ represents a breaking block that contain $q$ special colors $\{ c_{Ti} \}$
$E^B$ is a sequence of $B$ "blocks" that can contain any color from $\Sigma \setminus \{ c_S, c_{Ti}\}$

The horizontal constraints are:

$(S,c^i_1)$ for $i = 1...n$: that allows to start from $S$ and start using a color sequence from $c^i$
$(c^i_j, c^i_{j+1})$ for $j = 1...i-1$: that forces the complete color sequence of each $c^i$ (once started)
$(c^i_i, c^j_1)$ for $i \neq j$ that allows to start another color sequence once ended the previous one
$(c^i_i, c_{Tj})$ for $i = 1...n, j=1..q-1$: that "align" the color sequences to the break blocks (that guarantee that the "unary" sum is equal to $B$)
$(c_{Tj}, c^i_1, )$ for $i = 1...n, j=1..q-1$: that allows another color sequence after a breaking block $T_j$

The $n \times 1$ grid $G$ can be properly colored if and only if the original 3-PARTITION problem has a solution.

This is an example: given the 3-PARTITION instance:

$A = \{ 3,3,2,2,2,2 \}\; (B=7, q=2)$

We can use $2B + 2$ distinct colors and build a coloring game instance on a $2B + 2 + 1 = 17 \times 1$ grid like in the figure.


Why are NPI problems not all of the same complexity? How does one look at a problem and reason that it is likely NP-Intermediate as opposed to NP-Complete?  It is often pretty simple to look at a problem and tell whether it is likely NP-Complete or not but it appears to me to be much harder to tell whether a problem is NP-Intermediate as the line seems to be quite thin between the two classes.  Basically what I am asking is why would a problem that can be verified in polynomial time (if at all) but not solved in polynomial time (as long as P dosn't equal NP) not be polynomial time reducible to each other.  Also, is there some way to show a problem is NP-Intermediate similar to how a problem is shown to be NP-Hard, such as reduction or some other technique?  Any links or textbooks that would help me understand the class of NP-Intermediate would be appreciated as well.

You cannot show that a problem is $\mathsf{NPI}$ without separating $\mathsf{P}$ from $\mathsf{NP}$.

There are artificial problems that can be proven to be in $\mathsf{NPI}$ using generalizations of Lander's theorem (also see this) assuming that $\mathsf{NP}\neq\mathsf{P}$.

Also padded version of $ \mathsf{NEXP\text{-}complete} $ problems are $\mathsf{NPI}$ assuming $ \mathsf{NEXP} \neq \mathsf{EXP} $ (see also this and this).

A problem in $\mathsf{NP}$ is often conjectured to be $\mathsf{NPI}$ when:

we can show under reasonable assumptions that it is not $\mathsf{NPC}$ yet it is not known to be in $\mathsf{P}$,
we can show under reasonable assumptions that it is not in $\mathsf{P}$ yet it is not known to be in $\mathsf{NPC}$,

and sometime just when we cannot show that it is in $\mathsf{NPC}$ or $\mathsf{P}$.

An example of a reasonable assumption is the exponential time hypothesis (or some of other computational hardness assumptions).

  Basically what I am asking is why would a problem that can be satisfied in polynomial time (if at all) but not solved in polynomial time (as long as P doesn't equal NP) not be polynomial time reducible to each other.

I don't see why one would expect that to be true. But in any case, assuming $\mathsf{NPC}\not \subseteq \mathsf{P}$ it follows from Lander's theorem that there are infinitely many levels of $\mathsf{P}$-degrees between $\mathsf{P}$ and $\mathsf{NP}$.


Completeness and Context-Sensitive Languages. I'm interested in two questions regarding context-sensitive languages (CSL) and completeness:

 Is there a notion of completeness for CSL, and which languages are complete?
 Are there natural CSL that are NP-complete?

For 2., I can certainly think of natural NP-complete languages that are CSL (as CSL is equal to NSPACE[$n$], SAT is a CSL), but I'm searching for the other way around, i.e., a context-sensitive grammar describing an NP-complete language.

To answer your first question, a reducibility fitting your needs is log-lin-reducibility, which is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. If I remember correctly, the membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.

On the applied side, the universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in  Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974). For further background and similar results in that area, see also the recent survey by Holzer and Kutrib (DLT 2010).

EDIT (2017/03/06): Regarding your second question, the accepted answer to the question below cites a paper by Rounds (1973), which constructs a one-way nested stack automaton recognizing SAT. While SAT will not qualify as a "natural" CSL, it might be worth to search the literature for other examples of one-way nested stack automata or indexed grammars.

Context-sensitive grammar for SAT?


What is the complexity of chordalization? A graph $G=(V,E)$ is a chordal graph, if it does not contain an induced
cycle of length at least four. We say a graph $H$ is a chordalization of graph
$G$, if $H$ contains $G$ as a subgraph, and $H$ is chordal.

$Q_1$: Find minimum number of edges whose addition to a given graph makes the graph a chordal graph.

According to this, $Q_1$ is NP-hard.

$Q_2$: Find a chordalization that does not introduce new $K_4$?

What is the complexity of $Q_2$? Is $Q_2$ harder than $Q_1$?

{
Remark: After Florent comment, I changed $Q_1$ from the following:

$Q_1$ in first version of my post: What is the complexity of giving an arbitrary chordalization of input graph?
}

If the graph doesn't already have any K4, then Q2 is the same as asking for whether the graph has treewidth at most two. This is easy to check in linear time: it's true iff every biconnected component is series-parallel.


Ensuring integral maximizer from integral linear program An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is totally unimodular.
Suppose that we have an integral LP, how can we then efficiently find an integral maximizer? After all, the optimum may be achieved by (exponentially) many different maximizers rather than just the integral ones.

Cross-posted from CS.SE where no answers have been posted after two weeks.

Given an integral LP, you can use a LP algorithm to compute in polynomial time

the optimal value of the LP,

a vertex of the feasible region (polytope) of the LP where the optimal value is attained.

Thus, if you know that the polytope is integral (i.e., all the vertices are integral), then you can indeed compute in polynomial time an integral maximizer. In particular, this applies if the constraint matrix is totally unimodular.
However, as noted in the comments by Laakeri, it is in general NP-hard to compute an integral maximizer if you only know that one exists. This follows by reduction from the NP-complete problem of feasibility of ILP:

If you can compute integral maximizers of LPs that have them, you can also determine if a given LP has an integral maximizer:

Using an LP algorithm, compute the optimal value $v$.

Run the integral maximizer finder to compute a point $x$. (If the algorithm crashes, outruns its allotted time, etc., just fix $x$ as some garbage point.)

Check that $x$ is an integral point, it satisfies the inequalities of the LP, and it gives value $v$.

If this checks out, then $x$ is indeed an integral maximizer of the LP. Conversely, if the LP has an integral maximizer, the algorithm finds it by assumption.

An LP has an integral feasible point iff the constant $0$ objective function has an integral maximizer.


Design of exact algorithms for non-local hard problems In the connected dominating set problem (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent to some vertex in $S$. If we drop the connectedness requirement (the usual dominating set problem (DS)), we have exact algorithms that are much faster than the naive brute force method. The trivial algorithm for CDS runs in $\Omega(2^n)$ time and enumerates all the subsets of vertices. To the best of my knowledge, the fastest known exact algorithm for CDS is the one given by Fomin, Grandoni and Kratsch running in $O(1.9407^n)$ time.
It seems both intuitively true, and also generally accepted in the literature, that non-local problems (such as CDS) are harder to solve than local problems (such as DS). The reason seems to be that often exact algorithms are exploiting the local structure of the problem whereas say connectivity is a global property. Another non-local problem is TSP, for which as far as I know, the fastest known algorithm dates back to the sixties and runs in $\Omega(2^n)$ time.
Say for TSP, we do have faster algorithms for special graph classes of course (cubic, bounded-degree, and so on). Also, for many non-local problems on graphs of bounded treewidth we have (I guess possibly even optimal under SETH) algorithms (see the work by Cygan et al). Similarly, I think we can get $O(c^{\sqrt{n}})$ algorithms for non-local problems on planar graphs using a result of Fomin and Thilikos bounding the treewidth of a planar graph, and showing how a tree decomposition of such width can be found in polynomial time. But what about general (undirected) graphs?
It indeed appears that for many non-local problems the best known algorithms are still trivial. For Steiner tree (i.e. find a minimum size subtree of a given graph spanning a given subset of $k$ nodes), we have a $O(1.4143^n)$ time algorithm obtained by combining the $O((2+\epsilon)^kn^{O(1)}$ DP algorithm (for small $k$) with the trivial $O(2^{n-k}n^{O(1)})$ enumeration of Steiner nodes (for large $k$). To the best of my knowledge, finding a polynomial space algorithm faster than $2^n$ is still open.

(1) What other examples of non-local problems besides connected dominating set and Steiner tree do we have such that there is a faster non-trivial exact algorithm for them (on general graphs)?
(2) Is it possible to extract some kind of general algorithmic design techniques from the known fast exact algorithms for non-local problems?

Well, Hamiltonicity was $\Omega(2^n)$ problem till recently, when it was shown that simple k-path can be solved in $O^*(1.657^k)$, which means $O(1.657^n \cdot poly(n))$ for the classical Hamiltonicity.


Dependent eliminator for empty type in intensional Martin-Löf type theory In calculus of inductive constructions you can just say that the empty type is the type with no constructors and it automatically builds the dependent eliminator.
But let's say I'm setting up intensional Martin-Löf type theory with the primitives $0$, $1$, $2$, $\Pi$, $\Sigma$, $\mathrm{Id}$, $W$ and the universes (like in this pdf).
Do I have to make the eliminator for $0$ dependent or can it just be $\mathrm{absurd}_C$ for each fixed type $C$? Does this choice make any difference (e.g. some type is inhabited if the dependent eliminator is allowed and not otherwise)?
Intuitively it doesn't make sense that the eliminator must be dependent as there is nothing to depend on.

$\text{absurd} : (A : \text{U}) \to 0 \to A$ and $\text{elim} : (A : 0 \to \text{U}) \to (x : 0) \to A\,x$ are equivalent. To go right, use $\text{absurd}\,(A\,x)\,x$. To go left, use $\text{elim}\,(\lambda\,x.\,A)\,x$. Also, both types are propositions because of the $0$-s in domains. There's not much reason to assume or use $\text{elim}$ instead of $\text{absurd}$.


Comparison between the maximum clique and maximum biclique problem It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For example, a reduction of the maximum clique problem to the maximum biclique problem.)

Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by R B), here is a paper whose abstract gives some detailed information about the polynomial-time solvability of variants of biclique detection.


A protocol for honest compromise This question did not originate in my research, but I think it's interesting. It is somewhat underspecified. I'd be interested in an example in any particular case.

We have $n$ parties that between them must choose a value $x \in \mathbb{R}$. Each party has a preferred value $p_i$ for $x$, but we must find a compromise. Let's say we want the mean of the preferences.

Now, anybody who has been involved in politics will know that taking the middle way between stated preferences can be gamed by stating a more extreme position than the actual preference, so that the mean lands closer to it. Is there a protocol that lets us find (an approximation to) the mean of the true preferences?

As an analogy, one can take the second-price auction, where everybody is best served by bidding their true valuation.

There's a trivial protocol whose expected value is the correct mean: everybody announces their preference, and one is chosen at random. No player (acting alone) can do better than to announce their true preference. I haven't yet looked at the collusion-resistance of this protocol (I would guess it depends on the exact payoff functions).


Tighter Probability Bounds Let $\mathcal{F}$ be a class of binary functions on a probability space $\Omega$. For $f \in \mathcal{F}$, let $P(f) =\mathbb{E}(f(Z))$ and $P_n(f) = \frac{1}{n} \sum_{i=1}^n f(Z_i)$ where $Z_i$'s are i.i.d. samples from $\Omega$. It is known that

  Theorem 1. If $\mathcal{F}$ has finite VC-dimension $d$,
  $$
\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq \sqrt{\frac{8}{n} \left(\log(\frac{4}{\delta}) + d\log(\frac{ne}{d})\right)}\right) \geq 1 - \delta
$$

The following bound based on the Rademacher complexity of $\mathcal{F}$, denoted $\mathcal{R}_n(\mathcal{F})$, is also known.

  Theorem 2. $$
\mathbb{P}\left(\sup_{f \in \mathcal{F}} |P_n(f) - P(f)| \leq 2\mathcal{R}_n(\mathcal{F}) + \sqrt{\frac{1}{2n} \log (\frac{2}{\delta})}\right) \geq 1- \delta
$$

Are there other bounds on $\sup_{f\in \mathcal{F}}|P_n(f) - P(f)|$ tighter than the ones above?

This is almost a duplicate (see my comment above) but I'll give a quick answer before it (likely) gets closed. The first inequality in the OP has a superfluous $\log(n/d)$, which may be removed via chaining, as discussed here:
Tight VC bound for agnostic learning

Once that log-factor is removed from the VC bound, it becomes optimal up to constants (i.e., essentially unimprovable). See Section 5 in the Anthony-Bartlett book:
http://www.cambridge.org/gb/academic/subjects/computer-science/pattern-recognition-and-machine-learning/neural-network-learning-theoretical-foundations?format=HB&isbn=9780521573535#JEHXi1lP4I6Gl8dg.97

Regarding the optimality of the Rademacher bound, see the discussion and links here concerning Sudakov's inequality:Rademacher complexity beyond the agnostic setting


About the origin of the names "immune" and "simple" I have been wondering for a while about the origin of the names "immune"
and "simple". I also posed the same question to Andrea Sorbi, who in turn
involved a few more colleagues in the discussion.

About "simple" we have a few conjectures. Martin Davis suggests that the name
derives from an analogy with simple groups. Simple groups have no
non-trivial normal subgroups; complements of simple sets have no
infinite r.e. subsets.

Other people (Stephan, Nerode) seem to think that "simple" just refers to
the fact that they are simpler than creative sets, the latter being
considered a useful property of a human mind.

This is Nerode's
account:

"Post originally hoped to get computably enumerable sets with degrees of
unsolvability different from one of his creative sets  by  controlling
the lattice of re subsets of their complements. Simple sets are those
infinite re sets with infinite complements for which the lattice of re
subsets of the complement is as small as possible. So "simple" was
chosen to connote "fewest re subsets of complement", in stark contrast
with "creative set" which connotes "effectively uncountable number of re
subsets of the complement", which informally represents the perpetual
incompleteness of mathematics."

About "immune" we have no clue, however. Apparently, the word was introduced
by Dekker, in an article with Myhill in the fifties. Again this is Nerode's
affectionate opinion:

"As to why "immune", Dekker also introduced "isolated" and "regressive".
Stanley Tennenbaum always said that this was because Jim Dekker lived an
isolated life. He was an engaging homebody. I think that I and Myhill
and Stanley Tennenbaum were his main friends, scientifically and
personally. We all met at U Chicago in about 1952 just after Myhill
proved that all creative sets were recursively isomorphic, still one of
my favorite theorems."

If anybody has better information, I would be extremely grateful if he could
share this bit of knowledge.

I don't know the history, but "immune" always struck me as fairly appropriate terminology. ("Simple" never really did, but I never thought of the analogy with simple groups before - it's nice, even though it's not quite a perfect fit.) The English word immune has two general uses: (1) biological (immune to disease), and (2) more general ("not affected or influenced by something"), and both of these seem to fit with the computability definition. Immune sets are immune (in the non-technical sense) to the effects of (containing infinite) ce sets, in some sense.

It also ties well with "productive", as immune sets are somewhat the opposite of productive sets, and in that context, I think of the use of productive as in "productive cough."


Paper about the upper bound of the number of inequalities to describe the Integer hull of a polyhedron I am interested in the upper bound of the number of inequalities to describe the integer hull of a polyhedron. That is, given an integer programming problem with n inequalities which construct a polyhedron P, we often adding some inequalities to get the integer hull P_I of P. Then what is the maximum number of inequalities needed to describe this P_I? I have known that there are some conclusions on this topic but I don't what they are. I need some paper about it. Please tell me if you know it.

Via Rubin:

There is a sequence of polytopes $\{ P_k\}_k$ each defined by two variables and one constraint (plus two nonnegativity constraints) such that the integer hull of $P_k$ has $k+3$ vertices and $k+3$ facets.

$P_k=\{ (x,y)\in \mathbb{R}^2_+ ~|~f_{2k} x + f_{2k+1}y \le f^2_{2k+1}-1\}$

Here, $f_j$ is the $j$-th Fibonacci number.

This shows that the number of facets of the integer hull $P_I$ cannot be bounded above in terms of the number variables and constraints of $P$.

Schrijver provides a nice collection of these kind of results in his Theory of Linear and Integer Programming.


Truly random number generator: Turing computable? I am seeking a definitive answer to whether or not generation of "truly random" numbers
is Turing computable.  I don't know how to phrase this precisely.
This StackExchange question on "efficient algorithms for random number generation"
comes close to answering my question.
Charles Stewart says in his answer, "it [Martin-Löf randomness] cannot be generated by a machine." Ross Snider says, "any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers." Is there a clear and accepted notion of what constitutes a truly random number generator?
And if so, is it known that it cannot be computed by a Turing Machine?

Perhaps pointing me to the relevant literature would suffice.  Thanks for any help you can provide!

Edit. Thanks to Ian and Aaron for the knowledgeable answers!  I am relatively unschooled in this area, and I am grateful for the assistance. If I may extend the question a bit in this addendum: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

I am joining the discussion fairly late, but I will try to address several questions that were asked earlier.

First, as observed by Aaron Sterling, it is important to first decide what we mean by "truly random" numbers, and especially if we are looking at things from a computational complexity or computability perspective.

Let me argue however that in complexity theory, people are mainly interested in pseudo-randomness, and pseudo-random generators, i.e. functions from strings to strings such that the distribution of the output sequences cannot be told apart from the uniform distribution by some efficient process (where several meanings of efficient can be considered, e.g. polytime computable, polynomial-size circuits etc). It is a beautiful and very active research area, but I think most people would agree that the objects it studies are not truly random, it is enough that they just look random (hence the term "pseudo").

In computability theory, a concensus has emerged to what should be a good notion of "true randomness", and it is indeed the notion of Martin-Löf randomness which prevailed (other ones have been proposed and are interesting to study but do not bare all the nice properties Martin-Löf randomness has). To simplify matters, we will consider randomness for infinite binary sequences (other objects such as functions from strings to strings can easily be encoded by such sequence).

An infinite binary sequence $\alpha$ is Martin-Löf random if no computable process  (even if we allow this process to be computable in triple exponential time or higher) can detect a randomness flaw.

(1) What do we mean by "randomness flaw"? That part is easy: it is a set of measure 0, i.e. a property that almost all sequences do not have (here we talk about Lebesgue measure i.e. the measure where each bit has a $1/2$ probability to be $0$ independently of all the other bits). An example of such a flaw is "having asymptotically 1/3 of zeroes and 2/3 of ones", which violates the law of large numbers. Another example is "for every n, the first 2n bits of $\alpha$ are perfectly distributed (as many zeroes as ones)". In this case the law of large numbers is satified, but not the central limit theorem. Etc etc.
(2) How can a computable process test that a sequence does not belong to a particular set of measure 0? In other words, what sets of measure 0 can be computably described? This is precisely what Martin-Löf tests are about. A Martin-Löf test is a computable procedure which, given an input k, computably (i.e., via a Turing machine with input $k$) generates a sequence of strings $w_{k,0}$, $w_{k,1}$, ... such that the set $U_k$ of infinite sequences starting by one of those $w_{k,i}$ has measure at most $2^{-k}$ (if you like topology, notice that this is an open set in the product topology for the set of infinite binary sequences). Then the set $G=\bigcap_k U_k$ has measure $0$ and is referred to as Martin-Löf nullset. We can now define Martin-Löf randomness by saying that an infinite binary sequence $\alpha$ is Martin-Löf random if it does not belong to any Martin-Löf nullset.

This definition might seem technical but it is widely accepted as being the right one for several reasons:

it is effective enough, i.e. its definition involves computable processes
it is strong enough: any "almost sure" property you may find in a probability theory textbook (law of large numbers, law of iterated logarithm, etc) can be tested by a Martin-Löf test (although this is sometimes hard to prove)
it has been independently proposed by several people using different definitions (in particular the Levin-Chaitin definition using Kolmogorov complexity); and the fact that they all lead to the same concept is a hint that it should be the right notion (a little bit like the notion of computable function, which can be defined via Turing machines, recursive functions, lambda-calculus, etc.)
the mathematical theory behind it is very nice! see the three excellent books An Introduction to Kolmogorov Complexity and Its Applications (Li and Vitanyi), Algorithmic randomness and complexity (Downey and Hirschfeldt) Computability and Randomness (Nies).

What does a Martin-Löf random sequence look like? Well, take a perfectly balanced coin and start flipping it. At each flip, write a 0 for heads and a 1 for tails. Continue until the end of time. That's what a Martin-Löf sequence looks like :-)

Now back to the initial question: is there a computable way to generate a Martin-Löf random sequence? Intuitively the answer should be NO, because if we can use a computable process to generate a sequence $\alpha$, then we can certainly use a computable process to describe the singleton {$\alpha$}, so $\alpha$ is not random. Formally this is done as follows. Suppose a sequence $\alpha$ is computable. Consider the following Martin-Löf test: for all $k$, just output the prefix $a_k$ of $\alpha$ of length $k$, and nothing else. This has measure at most (in fact, exactly) $2^{-k}$, and the intersection of the sets $U_k$ as in the definition is exactly {${\alpha}$}. QED!!

In fact a Martin-Löf random sequence $\alpha$ is incomputable in a much stronger sense: if some oracle computation with oracle $\beta$ (which itself is an infinite binary sequence) can compute $\alpha$, then for all $n$, $n-O(1)$ bits of $\beta$ are needed to compute the first $n$ bits of $\alpha$ (this is in fact a characterization of Martin-Löf randomness, which unfortunately is rarely stated as is in the literature).

Ok, now the "edit" part of Joseph's question: Is it the case that a TM with access to a pure source of randomness (an oracle?), can compute a function that a classical TM cannot?

From a computability perspective, the answer is "yes and no". If you are given access to a random source as an oracle (where the output is presented as an infinite binary sequence), with probability 1 you will get a Martin-Löf random oracle, and as we saw earlier Martin-Löf random implies non-computable, so it suffices to output the oracle itself! Or if you want a function $f: \mathbb{N} \rightarrow \mathbb{N}$, you can consider the function $f$ which for all $n$ tells you how many zeroes there are among the first $n$ bits of your oracle. If the oracle is Martin-Löf random, this function will be non-computable.

But of course you might argue that this is cheating: indeed, for a different oracle we might get a different function, so there is a non-reproducibility problem. Hence another way to understand your question is the following: is there a function $f$ which is non-computable, but which can be "computed with positive probability", in the sense that there is an Turing machine with access to a random oracle which, with positive probability (over the oracle), computes $f$. The answer is no, due to a theorem of Sacks whose proof is quite simple. Actually it has mainly been answered by Robin Kothari: if the probability for the TM to be correct is greater than 1/2, then one can look for all $n$ at all the possible oracle computations with input $n$ and find the output which gets the "majority vote", i.e. which is produced by a set of oracles of measure more than 1/2 (this can be done effectively). The argument even extend to smaller probabilities: suppose the TM outputs $f$ with probability $\epsilon >0$. By Lebesgue's density theorem, there exists a finite string $\sigma$ such that if we fix the first bits of the oracle to be exactly $\sigma$, and then get the other bits at random, then we compute $f$ with probability at least 0.99. By taking such a $\sigma$, we can apply the above argument again.


Regular languages under change of encoding Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$.
Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other encoding (say unary, or, decimal) also form a regular language ?

Formally, is it the case that the language $L' = \{w | w \in 1^*, \exists w' \in L \text{ such that the unary encoding of } w' \text{ is } w \}$ also regular?

What happens when the base is shifted to a lower number? For example can we also say anything about the following language:
$L'' = \{w | w \in \{0,1,2\}^*, \exists w' \in L \text{ such that the ternary encoding of } w' \text{ is } w \}$

The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:

Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.

It's easy to see that $L$ is regular while $L'$ is not even context free.

L'' also isn't regular either, by the link @Sylvain posted in his comment.


Complexity of union (computational geometry) I'm courrently rading "Computational Geometry" from Mark de Berg, Otfried Cheong,
Marc van Kreveld, Mark Overmars and found the following theorem 13.9.

  Let $S$ be a collection of convex polygonal pseudodiscs with n
  edges in total. Then the complexity of their union is at most $2n$.

I'm not really sure what this should mean (this might be a a language barrier). First I thought that this would be the time complexity, but I'm now pretty much unsure about this.

The complexity of a union of objects is the number of pieces in the boundary of the union. In the plane "complexity of boundary" is equivalent (upto a constant factor) to "number of vertices". But in general the boundary complexity is the sum of complexities of all objects needed to describe the boundary (vertices, edges, faces, and so on). It's just that in the plane the number of vertices in the boundary is the same as the number of edges (because the boundary is a set of cycles in this case)


Is testing easier/harder than learning? How is the Property testing  is related to PAC model of learning?

More precisely,

Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$  which receives as input a size parameter $n$ (labeled input $(x_1,f(x_1)), (x_2,f(x_2)),...,(x_n,f(x_n))$), distance parameter $0<\epsilon<1$,  confidence interval $0<\delta<1/2$, and does the following:

-if $f\in \mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ accepts $f$.

-if $f$ is $\epsilon$-far from $\mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ rejects $f$.

Now, I have following two questions:

1) Now, how this tester $\mathcal{A}$ can be used to generate learning algorithm (under PAC learning model) for the concept class $\mathcal{F_n}$, and vice versa. And how does VC-dim of $\mathcal{F_n}$ plays role in the reduction.

2) Can we give some sort of characterization (for example, on the basis of VC-dim) over the concept class for which  testing is easier/harder than  learning?

Pls let me know if I am not able to put the question clearly.

Thanks.

If the learning algorithm is proper (i.e. it always produces a hypothesis from the class $F_n$), then it also gives a testing algorithm -- simply run the learning algorithm, and see whether the hypothesis it produced has error rate $<\epsilon$, which can be done with only $\approx 1/\epsilon^2$ samples. If it does, since the hypothesis is in $F_n$, this is a constructive proof that the function you are testing has distance at most $\epsilon$ from $F_n$. If the algorithm was a PAC learning algorithm for $F_n$, then when $f \in F_n$, it must generate such a hypothesis. So any proper learning algorithm can be converted to a testing algorithm with only an additional $\approx 1/\epsilon^2$ samples at most.

Moreover, if you are only worried about sample complexity and not computational efficiency, then without loss of generality you can always use a proper PAC learning algorithm. Since the sample complexity of learning is $\mathrm{VCDIM}(F_n)/\epsilon^2$, this means you can always test with at most this many samples.

However, generally testing is easier than learning. For example, linear functions in $d$ dimensions require $d$ samples to learn, but only a constant number of samples to test.


Qubits and permutation symmetry To put it straight - are qubits fermions, bosons or else?

For example, the Bell states that are frequently used in quantum computations have different symmetry (00 + 11 is symmetric, 10 - 01 is antisymmetric). Indistinguishable physical particles in a real world are either bosons (symmetric) or fermions (antisymmetric), not both.

Should we take into account permutation symmetry while discussing multiple qubit states?

In general, a state of $n$ qubits is a state of $n$ distingushable particles. Eg.
$|01\rangle$ means that the first particle is in the state $|0\rangle$, and the second is in the state $|1\rangle$.

How can be elementary particles distinguishable? Place two particles in different places. Eg. two electrons are in the positions $x_1$ and $x_2$, respectively. (Or two photons in two consecutive pulses, one in each.)

However, you can make the qubits indistinguishable by imposing a permutation symmetry, i.e. symmetrization and antisymmetrization.

And $n$ photons in the same place gives 'automatically' symmetrized state.