DFA intersection algorithm for special cases I'm interested in efficient algorithms for DFA intersection for special cases. Namely, when the DFAs to intersect obey a certain structure and/or operates on limited alphabet. Is there any source where I can find algorithms such cases?

In order to not make the question too broad, the following structure is of particular interest: all the DFAs to intersect operate in the binary alphabet (0|1), they can also use don't care symbols. Moreover, all the states have only one transition except for at most K special states, which have only two transitions (and these transitions are always 0 or 1, but no don't care). K is an integer, less than 10 for practical purposes. Also, they have a single accepting state. Additionally, it is known that the intersection is ALWAYS a DFA in form of "strip", i.e., no branches as in the following image:

EDIT: Perhaps the description of the constraint on the input DFAs is not very clear. I will try to improve it in this paragraph. You have as input T DFAs. Each of these DFAs operates only on the binary alphabet. Each of them has at most N states. For each DFA, each of its states is one of the following:

1) the accepting state (it is only one and there's no transition from it to any other state)

2) a state with two transitions (0 and 1) to the same target state (the majority of the states is of this kind)

3) a state with two transitions (0 and 1) to different target states (at most K of this kind)

It is guaranteed that there's only one accepting state and that there are at most K states of type (3) in each input DFA. It is also guaranteed that the intersection DFA of all the input DFAs is a "strip" (as described above), of size less than N.

EDIT2: Some additional constraints, as requested by D.W. in the comments:

The input DFAs are DAGs.
The input DFAs are "levelled", following the D.W. definition in the comments. Namely, you can assign different integers to every state in such a way that every transitions goes from an integer u to an integer v, such that u + 1 = v.
The number of accepting states for each input DFA, doesn't exceed K.

Any ideas? Thanks.

Yes, there are some cases of the DFA non emptiness insersection problem that are inside P. My master's thesis is devoted to this question, but unfortunately it is in French. However, most of the results have appeared here in $[2]$.

When the alphabet is unary, then the problem is L-complete when each DFA has at most two final states, and NP-complete otherwise. Most of the other cases are restriction on the transition monoids of the automata. For example, for abelian group transition monoids, the problem is in $\text{NC}^3$ when each DFA has at most one final state, and NP-complete otherwise; for elementary 2-group transition monoids, the problem is $\oplus$L-complete when each DFA has at most two final states, and NP-complete otherwise.

Let me now address your more precise question, which can only be found in $[1]$. Suppose you are given DFAs working over $\{0,1\}$ and shaped as trees, i.e there exists a state $u$ (initial state) such that for each state $v$ there exists a unique path from $u$ to $v$. Then, deciding the intersection non emptiness is:

L-complete for one final state in each DFA,
NL-complete for two final states in each DFA, and
NP-complete for three or more final states in each DFA.

The hardness results still hold even if you "fork" respectively 0, 1 or 2 times (this is your $K$). Now if your DFAs are directed acyclic graphs instead of trees, then the problem is NP-complete even with one final state in each DFA and $K=2$; the reduction is quite straightforward and is from Monotone 1-in-3 3-SAT.

Therefore, no, I don't think there is an efficient algorithm for your problem.

Now, if the number of automata is fixed, you might want to discuss with Michael Wehar who has recently published $[3]$.

EDIT: Since OP edited his question, let me clarify my answer with his new requirements. Consider the NP-complete problem Monotone 1-in-3 3-SAT where you are given a formula in 3-CNF without negation, and where you have to determine whether there is an assignment that makes exactly one variable true in each clause. You can reduce this problem to the non emptiness intersection problem as follows. For example, for the clause $x_2 \lor x_3 \lor x_5$, you build the following automaton:

$\hskip2in$

Note that the automata are trees (and hence DAGs), are levelled, and have three final states. Actually, the three final states coud be merged into a single one, if one is satisfied with DAGs. Moreover, only two states have two (distinct) outgoing transitions.

Michael Blondin. Complexité raffinée du problème d'intersection d'automates, M.Sc. thesis, Université de Montréal, 2012.
Michael Blondin, Andreas Krebs et Pierre McKenzie. The Complexity of Intersecting Finite Automata Having Few Final States, Computational Complexity (CC), 2014.
Michael Wehar. Hardness Results for Intersection Non-Emptiness. ICALP, 2014.


Number of edges in $K_4$-free graphs What can be the upper bound on the number of edges in a graph of $n$ vertices such that the graph does not have $K_4$ as a minor? Is there some relevant paper/book that I can look into it or it would be kind if some one can give intuition or some proof of some kind along with the bound.

I think $K_4$-minor-free graphs have at most $2n - 3$ edges for $n \geq 2$, and this is tight. Here's one way of looking at it.

It is well-known that the $K_4$-minor-free graphs are exactly the graphs of treewidth at most two, see http://en.wikipedia.org/wiki/Forbidden_graph_characterization . Standard theory on treewidth tells us that a graph of treewidth at most 2 is 2-degenerate (see http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29 ), which means that all induced subgraphs have a vertex of degree at most two. So to count the number of edges in a $K_4$-minor-free graph, we can do the following: we find a vertex of degree at most two, and delete it. We remove one vertex, and at most two edges. What we're left with is still $K_4$-minor-free (since minor-freeness is preserved when deleting vertices), so if the graph is not yet empty then we know it is 2-degenerate, and has another vertex of degree at most two. If we keep removing vertices of degree at most two then we delete $n$ vertices until the graph is empty, and for each removed vertex we delete at most two edges. Hence the number of edges is at most $2n$.

Now observe that when removing the second-to-last vertex, there are only two vertices left so there can be only one edge that is removed in that step. Similarly, when we've removed all but one of the vertices then there can be no edges left, so in the last step we don't remove any edges. This shows that the number of edges is at most $2n - 3$ because we save 1 in the second-to-last step, and 2 in the last step.

To see that this is tight, start with a graph on two vertices and one edge. Now repeatedly select two adjacent vertices, and add a new vertex with edges to the selected two. The constructed graph will have treewidth two (since it is a 2-tree, see http://en.wikipedia.org/wiki/K-tree ) and will therefore be $K_4$-minor-free, and the number of edges you build in this way is $2n-3$.


Is Norbert Blum's 2017 proof that $P \ne NP$ correct? Norbert Blum recently posted a 38-page proof that $P \ne NP$. Is it correct?

Also on topic: where else (on the internet) is its correctness being discussed?

Note: the focus of this question text has changed over time. See question comments for details.

As noted here before, Tardos' example clearly refutes the proof; it gives a monotone function, which agrees with CLIQUE on T0 and T1, but which lies in P. This would not be possible if the proof were correct, since the proof applies to this case too. However, can we pinpoint the mistake? Here is, from a post on the lipton's blog, what seems to be the place where the proof fails:

The single error is one subtle point in the proof of Theorem 6, namely in Step 1, on page 31 (and also 33, where the dual case is discussed) - a seemingly obvious claim that $C'_g$ contains all the corresponding clauses contained in $CNF'(g)$ etc, seems wrong.

To explain this in more detail, we need to go into the proof and approximation method of Berg and Ulfberg, which restates the Razborov's original proof of the exponential monotone complexity for CLIQUE in terms of DNF/CNF switches. This is how I see it:

To every node/gate $g$ of a logic circuit $\beta$ (containing binary OR/AND gates only), a conjunctive normal form $CNF(g)$, a disjunctive normal form $DNF(g)$, and approximators $C^k_g$ and $D^r_g$ are attached. $CNF$ and $DNF$ are simply the corresponding disjunctive and conjunctive normal forms of the gate output. $D^r_g$ and $C^k_g$ are also disjunctive and conjunctive forms, but of some other functions, "approximating" the gate output. They are however required to have bounded number of variables in each monomial for $D^r_g$ (less than a constant r) and in each clause for $C^k_g$ (less than a constant k).

There is notion of an "error" introduced with this approximation. How is this error computed? We are only interested in some set T0 of inputs on which our total function takes value 0, and T1 of inputs on which our total function takes value 1 (a "promise") . Now at each gate, we look only at those inputs from T0 and T1, which are correctly computed (by both $DNF(g)$ and $CNF(g)$, which represent the same function - output of gate $g$ in $\beta$) at gate output, and look how many mistakes/errors are for $C^k_g$ and $D^r_g$, compared to that. If the gate is a conjunction, then the gate output might compute more inputs from T0 correctly (but the correctly computed inputs from T1 are possibly decreased). For $C^k_g$, which is defined as a simple conjunction, there are no new errors however on all of these inputs. Now, $D^r_g$ is defined as a CNF/DNF switch of $C^k_g$, so there might be a number of new errors on T0, coming from this switch. On T1 also, there are no new errors on $C^k_g$ - each error has to be present on either of gate inputs, and similarly on $D^r_g$, switch does not introduce new errors on T1. The analysis for OR gate is dual.

So the number of errors for the final approximators is bounded by number of gates in $\beta$, times the maximal possible number of errors introduced by a CNF/DNF switch (for T0), or by a DNF/CNF switch (for T1). But the total number of errors has to be "large" in at least one case (T0 or T1), since this is a property of positive conjunctive normal forms with clauses bounded by $k$, which was the key insight of Razborov's original proof (Lemma 5 in the Blum's paper).

So what did Blum do in order to deal with negations (which are pushed to the level of inputs, so the circuit $\beta$ is still containing only binary OR/AND gates)?

His idea is to preform CNF/DNF and DNF/CNF switches restrictively, only when all variables are positive. Then the switches would work EXACTLY like in the case of Berg and Ulfberg, introducing the same amount of errors. It turns out this is the only case which needs to be considered.

So, he follows along the lines of Berg and Ulfberg, with a few distinctions. Instead of attaching $CNF(g)$, $DNF(g)$, $C^k_g$ and $D^r_g$ to each gate $g$ of circuit $\beta$, he attaches his modifications, $CNF'(g)$, $DNF'(g)$, ${C'}^k_g$ and ${D'}^r_g$, i.e. the "reduced" disjunctive and conjunctive normal forms, which he defined to differ from $CNF(g)$ and $DNF(g)$ by "absorption rule", removing negated variables from all mixed monomials/clauses (he also uses for this purpose operation denoted by R, removing some monomials/clauses entirely; as we discussed before, his somewhat informal definition of R is not really the problem, R can be made precise so it is applied at each gate but what is removed depends not only on previous two inputs but on the whole of the circuit leading up to that gate), and their approximators ${C'}^r_g$ and ${D'}^r_g$, that he also introduced.

He concludes, in Theorem 5, that for a monotone function, reduced $CNF'$ and $DNF'$ will really compute 1 and 0 on sets T1 and T0, at root node $g_0$ (whose output is the output of the whole function in $\beta$). This theorem is, I believe, correct.

Now comes the counting of errors. I believe the errors at each node are meant to be computed by comparing reduced $CNF'(g)$ and $DNF'(g)$ (which are now possibly two different functions), to ${C'}^r_g$ and ${D'}^k_g$ as he defined them. The definitions of approximators parrot definitions of $CNF'$ and $DNF'$ (Step 1) when mixing variables with negated ones, but when he deals with positive variables, he uses the switch like in the case of Berg and Ulfberg (Step 2). And indeed, in Step 2 he will introduce the same number of possible errors like before (it is the same switch, and all the involved variables are positive).

But the proof is wrong in Step 1. I think Blum is confusing $\gamma_1$, $\gamma_2$, which really come, as he defined them, from previous approximators (for gates $h_1$, $h_2$), with positive parts of $CNF'_\beta(h_1)$ and $CNF'_\beta(h_2)$. There is a difference, and hence, the statement "$C_g'$ contains still all clauses contained in $CNF'_\beta(g)$ before the approximation of the gate g which use a clause in $\gamma_1'$ or $\gamma_2'$" seems to be wrong in general.


Set data structure for efficient repeated insertions I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)).  By "space-efficient" I mean, ideally, $n + o(n)$ words to store $n$ elements.

Being a set is an important part of the question: if each element is added $\log n$ times the space used can't be $n\log n$.

The structure should also support listing its elements (reasonable efficiently); any sane structure should have no trouble here.  (Fast membership queries are a plus.)

I think Raman and Rao's "Succinct Dynamic Dictionaries and Trees"  meets the bounds you specify. From the abstract:

  We first give a representation of a set $S \subseteq U =
\{0, \dots , m − 1\}, |S| = n$ that supports membership queries in $O(1)$ worst
  case time and insertions into/deletions from $S$ in $O(1)$ expected amortised time. The representation uses $B + o(B)$ bits, where $B = \lceil lg \binom{m}{n} \rceil$ is the information-theoretic minimum space to represent $S$.


Find negative cycle with vertex constraints Given a graph with weighted edges, how can we find a negative cycle that contains at least one vertex in a given vertex set $\{V_1, V_2, \ldots, V_k\}$? Thanks.

If you don't require the cycle to be simple, then break the (directed) graph into its strongly connected components, and for each component containing one of the given vertices $V_i$, check whether the component contains a negative cycle.  If no component does, there is no negative cycle containing any $V_i$.  But if some component does, you can find a (non-simple) negative cycle containing $V_i$ by taking many copies of the negative cycle, and adding to that paths to and from some vertex in the cycle to $V_i$.  (The total time to find an implicit representation of the desired cycle will be the same as the time to find a negative cycle in a directed graph, e.g. $O(nm)$, if I recall.)

If you do require the cycle to be simple, then the problem becomes NP-complete, even if only a single vertex $V_1$ is given.  (You can reduce Hamiltonian Path to the problem: to find a Hamiltonian path from a given source $S$ to a given sink $T$ in a given graph $G$, give the existing edges weight -1, then add an artificial vertex $V_1$ with two edges of cost $N/2-0.01$ each, one from $V_1$ to $S$ and one from $T$ to $V_1$.)

If you allow the cycle to repeat vertices but not edges, I believe it is still NP-complete (by a similar reduction, but splitting each vertex $v$ into a directed edge $(v,v')$ in a standard way).


Efficient algorithm for a particular graph closure property In the context of an unusual compiler problem, I have a graph in which the vertices are variables, and the edges correspond to whether the instruction set has an instruction that copies the source vertex to the target vertex.  The instruction set also has the unusual property that the instructions may destroy (overwrite with non-predictable values) the contents of some of the variables.  Hence the edges are labeled with sets:  subsets of the (fixed) set of all variables that are destroyed by the instruction.

So for example, I might have instructions like the following:

a -> b, clobber set = {d}
b -> c, clobber set = {}
a -> c, clobber set = {d,f}

Note that there is a direct path from a -> c, but that there is also an indirect path from a -> b -> c, where the union of the clobber sets is {d}, i.e., a strict subset of the clobber set from the direct path, namely {d,f}.  Hence the path a -> b -> c should be preferred as it has a lesser effect on the other variables.

Consider the following variation on the above example:

a -> b, clobber set = {e}
b -> c, clobber set = {}
a -> c, clobber set = {d,f}

By similar reasoning, we have two paths from a -> c:  the direct one, which clobbers {d,f} and the indirect one a -> b -> c which clobbers {e}.  Given that {d,f} and {e} are incomparable subsets of the variable set, we would like to retain information about both of these paths.

So the problem is as follows:  given such a directed graph with edges labeled with sets, compute all "minimal" paths through the graph with respect to the clobber sets.  For the first example, we should return a -> b: {d}, b -> c: {}, a -> c: {d}.  For the second example, we should return a -> b: {e}, b -> c: {}, a -> c: {d,f}, a -> c: {e} (where this last fact was derived from the other edges).

The problem has some flavor of a shortest-paths problem, but given the weaker partial ordering rather than the stricter total ordering on the edge labels, the existing algorithms are inapplicable.

References to literature would also be appreciated.

I suggest you use a fixpoint algorithm, using a worklist implementation.  I'll start by providing an intuitive, English-language description of an algorithm for this problem; then a more formal presentation.

Intuitive algorithm. Basically, we'll apply the following closure rules to the graph as many times as possible, until they don't produce anything new:

If there is an edge $u\to v$ with clobber set $S$ and an edge $v\to w$ with clobber set $T$, then add an edge $u\to w$ with clobber set $S\cup T$.
If there is an edge $u \to v$ with clobber set $S$ and an edge $u \to v$ with clobber set $T$, where $S \subset T$, then remove the edge with clobber set $T$.

Intuitively, we'd like to keep applying these in all possible ways until the graph doesn't get any bigger; then you're done.  Note that I'm treating the graph as a multigraph, so there can be multiple edges between any pair of vertices.

In practice, you need to implement this carefully (you don't want to add an edge that would be immediately removed by the other closure rule).  So, here is an algorithm that applies the above idea, in a reasonable way:

Initially, mark all of the edges of the graph.
While there exists at least one marked edge:

a. Pick any marked edge; suppose it is $u \to v$ with clobber set $S$.  Remove the mark on this edge.

b. For each edge $v\to w$ with clobber set $T$, call $\text{MaybeAddEdge}(u,w,S\cup T)$.

Here the subroutine $\text{MaybeAddEdge}(u,v,S)$ is defined to do the following steps:

For each edge $u \to v$ with clobber set $T$:

a. If $T \subseteq S$, return immediately (without adding any edges).

b. If $S \subset T$, remove the edge with clobber set $T$.
Add an edge $u \to v$ with clobber set $S$, and mark it.

At the end of execution, after we've finished applying the closure rules, the set of clobber sets on all of the edges from $u$ to $v$ gives the set of minimal clobber sets for all paths from $u$ to $v$.  This is effectively a worklist/fixpoint algorithm, and it follows pretty directly from the problem statement.

If you prefer a more formal treatment of this problem, see below.

Notation. Let $V$ denote the set of variables.  Define a partial order $\mathcal{L}$ as follows: Consider the pre-order $(2^{2^V},\le)$, where an element $\ell \in 2^{2^V}$ is a set of clobber sets, and we define $\ell \le \ell'$ iff for every clobber set $S \in \ell$, there exists a clobber set $S' \in \ell'$ such that $S' \subseteq S$.  Now we can define the equivalence relation $\equiv$ by $\ell \equiv \ell'$ iff $\ell \le \ell'$ and $\ell' \le \ell$.  Modding out by $\equiv$ yields a partial order $(\mathcal{L},\le) = (2^{2^V},\le)/\equiv$.  In other words: every set $\ell \in 2^{2^V}$ of clobber sets is equivalent to one where there is no pair of sets $S,S' \in \ell$ such that $S \subset S'$ and $S\ne S'$ (if there is such a pair of sets, we can remove $S'$ from $\ell$ and get another equivalent set), so we let $\mathcal{L}$ denote the set of elements $\ell$ that are in this canonical form.

As it happens, $\mathcal{L}$ is a meet semi-lattice with a meet operation $\wedge$.  In particular, the join operation is defined by $\ell \vee \ell' \equiv \ell \cup \ell'$.    Let $\bot = \{2^V\}$ denote the bottom element in this lattice and $\top = \{\emptyset\}$ denote the top element.  Of course, if $S$ is a clobber set (i.e., $S \subseteq V$), then $\{S\}$ is a lattice element of $\mathcal{L}$ (corresponding to the single clobber set $S$).

Notice that a lattice element $\ell \in \mathcal{L}$ corresponds to a set of minimal clobber sets.  Thus, the lattice will be helpful for recording this kind of information as the algorithm progresses.

Define the binary operation $\circ$ by $\ell \circ \ell' \equiv \{S \cup S : S \in \ell, S' \in \ell'\}$.  Conceptually, this is going to represent the effect of concatenating two paths (where $\ell$ is the set of minimal clobber sets for some path $u\to v$ and $\ell'$ is the set for some path $v \to w$).

Approach.  We are going to build a 2-dimensional table $T[\cdot,\cdot]$.  At any point in the algorithm, for each pair of variables $u,v \in V$, $T[u,v]$ will hold an element of $\mathcal{L}$ that denotes an over-approximation of the desired set of minimal clobber sets for all paths from $u$ to $v$.

If $u,v \in V$ are variables, at the end of the algorithm $T[u,v]$ will contain the set of all minimal clobber sets for all paths from $u$ to $v$.  We'll find a least fixpoint for $T[\cdot,\cdot]$, subject to the following condition:

For all vertices $u$ and all edges $v\to w$ (with clobber set $S$), $T[u,v] \circ \{S\} \le T[u,w]$.
For all vertices $u$, $T[u,u] = \top$.

To find the least fixpoint, we'll use a standard worklist approach.

Algorithm. Let $W$ denote a set data structure that can hold pairs of vertices.  Then the algorithm is as follows:

Initialize $T[u,v] \gets \{S\}$ for each edge $u\to v$ with clobber set $S$ in the graph, $T[u,u] \gets \top$ for each vertex $v \in V$, and otherwise $T[u,v] \gets \bot$.  Initialize $W$ to contain the set of pairs $(u,v)$ such that there is an edge $u\to v$ in the graph together with the set of pairs $(u,u)$ such that $u$ is a vertex in the graph.
While $W \ne \emptyset$, do:

a. Pop an arbitrary vertex-pair $(u,v)$ from $W$.

b. For all edges $v \to w$ (with clobber set $S$) out of $v$, do:

Let $o \gets T[u,w]$. Set $T[u,w] \gets T[u,w] \vee (T[u,v] \circ \{S\})$.  If $o \le T[u,w]$, insert $(u,w)$ into $W$.

The final value of $T[\cdot,\cdot]$ will have the desired form (it is a minimal fixpoint subject to all of the conditions above), and thus will be a valid solution to your problem.  Each $T[u,v]$ contains the set of minimal clobber sets, taken over all paths from $u$ to $v$.

Notice that the above algorithm does not specify the order in which you pull items out of the worklist.  Good scheduling algorithms can improve the performance of this scheme.  One standard heuristic is to use reverse post-order (derived from a DFS on the graph) to prioritize which elements to pull out of the worklist.

Also note that the running time of this algorithm could be exponential, if your graph is unfortunate.  This is unavoidable: there might be exponentially many clobber sets, so the output size might be exponential in the size of the input in the worst case.


What is the computational complexity of sin and cos for floating point inputs? What is the computational complexity of the problem

INPUT: $\;\;\;$ integers $x$ and $y \:$ (both in binary)

OUTPUT:

rational approximations to $\: \sin\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right) \:$ and $\: \cos\hspace{-0.03 in}\left(x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y}\hspace{-0.02 in}\right)$

whose absolute errors are each less than $1/\hspace{-0.04 in}\left(2^{\hspace{.02 in}\operatorname{length}(x)}\hspace{-0.05 in}\right)$

?

One could just expand $\: x\hspace{-0.04 in}\cdot \hspace{-0.04 in}2^{\hspace{.02 in}y} \:$, $\:$ but that would use at least $\:\left|\hspace{.03 in}y\right|\:$ bits of space.

(I believe most work on the complexity of such functions

only considers their restrictions to compact intervals.)

$\def\tc{\mathrm{TC}^0}\DeclareMathOperator\len{len}$Since there were no other takers, let me expand the comments above.
The fundamental fact here is that approximations of basic arithmetic operations, and trigonometric and cyclometric functions like $\sin x$, $\cos x$, $\arctan x$, are computable in uniform $\tc$ (and therefore in logarithmic space) for fixed-point rational inputs. See e.g. Reif, Reif and Tate, Maciel and Thérien for the basic arguments, however, the most crucial result for the uniform version is the proof that integer division and iterated multiplication are in uniform $\tc$ by Hesse, Allender, and Barrington. This is optimal in that all such functions (except addition and subtraction) are $\tc$-complete.
(These results are typically stated for approximation of functions on a bounded domain, but they apply to arbitrary fixed-point inputs all the same, the point being that as long as there is only a linear number of bits before the binary point, we can reduce the input modulo $2\pi$ by just computing an approximation of $2\pi$ with a sufficent accuracy, followed by a division.)
This has several consequences.
First, $\sin(x2^y)$ and $\cos(x2^y)$ can also be approximated in uniform $\tc$ when $y$ is negative, by converting the input to fixed-point notation up to the desired accuracy. Thus, from now on I will only consider the case with $y\ge0$. We can as well also assume $x\ge0$, as this only affects the sign of sin.
Second, the problem is not really about trigonometric functions, as all the complexity is in reducing the input to a bounded domain. More precisely, we have:

Proposition 1: The following search problems are equivalent up to uniform $\tc$ (and a fortiori log-space) bounded-query Turing reductions:

Given $x,y$, approximate $\sin(x2^y)$ and $\cos(x2^y)$ to $\len(x)$ bits of accuracy.

Given $x,y$, approximate $\sin(x2^y)$ to $\len(x)$ bits of accuracy.

Given $x,y$, approximate $x2^y\bmod 2\pi$ to $\len(x)$ bits of accuracy.

Given $y$ and unary $n$, approximate $2^y\bmod \pi$ to $n$ bits of accuracy.

Here, approximation of $z\bmod2\pi$ is defined so that when $z$ is very close to an integer multiple of $2\pi$, numbers close to $0$ and close to $2\pi$ are both considered valid outputs.
Proof: For $1\le2$, use the identity $\cos z=1-2\sin^2(z/2)$. For $1\le3$, $\sin$ and $\cos$ are $2\pi$-periodic, and computable on $[0,2\pi]$ in $\tc$. For $3\le1$, we can compute $z\bmod2\pi$ from $u=\cos z$ and $v=\sin z$ in $\tc$ using $\arctan(v/u)$ and a little fiddling with quadrants. For $3\le4$, compute $2^y\bmod2\pi$ to $2\len(x)+O(1)$ bits of accuracy, and use $x2^y\bmod2\pi=x(2^y\bmod2\pi)\bmod2\pi$, which holds as $x$ is an integer. QED
Curiously, the argument above gives a reduction of $\cos(x2^y)$ to $\sin(x2^y)$—or actually to $|\sin(x2^y)|$—and conversely we can reduce $|\sin(x2^y)|$ to $\cos(x2^y)$ using the identity $\sin z=\pm\sqrt{1-\cos^2z}$, but I don’t know how to reduce $\sin(x2^y)$ itself to $\cos(x2^y)$.
Third, exponentially scaled uniform $\tc$ circuits can be evaluated with $O(1)$ alternations of existential and universal nondeterminism, and counting. That is,

Proposition 2: The problems from Proposition 1 are computable in the counting hierarchy FCH, and therefore in polynomial space.

(Notice that the trivial algorithm that expands $x2^y$ in full followed by a computation of $\sin,\cos$ only gives an exponential-time upper bound, so this is an improvement.)
The level of CH the problem lands in corresponds to the depth of the uniform $\tc$ circuits, up to small differences depending on the exact definitions of the levels and the circuit model. The recent paper by Allender, Balaji, and Datta tries to optimize the level for some of the basic ingredients (division, iterated multiplication). They do not mention trigonometric functions, so this would need further work, however it is a safe guess that the argument should give something in the vicinity of the 3rd–5th level of CH.


New algorithm for Discrete log and its implications for Quantum computing A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.
http://arxiv.org/abs/1306.4244

If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for the discrete logarithm problem? Does this have any implication for quantum complexity theory?

Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$.  The latter is the much more common setting that people talk about, both for cryptography and for Shor's algorithm, and the new algorithm doesn't threaten the quantum speedup there.  On the other hand, yes, unless I'm mistaken it does make the speedup much smaller in the $Z_{p^k}$ case.


Good text on introduction to circuit complexity I would like to ask suggestions for good texts which introduce circuit complexity. Any pointers to recent advances and open problems in this field would also be helpful.

To start off, there is of course Arora and Barak's book Computational Complexity: A Modern Approach. From there, parts 3 and 4 of Jukna's book Boolean Function Complexity: Advances and Frontiers make excellent reading material. Also, Ryan Williams teaches a nice course on circuit complexity whose course notes might hopefully be put up online :)


Compression algorithms for low-complexity strings? Let $s$ denote a string over a finite alphabet, $n_s = |s|$ be the length of $s$, and $n_s^{*}$ denote the minimum description size of $s$ under a given computational model (TM, CFG, etc.). Are there compression algorithms that, when restricted to input $s$ where $n_s / n_s^*$ is large, achieve provably tighter approximations than algorithms with unrestricted input?

In other words, can a compression algorithm specifically tailored for low complexity inputs outperform the best general input algorithm on inputs of low complexity?

Admittedly, the question isn't completely precise, but I'm hoping to find results of roughly the same flavor.

Edit: See domotorp's answer below for a proof of the impossibility of a large class of low-complexity compression algorithms under the TM model. Note that this result does not bar the possibility of compression algorithms where the function $A$ (see the answer for context) is non-computable. For example, setting $A(|x|) = 100*BB^{-1}(|x|)$ where $BB^{-1}$ is the inverse busy beaver function, could make for a useful compression algorithm and is not covered by the proof.

No, at least not in the TM model, i.e., for Kolmogorov complexity. Given $g(x) \leq f(x) \leq |x|$ for all $x$ where $g$ is monotonic and unbounded and $f$ is recursive, it is not possible to enumerate an infinite subset of $\{ x : K(x) > f(x)\}$.

Suppose for the sake of contradiction there exists a recursive function $h$, the low-complexity compression algorithm, which on input $x$ outputs a TM that reproduces $x$ and has the following additional property: Let $A:\mathbb{N} \rightarrow \mathbb{N}$ and $B:\mathbb{N} \rightarrow \mathbb{N}$ be given such that both are recursive, $A(|x|) \leq B(|x|) \leq |x|$ for all $x$, and $A$ is unbounded. Then $\forall x, K(x) \leq A(|x|) \implies |h(x)| \leq B(|x|)$.

Now choose $f(x) = A(|x|)$. We wish to enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$. Note that there are infinite $x$ such that $K(x) > B(|x|)$ because $B(|x|) \leq |x|$. For any such $x$, $|h(x)| \geq K(x)$ by the definition of $K$ so $|h(x)| > B(|x|)$. Then for a generic string $x$, $|h(x)| > B(|x|) \implies K(x) > A(|x|)$ and we can enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$, a contradiction.


Which are the best universities for a DPhil/PhD in proof theory and automated reasoning? I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in automated theorem proving and mainly the theory behind these areas (I don't like implementation that much). Which universities are specialized in these fields?
Thanks in advance!

I'm aware of at least two perfect places.

Paris and suburbs. You might want to check websites of David Baelde/Gilles Dowek (ENS Paris-Saclay), Delia Kesner (IRIF), Dale Miller (INRIA Saclay).

Vienna. There is a strong group of Agata Ciabatoni and of Roman Kuznets.

You also might check the list of the accepted papers for LICS/CSL/MFCS/FOSSACS/ESOP/JELIA and see the authors of the papers that seem to be related to proof theory.


Algorithms and structural complexity theory Many important results in computational complexity theory, and in particular "structural" complexity theory, have the interesting property that they can be understood as fundamentally following (as I see it...) from algorithmic results giving an efficient algorithm or communication protocol for some problem. These include the following:

IP = PSPACE follows from a space-efficient recursive algorithm simulating interactive protocols, and an efficient interactive protocol for evaluating totally quantified boolean formulae. In fact any complexity class equality A=B can be seen as following from two efficient algorithms (an algorithm for problems in A which is efficient with respect to B, and vice versa).

Proving NP-completeness of some problem is just finding an efficient algorithm to reduce an NP-complete problem to it.

The (arguably!) crucial ingredient in the Time Hierarchy Theorem is an efficient universal simulation of Turing machines.

The recent result of Ryan Williams that ACC $\not \supset$ NEXP is based on an efficient algorithm to solve circuit satisfiability for ACC circuits.

The PCP Theorem is that efficient gap amplification is possible for constraint satisfaction problems.

etc., etc.

My question (which is possibly hopelessly vague!) is as follows: Are there any important results in structural complexity theory (as distinct from "meta-results" like the relativisation barrier) which are not known to have a natural interpretation in terms of efficient algorithms (or communication protocols)?

For many lower bounds in algebraic complexity, I do not know of a natural interpretation in terms of efficient algorithms. For example:

the partial derivatives technique of Nisan and Wigderson
the rank-of-Hessian technique of Mignon and Ressayre (giving the currently best known lower bound on permanent versus determinant)
the degree bound of Strassen (and Baur-Strassen)
the connected components technique of Ben-Or.

In all the above results, they really seem to be using a property of the functions involved, where that property itself seems unrelated to the existence of any particular algorithm (let alone an effective one).

For non-algebraic results, here are a couple of thoughts:

The standard counting argument for the $n \log n$ sorting lower bound does not appear to have an interpretation in terms of efficient algorithms. However, there is an adversarial version of this lower bound [1], in which there is an algorithm which, given any decision tree that uses too few comparisons, efficiently constructs a list that the decision tree sorts incorrectly. But the adversarial version, while not difficult, is significantly more difficult than the counting proof. (Note that this is quite a bit stronger than what one gets by applying the adversary lower bound technique, e.g. as in these notes, since in [1] the adversary itself is efficient.)
I think I've changed my mind about PARITY not in $AC^0$ (even the original proof, let alone the Razborov-Smolensky proof, as pointed out by @RobinKothari). Although the Switching Lemma can be viewed as a randomized (or deterministic) algorithm that lets you swap two rows of a circuit without a big blow-up in size, I think this really has a different flavor than many results in complexity, and specifically the ones you cite. For example, Williams's proof that $ACC \neq NEXP$ is based crucially on the existence of a good algorithm for a particular problem. In contrast, if one could prove something like the Switching Lemma nonconstructively, it would be just as good for proving PARITY not in $AC^0$.

Because of these last two examples - especially sorting, where the standard proof is nonconstructive - it seems to me that the question may not just be about natural interpretations in terms of efficient algorithms, but also somehow about the constructiveness / effectiveness of the proofs of various complexity results (depending on what the OP had in mind). That is, the standard sorting lower bound is not constructive or algorithmic, but there is a constructive, algorithmic proof of the same result.

[1] Atallah, M. J. and Kosaraju, S. R. An adversary-based lower bound for sorting. Inform. Proc. Lett. 13(2):55-57, 1981.


Parametricity of Linear Logic Are we able to prove a free parametricity theorems about functions like $f : \forall A . [A] ⊸ [A]$?
It is supposed to state that $f$ takes a list and always returns a permutation of it.

Another example: prove that function $f : \forall A . (A ⊸ (A, A)) ⊸ [A] ⊸ [A]$ will always return a permuted list with exactly one element copied.

Various people are interested in proving this sort of thing. Neel Krishnaswami mentioned this particular theorem here. I’ve also seen Frank Pfenning give some cool examples for ordered logics. For example, if you have $A, x : [A], y : [A] \vdash e : [A]$, then in an ordered type system, $e$ must append the lists $x$ and $y$.

The short answer is that yes, we can prove your first example. In the context of lambda calculi, a logical relations-based approach is described in this paper. They would prove your theorem in two steps:

Define a relational interpretation of types and use it to prove a conventional free theorem completely ignoring linearity i.e. essentially using the same reasoning you see in, for example, “Theorems for Free!”. Given $\vdash f : \forall A . [A] \multimap [A]$, the usual free theorem tells us that $f$ returns a list which contains only elements that were present in the list it was given. Given a list of distinct free linear variables $x_1 \ldots x_n$, we deduce that $f [x_1, ..., x_n]$ evaluates to some list $[y_1, ..., y_m]$ where $\{y_1, \ldots, y_m\} \subseteq \{x_1, ..., x_n\}$.
Notice that free linear variables must be preserved under evaluation. This lets us take advantage of linearity. If $[y_1, \ldots, y_m]$ were not a permutation of $[x_1, ..., x_n]$, then it would imply that some $x_i$ were lost or duplicated during evaluation, which cannot happen.

But, these sorts of theorems get more interesting when we look at a language with effects and our ability to prove them for such languages is sadly limited. For example, consider the isomorphism $\tau \cong \forall A . (\tau \to A) \to A$ from System F. In a call-by-value setting, this isomorphism breaks when we add non-termination. We should be able to recover a similar isomorphism, though, with linear types: $\tau \cong \forall A . (\tau \to A) \multimap A$. Unfortunately, we do not have operational logical relations that can prove this.

That said, there are also syntactic methods that can prove both this isomorphism and your theorem. This seems to be a particularly useful approach in a linear setting, and is much less of a burden than setting up a logical relation for proving simple theorems.

Edit: Since you asked, here’s an example of a syntactic proof of a free theorem for the type $\forall A . (A \otimes A) \multimap A$ in a setting with a term $\bot$ that loops forever and is well-typed under any context at any type. The idea is to find a set of canonical terms of a type and use that to determine what the possible return values for a function are. We start with a soundness theorem for well-typed terms.

  Theorem (Canonicity). If $\Delta; \Gamma \vdash e : \tau$ then either

  $e \approx v$, which is a value such that $\Delta; \Gamma \vdash v : \tau$.
  $e \approx n$, a term which is stuck because it is trying to use a free variable in $\Gamma$, and $\Delta; \Gamma \vdash n : \tau$ OR
  $e \approx \bot$

Here, $\approx$ is your favorite notion of equivalence for the language and $\Delta$ is an environment containing free type variables. I will consider free variables $x$ to be values. For simple languages, a straightforward progress & preservation argument can be made to justify this theorem.

Now, given a value $\vdash f : \forall A . (A \otimes A) \multimap A$, we know that $f \approx \lambda x . e$ where $A; x : (A \otimes A) \vdash e : A$. From the type of e, we have a couple possible cases:

$e$ is equivalent to a pair $A; x : (A \otimes A) \vdash (v_1, v_2) : A$. This case is impossible since $v_1$ and $v_2$ must be values of type $A$, which is a free type variable. There are no such values because there are no variables in the context of type $A$.
$e$ is equivalent to a term which tries to use the free variable $x$.
$e$ diverges. This case gives us one possible value for $f$: $\lambda x . \bot$.

Since the second case is the only one left, we assume $e \approx\ \mathrm{let} (x_1, x_2) = x\ \mathrm{in}\ e’$ where $A; x_1 : A, x_2 : A \vdash e’ : A$. Thus far in the proof, we have established that $f \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ e’$. Finally, we apply our canonicity theorem one more time and find that $e’$ must diverge: the only values of type $A$ are variables but we have two variables in the context, so it cannot be the case that $e’ \approx x_i$.

Therefore, we have that the only inhabitant of $\forall A . (A \otimes A) \multimap A$ is $\lambda x . \bot \approx \lambda x . \mathrm{let }\ (x_1, x_2) = x\ \mathrm{ in }\ \bot$.

You asked for a reference for this sort of proof, but I’m not sure of a good one. This kind of reasoning is well-known in certain circles and goes back perhaps as far as Gentzen. I'm told that it is reminiscent of focused proof search for sequent calculus, but I don't know exactly what the connection is.

That said, I’m not aware of any modern published work that explains this relatively simple method well. Admittedly, it is a bit limited in its applicability to simpler languages. On the other hand, I think it has been overshadowed by “Theorems for Free!” et al and as a result even many senior researchers immediately think of logical relations when they hear the phrase “free theorem”, unaware that techniques like this can be a simpler alternative approach to such proofs (especially in the context of linear type systems).

As for your second example, I don’t think the free theorem you want actually holds. I could for example, instantiate $A$ with the integer type and then pass in a function that returns integers which are not in the list I give to $f$. Perhaps $\forall A. (\forall B. B \multimap (B, B)) \multimap [A] \multimap [A]$ is closer to the type you had in mind. But even then, no function of type $\forall B. B \multimap (B, B)$ exists since it would have to duplicate its input.


What are recent advances in relational databases? I'm wondering what are recent advances in relational database theory and related domains?

I'm interested in new approaches, query languages (alternatives to SQL and/or extensions to it), products (proprietary and open source, though I'm much more interested in open source) and research projects developed in last years.

In db query area arguably Provenance Semiring enjoyed the most attention recently. The "provenance" adjective is just marketing connecting it to a large body of research. Nevertheless the idea that one may have much more elegant mathematical foundation for database query languages is compelling. My personal view is that semiring perspective (which works wonders in formal language theory) has to be complemented with Relational Lattice.

Here is another view of what happened in the last decade. (The speaker holds a record of continued PODS admittance:).

On less theoretical note lets mention Dedalus, and plenty of Tutorial D enthusiasts; both, however, are hardly the recent ideas.


Max-cut via linear programming or sdp I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is the best ratio achieved via this approach. Please mention the formulation along with the integrality gap. Any other information/comments are invited. My primary interest includes to know about the alternate ways that lead to 0.8 approximation for max-cut or near to it (preferably via primal dual scheme).

Did you try to look this up? Max Cut might be the most well studies problem out there, with tons of information on it on the web.

The survey by Poljak from '95 has a lot on different LP relaxations of Max Cut and the relationships between them. He considers special cases in which the relaxations are integral or almost integral. There are numerous other bounds on Max Cut, as well as non-polyhedral relaxations. This survey is very old, but all known LPs for Max Cut have been known to be dead ends for many years: every known LP relaxation of Max Cut, including the ones mentioned by Poljak, has integrality gap 2. So they are no better starting point than the trivial randomized or greedy algorithms. LPs for Max Cut have been out of fashion at least since Goemans and Williamson's SDP paper.

Some newer results: de la Vega and Mathieu show that adding any constraints with bounded support to the standard LP relaxation leaves the integrality gap at 2 (http://portal.acm.org/citation.cfm?id=1283390). The same is true for $n^\delta$ rounds of the Sherali-Adams hierarchy (http://portal.acm.org/citation.cfm?id=1536455). So in a very strong sense LPs are no help for Max Cut.

On the other hand there is work on primal-dual algorithms for Max Cut based on the GW SDP. Klein and Lu gave a fast approximation for MaxCut that matches Goemans-Williamson: http://dx.doi.org/10.1145/237814.237980 (they use what is now known as the multiplicative weights method to solve the SDP). I don't know the details, but I know that Luca's approximation of Max Cut using eigenvectors is in some sense a dual of the GW SDP (http://arxiv.org/abs/0806.1978). The latest combinatorial random-walk based algorithm is based on Luca's: http://arxiv.org/abs/1008.3938.


How would a theory of computation course that culminated in lambda-calculus as "the" model of computation, instead of Turing machines, look like? Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics:

Finite automata and regular languages
Pushdown automata and context-free languages
Turing Machines
Undecidability and TMs
Complexity classes (P, NP etc.)

If one were to redesign the ToC course where TMs in #3 and #4 above would be replaced by $\lambda$-calculus how would the rest of the course look like? That is, what would we teach in place of #1 & #2 above to progressively lead to $\lambda$-calculus? Also, could there really be chapter on complexity classes with $\lambda$-calculus as THE model of computation?

The kind of approach to theory of computation you describe is what I like to call an abstract machine based computability theory:
i.e. a theory that define computable functions/languages/etc via some abstract kind of machine (automata, linear automata, Turing
machine etc).

An approach that uses $\lambda$-calculus instead of Turing machines could be thought as an expressions based computability theory:
i.e. a theory where one prescribe some basic operations which are intuitively calculable and some operators defined between them to
build other computable operations.

In this expression based computability theory

regular expressions correspond to finite state automata;
linear and context free grammar correspond to pushdown automaton and linear bounded automaton
(untyped) $\lambda$-calculus correspond to Turing machines
I don't know very much about complexity in $\lambda$-calculus but I guess  it could be approached as done for complexity of $\mu$-recursive function or of logic formulas, classifying $\lambda$-terms in complexity
classes by their structure (then of course it would be nice to compare these complexity classes with complexity classes for other models of computation, like Turing machines).

Hope this helps.


How to find the "best vectors" in a given matrix whose sum of products is as small as possible? The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater than $1$ nor all less than one.

The question is to find a subset $S$ of $\{1,\ldots,n\}$ and $S\neq \emptyset$ such that $$\sum_{i=1}^k\prod_{j\in S}a_{ij}\leqslant v.$$

In fact, in the optimization settings, I would like to find a subset $S$ whose sum of products is minimum.

Example: Take $v=0.55$ and $$\mathbf{A}=\begin{bmatrix} 0.1&2&3\\2&0.2&0.1\end{bmatrix}.$$ This has the solution $S=\{1,3\}$. Its value (its sum of products) is $0.5$.

How to solve this problem?  Is this problem known (or is there any similar problem in the literature)?

Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.

The problem is NP-complete.
I sketch a reduction from 3-SAT.

Consider Boolean variables $x_1,\ldots,x_n$ and clauses $c_1,\ldots,c_m$ over these variables, so that each clause consists of three literals.  The question is to decide whether there exists a truth setting of the variables so that every single clause is satisfied (and hence contains at least one true literal).

We construct a matrix with $n+m+1$ rows and $2n+1$ columns.

There is a special row $R^*$, and there is a special column $C^*$.
For every clause $c_j$, there is one corresponding row $R(c_j)$.
For every variable $x_i$, there is one corresponding row $R(x_i)$.
For every variale $x_i$, there are two corresponding columns $C^+(x_i)$ and $C^-(x_i)$.

Let $Z=100(m+n)^{100}$ be a huge integer.

The entry at the crossing of special column $C^*$ and special row $R^*$ is $1/Z^n$. All other entries in row $R^*$ take value $Z$.
All entries at a crossing of $C^*$ with a clause row $R(c_j)$ are $Z$.
All entries at a crossing of $C^*$ with a variable row $R(x_i)$ are $1/Z$.
The crossings of variable row $R(x_i)$ with columns $C^+(x_i)$ and $C^-(x_i)$ take value $Z$; all remaining entries in row $R(x_i)$ are $1$.
If clause $c_j$ contains the positive literal $x_i$, then the crossing of row $R(c_j)$ and column $C^+(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.
If clause $c_j$ contains the negative literal $\lnot x_i$, then the crossing of row $R(c_j)$ and column $C^-(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.

It can be shown that the 3-SAT instance is satisfiable, if and only if the column selection problem has a solution $S$ for which the sum of products is at most $v=n+m+1$. Some comments:

The set $S$ must contain the special column $C^*$; otherwise the contribution of the special row $R^*$ to the objective function (sum of products) is at least $Z>v$.
The set $S$ can contain at most one of the two columns $C^+(x_i)$ and $C^-(x_i)$; otherwise the contribution of row $R(x_i)$ to the objective function will be at least $(1/Z)\cdot Z\cdot Z>v$.
For every clause $c_j$, the set $S$ must contain some column $C^+(x_i)$ and $C^-(x_i)$ so that the corresponding literal $x_i$ respectively $\lnot x_i$ satisfies $c_j$. Otherwise, the contribution of row $R(c_j)$ to the objective function will be at least $Z>v$.


Is there a problem that is easy for cubic graphs but hard for graphs with maximum degree 3? Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic graphs is the class of graphs with maximum degree $\Delta \leq 3$.

  Is there any problem that can be solve in polynomial time for cubic graphs but that is NP-hard for graphs with maximum degree $\Delta \leq 3$?

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


techniques or examples of analyzing a series of graphs Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "systematic" way. in this particular case $G_n$ is "more complex" than $G_{n-1}$ and generally has more edges/vertices.
Question:
What is some systematic method of determining the "basic differences" between $G_n$ and $G_{n-1}$?  In some sense, how does one derive a "recurrence relation" like a formula that derives $G_n$ from $G_{n-1}$ (similar to [1] but instead of using integers as parameters, here with graphs as the parameters)?  What are some famous examples of graph sequences like this, successfully analyzed in the literature?
Presumably this general question is undecidable for some contrived cases [exercise for reader] but is decidable for special cases.  I am interested in the subset of decidable cases.
Background
This is an old problem that first occurred to me about 2 decades ago which to my knowledge has not been studied too much in particular but which seems significant.  I have a particular algorithm in mind for generating $G_n$ from $G_{n-1}$ for which I suspect there is not much research (hint, see other question [2]), and might mention/further clarify at a later date; but for now I am interested in a more general approach.
Another analogy would be with textual "diff" programs which find lines added, deleted, modified between two text files.  Is there an analogous approach for graphs that has been used somewhere?  Actually, I suspect this type of construction is somewhat widespread in graph theory proofs, maybe even key/famous ones, but not necessarily studied so much in isolation.
In the best case scenario, there would be a software package that would actually successfully derive such formulas in some cases, but to my knowledge it does not exist right now.
[1] solving recurrence relations, wikipedia
[2] largest language class for which inclusion is decidable

I think your question falls in the context of "graph operators". A graph operator $S$ is just a map from the class of graphs to the class of graphs, and you then have a sequence $G$, $S(G)$, $S^2(G)$, etc.

I do not think that there could possibly be a general way to determine $S^n(G)$ as a function of $n$ and $G$ that could work for all $S$, even for a fixed $S$. For example, if $S(G)$ is the intersection graph of the maximal cliques of $G$ (considered in Harary's book and denoted by $K$), then what you ask is known for only a handful of families, including the complements of $nK_2$, the locally $C_6$ graphs and the so called "clockwork graphs".

Many other graph operators are studied in the book "Graph Dynamics" by Erich Prisner.


Riemann Hypothesis and Complexity Theory It is known that "Assuming the generalized Riemann hypothesis (GRH) if VP = VNP then PH collapses to second level". Why would one think of a relation between VP,VNP and the Riemann hypothesis. Where does a statement about the zeros of the Riemann zeta function appear in a statement about complexity classes ? I have not read the original result. It would be nice if anyone could provide some intuition.

Valiant's classes are defined over some field. They can use arbitrary constants from that field. To draw some conclusion about Boolean complexity classes, one needs to replace these arbitrary constants by small discrete constants. Here GRH comes into play, since it ensures the existence of enough primes with certain properties.


Arithmetic circuits with just one threshold gate When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 threshold gate as the output gate. On input $a\in\{0,1\}^n$, the resulting threshold  $\{+,\times\}$-circuit then outputs $1$ if $F(a)\geq t$,
and outputs $0$ if $F(a)\leq t-1$; the threshold $t=t_n$ can be any positive integer, which may dependent on $n$ but not on input values. The resulting circuit computes some (monotone) boolean function
$F':\{0,1\}^n\to \{0,1\}$.

Question: Can threshold $\{+,\times\}$-circuits be efficiently simulated by  $\{\lor,\land\}$-circuits?

Under "efficiently" I mean "with at most a polynomial increase of size."
The answer is clear "yes" for threshold $t=1$: just replace $+$ by $\lor$, $\times$ by $\land$, and remove the last threshold gate. That is, $\{\lor,\land\}$-circuits are in fact threshold-$1$
$\{+,\times\}$-circuits.
But what about larger thresholds, say, $t=2$?

One can define arithmetic analogues $\#C$ of most boolean circuit classes $C$ by just using $+$
instead of OR, $\times$ instead of AND, and $1-x_i$ instead of $\bar{x}_i$.
For example, $\#AC^0$ circuits
are $\{+,\times\}$-circuits of constant depth with unbounded fanin $+$ and $\times$ gates, and inputs $x_i$ and $1-x_i$.
Agrawal, Allender and Datta have shown that  threshold $\#AC^0$ = $TC^0$. (Recall that $AC^0$ itself is a proper subset of $TC^0$; take, say, the Majority function.) In other words, constant-depth threshold circuits can be efficiently simulated by
constant-depth $\{+,-,\times\}$-circuits, with just a single threshold gate!
Note, however, that my question is about monotone circuits (no Minus "$-$" as gates, and even no $1-x_i$ as inputs). Can one (last) threshold gate be so powerful also then?
I don't know this stuff, so any related pointers are welcome.

N.B. There is yet another interesting related result  due to Arnold Rosenbloom: $\{+,\times\}$-circuits with just one monotone function $g:\mathbb{N}^2\to\{0,1\}$ as output gate can compute every slice function with $O(n)$ gates.
A slice function is a monotone boolean function which, for some fixed $k$, outputs $0$ (resp. $1$) on all inputs with less (resp., more) than $k$ ones. On the other hand, easy counting shows that most slice functions require general $\{\lor,\land,\neg\}$-circuits of exponential size. Thus, one "innocent" additional output gate can make monotone circuits omnipotent! My question asks
whether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate.

ACTUALIZATION (added 03.11.2014): Emil Jeřábek has shown (via an amazingly simple construction, see his answer below) that the answer is "yes" as long as  $t\leq n^c$ for a constant $c$.
So, the question remains open only for super-polynomial (in $n$) thresholds.

Usually, in applications, only large thresholds do work: we usually need thresholds of the form $2^{n^{\epsilon}}$ for $\epsilon > 0$. Say, if $F:\{0,1\}^n\to \mathbb{N}$ counts the number of $s$-$t$ paths in graph specified by the $0$-$1$ input, then for $t=m^{m^2}$ with $m\approx n^{1/3}$, the threshold-$t$ version of $F$ solves the existence of a Hamiltonian $s$-$t$ path problem on $m$-vertex graphs (see, e.g. here).

(Added 14.11.2014): Since Emil answered a big portion of my question, and since the case of exponential thresholds is not in sight, I now accept this Emil's (very nice) answer.

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.

First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, and either $ab,a'b\ge t$ as well, or $ab=a'b(=0)$.

With this in mind, we can simulate the circuit with a Boolean monotone circuit by replacing each node $c$ with nodes $c_0,\dots,c_t$, where $c_i$ is intended to compute the predicate $c\ge i$. (We need $c_0$ only for notational convenience, it computes the constant $1$ function.) If $c$ is a Boolean input variable $x$, we take $c_1=x$, $c_2=\dots=c_t=0$. If $c$ is an addition gate, say $c=a+b$, we implement it via
$$c_i=\bigvee_{\substack{j,k\le t\\j+k\ge i}}(a_j\land b_k).$$
Multiplication gates are handled in the same way.

This takes $O(t^3)$ gates per one gate of the original circuit. As a minor optimization, we can reduce it to $O(t^2)$ by putting
\begin{align*}
c_t&=\bigvee_{j+k\ge t}(a_j\land b_k),\\
c_i&=c_{i+1}\lor\bigvee_{j+k=i}(a_j\land b_k),\qquad i<t,
\end{align*}
so that each $a_j\land b_k$ is used as an input of only one of the $c_i$ gates.


Impossibility in Computability and Complexity: always ultimately due to diagonal arguments? In Computability, if we want to prove that a problem is not recursive or not recursively enumerable, we can use e.g. reductions from other non-recursive or non-r.e. problems, Rice's theorem, Rice-Shapiro's theorem, etc. These techniques work thanks to, or are directly based on, the existence of some diagonal argument (i.e. some program $M$ behaves in the opposite way as its input program $M'$, so $M = M'$ is contradictory). In Complexity, if we want to prove that some problem cannot be computed in some time (regardless of any unproved claims such as e.g. $P \neq NP$), we use arguments which are, ultimately, based on some diagonal argument (e.g. the Time Hierarchy theorem proves $EXPTIME$-complete problems are not in $P$, but that theorem is also proved by using a diagonal argument).

So my question is the following. Are all important impossibility results in Computability and Complexity (actual impossibility, not impossibility up to some unproved result) ultimately due to some diagonal argument? That is, does all our important "impossibility knowledge" in Computability and Complexity come from the fact that programs are powerful enough to execute programs?

The only important impossibility result coming to my mind which is not ultimately due to a diagonal argument is that the Ackermann function is not primitive recursive. Am I missing other important counterexamples of this apparent "rule"?

EDIT (Nov 18): Sorry for implying that my question was particularly focusing on the diagonal argument itself, but I'm more interested on all arguments that rely on the self reference of programs (including the diagonal argument, Berry paradox, etc). For simpler languages (e.g. regular or context-free), we have "structural" impossibility arguments based on how these languages are constructed (e.g. pumping lemmas). However, for recursive or r.e. languages, most of impossibility results strongly rely on the self reference of programs. This is what I meant.

The standard comparison-model lower bound for sorting, and most cell probe model lower bounds for data structures, are unconditional (for computing within the model but you could say the same about Turing machine lower bounds) and depend on information theory rather than diagonalization.


What is a good special-case sorting algorithm? I have a dataset which is a number of objects arranged in a 2-D grid.  I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each column.  For example,

1 2 3
4 6 7
5 8 9

Can I improve on naive sorting to sort the entire dataset linearly (as measured in comparisons)?

What about for n-d datasets?  Arbitrary finite datasets with a subset of comparisons known?

It's easy to prove an Ω(n2 log n) lower bound on this problem (in the comparison sorting model): if the element at position (i,j) is always within distance 1/2 of i+j, then the grid diagonals are independent of each other, and the sorted order within each grid diagonal is arbitrary. So under this constraint the total number of orderings possible is the product (over all the diagonals of the grid) of the factorials of the lengths of the diagonals, which is exponential in n2 log n.

Which is to say that standard comparison sorting algorithms are asymptotically optimal for grids ordered as you describe.


Progress on generalized star-height problem? The (generalized) star height of a language is the minimum nesting of Kleene stars required to represent the language by an extended regular expression. Recall that an extended regular expression over a finite alphabet $A$ satisfies the following:

(1) $\emptyset, 1$ and $a$ are extended regular expressions for all $a\in A$

(2) For all extended regular expressions $E,F$;
 $E\cup F$, $EF$, $E^*$ and $E^c$ are extended regular expressions

One phrasing of the generalized star height problem is whether there is an algorithm to compute the minimum generalized star height.  With regards to this problem I have a few questions.

Has there been any recent progress (or research interest) concerning this problem? I know a number of years ago that Pin Straubing and Thérien published some papers in this area.
The restricted star height problem was resolved in 1988 by Hashiguchi but the generalized version  (as far as I know) is still open. Does anyone have any intuition as to why this might be the case?

A link that might be helpful is the following:  starheight

Regarding your second question, an explanation why the generalized star height problem is less accessible than the star height problem is the following: Already Eggan's seminal paper in 1963 contained languages of (ordinary) star height $k$, for each $k\ge 0$. Only a few years later, McNaughton, and, independently, Déjean and Schützenberger, found examples over binary alphabets. This made clear what the problem "is about". During the years that followed, there was a more or less steady flow of published results in the area of the ordinary star height problem. This gave an ever increasing body of published examples, counterexamples and phenomena surrounding this problem.

In contrast, after some fifty years now, we don't know whether there is any regular language of star height at least two. So we do not even know whether there is a need for a decision procedure after all. This "complete lack of examples" indicates that it is extremely difficult to get a grip on this problem.


Interactive proofs for levels of the polynomial hierarchy We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want to give an interactive proof of membership in a $\Sigma_2$ language. Is it enough to be able to solve problems in $\Sigma_2$? Is solving problems in $\Sigma_5$ adequate? More generally, if you can solve $\Sigma_k$ or $\Pi_k$ problems, for what $\Sigma_\ell$ is this sufficient to generate interactive proofs of all languates in $\Sigma_\ell$?

This question was inspired by this cstheory stackexchange question.

Even for giving an IP for coNP, using current techniques, one needs to arithmetize, i.e. use counting, which means essentially the full power of #P.  Any weaker prover even for coNP would be very interesting, I think (in particular would imply a new non relativing technique.)


Explanation of states, models and worlds in Kripke semantics? Can someone explain to me how the concepts of states, models and worlds work together in Kripke semantics?

I've been trying to piece together how the parts work are linked together but cannot figure it out.

From what I understand, a model $M$ consists of worlds.
Now as far as I can gather from that, states would be the same as worlds.
However, I cannot find this confirmed anywhere.

Could someone explain to me how these concepts work?
Obviously, I've googled them, but most texts are quite complicated to grasp with little experience on the subject. Even textbooks remain quite vague.

Here is a sketch (massively simplifying for reasons of
pedagogy):

Setting the scence. You can think of logic as a tool, an API in computing parlance,
to reason about things, where reasoning means deriving true
statements from true assumptions. The things that we reason about
using logic is called a model.  What makes logic useful is that
this API, in particular its dominant strain called first-order
logic (of course there are other logics), is completely generic,
meaning we can use it to reason
about teddy bears, cars, bridges over rivers, stars, computation,
whatever you want. Because logic is so generic, we can build up a
generic reasoning infrastructure that can be reused in many
domains. Example include interactive theorem provers, SAT
solvers, textbooks, social conventions such as learned journals,
career structures in the sciences, conventions about when we deem to have
lost/won an argument etc. So logic is a great labour saving
device, because we don't have to reinvent these core tools again
and again for everything that we want to reason about.

Is logic all we need to reason? Naturally not. Because logic is generic, we have to inject domain
specific assumptions, usually called axioms, to cater for domain specific
knowledge (e.g. ZFC or Peano arithmetic to found mathematics,
deontic axioms for reasoning about ethics etc).

What has all of   this to do  with Kripke semantics?
Often we want to reason about things that change over
time (e.g. traffic at a traffic light, concurrent processes using
shared memory communication, knowledge of observers).  We can do
this by injecting suitable axioms into first-order logic for each
domain separately.  However, just as with first-order logic, it
turns out that a lot of the axioms that we need to reason about
change are similar regardless of what changes over time.  So why
not 'factor out'    this similarity and create an API for reasoning
about change, just as we did with first-order logic as an API for
general reasoning? Let this new logic/API be called modal logic.

Now we come back to the notion of model, because models are what
we reason about.

What is this API called modal logic about? Well, things that change.
Let's call them worlds. Now ,
the worlds change into each other over time.  Would a description of
this change not be a
binary relation on the set of world? The set of worlds together with the
relation is the model.

Voila, Kripke semantics.

Warning: the description above is simplistic, and terminology is
not uniform.  Moreover, for most modal logics the model must also
account for variables.
In more neutral terminology (and still simplifying), a model is a
triple $( W, R, \sigma )$ where

$W$ is a non-empty set
(elements of W are called nodes or worlds or points).
$R$ is a binary relation on $W$, and is known as the
accessibility relation which regulates how 'time' flows.
$\sigma$ is a map from variables (in the ambient logic) to the
powerset of W. The idea behind $\sigma$ is that $\sigma$
controls at what points/worlds the variables are true.

If you want to know even more, maybe check the Wikipedia entries
on Kripe semantics or modal logic or any good book on
the subject such as Modal Logic, by Blackburn, de Rijke and Venema.


Ordering sequences containing bitvectors for size-change termination I'm working with the size-change termination principle to show program termination. In the system I work with, there is a so-called bit-vector ordering that goes as follows:

Given two sequences of arguments $s_1,s_2$.

Filter the bitvector arguments (long/int/short/byte)
Divide each sequence of arguments $s$ according to length (so one group is int, other short and so on). Denote the arguments of type $t$ in sequence $s$ as $s.t$.
If $s.t$ is defined for $s_1,s_2$, compare $s_1.t$ with $s_2.t$ lexicographically.

We define $s_1 < s_2$ when there exists a type $t$ such that $s_1.t < s_2.t$.

I have confirmed that this behaviour is wrong. Indeed, if one has two sequences $s_1,s_2$ that contain ints and shorts where $s_1.int < s_2.int$ and $s_2.short < s_1.short$ we would deduce that $s_1 < s_2$ and $s_2 < s_1$.

What is the standard orders for lists of bitvectors while using the size-change termination principle?

Surely, you want $s_1 < s_2$ if there is a $t$ such that $s_1.t < s_2.t$ and $s_1.u \leq s_2.u$ for every other field $u$. That, at least, gives you a well-founded order.

But there are many other well-founded orders on tuples, e.g. lexicographical order for some order of the fields (though you might need a heuristic to find the order), and various arithmetic combinations of the sizes of each field.

Modern termination checkers will actually simultaneously search for some order that works among a large family of such orders, by generating constraints of the form "There is some lexicographic order, or some polynomial order that shows termination" and trying to satisfy this constraint all at once.

A couple of papers that address termination analysis for bit-vectors and Java, respectively, are:

Termination and Complexity Analysis for Programs with Bitvector Arithmetic by Symbolic Execution

and

Automated Termination Proofs for Java Programs with Cyclic Data

by Giesl & al.


Recommendation for a good book on first order logic w.r.t inductive logic programming I have had 10 days to read up on Computational Logic but the books I am following are only succeeding in confusing me. I find most of text's ( Niehuys-Cheng & de Wolf 1997, De Raedt 2008, Lloyd 1987 ) very wordy. None of them provide will worked out examples for, say, SLD-resolution. So I was wondering if anyone knows of a good book with nice examples which explain first order logic in an intuitive manner ? Thanks in advance.

How about foundations of disjunctive logic programming? While rather old (1992), it has over 100 examples. For instance, SLI and SLD resolutions are discussed and exemplified in section 4.2.

PS: You may read some parts of that section on Google Books.


How to generate Skolem function in practice Context: Skolemization is the process of removing the existential quantifiers in a first-order formula. The existential bounded variables are replaced with existential quantified function.

Questions: How, in practice, are these functions generated by an algorithm? Do we have another choice than a brute force strategy over all the possible functions? Is it of any practical use?

Example: Assume the formula $\forall{x}.\exists{y}.x \neq y$, then the Skolem form is $\exists{f}.\forall{x}.x \neq f(x)$ where $f$ is the function that explicits the dependency between $x$ and $y$. With resolution or any other method, how to, algorithmically, decide what is the result of $f(x)$? Is it all the values of the domain of discourse of $y$? If yes, does it mean that the role of the function is actually to "forbid" the value of $f(x)$ to change when a variable other than $x$ (if there was any) is instantiated?

Partial answer: As given below, we do not need to interpret the function $f$ to prove the validity. However, what about finding a model that satisfies the formula?

As I understood it...: Replying to myself to close this question. I guess there is no magic and we need to consider every function $f$ until we find a model. So if $f$ takes 2 arguments, it can maps to $|U| * |U|$ values ($|U|$ being the cardinality of the universe of discourse) and hence, the Skolem function is equivalent to the initial $\exists$ quantifier.

First of all there are two Skolem transformations, one replaces universal quantifiers and preserves validity, the other one replaces existential quantifiers and preserves satisfiability of the formula. Your question is about the second kind, so I will present it this way, but the other version is dual (and at least for me easier to understand).

Lemma: let $F$ be a formula and $sk(F)$ a Skolem transformation of $F$. Then if there exists a model $\mathcal{M}$ s.t. $\mathcal{M} \models F$ there exists a model $\mathcal{N}$ s.t. $\mathcal{N} \models sk(F)$.

If we can show that $sk(F)$ is unsatisfiable, it has no model. But then also $F$ can not have a model.

Now, Resolution is a quite efficient method to show that a formula (in conjunctive normal form) is unsatisfiable. This leads to the following approach to proving the validity of some formula $F$:

Negate $F$
Skolemize, transform the formula into conjunctive normal form
Find a refutation for the CNF formula (a so called clause set)
Because $\neg F$ does not have a model, all interpretations of $F$ must be a model - in other words: $F$ is valid.

Nowhere in this procedure do you need the actual interpretation of a Skolem function, you just rely on the fact that one must exist as part of the model $\mathcal{N}$.


Approximation algorithms for Directed Minimum Cut with Cardinality Constraints We would like to know whether there are any known approximation results for the cardinality constrained minimum $s$-$t$-cut on directed graphs. We weren't able to find any such result in literature.

The problem is defined as follows:

Instance: A directed graph $G=(V,E)$, a cost function $w : E \to \mathbb{R_0^+}$, two vertices $s,t \in V$ and an integer $k$.

Solution: An $s$-$t$-cut, i.e. a partition of $V$ into two sets $V_1, V_2$ such that $s \in V_1$, $t \in V_2$ and the number of edges that cross the cut is at most $k$, i.e. $|\{ (u,v) \in E: u \in V_1, v \in V_2 \}| \le k$.

Measure (to minimize): The cost of the cut: $$ \sum_{ (u,v) \in E : u \in V_1, v \in V_2 } w(u,v) $$

In "Cardinality constrained and multicriteria (multi)cut problems" the autors prove that this problem is strongly NP-Hard even for undirected graphs.

We are mainly interested in approximation algorithms for directed graphs, but approximation results for the undirected case might also be useful.

Thank you for any insights.

We can get a $(2,2)$ bi-criteria approximation as follows (or more generally $(1+\varepsilon, 1 + 1/\varepsilon)$ bi-criteria approximation).

We may assume that we know the cost of the optimal solution. Denote it by $OPT$. Let
$$w'(u,v) = \frac{w(u,v)}{OPT} + \frac{1}{k}.$$
Consider the optimal solution $(V_1, V_2)$. Then
$$\sum_{(u,v) \in E(V_1, V_2)} w'(u,v) = \sum_{(u,v) \in E(V_1, V_2)} \left(\frac{w(u,v)}{OPT} + \frac{1}{k}\right) = 1 + \frac{|E(V_1,V_2)|}{k} \leq 2.$$

Our algorithm finds the minimum directed $s$-$t$ cut $(V_1', V_2')$ in $G$ with edge weights $w'$. The cost of this cut is at most $2$. Therefore, the cut $(V_1', V_2')$ cuts at most
$$E(V_1', V_2') = \sum_{(u,v)\in E(V_1',V_2') } 1 \leq k \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2k$$
edges. The cost of the cut is at most
$$\sum_{(u,v)\in E(V_1',V_2')} w(u,v) \leq OPT \sum_{(u,v)\in E(V_1',V_2')} w'(u,v) \leq 2OPT.$$


Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$? I am trying to find about algorithms that, given graph $H, G$, determine if $H$ is a topological minor of $G$ (and if so, exhibit this explicitly). Most of the literature on this topic seems to be focused on the case when $H$ is a fixed small graph while $G$ goes to infinity --- e.g. testing if $G$ is planar. What are the algorithms when $H$ and $G$ are comparable in size?

If this problem requires exponential time, I would still be interested in the best algorithms and/or real implementations

The general problem when $H$ is not fixed is NP-hard: Take $H$ to be a cycle of length $|V(G)|$ and it amounts to testing whether $G$ is hamiltonian.

I think that the state of the art on this is the FPT algorithm of
Grohe, Kawarabayashi, Marx and Wollan. The dependency on $G$ is cubic, but the one on $H$ seems impractical, since it relies quite heavily on the Robertson-Seymour theory.


Canonisation of boolean matrices under row and column permutations Consider the equivalence relation $\sim$ on boolean matrices $A,B\in\{0,1\}^{m\times n}$ which is defined as follows:

$A\sim B$ :iff there are permutation matrices $P\in\{0,1\}^{n\times n}, Q\in\{0,1\}^{m\times m}$, so that $B=QAP$

In other words two matrices are equivalent, if they are equal up to permutation of rows and columns.

A canonisation function for $\sim$ is any function $N$ on the set of all boolean matrices with $N(A)\in \{0,1\}^{m\times n}$ for all $m,n\geq 1$ and $A\in \{0,1\}^{m\times n}$ with the following two properties:

$N(A)\sim A$ for every $A$
$A\sim B \Leftrightarrow N(A)=N(B)$ for all $A,B\in\{0,1\}^{m\times n}$

Now i want to find a canonisation function for $\sim$ that is most efficiently computable.
One possible canonisation function is the function $\mathrm{MaxLex}$ which maps every matrix $A$ to the lexicographically largest $B$ that is equivalent to $A$.

For this i first define a linear order on bitvectors as follows:
For $b,c\in\{0,1\}^k$

$b<_{llex} c$ iff: the number of ones in $c$ is larger than in $b$ or ($b$ and $c$ have the same number of ones and $b(i)>c(i)$ for the first index $i$ with $b(i)\neq c(i)$)

Then a lexicographic order $<_{lex}$ on matrices of equal dimension is defined as follows:

$A<_{lex}B$ iff $w_A<_{llex}w_B$

where
$w_X=X(1,-)X(2,-)\ldots X(m,-)\in\{0,1\}^{mn}$ denotes the bit vector that results from the concatenation of the rows $X(i,-)$ of $X$.

Then $\mathrm{MaxLex}(A):=\max_{<_{lex}} \{ B : A\sim B\}$

I have found a simple recursive algorithm that computes $\mathrm{MaxLex}$, which has however a worst case runtime of $\mathcal{O}(m!)$.

Now my questions are:

Is there a more efficient algorithm that computes $\mathrm{MaxLex}$ than my $\mathcal{O}(m!)$ algorithm?
Is there a polynomial time algorithm that computes  $\mathrm{MaxLex}$
Is there a canonisation function for $\sim$ that is computable in polynomial time?
Is anything known about the computational complexity of this problem?

I am thankful for any tips, pointers or comments. I have already googled this problem but couldn't find anything. The only thing i found which resembles this is the decision problem of whether a boolean matrix is equivalent to a triangle matrix, which according to this posting is in NP, but not known to be NP-hard nor in P.

This problem is precisely the canonization problem for isomorphism of bipartite undirected graphs. While the lexicographically maximum form may be harder, any canonical form will be GI-hard (and so, in particular, it doesn't matter whether the $P$ and $Q$ are restricted to satisfy $P=Q^{-1}$ or not, as asked in a comment above).

In particular, there is a canonization procedure that takes only $2^{\tilde{O}(\sqrt{n})}$ time (much better than $n! \sim 2^{\Theta(n \log n)}$), by Babai-Luks 1983, though in practice I'd recommend just using nauty.


Does fixed hyperparameters perform well regardless the number of training examples? I'm new in this community and I don't know whether my question is proper for this community. I will delete this post if it is not proper.

I'm interested in deep learning network models and have a question about this.

Suppose we have a feedforward neural network models with different hyperparameters (for example, the number of layers, neurons and so on), say $H_1,..., H_n$. Also assume all the samples are selected from a particular distribution.

First we got $100$ samples. If we find that a typical hyperparameter set, $H_i$, performs best. Now I want to increase the number of samples to $1000, 10000,$ even millions. Is $H_i$ still the best hyperparameter set to perform among $H_i$'s? I want to know whether there are references about such topics. The best is a mathematical proof about this fact.

Again, please tell me if this question is not proper to the community. Thanks a lot!

No. You're asking about model selection. Larger sample sizes will allow you to choose more complex models. Read up on the keywords overfit/underfit, model selection, Structural Risk Minimization, and in particular this article:
https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=705570


Partition planar graph into connected subgraphs of equal size Work

Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549.

states that for 4-edge-connected graph one can partition its edges into disjoint subsets of size $r$, such that each subset form a connected subgraph.

I wonder if the same kind of statement could be formulated for partition of vertices.
For what kind of graphs one find partition of vertices into disjoint subsets of size $\approx r$, such that each subset form a connected subgraph (for each r)? I'm particularly interested in planar graphs, but would be happy with any class.

I can soften some conditions (it will still meet my needs): for what graph classes existence of partition into less than $\frac{\alpha n}{r}$ connected subgraphs of size less than $r$ is guaranteed (for some $\alpha$)?

For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed).

However, the problem is polynomial for cycles, and thus for Hamiltonian graphs. It is also polynomial for trees and for series-parallel graphs when the number of subsets is fixed.

You can find these results in:

M. E. Dyer and A. M. Frieze. On the complexity of partitioning graphs into connected subgraphs.  Discrete Applied Mathematics, 10(2), 139-153. 1985.
N. Apollonio & al. Bicolored graph partitioning, or: gerrymandering at its worst.  Discrete Applied Mathematics, 157(17), 3601-3614. 2009.

Edit (bis): I think that I was wrong about Hamiltonian graphs. They may be partitioned even if their Hamiltonian cycle cannot. Thus the problem can be not polynomial. See the first comment.


Producing colouring of maximal planar graphs G from colouring of dual of G A (simple) graph is said to be maximal planar if it is planar and adding one more edge loses planarity. In other words, the graph is planar and every face is a triangle. Tait gave a one-one correspondence between 4-colourings of maximal planar graphs and 3-edge colourings of their dual graphs. That is, given a 4-vertex colouring of a maximal planar graph $G$, one can produce a 3-edge colouring of the dual graph $G^*$ of $G$, and vice versa. The schemes to produce one from the other are elegant.

Similarly, there are schemes to produce (vertex) colouring of $G^*$ from colouring of $G$.

Is there a known scheme to produce a colouring of a maximal planar graph from a colouring of its dual graph?
(In other words, given a face colouring of a maximal planar graph, can we produce a vertex colouring?)

Clarification: I am not asking for a 4-colouring of the maximal planar graph. From a 4-colouring (or 5-coluoring) of its dual graph, is it possible to produce a colouring of the maximal planar graph (may be with 5 or even 6 colours; but it should be a colouring scheme that actually use the colouring of the dual graph).

The simple but useless answer is that I don't know of such a scheme. However, more to the point: proving that such a scheme worked would be tantamount to proving the 4-color theorem. It is very easy to prove that duals of maximal planar graphs have 4-colorings (in fact 3-colorings except for $K_4$ by Brooks' theorem), so if you could prove that a 3- or 4-coloring of the dual graph could always be converted into a 4-coloring of the primal graph then you would have also proved that a 4-coloring of the primal graph exists.

Perhaps there are more, but the only widely-accepted alternative proofs of the 4-color theorem reported by the Wikipedia article are the ones by Robertson, Sanders, Seymour, and Thomas (in connection with a faster algorithmic version of the theory) and Werner and Gonthier (in connection with a formalized proof in Coq). I think both are in roughly the same style of Appel and Haken, of proving that a reducible configuration exists, rather than using dual colorings.


K-NN or matrix factorization for discovering correlated features? I am looking to cluster users together in a database, with each user represented by a number of features that are both discrete and continuous in nature.  "Similar" users should be clustered together in a way that underlying strongly correlated features can be easily discovered.  A few other requirements:

The number of clusters is unknown
The runtime execution time is not a concern
The number of users can be on the order of 100,000 and number of features around 50

There are a number of clustering techniques, from KNN, k-means, matrix factorization, even PCA, but many seem to hide the underlying correlations that tie the users together.  Any advice?

You're asking essentially a modelling question, and so the answer really depends on your data. If you're saying that strong correlations are not being identified by the methods you listed, it's possible that the correlations are non-linear (the above methods with the exception of k-NN are linear), and so you might try something like ICA.

For something closer to home, have you considered correlation clustering ? you don't say how the data is presented, but if you have similarity and dissimilarity information, then correlation clustering is a good solution, and also does not require you to specify the number of clusters.

Another idea would be to try spectral methods (if all you have is a distance function) like spectral clustering.


$NotTooManyP^{cc}$ class in communication complexity Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication.

Class $NP^{cc}$ is class of languages admitting nondeterministic communication protocol with polylog size witness.

Class  $FewP^{cc}$  is class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polylog correct witnesses.

It was proven that $FewP^{cc} = P^{cc}$ [1]. My question is about what happens if we allow not too many correct witnesses instead of few.

Let class $NotTooManyP^{cc}$ be class of languages admitting nondeterministic communication protocol with polylog size witness, where each input has at most polynomial correct witnesses. Is this class different from $P^{cc}$? If yes, how much weaker is this class then $NP^{cc}$?

When the inputs are the indicator functions, set non-disjointness is in NPcc with witnesses

from {0,1,2,3,...,n-2,n-1} $\big(\hspace{-0.04 in}$so in particular is in NotTooManyPcc$\hspace{-0.03 in}\big)$,  but by this paper,

the coUSBP (and thus also P) communication complexity of that problem is $\Theta$(n).

By padding, that means we leave coUSBPcc $\big(\hspace{-0.04 in}$and thus also Pcc$\hspace{-0.03 in}\big)$  as soon

as the number of witnesses is no longer polylogarithmically-bounded.

Also, for all functions  f : {0,1,2,3,...} $\to$ (0,1] ,  if the version with at most

nf(n) correct witnesses equals NPcc then f has a positive lower bound.

Proof:

Let f be any function from {0,1,2,3,...} to (0,1] such that the problem at

the start of this answer can be solved with at most nf(n) correct witnesses.

Let  g : {0,1,2,3,...} $\to$ {0,1,2,3,...}  be given by

g(0) = 0 = g(1)  and otherwise  g(n) = (log(n))1/(f(n))  .

g(0) = 0  and  g(1) = 0 < 1  and  for all other inputs n,

g(n) = (log(n))1/(f(n)) < n1/(f(n)) ≤ n1/1 = n1 = n  .

Accordingly, consider the problem   non-disjointness of subsets of  {0,1,2,3,...,(g(n))-2,(g(n))-1}  whose inputs are padded indicator functions.

By removing the padding, that problem can be solved with at most (g(n))f(n) correct witnesses.

For all integers n such that  1 < n ,  (g(n))f(n) = $\big(\hspace{-0.05 in}$(log(n))1/(f(n))$\hspace{-0.03 in}\big)^{\hspace{.02 in}f\hspace{.02 in}(n)}$ = (log(n))(1/(f(n)))$\cdot$f(n) = (log(n))1 .

Thus the problem is in FewPcc, so by the result you mentioned, it's also in Pcc.

By the communication lower bound in this answer's starting sentence, that means g is

at most polylogarithmic, so 1/(f(n)) is bounded above, so f has a positive lower bound.

I'm not aware of any other results about limited-ambiguity versions of NPcc,

although with inputs as in the rest of this answer, (paddings of, if necessary) the problems

"  Does the intersection have at least _ elements?  "

seem like natural candidates for separating those classes.

$\big(\hspace{-0.04 in}$On the other hand, I wasn't even aware of  unambiguousPcc = Pcc ,

and still know neither a proof of that nor a reference for that.$\hspace{-0.03 in}\big)$


Can a probabilistic Turing machine solve the halting problem? A computer given an infinite stream of truly random bits is more powerful than a computer without one.  The question is: is it powerful enough to solve the halting problem?

That is, can a probabilistic computer determine whether or not a deterministic program halts?

Example of a probabilistic computer doing something a deterministic one can't: Consider a small program (less than a kilobyte in length) that outputs a string with Kolmogorov complexity greater than a gigabyte.  The Kolmogorov complexity of a string is the length of the shortest deterministic program producing that string.  Thus, by definition, a deterministic program cannot produce a string whose complexity is greater than its own length.  However, if given an infinite stream of truly random bits, a small program is capable of achieving the task with 99.99999...% success by simply echoing out, say, 10 billion random bits and hoping the Kolmogorov complexity of those bits is high enough.  Hence, producing a string of superior Kolmogorov complexity is within the possibility horizon of the probabilistic program, but not possible at all for the deterministic program.

That said, I'm wondering if it is possible to use truly random bits to hacksaw at the halting problem.  For instance, an algorithm might randomly generate theorems and prove/disprove/discard them until it knows enough to prove/disprove that a given deterministic program halts.

edit: I just realized some of the things I wrote were total nonsense, sorry for that. Now I changed the proof and made the definition of probabilistic machine I am using more precise.

I don't know whether I get right your definition of probabilistic Turing machine: it is a machine with an additional tape on which an infinite incompressible string is written, and beside that it acts just like a deterministic machine? If we fix the incompressible string, the class we get doesn't seem to be interesting.

I think we can define a probabilistic Turing machine in several ways. I will use a definition that seems quite natural (and for which my proof works ;) Let's define a probabilistic machine like that: it gets an additional tape on which some infinite string is written, we say that this machine decides a language $L$ if for every $x \in L$ it halts and accepts with probability $>\frac{1}{2}$, when the probability is taken over those additional random strings, and for every $x \not \in L$ it halts and rejects with probability $>\frac{1}{2}$.

We will now show that if there exists such a probabilistic machine $P$ that solves the halting problem for the deterministic machines, we could use it to build a deterministic machine $H$ that solves the halting problem for the deterministic machines - and we know that such a machine cannot exist.

Assume such $P$ exists. We can construct a deterministic machine $M$ that takes as an input a probabilistic machine $R$ with some input $x$, which

halts and accepts if and only if $R$ accepts $x$ (i.e. $R$ halts and accepts $x$ on more than half random strings).
halts and rejects if and only if $R$ rejects $x$ (i.e. $R$ halts and rejects $x$ on more than half random strings).
loops otherwise

Basically, $M$ will for all $i \in 1, 2, ...$ simulate $R$ on input $x$ and on every string from ${{0,1}}^i$ as a prefix of the string on $R$'s random tape. Now:

if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and accepted without trying to read more than $i$ bits from the random tape, $M$ halts and accepts
if for $>\frac{1}{2}$ prefixes of length $i$ $R$ halted and rejected without trying to read more than $i$ bits from the random tape, $M$ halts and rejects
otherwise $M$ runs the simulation with $i := i+1$.

We have to convince ourselves now, that if $R$ accepts (rejects) $x$ with probability $p >\frac{1}{2}$, then for some $i$ it will accept (reject) for $>\frac{1}{2}$ prefixes of length $i$ of the random string without trying to read more than $i$ bits from the random tape. It is technical, but quite easy - if we assume otherwise then the the probability of accepting (rejecting) approaches $p >\frac{1}{2}$ as $i$ goes to infinity, hence for some $i$ it will have to be $p >\frac{1}{2}$.

Now we just define our deterministic machine $H$ solving the halting problem (i.e. deciding whether a given deterministic machine $N$ accepts a given word $x$) a as $H(N,x) = M(P(N,x))$. Note that $M(P(N, x))$ always halts, because deciding a language by our probabilistic machines was defined in such a way that one of those two always occurs:

the machine halts and accepts for more than half random strings
the machine halts and rejects for more than half random strings.